В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 10
Текст из файла (страница 10)
Выполнить шаги 1–4:(1) Положить F OLLOW (X) = ∅ для каждого символа X ∈ N .(2) Добавить $ к F OLLOW (S).(3) Если в P eсть правило вывода A → αBβ, где α, β ∈ (N ∪ T )∗ то всеэлементы из F IRST (β), за исключением e, добавить к F OLLOW (B).(4) Пока ничего нельзя будет добавить ни к какому множествуF OLLOW (X), выполнять:если в P есть правило A → αB или A → αBβ, α, β ∈ (N ∪ T )∗ , гдеF IRST (β) содержит e (т.е. β ⇒∗ e), то все элементы из F OLLOW (A)добавить к F OLLOW (B).Пример 4.4. Рассмотрим грамматику из примера 4.3.
Для нееF IRST (E) = F IRST (T ) = F IRST (F ) = {(, id}F IRST (E 0) = {+, e}F IRST (T 0) = {∗, e}F OLLOW (E) = F OLLOW (E 0 ) = { ), $}F OLLOW (T ) = F OLLOW (T 0 ) = {+, ), $}F OLLOW (F ) = {+, ∗, ), $}Например, id и левая скобка добавляются к F IRST (F ) на шаге 3 при i = 1,поскольку F IRST (id) = {id} и F IRST (”(”) = {”(”} в соответствии с шагом 1.На шаге 3 при i = 1, в соответствии с правилом вывода T → F T 0 к F IRST (T )добавляются также id и левая скобка. На шаге 2 в F IRST (E 0) включается e.При вычислении множеств F OLLOW на шаге 2 в F OLLOW (E) включается$.
На шаге 3, на основании правила F → (E), к F OLLOW (E) добавляется такжеправая скобка. На шаге 4, примененном к правилу E → T E 0 , в F OLLOW (E 0 )включаются $ и правая скобка. Поскольку E 0 ⇒∗ e, они также попадают и вомножество F OLLOW (T ). В соответствии с правилом вывода E → T E 0 , на шаге3 в F OLLOW (T ) включаются и все элементы из F IRST (E 0), отличные от e.4.3.3Конструирование таблицы предсказывающего анализатораДля конструирования таблицы предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее.
Предположим, что A → α – правило вывода грамматики иa ∈ F IRST (α). Тогда анализатор делает развертку A по α, если входнымсимволом является a. Трудность возникает, когда α = e или α ⇒∗ e. Вэтом случае нужно развернуть A в α, если текущий входной символ принадлежит F OLLOW (A) или если достигнут $ и $ ∈ F OLLOW (A).62ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗАлгоритм 4.6. Построение таблицы предсказывающего анализатора.Вход. КС-грамматика G = (N, T, P, S).Выход. Таблица M [A, a] предсказывающего анализатора, A ∈ N , a ∈T ∪ {$}.Метод.
Для каждого правила вывода A → α грамматики выполнитьшаги 1 и 2. После этого выполнить шаг 3.(1) Для каждого терминала a из F IRST (α) добавить A → α к M [A, a].(2) Если e ∈ F IRST (α), добавить A → α к M [A, b] для каждого терминала b из F OLLOW (A). Кроме того, если e ∈ F IRST (α) и $ ∈F OLLOW (A), добавить A → α к M [A, $].(3) Положить все неопределенные входы равными “ошибка”.Пример 4.5. Применим алгоритм 4.6 к грамматике из примера 4.3. Поскольку F IRST (T E 0) = F IRST (T ) = {(, id }, в соответствии с правилом выводаE → T E 0 входы M [E, ( ] и M [E, id ] становятся равными E → T E 0 .В соответствии с правилом вывода E 0 → +T E 0 значение M [E 0 , +] равно E 0 →+T E 0 .
В соответствии с правилом вывода E 0 → e значения M [E 0 , )] и M [E 0 , $]равны E 0 → e, поскольку F OLLOW (E 0 ) = { ), $}.Таблица анализа, построенная алгоритмом 4.6 для этой грамматики, приведена на рис. 4.3.4.3.4LL(1)-грамматикиАлгоритм 4.6 для построения таблицы предсказывающего анализатораможет быть применен к любой КС-грамматике.
Однако для некоторыхграмматик построенная таблица может иметь неоднозначно определенные входы. Нетрудно доказать, например, что если грамматика леворекурсивна или неоднозначна, таблица будет иметь по крайней мере одиннеоднозначно определенный вход.Грамматики, для которых таблица предсказывающего анализаторане имеет неоднозначно определенных входов, называются LL(1)-грамматиками.Предсказывающий анализатор, построенный для LL(1)-грамматики, называется LL(1)-анализатором. Первая буква L в названии связано с тем,что входная цепочка читается слева направо, вторая L означает, что строится левый вывод входной цепочки, 1 – что на каждом шаге для принятия решения используется один символ непрочитанной части входнойцепочки.Доказано, что алгоритм 4.6 для каждой LL(1)-грамматики G строиттаблицу предсказывающего анализатора, распознающего все цепочкииз L(G) и только эти цепочки.
Нетрудно доказать также, что если G –LL(1)-грамматика, то L(G) – детерминированный КС-язык.Справедлив также следующий критерий LL(1)-грамматики. Грамматика G = (N, T, P, S) является LL(1)-грамматикой тогда и только тогда,4.3. ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗ63когда для каждой пары правил A → α, A → β из P (т.е. правил с одинаковой левой частью) выполняются следующие 2 условия:(1) F IRST (α) ∩ F IRST (β) = ∅;(2) Если e ∈ F IRST (α), то F IRST (β) ∩ F OLLOW (A) = ∅.Язык, для которого существует порождающая его LL(1)-грамматика,называют LL(1)-языком. Доказано, что проблема определения того, порождает ли грамматика LL-язык, является алгоритмически неразрешимой.Пример 4.6. Неоднозначная грамматика не является LL(1).
Примером может служить следующая грамматика G = ({S, E}, {if, then, else, a, b}, P, S) с правилами:S → if E then S | if E then S else S | aE→bЭта грамматика является неоднозначной, что иллюстрируется на рис. 4.6.6LI (E66WKHQLI (LI ( WKHQ 6 HOVHED6DEWKHQ6HOVHLI (WKHQ 6ED6DРис. 4.6:4.3.5Удаление левой рекурсииОсновная трудность при использовании предсказывающего анализа –это нахождение такой грамматики для входного языка, по которой можно построить таблицу анализа с однозначно определенными входами.Иногда с помощью некоторых простых преобразований грамматику, неявляющуюся LL(1), можно привести к эквивалентной LL(1)-грамматике.Среди этих преобразований наиболее эффективными являются левая факторизация и удаление левой рекурсии. Здесь необходимо сделать два замечания. Во-первых, не всякая грамматика после этих преобразованийстановится LL(1), и, во-вторых, после таких преобразований получающаяся грамматика может стать менее понимаемой.ГЛАВА 4.
СИНТАКСИЧЕСКИЙ АНАЛИЗ64Непосредственную левую рекурсию, т.е. рекурсию вида A → Aα, можно удалить следующим способом. Сначала группируем A-правила:A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn ,где никакая из строк βi не начинается с A. Затем заменяем этот наборправил наA → β1 A0 | β2 A0 | ... | βn A0A0 → α1 A0 | α2 A0 | ...
| αm A0 | eгде A0 – новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии. С помощью этойпроцедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шага. Приведенныйниже алгоритм 4.7 позволяет удалить все левые рекурсии из грамматики.Алгоритм 4.7. Удаление левой рекурсии.Вход. КС-грамматика G без e-правил (правил вида A → e).Выход. КС-грамматика G0 без левой рекурсии, эквивалентная G.Метод.
Выполнить шаги 1 и 2.(1) Упорядочить нетерминалы грамматики G в произвольном порядке.(2) Выполнить следующую процедуру:for (i=1;i<=n;i++){for (j=1;j<=i-1;j++){пусть Aj → β1 | β2 | ... | βk - все текущие правила для Aj ;заменить все правила вида Ai → Aj αна правила Ai → β1 α | β2 α | ... | βk α;}удалить правила вида Ai → Ai ;удалить непосредственную левую рекурсию в правилах для Ai ;}После (i − 1)-й итерации внешнего цикла на шаге 2 для любого правила вида Ak → As α, где k < i, выполняется s > k.
В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле Ai → Am α, пока не будетm > i. Затем, после удаления непосредственной левой рекурсии для Ai правил, m становится больше i.Алгоритм 4.7 применим, если грамматика не имеет e-правил (правилвида A → e). Имеющиеся в грамматике e-правила могут быть удаленыпредварительно. Получающаяся грамматика без левой рекурсии можетиметь e-правила.4.3. ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗ4.3.665Левая факторизацияOсновная идея левой факторизации в том, что в том случае, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно изменить A-правила так, чтобы отложить решение дотех пор, пока не будет достаточно информации для принятия правильного решения.Если A → αβ1 | αβ2 – два A-правила и входная цепочка начинаетсяс непустой строки, выводимой из α, мы не знаем, разворачивать ли попервому правилу или по второму.
Можно отложить решение, развернувA → αA0 . Тогда после анализа того, что выводимо из α, можно развернуть по A0 → β1 или по A0 → β2 . Левофакторизованные правила принимают видA → αA0A0 → β1 | β2Алгоритм 4.8. Левая факторизация грамматики.Вход. КС-грамматика G.Выход. Левофакторизованная КС-грамматика G0 , эквивалентная G.Метод. Для каждого нетерминала A ищем самый длинный префиксα, общий для двух или более его альтернатив.
Если α 6= e, т.е. существует нетривиальный общий префикс, заменяем все A-правилаA → αβ1 | αβ2 | ... | αβn | z,где z обозначает все альтернативы, не начинающиеся с α, наA → αA0 | zA0 → β1 | β2 | ... | βnгде A0 – новый нетерминал. Повторно применяем это преобразование,пока никакие две альтернативы не будут иметь общего префикса.Пример 4.7.
Рассмотрим вновь грамматику условных операторов из примера 4.6:S → if E then S | if E then S else S | aE→bПосле левой факторизации грамматика принимает видS → if E then SS 0 | aS 0 → else S | eE→bК сожалению, грамматика остается неоднозначной, а значит, и не LL(1).ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ664.3.7Рекурсивный спускВыше был рассмотрен таблично-управляемый вариант предсказывающего анализа, когда магазин явно использовался в процессе работы анализатора. Можно предложить другой вариант предсказывающего анализа, в котором каждому нетерминалу сопоставляется процедура (вообще говоря, рекурсивная), и магазин образуется неявно при вызовах таких процедур. Процедуры рекурсивного спуска могут быть записаны,как показано ниже.В процедуре A для случая, когда имеется правило A → ui , такое, чтоui ⇒∗ e (напомним, что не может быть больше одного правила, из которого выводится e), приведены два варианта 1.1 и 1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
