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

Генератор синтаксических анализаторов 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), что является наиболее гибким решением, так как созданный текст, переносим и легко поддается любому другому преобразованию (если появится хорошая идея).

Генератор yaccсам по себе представляется мощным программным средством. Его изучение потребует от вас, конечно, некоторых усилий, но все ваши "затраты" многократно окупятся. Анализаторы, создаваемые yacc, — небольшие, эффективные и корректные (хотя за семантические преобразования отвечаете вы). Кроме того, многие неприятные проблемы, связанные с процессом разбора, решаются автоматически. Программы языковых распознавателей достаточно легко создавать и, что, возможно, еще более важно, изменять по мере совершенствования определения языка.

Исходный текст hoc1состоит из грамматических правил с описанием действий лексической процедуры yylexи функции main, хранимых в одном файле hoc.y. (Имена файлов, содержащих текст для yacc, традиционно оканчиваются на .y, но это соглашение в отличие от соглашения о сси .c не поддерживает сам yacc.) Грамматика составляет первую половину файла hoc.y:

$ cat hoc.y

%{

#define YYSTYPE double /* data type of yacc stack */

%}

%token NUMBER

%left '+' /* left associative, same precedence */

%left '*' '/' /* left assoc., higher precedence */

%%

list: /* nothing */

| list '\n'

| list expr '\n' { printf("\t%.8g\n", $2); }

;

expr: NUMBER { $$ = $1; }

| expr '+' expr { $$ = $1 + $3; }

| expr '-' expr { $$ = $1 - $3; }

| expr '*' expr { $$ = $1 * $3; }

| expr '/' expr { $$ = $1 / $3; }

| '(' expr ')' { $$ = $2; }

;

%%

/* end of grammar */

...

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

Альтернативные правила разделены символом '|'. С каждым грамматическим правилом может быть связано определенное действие, которое выполняется, когда экземпляр этого правила распознается во входном потоке. Действие описывается последовательностью операторов Си, заключенной в фигурные скобки. Внутри последовательности $n(т.е. $1, $2и т.д.) определяет значение, вырабатываемое n-м компонентом правила, а $$значение, вырабатываемое всеми компонентами правила в целом. Так, в правиле

expr: NUMBER { $$ = $1; }

$1— значение, вырабатываемое при распознавании NUMBER, и оно же является результирующим значением expr. В данном случае присваивание $$ = $1может быть опущено, так как $$всегда принимает значение $1(если не устанавливается явно каким либо иным образом). В следующей строке с правилом

expr: expr '+' expr { $$ = $1 + $3; }

результирующее значение exprявляется суммой двух компонентов, тоже expr. Отметим, что $2соответствует '+'т.е. каждый компонент пронумерован.

Строкой выше выражение, за которым следует символ перевода строки ( '\n'), распознается как список , и печатается его значение. Если за такой конструкцией следует конец входного потока, процесс разбора завершается правильно. Список может быть пустой строкой; так учитываются пустые входные строки.