Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

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

Пример 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,$].

S


A


y u v a...

z w
Магазин Непрочитанная часть
входной цепочки

Рис. 3.18

Центральная идея 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 и ситуация [A->uB.v,a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax=>*bw и тогда b равно a. Т.е. b принадлежит FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает функция closure.

S S


y A ax y A ax


u B v u B v

z bw zB
.q
Рис. 3.13

Aлгоритм построения множеств LR(1)-ситуаций приведен ниже.

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

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

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

В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va).

Если I - множество ситуаций, допустимых для некоторого активного префикса z, то goto(I,X) - множество ситуаций, допустимых для активного префикса zX.

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

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

void items(Grammar G')
{ do
{C={closure({[S'->.S,$]})};
for (каждого множества ситуаций I из C,
каждого символа грамматики X такого,
что goto(I,X) не пусто и не принадлежит C
)
добавить goto(I,X) к C;
}
while (к C можно добавить множество ситуаций);
}

Пример 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.

В каждый момент анализа в магазине находится активный префикс, который соответствует последовательности переходов из начального состояния (I₀) в текущее. Свертка - это замена суффикса префикса и переход в новое состояние, которое определяется из таблицы goto по символу левой части свернутого правила и предыдущему символу магазина, который соответствует состоянию после разбора префикса. Для определения этого нового состояния на верхушке хранится состояние, соответствующее активному префиксу без этого суффикса. Новое состояние определяется как goto[предыдущее состояние, новый нетерминал].

Рассмотрим теперь, как по множеству LR(1)-ситуаций строятся функции действия и переходов LR(1)-анализатора. Функции действия и переходов представляются таблицей.

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.

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

Глава 4. Элементы теории перевода

4.1. Преобразователи с магазинной памятью

Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P=<Q,T,Г,П,Ф,q₀,Z₀,F>, где Q - множество состояний, T - конечный входной алфавит, Г - конечный алфавит магазинных символов, П - конечный выходной алфавит, Ф - отображение множества Qx(T U {e})xГ в множество конечных подмножеств множества QxГ*xП*, q₀<-Q - начальное состояние, Z₀<-Г - начальный символ магазина, F<=Q - множество заключительных состояний.

Определим конфигурацию преобразователя P как четверку <q,x,u,y>, где q<-Q - состояние, x<-T* - цепочка на входной ленте, u<-Г* - содержимое магазина, y<-П* - цепочка на выходной ленте, выданная вплоть до настоящего момента. Если Ф(q,a,Z) содержит (r,u,z), то будем писать <q,ax,Zw,y>|-<r,x,uw,yz> для любых x<-A*, w<-Г* и y<-П*. Рефлексивное и транзитивное замыкание отношения |- будем обозначать |-*.

Характеристики

Список файлов лекций