Delphi World - Основы компиляции - Лекция 7
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Основы компиляции - Лекция 7

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

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

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования