yylex(){extern int yylval;int c;…c = getchar();…switch (c) {…case '0':case '1':…case '9':yylval = c – '0';return DIGIT;…}…
Вышеприведенный фрагмент возвращает номер токена DIGIT и значение, равное цифре. Если при этом сам текст лексического анализатора был помещен в секцию программ спецификации Yacca – есть гарантия, что идентификатор DIGIT был определен номером токена DIGIT, причем тем самым, который ожидает Yacc.
Такой механизм позволяет создавать понятные, легкие в модификации лексические анализаторы. Единственным ограничением является запрет на использование в качестве имени токена слов, зарезервированых или часто используемых в языке Си слов. Например, использование в качестве имен токенов таких слов как if или while, почти наверняка приведет к возникновению проблем при компиляции лексического анализатора. Кроме этого, имя error зарезервировано для токена, служащего делу обработки ошибок, и не должно использоваться.
Как уже было сказано, номера токенов выбираются либо Yaccом, либо человеком, но чаще Yaccом, при этом для отдельных символов (например для (или;) выбирается номер, равный ASCII коду этого символа. Для других токенов номера выбираются начиная с 257.
Для того, чтобы присвоить токену (или даже литере) номер вручную, необходимо в секции объявлений после имени токена добавить положительное целое число, которое и станет номером токена или литеры, при этом необходимо позаботиться об уникальности номеров. Если токену не присвоен номер таким образом, Yacc присваивает ему номер по своему выбору.
По традици, концевой маркер должен иметь номер токена, равный, либо меньший нуля, и лексический анализатор должен возвращать ноль или отрицательное число при достижении конца ввода (или файла).
Очень неплохим средством для создания лексических анализаторов является программа Lex. Лексические анализаторы, построенные с ее помощью прекрасно гармонируют с синтаксическими анализаторами, построенными Yaccом. Lex можно легко использовать для построения полного лексического анализатора из файла спецификаций, основанного на системе регулярных выражений (в отличие от системы грамматических правил для Yacca), но, правда, существуют языки (например Фортран) не попадающие ни под какую теоретическю схему, но для них приходится писать лексический анализатор вручную.
НАЗВАНИЕ
yacc – еще один компилятор компиляторов
СИНТАКСИС
yacc [-v] [-d] [-l] [-t] грамматикаОПИСАНИЕ
Команда yacc преобразует контекстно-свободную грамматику в набор таблиц для простого LR(1) – разбора. Грамматика может содержать неоднозначности; чтобы их преодолеть, используются заданные правила предшествования.
Выходной файл y.tab.c преобразуется C-компилятором в программу yyparse, которую нужно скомпоновать с программой лексического анализа yylex, а также с подпрограммой main и подпрограммой обработки ошибок yyerror. Эти подпрограммы должны быть предоставлены пользователем; при порождении лексических анализаторов полезен lex(1).
Допустимые опции:
| -v | Сгенерировать файл y.output, который содержит описание таблиц разбора с указанием конфликтных ситуаций, вызванных неоднозначностями грамматики. |
| -d | Сгенерировать файл y.tab.h, который содержит определения #define, связывающие заданные пользователем «имена лексем» с назначенными программой yacc «кодами лексем», что позволяет использовать коды лексем в исходных файлах, отличных от y.tab.c. |
| -l | Не вставлять в программу y.tab.c операторы #line. Рекомендуется использовать только после того, как грамматика и другие компоненты полностью отлажены. |
| -t | При помощи средств условной компиляции в программу y.tab.c всегда вставляются отладочные операторы, однако по умолчанию компилятор их пропускает. Если указана опция – t, то при отсутствии других указаний отладочные операторы будут скомпилированы. Вне зависимости от использования опции – t компиляцией отладочных операторов управляет переменная препроцессора YYDEBUG. Если YYDEBUG имеет ненулевое значение, отладочные операторы компилируются; при нулевом значении они пропускаются. Когда программа сформирована без отладочного кода, ее размер меньше и скорость выполнения несколько выше. |
ФАЙЛЫ
y.outputy.tab.cy.tab.h Определение кодов лексем.yacc.tmp Временный файл.yacc.debug Временный файл.yacc.acts Временный файл./usr/lib/yaccpar Прототип алгоритма разбора дляC-программ.СМ. ТАКЖЕ
lex(1).
ДИАГНОСТИКА
В стандартный протокол направляется информация о числе конфликтных ситуаций типа «свертка-свертка» и «перенос-свертка»; более подробные сообщения содержатся в файле y.output. Аналогичным образом сообщается о продукциях, недостижимых из начального символа грамматики.
ОГРАНИЧЕНИЯ
Так как имена файлов фиксированы, в данном каталоге в каждый момент времени может быть активным только один процесс yacc
Реализовать:
– транслятор с языка математических выражений на язык деревьев вывода
– интерпретатор языка деревьев вывода
К разрабатываемым программам предъявляются следующие требования:
– реализация осуществляется на языке C++.
– функциональность транслятора и интерпретатора должна быть реализована в виде класса (Класс Analyser).
Должна быть обеспечена поддержка следующей функциональности:
– вычисление математических выражений с любой степенью вложенности– поддержка в выражениях чисел с плавающей точкой– математические операции:– «+», «–» (бинарный / унарный), «*», «/», «^» (возведение в степень)– поддержка функций:log(), exp(), sin(), cos(), tan(), acos(), asin(), atan()– игнорирование пробелов, символов табуляции и переноса строки– оптимизация синтаксического дерева– объединение проходов синтаксического и лексического анализаторов в один проход. (Отсюда название «однопроходный / двухпроходный». Второй проход опциональный – это проход оптимизатора.)– запись / чтение синтаксического дерева в файл/из файлаГрамматика описана в виде формы Бэкуса-Наура, расширенной метасимволами.
Пояснения:
1) <e> это пустой символ3) {DIGIT} n – это итерация DIGIT, где n – натуральное число4) {<^>} 0 это отсутствие двойного возведения в степень5) имена переменных не должны совпадать с именами функций, поддерживаемых интерпретатором.Данная грамматика позволяет разбирать математические выражения с учетом приоритетов математических операций.Лексический анализатор выделяет лексемы на основе конца строки и следующих терминальных символов, одновременно являющихся разделителями:
+, -, *, /, ^, (,)
Синтаксический анализатор производит обработку потока входных лексем методом предиктивного(предсказывающего) анализа, который является специальным видом метода рекурсивного спуска.
В данном анализаторе нетерминалам грамматики ставится в соответствие функция-обработчик. Смыслом предиктивного анализа является однозначное определение следующей вызываемой функции-обработчика на основе текущей лексемы.
Соответствие нетерминалов функциям-обработчикам:
POW : powNT()
FACTOR : factorNT()
TERM : termNT()
EXPR : exprNT()
В Analyser реализовано объединение проходов лексического и синтаксического анализаторов в один проход. При просмотре следующей лексемы синтаксическим анализатором вызывается функция, реализующая извлечение лексемы из входной строки, содержащей математическое выражение.
В данном случае это более эффективный подход с точки зрения занимаемой оперативной памяти. Если делать полный проход лексического анализатора, то в оперативной памяти, помимо входной строки с математическим выражением, будет содержаться вектор лексем, который практически повторяет содержимое входной строки. Поскольку синтаксическому анализатору не требуется обозревать несколько лексем одновременно, то наличие вектора лексем не имеет смысла, значит объединение проходов анализаторов в один проход логически обосновано.
Оптимизатор делает проход по синтаксическому дереву и уменьшает количество его узлов за счет вычисления константных подвыражений с любыми знаками и функциями, и для операций +, -, *, если подвыражения частично являются константными.
Если входное выражение не оптимально, содержит переменную и требуется вычисление этого выражения на некотором множестве действительных чисел, мощность которого больше 1, то повышение скорости выполнения программы очевидно.
1) Просмотр текущего узла
2) Проверка этого узла на константность:
да:
– вычисление его значения
– освобождение памяти, выделенной для поддерева с вершиной в этом узле
– создание нового узла, содержащего вычисленную константу
нет:
– переход к шагу 3)
3) Операция этого узла + или * (операция «–» не рассматривается, т. к. при построении синтаксического дерева бинарный «–» заменяется унарным «–». Пример: 1–2 преобразуется в 1+(-2)):