-d

Сгенерировать файл y.tab.h, который содержит определения #define, связывающие заданные пользователем «имена лексем» с назначенными программой yacc «кодами лексем», что позволяет использовать коды лексем в исходных файлах, отличных от y.tab.c.

-l

Не вставлять в программу y.tab.c операторы #line. Рекомендуется использовать только после того, как грамматика и другие компоненты полностью отлажены.

-t

При помощи средств условной компиляции в программу y.tab.c всегда вставляются отладочные операторы, однако по умолчанию компилятор их пропускает. Если указана опция - t, то при отсутствии других указаний отладочные операторы будут скомпилированы. Вне зависимости от использования опции - t компиляцией отладочных операторов управляет переменная препроцессора YYDEBUG. Если YYDEBUG имеет ненулевое значение, отладочные операторы компилируются; при нулевом значении они пропускаются. Когда программа сформирована без отладочного кода, ее размер меньше и скорость выполнения несколько выше.

ФАЙЛЫ

y.output

y.tab.c

y.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 | [<+>|<->] TERM

TERM-> TERM<*>FACTOR | TERM</>FACTOR | FACTOR

FACTOR-> FACTOR<^>POW{<^>} 0 | POW

POW-> <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 MORETERMS

MORETERMS-> <+>TERM MORETERMS | <->TERM MORETERMS | <e>

TERM-> FACTOR MOREFACTORS

MOREFACTORS-> <*>FACTOR MOREFACTORS | </>FACTOR MOREFACTORS | <e>

FACTOR-> POW MOREPOWS

MOREPOWS-> <^>POW{<^>} 0 | <e>

POW-> <number> | <var_name> | <(>EXPR<)> | FUNC<(>EXPR<)>

FUNC-> <log> | <exp> | <sin> | <cos> | <tan> | <acos> | <asin> | <atan>

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

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

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

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

Синтаксический анализатор производит обработку потока входных лексем методом предиктивного(предсказывающего) анализа, который является специальным видом метода рекурсивного спуска.

В данном анализаторе нетерминалам грамматики ставится в соответствие функция-обработчик. Смыслом предиктивного анализа является однозначное определение следующей вызываемой функции-обработчика на основе текущей лексемы.

Соответствие нетерминалов функциям-обработчикам:

POW : powNT()

FACTOR : factorNT()

TERM : termNT()

EXPR : exprNT()

Взаимодействие анализаторов

В Analyser реализовано объединение проходов лексического и синтаксического анализаторов в один проход. При просмотре следующей лексемы синтаксическим анализатором вызывается функция, реализующая извлечение лексемы из входной строки, содержащей математическое выражение.

В данном случае это более эффективный подход с точки зрения занимаемой оперативной памяти. Если делать полный проход лексического анализатора, то в оперативной памяти, помимо входной строки с математическим выражением, будет содержаться вектор лексем, который практически повторяет содержимое входной строки. Поскольку синтаксическому анализатору не требуется обозревать несколько лексем одновременно, то наличие вектора лексем не имеет смысла, значит объединение проходов анализаторов в один проход логически обосновано.

Оптимизатор

Оптимизатор делает проход по синтаксическому дереву и уменьшает количество его узлов за счет вычисления константных подвыражений с любыми знаками и функциями, и для операций +, -, *, если подвыражения частично являются константными.

Если входное выражение не оптимально, содержит переменную и требуется вычисление этого выражения на некотором множестве действительных чисел, мощность которого больше 1, то повышение скорости выполнения программы очевидно.

Алгоритм оптимизации

1) Просмотр текущего узла

2) Проверка этого узла на константность:

да:

- вычисление его значения

- освобождение памяти, выделенной для поддерева с вершиной в этом узле

- создание нового узла, содержащего вычисленную константу

нет:

- переход к шагу 3)

3) Операция этого узла + или * (операция «-» не рассматривается, т. к. при построении синтаксического дерева бинарный «-» заменяется унарным «-». Пример: 1-2 преобразуется в 1+(-2)):

да:

- формирование векторов указателей на константные и неконстантные (включая не непосредственные) подузлы данного узла с той же операцией. Если встречается подузел, операция которого отличается от операции данного узла, то:

- добавление указателя на этот подузел в вектор указателей на неконстантные узлы

- переход к шагу 1) для этого подузла

- вычисление результата для вектора указателей на константы

- освобождение памяти, выделенной для узлов, указатели на которые содержатся в векторе указателей на константные узлы

- построение нового поддерева на основе вектора неконстант и вычисленной константы

нет:

- переход к шагу 1) для всех непосредственных подузлов данного узла

Пример оптимизации

Исходное математическое выражение:

(4^2+(2^3*2)^0.5+x*(1+2+3+4+(2*3*4*x)))+((1+2)+sin (x+1+2)) - (log (sin(x))+1)

Формат строки для синтаксического дерева в выводе программы имеет следующий:

(<указатель_на _текущую_вершину>) <список_указателей_на_непосредственные подузлы | значение_подузла> <операция>

или

(<указатель_на _текущую_вершину>) <функция | константа | переменная> [<список_указателей_на_непосредственные подузлы>] [<значение>]

Для этой формулы неоптимизированное синтаксическое дерево имеет вид:

Syntax Tree: (not optimized)

(0x8050da8) left=0x8050d28 right=0x8050d98 op=+

(0x8050d98) right=0x8050d88 op=-

(0x8050d88) left=0x8050d58 right=0x8050d78 op=+

(0x8050d78) CONST=1

(0x8050d58) op=l next=0x8050d48

(0x8050d48) op=s next=0x8050d38

(0x8050d38) VAR=x

(0x8050d28) left=0x8050c38 right=0x8050d18 op=+

(0x8050d18) left=0x8050c88 right=0x8050d08 op=+

(0x8050d08) op=s next=0x8050cf8

(0x8050cf8) left=0x8050cc8 right=0x8050ce8 op=+

(0x8050ce8) CONST=2

(0x8050cc8) left=0x8050c98 right=0x8050cb8 op=+

(0x8050cb8) CONST=1

(0x8050c98) VAR=x

(0x8050c88) left=0x8050c58 right=0x8050c78 op=+

(0x8050c78) CONST=2

(0x8050c58) CONST=1

(0x8050c38) left=0x8050aa8 right=0x8050c28 op=+

(0x8050c28) left=0x8050ab8 right=0x8050c18 op=*

(0x8050c18) left=0x8050b68 right=0x8050c08 op=+

(0x8050c08) left=0x8050be8 right=0x8050bf8 op=*

(0x8050bf8) VAR=x

(0x8050be8) left=0x8050bb8 right=0x8050bd8 op=*

(0x8050bd8) CONST=4

(0x8050bb8) left=0x8050b88 right=0x8050ba8 op=*

(0x8050ba8) CONST=3

(0x8050b88) CONST=2

(0x8050b68) left=0x8050b38 right=0x8050b58 op=+

(0x8050b58) CONST=4

(0x8050b38) left=0x8050b08 right=0x8050b28 op=+

(0x8050b28) CONST=3

(0x8050b08) left=0x8050ad8 right=0x8050af8 op=+

(0x8050af8) CONST=2

(0x8050ad8) CONST=1

(0x8050ab8) VAR=x

(0x8050aa8) left=0x80509e8 right=0x8050a98 op=+

(0x8050a98) left=0x8050a68 right=0x8050a88 op=^

(0x8050a88) CONST=0.5

(0x8050a68) left=0x8050a38 right=0x8050a58 op=*

(0x8050a58) CONST=2

(0x8050a38) left=0x8050a08 right=0x8050a28 op=^

(0x8050a28) CONST=3

(0x8050a08) CONST=2

(0x80509e8) left=0x80509b8 right=0x80509d8 op=^

(0x80509d8) CONST=2

(0x80509b8) CONST=4

nodes num: 47

Как видно из вывода, количество узлов в синтаксическом дереве равно 47.

После прохода оптимизатора дерево имеет следующий вид:

Syntax Tree: (optimized)

(0x8050da8) left=0x8050aa8 right=0x8050c28 op=+

(0x8050c28) left=0x8050e08 right=0x8050ab8 op=*

(0x8050ab8) VAR=x

(0x8050e08) left=0x8050b08 right=0x8050c08 op=+

(0x8050c08) left=0x8050b88 right=0x8050bf8 op=*

(0x8050bf8) VAR=x

(0x8050b88) CONST=24

(0x8050b08) CONST=10

(0x8050aa8) left=0x80509e8 right=0x8050d08 op=+

(0x8050d08) op=s next=0x8050cf8

(0x8050cf8) left=0x8050ce8 right=0x8050c98 op=+

(0x8050c98) VAR=x

(0x8050ce8) CONST=3

(0x80509e8) left=0x80509b8 right=0x8050d98 op=+

(0x8050d98) right=0x8050d58 op=-

(0x8050d58) op=l next=0x8050d48

(0x8050d48) op=s next=0x8050d38

(0x8050d38) VAR=x

(0x80509b8) CONST=22

nodes num: 19

Это дерево соответствует формуле:

22-log (sin(x))+sin (3+x)+x*(10+24*x)

Как видно из вывода, количество узлов в синтаксическом дереве равно 19, против 47, что приводит к повышению скорости выполнения программы.

Сохранение синтаксического дерева в файл

Эта функциональность добавлена для ускорения работы с математическими выражениями. После трансляции математического выражения в синтаксическое дерево, есть возможность сохранить его в том виде, в котором оно находится в оперативной памяти, в файл на жесткий диск. Т. о. если требуется вычислить несколько математических выражений несколько раз, то их можно оттранслировать один раз, сохранить в файлы, а потом извлекать их в виде, готовом для интерпретации, не тратя время на лексический и синтаксический анализ.

Сохранение синтаксического дерева начинается с корня дерева и обходит дочерние узлы слева - направо с их последующим сохранением.

Аналогичным образом происходит извлечение дерева из файла.

Интерпретатор

Интерпретатор выполняет извлечение из файла синтаксического дерева, являющегося результатом выполнения транслятора.

После извлечения дерева интерпретатор совершает его обход. Результатом работы интерпретатора является число, в точности соответствующее значению математического выражения, которому, в свою очередь, эквивалентно извлеченное синтаксическое дерево.

Заключение

В работе были рассмотрены теоретические основы построения трансляторов.

Результатом работы являются:

- класс Analyser, реализующий заявленную функциональность

- транслятор с языка математических выражений на язык деревьев вывода

- интерпретатор языка деревьев вывода