LR17 (Материалы к контрольным работам), страница 3

E +
I₀ I₁ I₄
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->*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

I₇ I₃ I₅
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,*

F
id id



I₈ I₆
T -> T*F.,$ F -> id.,+
T -> T*F.,+ F -> id.,*
T -> T*F.,* F -> id.,$

Рис. 3.19

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

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

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

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

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

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

Шаг 3. Переходы для состояния i определяются следующим образом: если goto(I_i,A)=I_j, то 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.

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

67