Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 7. YACC Программа YACC (Yet Another Compiler Compiler) предназначенa для построения синтаксического анализатора контекстно-свободно¦ го языка. Анализируемый язык описывается с помощью грамматики в виде, близком форме Бэкуса-Наура (НФБН). Результатом работы YACC'a является программа на Си, реализующая восходящий LALR(1) распознаватель. Структура YACC-программы YACC-программа состоит из трех секций, разделенных символом %% - секции описаний, секции правил, в которой описывается грамматика, и секции программ, содержимое которой просто копи¦ руется в выходной файл. Пример простейшей программы на YACC'e: %token name %start e %% e : e '+' m | e '-' m | m ; m : m '*' t | m '/' t | t ; t : name | '(' e ')' ; %% Секция правил содержит информацию о том, что символ name яв¦ ляется лексемой (терминалом) грамматики, а символ e - ее на¦ чальным нетерминалом. Грамматика записана обычным образом - идентификаторы обозна¦ чают терминалы и нетерминалы, символьные константы типа '+' '-' - терминалы. Символы : | ; - принадлежат метаязыку и читаются "есть по определению", "или" и "конец правила" соответственно. Разрешение конфликтов Написанная грамматика (она обладает свойством LALR(1) - уп¦ ражнение) задает язык арифметических формул, в котором приори¦ тет '*' и '/' выше приоритета '+' и '-', a все операции левоас¦ социативны. Для указания этих свойств языка в грамматику введе¦ ны дополнительные нетерминалы m, и t. Другая грамматика этого языка: e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; не однозначна (и, следовательно, не LALR(1)). Попытка применить YACC для анализа данной грамматики приведет к многочисленным (16) неразрешенным конфликтам типа сдвиг/свертка (shift/reduce) в построенном автомате. Если рассмотреть конфликты более под¦ робно, выясняется, что в каждом случае можно однозначно выбрать между сдвигом или сверткой, основываясь на приоритетах операций и порядке выполнения равноприоритетных операций слева направо. (Аналогично простому и операторному предшествованию). YACC позволяет дополнить грамматику информацией такого рода и получить бесконфликтный распознаватель: %token name %left '+' '-' %left '*' '/' %% e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; %% Предложения %left, %right и %nonassoc в секции описаний при¦ писывают всем перечисленным за ними символам одинаковый приори¦ тет и соответствующее значение ассоциативности. (Отсутствие ас¦ социативности означает недопустимость выражений вида a @ b @ c) Приоритет увеличивается сверху вниз для каждого нового предло¦ жения. LALR(1)-конфликты сдвиг/свертка или свертка/свертка разреша¦ ются выбором более приоритетного действия. Приоритет сдвига ра¦ вен приоритету считываемой лексемы. Приоритет свертки равен приоритету самой правой лексемы в правиле, по которому произво¦ дится свертка. Можно также явно указать приоритет свертки, на¦ писав "%prec <лексема>" справа от правила. Добавить в язык формул операцию унарного минуса, более при¦ оритетную, чем бинарные операции, можно следующим образом: %token name %left '+' '-' %left '*' '/' %left UMIN %% e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; e : '-' e %prec UMIN ; %% Фиктивная лексема UMIN используется только для задания при¦ оритета свертки по правилу e : '-' e ; Итак, YACC разрешает конфликты (если они возникнут) по сле¦ дующим правилам: - если приоритеты альтернативных действий определены и раз¦ личны, то выполняется действие с б`ольшим приоритетом; - если приоритеты действий определены и одинаковы, то в слу¦ чае левой ассоциативности выбирается свертка, в случае правой ассоциативности - сдвиг, если они неассоциативны - возбуждается ошибочная ситуация; - иначе (приоритет хотя бы одной из альтернатив не специфи¦ цирован) в случае конфликта сдвиг/свертка выполняется сдвиг, а в случае конфликта свертка/свертка - свертка по правилу, опре¦ деленному выше по тексту в описании грамматики, в обоих случаях YACC сообщает о неразрешенном конфликте в этом состоянии. Отметим, что для конфликтной грамматики с правилами s : if '(' e ')' s | if '(' e ')' s else s ; предпочтение сдвига "правильно" разрешает конфликт при разборе выражения if( e ) if( e ) s _ else s - else будет отнесено к ближайшему if'у, как и принято в алго¦ лоподобных языках. Для конфликтной грамматики арифметических формул, эти прави¦ ла приводят к вычислению выражения справа-налево без учета при¦ оритетов операций. Семантические действия С каждым правилом грамматики может быть связано действие, которое будет выполнено при свертке по данному правилу. Оно за¦ писывается в виде заключенной в фигурные скобки последователь¦ ности операторов языка Си, расположенной после правой части со¦ ответствующего правила. statement : IF '(' expr ')' statement { if_ctr++; } | WHILE '(' expr ')' statement { while_ctr++; } | assign_st { ass_ctr++; } ; В этом примере действие if_ctr++ будет выполнено после раз¦ бора всего оператора if. При необходимости выполнить семанти¦ ческие действия, например, сразу после вычисления выражения expr, можно поместить их между символами правой части правила. statement: IF '(' expr { action_1 } ')' statement { action_2 } ; В этих случаях YACC автоматически преобразует грамматику, вводя дополнительные нетерминалы и соответствующие им правила с пус¦ той правой частью. При их свертке и будут выполнены действия, расположенные между символами исходной грамматики. statement: IF '(' expr void_1 ')' statement { action_2 } ; void_1: { action_2 } ; Семантический стек Для естественного обмена данными между действиями, каждый терминал или нетерминал может иметь значение. Для доступа к не¦ му в действиях используются псевдопеременные $$ - значение ле¦ вого символа правила, $ - значение i-ого символа правой час¦ ти правила (символы нумеруются слева направо, начиная с 1). Другими словами, кроме обычного стека состояний построенный YACC'ом анализатор содержит "семантический" стек, содержащий значения символов. Значения имеют тип YYSTYPE, который по умол¦ чанию определяется как int. Действие expr : expr '+' expr { $$ = $1 + $3; } ; может быть использовано в интерпретаторе формул, в котором зна¦ чение нетерминала "выражение" есть его вычисленное значение. Если для правила не указано никакого действия, или действие не содержит упоминания псевдопеременной $$, то значение левой части правила становится равным значению первого символа правой части, т.е. неявно выполняется действие { $$ = $1; }. Значение очередной лексемы копируется из переменной int yylval, в кото¦ рую его обычно заносит сканер. Различные символы грамматики могут иметь значения разных ти¦ пов. Для этого следует определить тип YYSTYPE как union и спе¦ цифицировать тип терминалов и нетерминалов в разделе описаний. При этом будет осуществляться контроль типов при использовании псевдопеременных, а обращение к ним будет транслироваться в об¦ ращение к соответствующему полю union. %{ #define YYSTYPE yys typedef union { int intval; long longval; nodeptr *ptrval; } yys; %{ %token ICONST %token LCONST %type expr Если в качестве внутреннего представления программы исполь¦ зуется дерево, удобно иметь в качестве значения нетерминала указатель на соответствующий ему узел дерева. Кодировка лексем и интерфейс Файл, порождаемый YACC'ом в процессе работы, содержит табли¦ цы LALR(1)-анализатора и Си-текст функции int yyparse( void ), реализующей интерпретатор таблиц и семантические действия. Для запуска парсера достаточно вызвать эту функцию. В случае успеш¦ ного разбора она возвращает 0, в случае ошибки - 1. Для получения очередной лексемы парсер вызывает функцию int yylex( void ). Она должна возвратить код лексемы и поместить ее значение в переменную YYSTYPE yylval. Код лексемы - положительное целое число. Лексемам, заданным в виде символьных констант, соответствует их код в наборе сим¦ волов ЭВМ (обычно ASCII), лежащий в диапазоне 0..255. Лексемам, имеющим символические имена, присваиваются коды начиная с 257. Выходной файл содержит операторы #define, определяющие имена лексем как их коды. Если имена лексем требуются в других фай¦ лах, следует указать ключ -d при запуске YACC'а, и он продубли¦ рует эти определения в файле y.tab.h. Этот файл следует вклю¦ чить в другие файлы программы (например, сканер), использующие коды лексем. Обработка ошибок Если анализируемое предложение не соответствует языку, то в некоторый момент возникнет ошибочная ситуация, т.е. парсер ока¦ жется в состоянии, в котором не предусмотрено ни сдвига, ни свертки для полученной ошибочной лексемы. Обычная реакция пар¦ сера - вызов функции void yyerror( const char * ) с аргументом "Syntax error" и завершение работы - возврат из функции yyparse с значением 1. Реализация функции yyerror возлагается на поль¦ зователя, и он может попытаться организовать в ней выдачу более разумной диагностики (при использовании YACC-парсера это не яв¦ ляется тривиальной задачей). Во многих случаях желательно как-нибудь продолжить разбор. Для восстановления после ошибки YACC содержит следующие средства. Имеется специальная лексема с именем error, которая может употребляться в грамматике. При возникновении ошибки ус¦ танавливается флаг ошибки, вызывается функция yyerror, а затем из стека состояний удаляются элементы, пока не встретится сос¦ тояние, допускающее лексему error. При обнаружении такого сос¦ тояния выполняется сдвиг, соответствующий лексеме error в этом состоянии и разбор продолжается. Если при установленном флаге ошибки снова возникает ошибочная ситуация, то для избежания многократных сообщений yyerror не вызывается, а ошибочная лек¦ сема игнорируется. Флаг ошибки сбрасывается только после трех успешно считанных лексем. Специальными действиями в правилах, обрабатывающих ошибочные ситуации можно более активно вмешиваться в этот процесс. yyerrok() - сбрасывает флаг ошибки yyclearin() - удаляет просмотренную вперед ошибочную лексему Макро YYERROR явным образом возбуждает ошибочную ситуацию. Пример: statement : .... | error ';' при возникновении ошибки внутри statement продолжение разбора возможно только начиная с ';' - в результате будут пропущены все лексемы до точки с запятой, которая затем будет свернута в нетерминал statement. Разное Запустить YACC в ОS UNIX можно командой: yacc [-v] [-d] имя_файла. Результат работы (текст на Си) записывается в файл y.tab.c Ключи: v - создать текстовый файл y.output с описанием состояний и конфликтов построенного анализатора d - создать файл y.tab.h с определениями лексем. В версиях YACC'а для других систем имена файлов и ключей могут быть другими, например: -i -d, имя_входного_файла.(i,c,h) в RSX11M и RT11 y.out, ytab.c ytab.h в системах с файловой системой MS-DOS Фрагмент файла y.output: state 3 stat : expr_ (4) expr : expr_+ expr + shift 11 . reduce 4 Описано состояние (state) 3, соответствующее двум основным си¦ туациям. В этом состоянии символ '+' вызывает сдвиг (shift) и переход в состояние 11, а любой другой символ - свертку (reduce) по правилу 4 - stat : expr. Пример простейшего интерпретатора формул %token ICONST %left '+' '-' %left '*' '/' %% p : /* empty */ | p s ; s : e '\n' { printf( "%d\n", $1 ); } | error '\n' ; e : e '+' e { $$ = $1 + $3; } | e '-' e { $$ = $1 - $3; } | e '*' e { $$ = $1 * $3; } | e '/' e { $$ = $1 / $3; } | '(' e ')'{ $$ = $2; } | ICONST; ; %% #include main() { yyparse(); } yyerror( mes ) char *mes; { printf( "%s\n", mes ); } yylex() { int c, d; while((c=getchar())==' '); /* Skip spaces */ if( c>='0' && c<='9' ) { /* Integer constant */ for( d=c-'0'; (c=getchar()) >='0' && c<='9'; ) d=d*10+c-'0'; ungetc( c, stdin ); yylval = d; return ICONST; } return c; /* Others */ } - конец материала к лекции 7 -