Программа синтаксического разбора Вот грамматика языка, допускаемого калькулятором: program: END // END - это конец ввода expr_list END expr_list: expression PRINT // PRINT - это или "\n" или ";" expression PRINT expr_list expression: expression + term expression - term term term: term / primary term * primary primary primary: NUMBER // число с плавающей точкой в C++ NAME // имя C++ за исключением "_" NAME = expression - primary ( expression ) Другими словами, программа есть последовательность строк. Каждая строка состоит из одного или более выражений, разделенных запятой. Основными элементами выражения являются числа, имена и операции *, /, +, - (унарный и бинарный) и =. Имена не обязательно должны описываться до использования. Используемый метод синтаксического анализа обычно называется рекурсивным спуском; это популярный и простой нисходящий метод. В таком языке, как C++, в котором вызовы функций относительно дешевы, этот метод к тому же и эффективен. Для каждого правила вывода грамматики имеется функция, вызывающая другие функции. Терминальные символы (например, END, NUMBER, + и -) распознаются лексическим анализатором get_token(), а нетерминальные символы распознаются функциями синтаксического анализа expr(), term() и prim(). Как только оба операнда (под)выражения известны, оно вычисляется; в настоящем компиляторе в этой точке производится генерация кода. Программа разбора для получения ввода использует функцию get_token(). Значение последнего вызова get_token() находится в переменной curr_tok; curr_tok имеет одно из значений перечисления token_value: enum token_value { NAME NUMBER END PLUS="+" MINUS="-" MUL="*" DIV="/" PRINT=";" ASSIGN="=" LP="(" RP=")" }; token_value curr_tok; В каждой функции разбора предполагается, что было обращение к get_token(), и в curr_tok находится очередной символ, подлежащий анализу. Это позволяет программе разбора заглядывать на один лексический символ (лексему) вперед и заставляет функцию разбора всегда читать на одну лексему больше, чем используется правилом, для обработки которого она была вызвана. Каждая функция разбора вычисляет "свое" выражение и возвращает значение. Функция expr() обрабатывает сложение и вычитание; она состоит из простого цикла, который ищет термы для сложения или вычитания: double expr() // складывает и вычитает { double left = term(); for(;;) // ``навсегда`` switch(curr_tok) { case PLUS: get_token(); // ест "+" left += term(); break; case MINUS: get_token(); // ест "-" left -= term(); break; default: return left; } } Фактически сама функция делает не очень много. В манере, достаточно типичной для функций более высокого уровня в больших программах, она вызывает для выполнения работы другие функции. Заметьте, что выражение 2-3+4 вычисляется как (2-3)+4, как указано грамматикой. Странная запись for(;;) - это стандартный способ задать бесконечный цикл; можно произносить это как "навсегда" *2. Это вырожденная форма оператора for; альтернатива - while(1). Выполнение оператора switch повторяется до тех пор, пока не будет найдено ни + ни -, и тогда выполняется оператор return в случае default. Операции += и -= используются для осуществления сложения и вычитания. Можно было бы не изменяя смысла программы использовать left=left+term() и left=left-term(). Однако left+=term() и left- =term() не только короче, но к тому же явно выражают подразумеваемое действие. Для бинарной операции @ выражение x@=y означает x=x@y за исключением того, что x вычисляется только один раз. Это применимо к бинарным операциям + - * / % & | ^ << >> поэтому возможны следующие операции присваивания: += -= *= /= %= &= |= ^= <<= >>= Каждая является отдельной лексемой, поэтому a+ =1 является синтаксической ошибкой из-за пробела между + и =. (% является операцией взятия по модулю; &,| и ^ являются побитовыми операциями И, ИЛИ и исключающее ИЛИ; << и >> являются операциями левого и правого сдвига). Функции term() и get_token() должны быть описаны до expr(). Как организовать программу в виде набора файлов, обсуждается в этой главе. За одним исключением все описания в данной программе настольного калькулятора можно упорядочить так, чтобы все описывалось ровно один раз и до использования. Исключением является expr(), которая обращается к term(), которая обращается к prim(), которая в свою очередь обращается к expr(). Этот круг надо как-то разорвать; описание double expr(); // без этого нельзя перед prim() прекрасно справляется с этим. Функция term() аналогичным образом обрабатывает умножение и сложение: double term() // умножает и складывает { double left = prim(); for(;;) switch(curr_tok) { case MUL: get_token(); // ест "*" left *= prim(); break; case DIV: get_token(); // ест "/" double d = prim(); if (d == 0) return error("деление на 0"); left /= d; break; default: return left; } } Проверка, которая делается, чтобы удостовериться в том, что нет деления на ноль, необходима, поскольку результат деления на ноль не определен и как правило является роковым. Функция error(char*) будет описана позже. Переменная d вводится в программе там, где она нужна, и сразу же инициализируется. Во многих языках описание может располагаться только в голове блока. Это ограничение может приводить к довольно скверному искажению стиля программирования и/или излишним ошибкам. Чаще всего неинициализированные локальные переменные являются просто признаком плохого стиля; исключением являются переменные, подлежащие инициализации посредством ввода, и переменные векторного или структурного типа, которые нельзя удобно инициализировать одними присваиваниями *3. Заметьте, что = является операцией присваивания, а == операцией сравнения. Функция prim, обрабатывающая primary, написана в основном в том же духе, не считая того, что немного реальной работы в ней все-таки выполняется, и нет нужды в цикле, поскольку мы попадаем на более низкий уровень иерархии вызовов: double prim() // обрабатывает primary (первичные) { switch (curr_tok) { case NUMBER: // константа с плавающей точкой get_token(); return number_value; case NAME: if (get_token() == ASSIGN) { name* n = insert(name_string); get_token(); n->value = expr(); return n->value; } return look(name-string)->value; case MINUS: // унарный минус get_token(); return -prim(); case LP: get_token(); double e = expr(); if (curr_tok != RP) return error("должна быть )"); get_token(); return e; case END: return 1; default: return error("должно быть primary"); } } При обнаружении NUMBER (то есть, константы с плавающей точкой), возвращается его значение. Функция ввода get_token() помещает значение в глобальную переменную number_value. Использование в программе глобальных переменных часто указывает на то, что структура не совсем прозрачна, что применялась некоторого рода оптимизация. Здесь дело обстоит именно так. Теоретически лексический символ обычно состоит из двух частей: значения, определяющего вид лексемы (в данной программе token_value), и (если необходимо) значения лексемы. У нас имеется только одна простая переменная curr_tok, поэтому для хранения значения последнего считанного NUMBER понадобилась глобальная переменная number_value. Это работает только потому, что калькулятор при вычислениях использует только одно число перед чтением со входа другого. Так же, как значение последнего встреченного NUMBER хранится в number_value, в name_string в виде символьной строки хранится представление последнего прочитанного NAME. Перед тем, как что-либо сделать с именем, калькулятор должен заглянуть вперед, чтобы посмотреть, осуществляется ли присваивание ему, или оно просто используется. В обоих случаях надо справиться в таблице имен. Сама таблица описывается в этом пункте; здесь надо знать только, что она состоит из элементов вида: srtuct name { char* string; char* next; double value; } где next используется только функциями, которые поддерживают работу с таблицей: name* look(char*); name* insert(char*); Обе возвращают указатель на name, соответствующее параметру - символьной строке; look() выражает недовольство, если имя не было определено. Это значит, что в калькуляторе можно использовать имя без предварительного описания, но первый раз оно должно использоваться в левой части присваивания. <<<  Назад Вперед  >>>  1  2  3  4  5  6   8  Комментарии к статье  8 8  Обсудить в чате

8  В тему Краткая сводка операций Сводка операторов Комментарии и Выравнивание