Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 7
Текст из файла (страница 7)
В этомслучае нужно развернуть A в u, если текущий входной символпринадлежит FOLLOW(A) или если достигнут $ и $<-FOLLOW(A).Алгоритм 3.4. Построение таблиц предсказывающего анализатора.Для каждого правила вывода A->u грамматики выполнить шаги 1 и 2Шаг 1. Для каждого терминала a из FIRST(u) добавить A->u к M[A,a].40Шаг 2. Если e<-FIRST(u), добавить A->u к M[A,b] для каждоготерминала b из FOLLOW(A). Если e<-FIRST(u) и $<-FOLLOW(A),добавить A->u к M[A,$].Шаг 3. Положить все неопределенные входы равными error.Применим алгоритм 3.4 к грамматике (*). ПосколькуFIRST(TE')=FIRST(T)={(,id}, в соответствии с правилом вывода E->TE'входы M[E,(] и M[E,id] становятся равными E->TE'.В соответствии с правилом вывода E'->+TE' вход M[E',+] равен E'>+TE'.
В соответствии с правилом вывода E'->e входы M[E',)] и M[E',$]равны E'->e, поскольку FOLLOW(E')={),$}.Таблица анализа, построенная алгоритмом 3.4, приведена на рис. 3.4.Пример 3.3.3.2.4. LL(1)-грамматикиАлгоритм 3.4 для построения таблицы анализа M может быть применен клюбой грамматике. Однако для некоторых грамматик M может иметьнеоднозначно определенные входы. Например, если грамматикалеворекурсивна или неоднозначна, M будет иметь по крайней мере одиннеоднозначно определенный вход.Грамматики, для которых таблицы анализа не имеют неоднозначноопределенных входов, называются LL(1).
Первое L означает сканированиевхода слева-направо, второе L означает, что строится левый вывод, 1 - чтона каждом шаге для принятия решения используется один символнепросмотренной цепочки. Можно показать, что алгоритм 3.4 для каждойLL(1)-грамматики G строит таблицы, по которым распознаются всецепочки из L(G) и только они.LL(1)-грамматики имеют несколько отличительных свойств.Неоднозначная или леворекурсивная грамматика не может быть LL(1).Можно также показать, что грамматика G является LL(1) тогда и толькотогда, когда для двух правил вида A->u|v выполняется следующее:1) ни для какого терминала a одновременно из u и v не выводятсястроки, начинающиеся с a;2) только из одной из строк u или v может выводиться пустая строка;3) если v=>*e, то из u не выводится никакая строка, начинающаяся стерминала из FOLLOW(A).Эквивалентным является следующее определение:КС-грамматиканазываетсяLL(1)-грамматикой,еслиизсуществования двух левых выводов(1) S =>* w A u => w v u =>* wx,(2) S =>* w A u => w z u =>* wy,41для которых FIRST(x)=FIRST(y), вытекает, что v=z.
Это означает, что дляданной цепочки wAu и первого символа, выводящегося из Au (или $),существует не более одного правила, которое может быть применено к A,чтобы получить вывод какой-нибудь терминальной цепочки,начинающейся с w и продолжающейся этим первым символом.Язык, для которого можно построить LL(1)-грамматику, называютLL(1)-языком.Если таблица анализа имеет неоднозначно определенные входы, тограмматика не является LL(1). Примером может служить следующаяграмматика:St -> if Ex then St| if Ex then St else St| ContEx -> ...Эта грамматика неоднозначна, что иллюстрируется рис. 3.7.
Посколькуграмматика неоднозначна, она не является LL(1). Проблема, порождает лиграмматика LL-язык, алгоритмически неразрешима.StStStStif E then if E then S else S if E then if E then S else Sа)б)Рис. 3.73.2.5. Удаление левой рекурсииОсновная трудность при использовании предсказывающего анализа - этонаписание такой грамматики для входного языка, чтобы по ней можнобыло построить предсказывающий анализатор. Иногда с помощьюнекоторых простых преобразований не LL(1)-грамматику можно привестик LL(1)-виду. Среди этих преобразований наиболее очевидными являютсялевая факторизация и удаление левой рекурсии.
Здесь необходимо сделатьдва замечания. Во-первых, не всякая грамматика после этихпреобразований становится LL(1) и, во-вторых, после удаления левойрекурсии и левой факторизации получающаяся грамматика может статьтрудно понимаемой.42Грамматика леворекурсивна, если в ней имеется нетерминал Aтакой, что существует вывод A=>+Au для некоторой строки u.Леворекурсивные грамматики не могут анализироваться методами сверхувниз, поэтому необходимо удаление левой рекурсии.Непосредственную левую рекурсию, т.е. рекурсию вида A->Au,можно удалить следующим способом. Сначала группируем A-правила:A -> Au1 | Au2 | ...
| Aum | v1 | v2 | .... | vnгде никакая из строк vi не начинается с A. Затем заменяем A-правила наA -> v1A' | v2A' | .... | vnA'A'-> u1A' | u2A' | .... | umA' | eНетерминал A порождает те же строки, что и раньше, но теперь нетлевой рекурсии. С помощью этой процедуры удаляются всенепосредственные левые рекурсии, но не удаляется левая рекурсия,включающая два или более шагов.
Приведенный ниже алгоритм 3.5позволяет удалить все левые рекурсии из грамматики.Алгоритм 3.5. Удаление левой рекурсии.Шаг 1. Упорядочиваем нетерминалы в произвольномпорядке.Шаг 2. for (i=1;i<=n;i++){for (j=1;j<=i-1;j++){/*По индукции v1,...,vk не имеют ссылок на Ai вначале*/пусть Aj->v1 | v2 | ...
| vk - все текущиеправиладля Aj;заменить все правила вида Ai->Aju направилаAi->v1u | v2u | ... | vku;}удалить непосредственную левую рекурсиюв правилах для Ai;}После (i-1)-й итерации внешнего цикла на шаге 2 для любого правила видаAk->Alu, где k<i, выполняется l>k. В результате на следующей итерации(по i) внутренний цикл (по j) последовательно увеличивает нижнююграницу по m в любом правиле Ai->Amu, пока не будет m>=i. Затем,удаляя непосредственную левую рекурсию для Ai-правил, делаем mбольше i.Алгоритм 3.5 применим, если грамматика не имеет циклов (выводов43вида A=>+A) и e-правил (правил вида A->e). Как циклы, так и e-правиламогут быть удалены предварительно. Получающаяся грамматика без левойрекурсии может иметь e-правила.3.2.6. Левая факторизацияOсновная идея левой факторизации в том, что, когда неясно, какую из двухальтернатив надо использовать для развертки нетерминала A, нужнопеределать A-правила так, чтобы отложить решение до тех пор, пока небудет досточно информации, чтобы принять правильное решение.Если A->uv1 | uv2 - два A-правила и входная строка начинается снепустой строки, выводимой из u, мы не знаем, разворачивать ли по uv 1или по uv2.
Однако можно отложить решение, развернув A->uA'. Тогдапосле анализа того, что выводимо из u, можно развернуть A'->v1 или A'>v2. Левофакторизованные правила принимают видA -> u A'A' -> v1 | v2Алгоритм 3.6. Левая факторизация грамматики.Для каждого нетерминала A ищем самый длинный префикс u, общий длядвух или более его альтернатив. Если u#e, т.е.
существует нетривиальныйобщий префикс, заменяем все A-правила A->uv1 | uv2 | ... | uvn | z, где z все альтернативы, не начинающиеся с u, наA -> uA' | zA' -> v1 | v2 | ... | vnЗдесь A' - новый нетерминал. Повторно применяем это преобразование,пока никакие две альтернативы не будут иметь общего префикса.Пример 3.4. Рассмотрим вновь грамматику условных операторов:St -> if Ex then St| if Ex then St else St| ContEx -> ...После левой факторизации грамматика принимает видSt-> if Ex then St St'| ContSt' -> else St | eEx -> ...44К сожалению, грамматика остается неоднозначной, а значит, и не LL(1),что иллюстрируется рис. 3.8.StStStSt'StSt’if E then if E then S else SS S' else SSt'if E then if E thenа)б)Рис. 3.83.2.7.
Рекурсивный спускВышебылрассмотрентаблично-управляемыйвариантпредсказывающего анализа, когда магазин явно использовался в процессеработыанализатора.Можнопредложитьдругойвариантпредсказывающегоанализатра,когдакаждомунетерминалусопоставляется, вообще говоря, рекурсивная процедура и магазинобразуется неявно при вызовах этих процедур. Процедуры рекурсивногоспуска могут быть записаны, как это изображено на рис. 3.9. В процедуреN для случая, когда имеется альтернатива N->ui->*e (не может быть болееодной альтернативы, из которой выводится e!), приведены два варианта1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующийвходной символ FOLLOW(N).
Если нет - выдается ошибка. Во второмварианте этого не делается, так что анализ ошибки откладывается напроцедуру, вызвавшую N.void N()/*N -> u1 | u2 | ... |uk*/{if (InSym<-FIRST(ui))//только одному!if (parse(ui))result(“N->ui”);else error();else//Вариант 1:if (имеется правило N->ui =>* e)//Вариант 1.1if (InSym<-FOLLOW(N))result(“N->ui“);else error();45//Конец варианта 1.1//Вариант 1.2:result(“N->ui“);//Конец варианта 1.2//Конец варианта 1Вариант 2:if (нет правила N->ui =>*e)error();}//Конец варианта 2:boolean parse(u)//из u не выводится e!{ v=u;while (v!=e){//v==Xzif (X-терминал a)if (InSym!=a)return(false);else InSym=getInsym();else //X-нетерминал BB;v=z;}return(true);}Рис. 3.93.2.8.
Диаграммы переходов для рекурсивного спускаКак правило, непосредственное программирование рекурсивного спуска изграмматики приводит к большому числу процедур. Число этих процедурможно уменьшить, заменив в некоторых правилах рекурсию циклом. Дляэтого можно воспользоваться диаграммой переходов грамматики, котораястроится следующим образом.Пусть имеется LL(1)-грамматика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
