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

Переменная yytext - указатель на совпавшую строку (оканчивающийся NULL-символом), и yyleng - длина совпавшей строки. Выражение yyout является выходным файлом и по умолчанию является stdout. Функция yywrap вызывается lex, когда входные данные закончились. Возвращает 1, если закончено, 0 если требуется дальнейшая обработка. Каждая программа на C требует main функцию. В этом случае просто вызывается yylex,

Основная точка входа для lex. Некоторые реализации lex включают копии main и yywrap в библиотеку, устраняя необходимость явно определять их. Поэтому первый пример, наименьшая программа lex правильно функционирует.

Следующий пример присоединяет слева номер линии для каждой линии в файле. Некоторые реализации lex предопределяют вычисление yylineno. Входной файл для lex - это yyin, и является по умолчанию stdin.

%{

int yylineno;

%}

%%

^(.*)\n printf («%4d\t % s», ++yylineno, yytext);

%%

int main (int argc, char *argv[]) {

yyin = fopen (argv[1], «r»);

yylex();

fclose(yyin);

}

Секции определений состоят из замен, кода и начальных состояний. Код в секциях определения просто копируется в начало генерируемого C файла, при этом код должен быть в скобках%{» и «%}». Замены облегчаются правилами совпадения шаблонов. Например, можно определить цифры и символы:

digit [0-9]

letter [A-Za-z]

%{

int count;

%}

%%

/* match identifier */

{letter} ({letter}|{digit})* count++;

%%

int main(void) {

yylex();

printf («number of identifiers =%d\n», count);

return 0;

}

Пробел должен разделять терм и ассоциируемое выражение. Ссылки на подстановки в секциях правил окружены скобками ({letter}), чтобы различать их с символами. Когда происходит совпадение в секции правил, ассоциируемый C код выполняется. Вот программа, которая считает количество символов, слов и линий в файле (подобная команде wc в Unix):

%{

int nchar, nword, nline;

%}

%%

\n {nline++; nchar++;}

[^ \t\n]+ {nword++, nchar += yyleng;}

{nchar++;}

%%

int main(void) {

yylex();

printf («%d\t % d\t % d\n», nchar, nword, nline);

return 0;

}

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

В целом подсистема LEX для систем UNIX включает следующие файлы:

/usr/ccs/bin/lex;

lex.yy.c;

/usr/ccs/lib/lex/ncform;

/usr/lib/libl.a;

/usr/lib/libl.so.

В каталоге /usr/ccs/lib/lex имеется файл-заготовка ncform, который LEX используется для построения ЛА. Этот файл является уже готовой программой лексического анализа. Но в нем не определены действия, которые необходимо выполнять при распознавании лексем, отсутствуют и сами лексемы, не сформированы рабочие массивы и т.д. С помощью команды lex файл ncform достраивается. В результате мы получаем файл со стандартным именем lex.yy.c. Если LEX-программа размещена в файле program.l, то для получения ЛА с именем program необходимо выполнить следующий набор команд:

lex program.l

cc lex.yy.c - ll - o program

Если имя входного файла для команды lex не указано, то будет использоваться файл стандартного ввода. Флаг - ll требуется для подключения /usr/ccs/lib/libl.a - библиотеки LEX. Если необходимо получить самостоятельную программу, как в данном случае, подключение библиотеки обязательно, поскольку из нее подключается главная функция main. В противном случае, если имеется необходимость включить ЛА в качестве функции в другую программу (например, в программу синтаксического анализа), эту библиотеку необходимо вызвать уже при сборке. Тогда, если main определен в вызывающей ЛА программе, редактор связей не будет подключать раздел main из библиотеки LEX.

Общий формат вызова команды lex:

lex [-ctvn - V - Q [y|n]] [file]

Флаги:

- c - включает фазу генерации Си-файла (устанавливается по умолчанию);

- t - поместить результат в стандартный файл вывода, а не в файл lex.yy.c;

- v - вывести размеры внутренних таблиц;

- n - не выводить размеры таблиц (устанавливается по умолчанию);

- V - вывести информацию о версии LEX в стандартный файл ошибок;

- Q - вывести (Qy) либо не выводить (Qn, устанавливается по умолчанию) информацию о версии в файл lex.yy.c.

YACC - Yet Another Compiler Compiler

Грамматики для yacc описываются с помощью Формы Бэкуса-Наура (Backus Naur Form, BNF)

Эту технику была ввели John Backus и Peter Naur и использовали ее, чтобы описать ALGOL60. Грамматика BNF может быть использована для описания контекстно-свободных языков. Большинство конструкций современного программирования могут быть представлены в BNF.

Например, грамматика для выражения, которое умножает и складывает числа может быть представлена следующим образом:

E -> E + E

E -> E * E

E -> id

Были специфицированы 3 правила продукции. Термы, которые могут быть с левой стороны правил продукции(lhs) продукции, такие как E (expression), являются нетерминальными символами. Термы, такие как id (identifier) являются терминальными символами (токенами, возвращаемыми lex) и могут быть только с правой стороны правил продукции(rhs).

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

E -> E * E (r2)

-> E * z (r3)

-> E + E * z (r1)

-> E + y * z (r3)

-> x + y * z (r3)

На каждом шаге мы расширяем терм, заменяем левую часть продукции соответствующей правой частью. Числа справа показывают какое правило применяется. Чтобы распознать выражение, необходима обратная операция. Кроме того, что необходимо начинать с единичного нетерминального (начального символа), и генерировать выражение из грамматики. Это известно под термином восходящий (bottom-up) анализ и использование стека для хранения термов. Вот некоторый пример в обратном порядке:

1. x + y * z shift

2 x. + y * z reduce(r3)

3 E. + y * z shift

4 E +. y * z shift

5 E + y. * z reduce(r3)

6 E + E. * z shift

7 E + E *. z shift

8 E + E * z. reduce(r3)

9 E + E * E. reduce(r2) emit multiply

10 E + E. reduce(r1) emit add

11 E. accept

Каждому правилу можно поставить в соответствие некое действие, которое будет выполняться всякий раз, как это правило будет распознано. Действия могут возвращать значения и могут пользоваться значениями, возвращенными предыдущими действиями. Более того, лексический анализатор может возвращать значения для токенов (дополнительно), если хочется. Действие - это обычный оператор языка Си, который может выполнять ввод, вывод, вызывать подпрограммы и изменять глобальные переменные.

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

A: ' (' B ')'

{hello (1, «abc»);}

и

XXX: YYY ZZZ

{printf («a message\n»); flag = 25;}

являются грамматическими правилами с действиями.

Чтобы обеспечить связь действий с анализатором, используется спецсимвол «доллар» ($). Чтобы вернуть значение, действие обычно присваивает его псевдопеременной $$. Например, действие, которое не делает ничего, но возвращает единицу:

{$$ = 1;}

Чтобы получить значения, возвращенные предыдущими действиями и лексическим анализатором, действие может использовать псевдопеременные $1, $2 и т.д., которые соответствуют значениям, возвращенным компонентами правой части правила, считая слева направо. Таким образом, если правило имеет вид:

A: B C D;

то $2 соответствует значению, возвращенному нетерминалом C, a $3 - нетерминалом D. Более конкретный пример:

expr: ' (' expr ')';

Значением, возвращаемым этим правилом, обычно является значение выражения в скобках, что может быть записано так:

expr: ' (' expr ')'

{$$ = $2;}

По умолчанию, значением правила считается значение, возвращенное первым элементом ($1). Таким образом, если правило не имеет действия, Yacc автоматически добаляет его в виде $$=$1;, благодаря чему для правила вида

A: B;

обычно не требуется самому писать действие.

В вышеприведенных примерах все действия стояли в конце правил, но иногда желательно выполнить что-либо до того, как правило будет полностью разобрано. Для этого Yacc позволяет записывать действия не только в конце правила, но и в его середине. Значение такого действия доступно действиям, стоящим правее, через обычный механизм:

A: B

{$$ = 1;}

C

{x = $2; y = $3;}

;

В результате разбора иксу (x) присвоится значение 1, а игреку (y) - значение, возвращенное нетерминалом C. Действие, стоящее в середине правила, считается за его компоненту, поэтому x=$2 присваивает X-у значение, возвращенное действием $$=1;

Для действий, находящихся в середине правил, Yacc создает новый нетерминал и новое правило с пустой правой частью и действие выполняется после разбора этого нового правила. На самом деле Yacc трактует последний пример как

NEW_ACT: /* empty */ /* НОВОЕ ПРАВИЛО */

{$$ = 1;}

;

A: B NEW_ACT C

{x = $2; y = $3;}

;

В большинстве приложений действия не выполняют ввода / вывода, а конструируют и обрабатывают в памяти структуры данных, например дерево разбора. Такие действия проще всего выполнять вызывая подпрограммы для создания и модификации структур данных. Предположим, что существует функция node, написанная так, что вызов node (L, n1, n2) создает вершину с меткой L, ветвями n1 и n2 и возвращает индекс свежесозданной вершины. Тогда дерево разбора может строиться так:

expr: expr '+' expr

{$$ = node ('+', $1, $3);}

Программист может также определить собственные переменные, доступные действиям. Их объявление и определение может быть сделано в секции объявлений, заключенное в символы%{и%}. Такие объявления имеют глобальную область видимости, благодаря чему доступны как действиям, так и лексическому анализатору. Например:

%{

int variable = 0;

%}

Такие строчки, помещенные в раздел объявлений, объявляют переменную variable типа int и делают ее доступной для всех действий. Все имена внутренних переменных Yacca начинаются c двух букв y, поэтому не следует давать своим переменным имена типа yymy.

Программист, использующий Yacc должен написать сам (или создать при помощи программы типа Lex) внешний лексический анализатор, который будет читать символы из входного потока (какого - это внутреннее дело лексического анализатора), обнаруживать терминальные символы (токены) и передавать их синтаксическому анализатору, построенному Yaccом (возможно вместе с неким значением) для дальнейшего разбора. Лексический анализатор должен быть оформлен как функция с именем yylex, возвращающая значение типа int, которое представляет собой тип (номер) обнаруженного во входном потоке токена. Если есть желание вернуть еще некое значение (например номер в группе), оно может быть присвоено глобальной, внешней (по отношению к yylex) переменной по имени yylval.

Лексический анализатор и Yacc должны использовать одинаковые номера токенов, чтобы понимать друг друга. Эти номера обычно выбираются Yaccом, но могут выбираться и человеком. В любом случае механизм define языка Си позволяет лексическому анализатору возвращать эти значения в символическом виде. Предположем, что токен по имени DIGIT был определен в секции объявлений спецификации Yaccа, тогда соответствующий текст лексического анализатора может выглядеть так:

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 в Unix

ФАЙЛЫ

y.output

y.tab.c

y.tab.h Определение кодов лексем.

yacc.tmp Временный файл.

yacc.debug Временный файл.

yacc.acts Временный файл.

/usr/lib/yaccpar Прототип алгоритма разбора для

C-программ.

СМ. ТАКЖЕ

lex(1).

ДИАГНОСТИКА

В стандартный протокол направляется информация о числе конфликтных ситуаций типа «свертка-свертка» и «перенос-свертка»; более подробные сообщения содержатся в файле y.output. Аналогичным образом сообщается о продукциях, недостижимых из начального символа грамматики.

ОГРАНИЧЕНИЯ

Так как имена файлов фиксированы, в данном каталоге в каждый момент времени может быть активным только один процесс yacc

- вычисление математических выражений с любой степенью вложенности

- поддержка в выражениях чисел с плавающей точкой

- математические операции:

- «+», «-» (бинарный / унарный), «*», «/», «^» (возведение в степень)

- поддержка функций:

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>

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

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, что приводит к повышению скорости выполнения программы.

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

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

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

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

Страницы: 1, 2