Автор: А.Г.Дымченко

Материал к лекции 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 > - значение 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 -