Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 10
Текст из файла (страница 10)
Тогда существуетправосторонний вывод 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.SyuSAaxBvyu59AaxBvzbwzB.qРис. 3.13Aлгоритм построения множеств 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.60void 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.1)2)3)4)5)E'->E ->E ->T ->T ->F ->EE + TTT * FFidМножество ситуаций и переходов для этой грамматики приведены на рис.3.19.В каждый момент анализа в магазине находится активный префикс,который соответствует последовательности переходов из начальногосостояния (I0) в текущее. Свертка - это замена суффикса префикса ипереход в новое состояние, которое определяется из таблицы goto посимволу левой части свернутого правила и предыдущему символумагазина, который соответствует состоянию после разбора префикса.
Дляопределения этого нового состояния на верхушке хранится состояние,соответствующее активному префиксу без этого суффикса. Новоесостояние определяется как goto[предыдущее состояние, новыйнетерминал].Рассмотрим теперь, как по множеству LR(1)-ситуаций строятсяфункции действия и переходов LR(1)-анализатора. Функции действия ипереходов представляются таблицей.61EI0E'-> .E, $E -> .E+T,$E -> .T, $T -> .T*F,$T -> .F, $ TF-> .id, $E -> .E+T,+E -> .T, +T -> .T*F,+T -> .F, +T -> .T*F,*T -> .F, *F -> .id, *F -> .id,I1E'-> E., $E -> E.+T,$E -> E.+T,+ETETTI2-> T., $-> T.*F,$-> T., +-> T.*F,+-> T.*F,*idI4E -> E+.T,$E -> E+.T,+T -> .T*F,$T -> .F, $T->*F,+T -> .F, +F -> .id, $F -> .id, +T -> .T*F,*T -> .F, *F -> .id, *F*I7T ->T ->T ->F ->F ->F ->+FI3T -> F.,$T -> F.,+T -> F.,*T*.F,$T*.F,+T*.F,*.id, $.id, +.id,*FI8T -> T*F.,$T -> T*F.,+T -> T*F.,*TidI5*E -> E+T.,$E -> E+T.,+T -> T.*F,$T -> T.*F,+T -> T.*F,*idI6F -> id.,+F -> id.,*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 - нетерминал).62Шаг 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).63Эта грамматика может быть преобразована к LR(1)-виду следующимобразом:St -> CondSt | UnCondStCondSt -> IfThenSt | IfThenElseStFullSt -> IfThenElseSt | UnCondStIfThenElseSt -> if Ex then FullSt else StIfThenSt ->if Ex then St3.3.5.
Восстановление после синтаксических ошибокОдним из простейших методов является следующий. При синтаксическойошибке просматриваем магазин от верхушки, пока не найдем состояние s спереходом на выделенный нетерминал A. Затем сканируются входныесимволы, пока не будет найден такой, который допустим после A.
В этомслучае на верхушку магазина помещается состояние goto[s,A] и разборпродолжается. Для нетерминала A может иметься несколько такихвариантов. Обычно A - это нетерминал, представляющий одну изосновных конструкций языка, например оператор.
Тогда s - это, например,точка с запятой или end.При более детальной проработке реакции на ошибки можно вкаждой пустой клетке анализатора поставить обращение к своейподпрограмме. Такая подпрограмма может вставлять или удалять входныесимволы или символы магазина, менять порядок входных символов.64Глава 4. Элементы теории перевода4.1. Преобразователи с магазинной памятьюПреобразователем с магазинной памятью (МП-преобразователем)называется восьмерка P=<Q,T,Г,П,Ф,q0,Z0,F>, где Q - множествосостояний, T - конечный входной алфавит, Г - конечный алфавитмагазинных символов, П - конечный выходной алфавит, Ф - отображениемножества Qx(T U {e})xГ в множество конечных подмножеств множестваQxГ*xП*, q0<-Q - начальное состояние, Z0<-Г - начальный символмагазина, 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<-П*.Рефлексивное и транзитивное замыкание отношения |- будем обозначать |*.Цепочку y назовем выходом для x, если <q0,x,Z0,e>|-*<q,e,u,y> длянекоторых q<-F и u<-Г*. Переводом (или преобразованием),определяемым МП-преобразователем P (обозначается t(P)), назовеммножество {(x,y)|<q0,x,Z0,e>|-*<q,e,u,y> для некоторых q<-F и u<-Г*}.Будем говорить, что МП-преобразователь P=<Q,T,Г,П,Ф,q0,Z0,F>детерминированный(ДМП-преобразователь),есливыполняютсяследующие условия:1) для всех q<-Q, a<-T U {e} и Z<-Г множество Ф(q,a,Z) содержит неболее одного элемента,2) если Ф(q,e,Z)#{}, то Ф(q,a,Z)={} для всех a<-T.Пример 4.1. Перевод арифметического выражения в ПОЛИЗ.ПОЛИЗ - Польская инверсная запись или, что то же, постфикснаязапись арифметических выражений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
