Реализация Yacc в Unix

YACC(1)

НАЗВАНИЕ

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()– игнорирование пробелов, символов табуляции и переноса строки– оптимизация синтаксического дерева– объединение проходов синтаксического и лексического анализаторов в один проход. (Отсюда название «однопроходный / двухпроходный». Второй проход опциональный – это проход оптимизатора.)– запись / чтение синтаксического дерева в файл/из файла

Транслятор

Грамматика синтаксического анализатора

Грамматика описана в виде формы Бэкуса-Наура, расширенной метасимволами.

Исходная грамматика

EXPR-> [<+>|<->] EXPR<+>TERM | [<+>|<->] EXPR<->TERM | [<+>|<->] TERMTERM-> TERM<*>FACTOR | TERM</>FACTOR | FACTORFACTOR-> FACTOR<^>POW{<^>} 0 | POWPOW-> <number> | <var_name> | <(>EXPR<)> | FUNC<(>EXPR<)>FUNC-> <log> | <exp> | <sin> | <cos> | <tan> | <acos> | <asin> | <atan>

Пояснения:

1) <e> это пустой символ3) {DIGIT} n – это итерация DIGIT, где n – натуральное число4) {<^>} 0 это отсутствие двойного возведения в степень5) имена переменных не должны совпадать с именами функций, поддерживаемых интерпретатором.Данная грамматика позволяет разбирать математические выражения с учетом приоритетов математических операций.

Эквивалентная грамматика без левой рекурсии

EXPR-> [<+>|<->] TERM MORETERMSMORETERMS-> <+>TERM MORETERMS | <->TERM MORETERMS | <e>TERM-> FACTOR MOREFACTORSMOREFACTORS-> <*>FACTOR MOREFACTORS | </>FACTOR MOREFACTORS | <e>FACTOR-> POW MOREPOWSMOREPOWS-> <^>POW{<^>} 0 | <e>POW-> <number> | <var_name> | <(>EXPR<)> | FUNC<(>EXPR<)>FUNC-> <log> | <exp> | <sin> | <cos> | <tan> | <acos> | <asin> | <atan>

Лексический анализатор

Лексический анализатор выделяет лексемы на основе конца строки и следующих терминальных символов, одновременно являющихся разделителями:

+, -, *, /, ^, (,)