Брайан Керниган - UNIX — универсальная среда программирования

выраж / выраж

( выраж )

Здесь список — последовательность выражений, каждое из которых завершается символом перевода строки, а выражение — число или пара выражений, объединенных операцией, либо выражение в скобках.

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

Генератор синтаксических анализаторов yacc [15] Автор yacc С. Джонсон назвал свою программу "еще одним компилятором компиляторов" (yet another compiler-compiler), поскольку во время ее разработки (1972 г.) уже существовало довольно большое число таких программ, yacc — одна из немногих, получивших признание. преобразует компилятор грамматических правил языка, подобных приведенным выше, в анализатор, который разбирает операторы языка. Yaccобладает возможностью приписывать значения компонентам грамматики таким образом, что в процессе разбора значение может быть "вычислено" . Используется yaccпоэтапно,

На первом этапе записывается грамматика языка, но более точно, чем было показано ранее, т.е. определяется синтаксис. На этом этапе назначение yacc— предупреждение появления ошибок и двусмысленностей в грамматике.

На втором этапе каждое правило (правило вывода грамматики) сопровождается описанием действия на тот случай, когда найден экземпляр грамматической конструкции в разбираемой программе. Часть действия записывается на Си, причем должны выполняться определенные соглашения о связи между грамматикой и текстом. Здесь определяется семантика языка.

Третий этап — создание лексического анализатора, который должен читать разбираемый входной поток и разбивать его для анализатора на осмысленные единицы. Примером лексической единицы длиной в несколько символов может служить NUMBER; операции из одного символа, такие, как +и *, также являются лексическими единицами. По традиции лексические единицы называют лексемами.

На следующем этапе разрабатывается управляющая процедура, которая вызывает анализатор, созданный yacc.

Программа yaccпреобразует грамматику и семантические процедуры в функцию разбора с именем yyparseи записывает ее в виде файла с текстом на Си. Если yaccне находит ошибок, то анализатор, лексический анализатор и управляющую процедуру можно откомпилировать, возможно, связать с другими программами на Си и выполнить.

Действие yaccсводится к многократному обращению к лексическому анализатору за лексемами, распознаванию грамматических (синтаксических) конструкций во входном потоке и выполнению семантических процедур по мере распознавания грамматических правил. Вызывать лексический анализатор нужно по имени yylex, так как именно эту функцию инициирует анализатор yyparseвсякий раз, когда ему нужна следующая лексема. (Все имена, используемые yacc, начинаются с y.)

Чтобы быть более точными, укажем, что входной поток для yaccдолжен иметь такой вид:

%{

Операторы Си типа #include, описания и т. д.

Эта часть необязательна.

%}

yacc-описания: лексемы, грамматические переменные,

информация о приоритетах и ассоциативности

%%

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

%%

еще операторы Си (необязательно):

main() {

...; yyparse(); ...

}

yylex() {

...

}

...

Этот поток поступает на вход yacc, а результат записывается в файл y.tab.c, имеющий следующую структуру:

Операторы на Си между %{ и %}, если есть

Операторы на Си из части после второй комбинации %%, если есть:

main() {

...; yyparse(); ...

}

yylex() {

...

}

...

yyparse() {

анализатор, который вызывает yylex()

}

Такой подход типичен для системы UNIX: yaccвыдает текст на Си, а не оттранслированный файл ( .o), что является наиболее гибким решением, так как созданный текст, переносим и легко поддается любому другому преобразованию (если появится хорошая идея).