Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 6
Текст из файла (страница 6)
d:Qx(T U {e})xГ ->{QxГ*};(5) q0<-Q - начальное состояние управляющего устройства;(6) Z0<-Г - символ, находящийся в магазине в начальный момент(начальный символ);(7) F<=Q - множество заключительных состоянийКонфигурацией МП-автомата называется тройка <q,w,u> <- QxT*xГ*, где(1) q - текущее состояние управляющего устройства;(2) w - неиспользованная часть входной цепочки; первый символцепочки w находится под входной головкой; если w e, то считается,что вся входная лента прочитана;(3) u - содержимое магазина; самый левый символ цепочки u считаетсяверхним символом магазина; если u=e, то магазин считаетсяпустым.Такт работы МП-автомата P будем представлять в виде бинарногоотношения |-, определенного на конфигурациях.
Будем писать(q,aw,Zu)|-(q',w,vu)если множество d(q,a,Z) содержит (q',v), где q, q'<-Q, a<-T U {e}, w<-T*,Z<-Г, u,v<-Г*.Начальной конфигурацией МП-автомата P называется конфигурациявида <q0,w,Z0>, где w<-T*, т.е. управляющее устройство находится вначальном состоянии, входная лента содержит цепочку, которую нужнораспознать, а в магазине есть только начальный символ Z0.Заключительная конфигурация - это конфигурация вида <q,e,u>, где q<-F,u<-Г*.Говорят, что цепочка w допускается МП-автоматом P, если<q0,w,Z0>|-*<q,e,u> для некоторых q<-F и u<-Г*. Языком, определяемым34(или допускаемым) автоматом P (обозначается L(P)), называют множествоцепочек, допускаемых автоматом P.Иногда допустимость определяют несколько иначе: цепочка wдопускается МП-автоматом P, если <q0,w,Z0>|-*<q,e,e>.
Эти определенияэквивалентны.3.2. Таблично-управляемый предсказывающий разбор3.2.1. Алгоритм разбора сверху-внизОсновная проблема предсказывающего разбора - определениеправила вывода, которое нужно применить к нетерминалу. Процесспредсказывающего разбора (сверху-вниз) с точки зрения построениядерева разбора можно проиллюстрировать рис.
3.1. Фрагментынедостроенного дерева соответствуют сентенциальным формам вывода.Вначале дерево состоит только из одной вершины, соответствующейаксиоме S. В этот момент по первому символу входного потокапредсказывающий анализатор должен определить правило S->X1 X2 ...,которое должно быть применено к S. Затем необходимо определитьправило, которое должно быть применено к X1, и т.д., до тех пор, пока впроцессе такого построения сентенциальной формы, соответствующейлевому выводу, не будет применено правило Y->a .... Этот процесс затемприменяется для следующего самого левого нетерминального символасентенциальной формыSSS/ | \/ | \X1 X2...X1 X2...//|........................//|YY|/|\/|\Z/ .../ .../|\a..........$a...........$a.....................b.......$а)б)в)Рис. 3.1На рис.
3.2 приведена структура предсказывающего анализатора, которыйопределяет очередное правило из таблицы. Такую таблицу множно35построить непосредственно из грамматики.ВходXМагазинa + b $Программа предсказывающего анализатораВыходYZ$Таблица анализатораРис. 3.2Таблично-управляемый предсказывающий анализатор имеет входнойбуфер, таблицу анализа и выход. Входной буфер содержитраспознаваемую строку, за которой следует $ - правый концевой маркер,признак конца строки. Магазин содержит последовательность символовграмматики с $ на дне. Вначале магазин содержит начальный символграмматики на верхушке и $ на дне. Таблица анализа - это двумерныймассив M[A,a], где A - нетерминал, и a - терминал или символ $.Анализатор управляется программой, которая работает следующимобразом. Она рассматривает X - символ на верхушке магазина и a текущий входной символ.
Эти два символа определяют действиеанализатора. Имеются три возможности.1. Если X=a=$, анализатор останавливается и сообщает об успешномокончании разбора.2. Если X=a#$, анализатор удаляет X из магазина и продвигаетуказатель входа на следующий входной символ.3.
Если X - нетерминал, программа заглядывает в таблицу M[X,a]. Поэтому входу хранится либо правило для X, либо ошибка. Если, например,M[X,a]={X->UVW}, анализатор заменяет X на верхушке магазина на WVU{на верхушке U}. Будем считать, что анализатор в качестве выхода простопечатает использованные правила вывода. Если M[X,a]=error, анализаторобращается к подпрограмме анализа ошибок.Поведение анализатора может быть описано в терминахконфигураций автомата разбора.Алгоритм 3.1. Нерекурсивный предсказывающий анализ.do{X=верхний символ магазина;if (X <- T|| X==`$`)36if (X==InSym){удалить X из магазина;InSym=очередной символ;}else error();else /*X - нетерминал*/if (M[X,InSym]==“X->Y1Y2...Yk“){удалить X из магазина;поместить Yk,Yk-1,...Y1 в магазин(Y1 на верхушку);вывести правило X->Y1Y2...Yk;}else error(); /*вход таблицы M пуст*/}while (X!=$) /*магазин пуст*/Рис.
3.3Вначале анализатор находится в конфигурации, в которой магазинсодержит S$, (S - начальный символ грамматики), во входном буфере w$(w - входная цепочка), переменная InSym содержит первый символвходной строки. Программа, использующая таблицу анализатора M дляосуществления разбора, изображена на рис. 3.3.Пример 3.1. Рассмотрим грамматику арифметических выражений:E -> T E'E' -> + T E' | eT -> F T'T' -> * F T' | eF -> ( E ) | idТаблица предсказывающего анализатора для нее изображена на рис. 3.4.Здесь пустые клетки - входы ошибок.
Непустые дают правила, по которымделается развертка нетерминала.НетерминалEE'TT'FВходной символidE->TE'T->FT'F->id+*(E->TE'E'->+TE'T'->eT'->*FT'T->FT'F->(E)Рис. 3.437)$E'->e E'->eT'->e T'->eМагазин Вход$E$E'T$E'T'F$E'T'id$E'T'$E'$E'T+$E'T$E'T'F$E'T'id$E'T'$E'T'F*$E'T'F$E'T'id$E'T'$E'$d+id*id$d+id*id$d+id*id$id+id*id$+id*id$+id*id$+id*id$id*id$id*id$id*id$*id$*id$id$id$$$$ВыходE->TE'T->FT'F->idET'->eE'->+TE`T->FT'F->idTF T'T'->*FT'F->ididE'+FidT'->eE'->eTE'T'* F T'idРис. 3.5Рис.
3.6Навходеid+id*idпредсказывающийанализаторсовершаетпоследовательность шагов, изображенную на рис. 3.5. Указатель входауказывает на самый левый символ в колонке Вход. Если внимательнопроанализировать действия анализатора, то видно, что он осуществляетлевый вывод, т.е. правила применяются в соответствии с левым выводом.За уже просмотренными входными символами следуют символыграмматики в магазине (сверху вниз), что соответствует левымсентенциальным формам вывода.Дерево разбора приведено на рис. 3.6.3.2.2. Множества FIRST и FOLLOW.При построении предсказывающего анализатора полезными оказываютсядве функции, связанные с грамматикой G.
Эти функции, FIRST иFOLLOW, позволяют построить таблицу предсказывающего разбора дляG, если, конечно, это возможно. Множества, даваемые этими функциями,могут, кроме того, быть использованы при восстановлении после ошибок.Если u - любая строка символов грамматики, положим FIRST(u) множество терминалов, с которых начинаются строки, выводимые из u.Если u=>*e, то e также принадлежит FIRST(u).Определим FOLLOW(A) для нетерминала A как множество38терминалов a, которые могут появиться непосредственно справа от A внекоторой сентенциальной форме, т.е.
множество терминалов a таких, чтосуществует вывод вида S=>*uAav для некоторых u и v. Отметим, чтомежду A и a в процессе вывода могут появиться нетерминальные символы,из которых выводится e. Если A может быть самым правым символомнекоторой сентенциальной формы, то $ принадлежит FOLLOW(A).Для построения FIRST(X) для всех символов грамматики Xприменим следующий алгоритм.Алгоритм 3.2. Построение множеств FIRST для символов грамматики.Шаг 1. Если X - терминал, то FIRST(X) - это {X}; если X - нетерминал,полагаем FIRST(X)={}.Шаг 2.
Если имеется правило вывода X->e, то добавить e к FIRST(X).Шаг 3. Пока ни к какому множеству FIRST(X) нельзя уже будетдобавить новые элементы или e:если X - нетерминал и имеется правило вывода X->Y1Y2...Yk, товключить a в FIRST(X), если для некоторого i a<-FIRST(Yi) и eпринадлежит всем FIRST(Y1),...,FIRST(Yi-1), т.е.
Y1...Yi-1=>*e.Если e принадлежит FIRST(Yj) для всех j=1,2,...,k, то добавить e кFIRST(X). Например, все, что принадлежит FIRST(Y1)принадлежит также и FIRST(X). Если из Y1 не выводится e, тоничего больше не добавляем к FIRST(X), но если Y1=>*e, тодобавляем FIRST(Y2), и т.д.Теперь FIRST для любой строки X1X2...Xn можно вычислить следующимобразом.Шаг 1. Полагаем FIRST(X1X2...Xn)={}.Шаг 2.
Добавим к FIRST(X1X2...Xn) все не e символы из FIRST(X1).Добавим также не e символы из FIRST(X2), если e<-FIRST(X1),не eсимволы из FIRST(X3), если e принадлежит как FIRST(X1), так иFIRST(X2), и т.д. Наконец, добавим e к FIRST(X1X2...Xn), если e<FIRST(Xi) для всех i.Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 3.3.Алгоритм 3.3. Построение FOLLOW(X) для всех X - нетерминаловграмматики.Шаг 1. Положить FOLLOW(X)={}.Шаг 2. Поместить $ в FOLLOW(S), где S - начальный символ и $ правый концевой маркер.39Шаг 3.
Если eсть правило вывода A->uBv, то все из FIRST(v), заисключением e, добавить к FOLLOW(B).Шаг 4. Пока ничего нельзя будет добавить ни к какому множествуFOLLOW(X): eсли есть правило вывода A->uB или A->uBv, гдеFIRST(v) содержит e (т.е. v=>*e), то все из FOLLOW(A) добавить кFOLLOW(B).Пример 3.2. Рaссмотрим снова грамматику (*). Для нееFIRST(E) =FIRST(T)=FIRST(F)={(,id}FIRST(E')={+,e}FIRST(T')={*,e}FOLLOW(E)=FOLLOW(E')={),$}FOLLOW(T)=FOLLOW(T')={+,),$}FOLLOW(F)={+,*,),$}Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i=1,поскольку FIRST(id)={id} и FIRST('(')={'('} в соответствии с шагом 1. Нашаге 3 при i=1, в соответствии с правилом вывода T->FT' к FIRST(T)добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.На шаге 1 для вычисления множеств FOLLOW в FOLLOW(E)включаем $.
На шаге 2, используя правило вывода F->(E), к FOLLOW(E)добавляется также правая скобка. На шаге 3, примененном к правилу E>TE', в FOLLOW(E') включаются $ и правая скобка. Поскольку E'=>*e, онитакже попадают в FOLLOW(T). В соответствии с правилом вывода E->TE',на шаге 2 в FOLLOW(T) включается все из FIRST(E'), отличное от e.3.2.3. Конструирование таблиц предсказывающего анализатораДля конструирования таблиц предсказывающего анализатора пограмматике G может быть использован алгоритм, основанный наследующей идее. Предположим, что A->u - правило вывода грамматики иa<-FIRTS(u). Тогда анализатор делает развертку A по u, если входнымсимволом является a. Трудность возникает, когда u=e или u=>*e.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
