Автор: В.А.Серебряков

3.2.8. Диаграммы переходов для рекурсивного спуска

Как правило, непосредственное программирование рекурсивного спуска из грамматики приводит к большому числу процедур. Число этих процедур можно уменьшить, заменив в некоторых правилах рекурсию циклом. Для этого можно воспользоваться диаграммой переходов грамматики, которая строится следующим образом. Пусть имеется LL(1)-грамматика. Тогда для каждого нетерминала построение диаграммы включает следующие шаги.

Шаг 1. Вводим начальное и заключительное состояния.

Шаг 2. Для каждого правила вывода A->X1X2...Xn строим путь из начального в конечное состояние с дугами, помеченными X1,...,Xn. Если анализатор, построенный по диаграмме переходов, оказывается в состоянии s и дуга, помеченная терминалом a, ведет в состояние t, то если очередной входной символ равен a, анализатор продвигает вход на одну позицию вправо и переходит в состояние t. Если же дуга помечена нетерминалом A, анализатор входит в начальное состояние для A без продвижения входа. После того как он достигает заключительного состояния для A, он переходит в состояние t, что означает "чтение" A из входа при переходе из состояния s в состояние t. Наконец, если есть дуга из s в t, помеченная e, то анализатор переходит из s в t, не читая входа. Если следовать программе рекурсивного спуска, то переход по e должен всегда выбираться в качестве последней альтернативы. Диаграммы переходов могут быть упрощены подстановкой одной в другую. Рассмотрим, например, диаграммы для арифметических выражений на рис. 3.10.

  +---+ T +---+ E'+-----+   +---+ + +---+ T +---+ E'+-----+
E:| 0 |-->| 1 |-->|| 2 ||E':| 3 |-->| 4 |-->| 5 |-->|| 6 ||
  +---+   +---+   +-----+   +---+   +---+   +---+   +-----+
                              |                        ^
                              |           e            |
                              +------------------------+

  +---+ T +---+ E'+-----+   +----+ + +----+ T +----+ E'+----+
E:| 7 |-->| 8 |-->|| 9 ||E':| 10 |-->| 11 |-->| 12 |-->||13||
  +---+   +---+   +-----+   +----+   +----+   +----+   +----+
                              |                           ^
                              |           e               |
                              +---------------------------+

                             51
     +----+  (  +----+  E  +----+  )  +------+
 F:  | 14 |---->| 15 |---->| 16 |---->|| 17 ||
     +----+     +----+     +----+     +------+
       |                                 ^
       |              id                 |
       +---------------------------------+
                        Рис. 3.10

                   e
       +---------------------+            +---------+
       |                     |            |    T    |
       v                     |            v         |
     +---+   +  +---+  T  +-----+       +---+ +   +---+
 E': | 3 |----->| 4 |---->|| 5 || => E':| 3 |---->| 4 |
     +---+      +---+     +-----+       +---+     +---+
       |e                                 |e
       |         +-----+                  |      +-----+
       +-------->|| 6 ||                  +----->|| 6 ||
                 +-----+                         +-----+

              +-------+          +---------+
              |  T    |          |    +    |
              v       |          v         |   e
   +---+ T +---+ + +---+       +---+ T   +---+   +-----+
E: | 0 |-->| 3 |-->| 4 | => E: | 0 |---->| 3 |-->|| 6 ||
   +---+   +---+   +---+       +---+     +---+   +-----+
             |  e +-----+
             +--->|| 6 ||
                  +-----+
                           Рис. 3.11

     +---------+                     +---------+
     |   +     |                     |   *     |
     v         |    e                v         |   e
   +---+ T   +---+     +-----+     +---+ F   +---+    +------+
E: | 0 |---->| 3 |---->|| 6 || T:  | 7 |---->| 8 |--->|| 13 ||
   +---+     +---+     +-----+     +---+     +---+    +------+

     +----+  (  +----+  E  +----+  )  +------+
 F:  | 14 |---->| 15 |---->| 16 |---->|| 17 ||
     +----+     +----+     +----+     +------+
       |                                 ^
       |              e                  |
       +---------------------------------+
                        Рис. 3.12

На рис 3.11 приведена эквивалентная диаграмма переходов для E'. Можно подставить диаграмму для E' рис.3.11 в диаграмму для E рис. 3.10. Получится диаграмма рис. 3.11 для E. Наконец, видно, что в этой диаграмме нулевая и четвертая вершины эквивалентны и их можно слить. Так же можно поступить с диаграммами для T и T'. В результате получится набор диаграмм рис. 3.12.

Такое преобразование эквивалентно описанию грамматики расширенными формулами Бэкуса-Наура, в которых помимо собственно рекурсивных определений допускаются описания повторений. При программировании рекурсивного спуска такая диаграмма для E записывается очевидным образом:

procedure E; repeat T; until InSym<>PLUS;

3.2.9. Восстановление после синтаксических ошибок

В приведенных программах рекурсивного спуска использовалась процедура реакции на синтаксические ошибки error(). В простейшем случае эта процедура выдает диагностику и завершает работу анализатора. Но можно попытаться некоторым разумным образом продолжить работу. Для разбора сверху вниз можно предложить следующий простой алгоритм.

Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ N и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из FIRST(N), либо из FOLLOW(N). В первом случае разворачиваем N по соответствующему правилу, во втором - удаляем N из магазина.

Если на верхушке магазина терминальный символ, то можно выкинуть все терминальные символы с верхушки магазина вплоть до первого (сверху) нетерминального символа и продолжать так, как это было описано выше.

3.3. Разбор снизу-вверх типа сдвиг-свертка

3.3.1. Основа

В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной строки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как "свертку" строки w к начальному символу грамматики. На каждом шаге свертки подстрока, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подстрока, то в обратном порядке прослеживается правосторонний вывод (рис. 3.13).

         S              S                     S
                                            / | \
                                           X1 X2...
                                          /   |
                                        .............
                                        /     |
                     Y                 Y      |
                    /|\               /|\     Z
                  / ...              / ...   /|\
   a.........$   a...........$      a........b.......$

        а)                б)                  в)

                         Рис. 3.13

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, как показано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F->id, то получим строку F+b*c. Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c
   ---    ---      -    -      -    -      -      -

          E -> E + T       а+b*c             E
          E -> T           F+b*c            /+\
          T -> T*F         T+b*c           E   T
          T -> F           E+b*c           |   |\
          F -> id          E+F*c           T   T F
                           E+T*c           |   |  \
                           E+T*F           F   F   id
                           E+T             |   |    c
                           E               a   b

             а)               б)                в)

                       Рис. 3.14

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы подчеркнуты. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A->v, не обязательно является основой, поскольку свертка по правилу A->v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c, которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z - это правило вывода A->v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S=>*uAw=>uvw, то A->v в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w - слово в рассматриваемой грамматике, то w=Zn, n-я правая сентенциальная форма еще неизвестного правого вывода

S = Z0 => Z1 => Z2 => ... => Zn-1 => Zn =w.

Чтобы восстановить этот вывод в обратном порядке, выделяем основу Vn в Zn и заменяем Vn на левую часть некоторого правила вывода An -> Vn, получая (n-1)-ю правую сентенциальную форму Zn-1. Затем повторяем этот процесс, т.е. выделяем основу Vn-1 в Zn-1 и сворачиваем эту основу, получая правую сентенциальную форму Zn-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки. Таким образом, главная задача анализатора типа сдвиг-свертка - это выделение и отсечение основы.

3.3.2. LR(k)-анализаторы

В названии LR(k) символ L означает, что разбор осуществляется слева-направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на которые заглядывает вперед анализатор при разборе. Когда k опущено, имеют в виду 1.

LR-анализ привлекателен по нескольким причинам:

- LR-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка; - LR-анализ может быть реализован довольно эффективно; - практически LR-анализаторы могут быть построены для всех конструкций языков программирования; - класс грамматик, которые могут быть проанализированы LR- методом, строго включает класс грамматик, которые могут быть анализированы предсказывающими анализаторами (сверху вниз типа LL).

                    +------------------------------+
               Вход | A1 | ... | Ai | ... | An | $ |
                    +------------------------------+
                                 ^
                                 |
            +------+          +-------------+ Выход
    Магазин |  Sm  |<---------|     LR      |-------->
            |------|          |  анализатор |
            |  Xm  |          +-------------+
            |------|                 |
            | Sm-1 |                 |
            |------|            +--------+
            | Xm-1 |            |        |
            |------|            v        v
            | .... |        +---------------+
            |------|        | action | goto |
            |  S0  |        +---------------+
            +------+
                            Рис. 3.15

Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА - это состояние, помещенное на верхушку магазина LR-анализатора в начале работы. Конфигурация-LR анализатора - это пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход:

(S0 X1 S1 X2 S2 ... Xm Sm, Ai Ai+1 ... An $)

Эта конфигурация соответствует правой сентенциальной форме

X1 X2 ... Xm Ai Ai+1 ... An

Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы. Очередной шаг анализатора определяется текущим входным символом Ai и символом состояния на верхушке магазина Sm. Элемент таблицы действий action[Sm,Ai] для состояния Sm и входа Ai, может иметь одно их четырех значений:

  1) shift S, сдвиг, где S - состояние,
  2) reduce A->w, свертка по правилу грамматики A -> w,
  3) accept, допуск,
  4) error, ошибка.

Конфигурации, получающиеся после каждого из четырех типов шагов, следующие

  1. Если  action[Sm,Ai]=shift S,  то анализатор выполняет шаг
сдвига, переходя в конфигурацию

(S0 X1 S1 X2 S2 ... Xm Sm Ai S, Ai+1 ... An $)

В магазин  помещаются как  входной символ  Ai, так и следующее
состояние  S,   определяемое  action[Sm,Ai].  Текущим  входным
символом становится Ai+1.

  2. Если  action[Sm,Ai]=reduce A->w,  то анализатор выполняет
свертку, переходя в конфигурацию

(S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, Ai Ai+1 ... An $)

где S=goto[Sm-r,A] и r - длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, - это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Sm-r. Затем анализатор помещает в магазин как A - левую часть правила вывода, так и S - содержимое таблицы goto[Sm-r,A]. На шаге свертки текущий входной символ не меняется. Для LR- анализаторов Xm-r+1 ... Xm - последовательность символов грамматики, удаляемых из магазина, всегда соответствует w - правой части правила вывода, по которому делается свертка. После осуществления шага свертки генерируется выход LR- анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например печатаются номера правил, по которым делается свертка.

3. Если action[Sm,Ai]=accept, то разбор завершен.

4. Если action[Sm,Ai]=error, анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению.

Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведут себя одинаково. Разница между ними заключается в различном содержании таблиц действий и переходов.

Алгоритм 3.7. Алгоритм LR-анализа.

loop Пусть S - состояние на верхушке магазина;
     if action[S,InSym]=shift S'
     then поместить InSym и затем S'
          на верхушку магазина;
          прочитать в InSym следующий
          входной символ

     else if action[S,InSym]=reduce N->w
          then удалить из магазина
               2*|w| символов;
               пусть теперь на верхушке магазина
               состояние S';
               поместить на верхушку магазина N, а
               затем состояние goto[S',InSym];
               вывести правило N->w
          else if action[S,InSym]=accept
               then return
               else error()
end  end  end  end;

Вначале в магазине помещено начальное состояние S0, а в буфере w$, InSym содержит первый символ w$; Анализатор выполняет приведенную ниже программу до тех пор, пока будет достигнуто либо состояние accept, либо состояние error.

          +--------------------------------------+
          |Состо-|     action       |  goto      |
          | яния |------------------+------------|
          |      |  id   +  *   $   |  E  T   F  |
          |------+------------------+------------|
          |  0   |  S6              |  1  2  3   |
          |  1   |      S4     acc  |            |
          |  2   |      R2  S7  R2  |            |
          |  3   |      R4  R4  R4  |            |
          |  4   |  S6              |     5  3   |
          |  5   |      R1  S7  R1  |            |
          |  6   |      R5  R5  R5  |            |
          |  7   |  S6              |        8   |
          |  8   |      R3  R3  R3  |            |
          +--------------------------------------+

                        Рис. 3.16

Пример 3.6. На рис. 3.16 изображены функции action и goto LR- таблиц для грамматики арифметических выражений с бинарными операциями + и * примера 3.5. Здесь Si означает сдвиг и помещение в магазин состояния i, Rj - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку. Значение goto[S,A] для терминала A ищется в поле действия, связанном с действием сдвига по входу A в состоянии S. Поле перехода дает goto[S,A] для нетерминалов A. На входе id+id*id последовательность состояний магазина и входа показаны на рис. 3.17. Например, в первой строке LR- анализатор находится в нулевом состоянии и читает первый входной символ id. Действие S6 в нулевой строке и столбце id в поле action рис. 3.17 означает сдвиг и помещение S6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния S6 помещаются в магазин и id удаляется из входной строки.

Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F->id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Теперь анализируется нулевое состояние Поскольку goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично.

+---------------------------------------------------------+
|Активный|     Магазин           |    Вход      | Действие|
|префикс |                       |              |         |
|--------+-----------------------+--------------+---------|
|        |0                      |id + id * id $| сдвиг   |
| id     |0 id 6                 |   + id * id $| F -> id |
| F      |0 F 3                  |   + id * id $| T -> F  |
| T      |0 T 2                  |   + id * id $| E -> T  |
| E      |0 E 1                  |   + id * id $| сдвиг   |
| E+     |0 E 1 + 4              |     id * id $| сдвиг   |
| E+id   |0 E 1 + 4 id 6         |        * id $| F -> id |
| E+F    |0 E 1 + 4 F 3          |        * id $| T -> F  |
| E+T    |0 E 1 + 4 T 5          |          id $| сдвиг   |
| E+T*   |0 E 1 + 4 T 5 * 7      |          id $| сдвиг   |
| E+T*id |0 E 1 + 4 T 5 * 7 id 6 |             $| F -> id |
| E+T*F  |0 E 1 + 4 T 5 * 7 F 8  |             $| T -> T*F|
| E+T    |0 E 1 + 4 T 5          |             $| E -> E+T|
| E      |0 E 1                  |              | допуск  |
+---------------------------------------------------------+

                         Рис. 3.17

3.3.3. LR-грамматики

Грамматики, для которых можно построить таблицу LR-разбора, называются LR-грамматиками. Есть КС-грамматики, не являющиеся LR-грамматиками, однако практически для описания языков программирования достаточно класса LR. Чтобы грамматика была LR, анализатор, работающий слева- направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке магазина. Но если возможно распознать основу, зная только символы грамматики в магазине, то существует конечный автомат, который может, читая символы грамматики в магазине, начиная с верхушки, определить эту основу. Функцией переходов этого конечного автомата является таблица переходов LR-анализатора. Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке.

Для принятия решения о сдвиге или свертке анализатор просматривает очередные k входных символов. Практический интерес представляют случаи k=0 и k=1. Например, в таблице действий рис. 3.16 используется один символ. Грамматика, которая может быть проанализирована LR анализатором, заглядывая на k входных символов на каждом шаге, называется LR(k)-грамматикой.

Можно дать другое определение LR(k)-грамматики. Пополненной грамматикой для данной грамматики G называется КС-грамматика, в которой введена новая аксиома S' и правило вывода S'->S. Это дополнительное правило вводится для того, чтобы определить, когда анализатор должет остановить разбор и зафиксировать допуск входа. Таким образом допуск имеет место тогда и только тогда, когда анализатор осуществляет свертку по правилу S'->S. Пополненная грамматика называется LR(k) для k>=0, если из условий

 (1) S' =>* uAw => uvw,
 (2) S' =>* zBx => uvy,
 (3) FIRST(w)=FIRST(y)

LR(1) ситуацией называется пара [A->u.v,a], где A->uv - правило грамматики, а a - терминал или правый концевой маркер $. "1" указывает на длину второй компоненты ситуации, которая называется аванцепочкой ситуации. Аванцепочка не играет роли в ситуациях вида [A->u.v,a], где v не равно e, но ситуация вида [A->u.,a] ведет к свертке по правилу A->u только если следующим входным символом является a. Таким образом свертка по правилу A->u требуется только для тех входных символов a, для которых [A->u.,a] является LR(1) ситуацией в состоянии на верхушке магазина. Будем говорить, что LR(1)-ситуация [A->u.v,a] допустима для активного префикса z, если существует вывод S=>*yAw=>yuvw, где. z=yu и либо a - первый символ w, либо w равно e и a равно $ (рис. 3.18).

                      S
                     /|\
                    / | \
                   /  A  \
                  /  /\   \
                 /  /  \   \
                y  u    v   a...
                 ----     ----
                   z       w

                  Рис. 3.18

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример 3.7. Рассмотрим грамматику

 S -> BB
 B -> aB | b

Существует правосторонний вывод S=>*aaBab=>aaaBab. Ситуация [B->a.B,a] допустима для активного префикса z=aaa, если в определении выше положить y=aa, A=B, w=ab, u=a, v=B. Существует также правосторонний вывод S*=>BaB=>BaaB. Из этого вывода видно, что для активного префикса Baa допустима ситуация [B->a.B,$]. Центральная идея LR-метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активные префиксы. Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающие активные префиксы, а их группирование на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного.

Для конструирования набора множеств допустимых LR(1)- ситуаций будут применяться пополненная грамматика G' и процедуры-функции closure и goto. Рассмотрим ситуацию вида [A->u.Bv,a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S=>*yAax=>yuBvax, где z=yu. Предположим, что из vax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B->q имеется вывод S=>*zBbw=>zqbw. Таким образом [B->.q,b] допустима для z. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax=>*bw и тогда b равно a. Т.е. b принадлежит FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает процедура closure. Aлгоритм построения множеств LR(1)-ситуаций приведен ниже.

Алгоритм 3.8. Конструирование множеств LR(1)-ситуаций.

Алгоритм заключается в выполнении главной программы items, которая вызывает процедуры closure и goto.

function closure(I);/*I - множество ситуаций*/
 begin repeat для каждой ситуации [A->u.Bv,a] из I,
              каждого правила вывода B->w из G' и каждого
              терминала b из FIRST(va), такого, что [B->.w,b]
              нет в I
          do добавить [B->.w,b] к I;
      until к I нельзя добавить новых ситуаций;
      return I;
 end;

В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va). Если I - множество ситуаций, допустимых для некоторого активного префикса z, то goto(I,X) - множество ситуаций, допустимых для активного префикса zX.

function goto(I,X);/*I - множество ситуаций;
                     X - символ грамматики*/
 begin Пусть [A->u.Xv,a] принадлежит I;
      Рассмотрим J - множество ситуаций [A-uX.v,a];
      return closure(J)
 end;

Работа алгоритма построения множества LR(1)-ситуаций начинается с того, что берется C - множество ситуаций {closure({[S'->.S,$]})}. Затем из имеющегося множества с помощью операции goto() строятся новые множества ситуаций. По- существу, goto(I,X) - переход конечного автомата из состояния I по символу X.

procedure items(G'); begin C:={closure({[S'->.S,$]})};
      repeat для каждого множества ситуаций I из C
                 и каждого символа грамматики X
                 такого, что goto(I,X) не пусто
                 и не принадлежит C
             do добавить goto(I,X) к C
      until к C нельзя больше добавить множеств ситуаций end;

Пример 3.8. Рассмотрим пополненную грамматику примера 3.5.

    E'-> E
 1) E -> E + T
 2) E -> T
 3) T -> T * F
 4) T -> F
 5) F -> id

Множество ситуаций и переходов для этой грамматики приведены на рис. 3.19. В каждый момент анализа в магазине находится активный префикс, который соответствует последовательности переходов из начального состояния (I0) в текущее. Свертка - это замена суффикса префикса и переход в новое состояние, т.е. как бы возврат по части пути, соответствующей основе, и замена этой части переходом, соответствующим левой части. Рассмотрим теперь, как по множеству LR(1)-ситуаций строятся функции действия и переходов LR(1)-анализатора. Функции действия и переходов представляются таблицей.

+-------------+ E  +-------------+ +  +-------------+
| I0          |--->| I1          |--->| I4          |
| E'-> .E,  $ |    | E'-> E.,  $ |    | E -> E+.T,$ |
| E -> .E+T,$ |    | E -> E.+T,$ |    | E -> E+.T,+ |
| E -> .T,  $ |    | E -> E.+T,+ |    | T -> .T*F,$ |
| T -> .T*F,$ |    +-------------+    | T -> .F,  $ |
| T -> .F,  $ | T  +-------------+    | T -> .T*F,+ |
| F -> .id, $ |--->| I2          |    | T -> .F,  + |
| E -> .E+T,+ |    | E -> T.,  $ |    | F -> .id, $ |
| E -> .T,  + |    | T -> T.*F,$ |    | F -> .id, + |
| T -> .T*F,+ |    | E -> T.,  + |    | T -> .T*F,* |
| T -> .F,  + |    | T -> T.*F,+ |    | T -> .F,  * |
| T -> .T*F,* |    | T -> T.*F,* |    | F -> .id, * |
| T -> .F,  * |    +-------------+    +-------------+
| F -> .id, * |       |                  F|   |  |
| F -> .id, + |-------+---+ +-------------+   |  |
+-------------+       | F | |               T |  | id
  |     +-------------+   | |                 |  +------+
+-+     | *               | |                 |         |
|       v                 v v                 v         |
| +-------------+    +-----------+      +-------------+ |
| | I7          |    | I3        |      | I5          | |
| | T -> T*.F,$ |    | T -> F.,$ |      | E -> E+T.,$ | |
| | T -> T*.F,+ |    | T -> F.,+ |      | E -> E+T.,+ | |
| | T -> T*.F,* |    | T -> F.,* |      | T -> T.*F,$ | |
| | F -> .id, $ |    +-----------+   *  | T -> T.*F,+ | |
| | F -> .id, + |<----------------------| T -> T.*F,* | |
| | F -> .id,*  |   id                  +-------------+ |
| +-------------+                                  +----+
|      | F |       id                              |
| id   |   +---------------------------------+     |
+------+----------------------------------+  |     |
       |                                  |  |     |
       v                                  v  v     v
 +-------------+ F                      +------------+
 | I8          |                        | I6         |
 | T -> T*F.,$ |                        | F -> id.,+ |
 | T -> T*F.,+ |                        | F -> id.,* |
 | T -> T*F.,* |                        | F -> id.,$ |
 +-------------+                        +------------+
                     Рис. 3.19

Алгоритм 3.9. Построение канонических таблиц LR анализатора.

Шаг1. Строим набор множеств LR(1)- ситуаций C={I0,I1,...,In} для G'.

Шаг 2. Состояние i анализатора строится из Ii. Действия анализатора для состояния i определяются следующим образом:

а) если [A->u.av,b] принадлежит Ii и goto(Ii,a)=Ij, то полагаем action[i,a]="shift j". Здесь a - терминал;

б) если [A->u.,a] принадлежит Ii, A#S', то полагаем action[i,a]="reduce A->u";

в) если [S'->S.,$] принадлежит Ii, полагаем action[i,$]="accept".

Шаг 3. Переходы для состояния i определяются следующим образом: если goto(Ii,A)=Ij, то goto[i,A]=j (здесь A - нетерминал).

Шаг 4. Все входы, не определенные шагами 2 и 3, полагаем равными "error".

Шаг 5. Начальное состояние анализатора строится из множества, содержащего ситуацию [S'->.S,$]. Если при применении этих правил возникает конфликт, т.е. в одном и том же множестве может быть более одного варианта действий (либо сдвиг/свертка, либо свертка/свертка), говорят, что грамматика не является LR(1), и алгоритм завершается неуспешно.

Таблица, получающаяся из функций анализатора action и goto в результате работы Алгоритма 3.10, называется канонической таблицей LR(1)-анализатора. LR-анализатор, работающий по этой таблице, называется каноническим LR-анализатором. Если функция анализатора action не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.

3.3.4. Конфликты разбора типа сдвиг-свертка

Если грамматика не является LR(1), то анализатор типа сдвиг- свертка для нее может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка). В частности, неоднозначная грамматика не может быть LR.

Пример 3.9. Рассмотрим вновь следующую грамматику оператора

if-then-else:

 St -> if Ex then St
       | if Ex then St else St
       | ...

Если анализатор типа сдвиг-свертка находится в конфигурации

              Магазин                   Вход
              ... if Ex then St       else ... $

то нельзя определить, является ли if Ex then St основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по St -> if Ex then St или сдвиг else, а затем разбор другого St и завершение альтернативы if Ex then St else St. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не LR(1). Эта грамматика может быть преобразована к LR(1)-виду следующим образом:

St -> CondSt | UnCondSt
CondSt -> IfThenSt | IfThenElseSt
FullSt -> IfThenElseSt | UnCondSt
IfThenElseSt -> if Ex then FullSt else St
IfThenSt ->if Ex then St

3.3.5. Восстановление после синтаксических ошибок

Одним из простейших методов является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходом на выделенный нетерминал A. Затем сканируются входные символы, пока не будет найден такой, который допустим после A. В этом случае на верхушку магазина помещается состояние goto[s,A] и разбор продолжается. Для нетерминала A может иметься несколько таких вариантов. Обычно A - это нетерминал, представляющий одну из основных конструкций языка, например оператор. Тогда s - это, например, точка с запятой или end.

При более детальной проработке реакции на ошибки можно в каждой пустой клетке анализатора поставить обращение к своей подпрограмме. Такая подпрограмма может вставлять или удалять входные символы или символы магазина, менять порядок входных символов.