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 <intval> ICONST
        %token <intval> LCONST
        %type  <ptrval> 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 <stdio.h>
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 */
}