LL17 (1131464), страница 2

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

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

Рис. 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 как множество терминалов 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->Y₁Y₂...Y_k, то включить a в FIRST(X), если для некоторого i a<-FIRST(Y_i) и e принадлежит всем FIRST(Y₁),...,FIRST(Y_i-1), т.е. Y₁...Y_i-1=>*e. Если e принадлежит FIRST(Y_j) для всех j=1,2,...,k, то добавить e к FIRST(X). Например, все, что принадлежит FIRST(Y₁) принадлежит также и FIRST(X). Если из Y₁ не выводится e, то ничего больше не добавляем к FIRST(X), но если Y₁=>*e, то добавляем FIRST(Y₂), и т.д.

Теперь FIRST для любой строки X₁X₂...X_n можно вычислить следующим образом.

Шаг 1. Полагаем FIRST(X₁X₂...X_n)={}.

Шаг 2. Добавим к FIRST(X₁X₂...X_n) все не e символы из FIRST(X₁). Добавим также не e символы из FIRST(X₂), если e<-FIRST(X₁),не e символы из FIRST(X₃), если e принадлежит как FIRST(X₁), так и FIRST(X₂), и т.д. Наконец, добавим e к FIRST(X₁X₂...X_n), если e<-FIRST(X_i) для всех i.

Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 3.3.

Алгоритм 3.3. Построение FOLLOW(X) для всех X - нетерминалов грамматики.

Шаг 1. Положить FOLLOW(X)={}.

Шаг 2. Поместить $ в FOLLOW(S), где S - начальный символ и $ - правый концевой маркер.

Шаг 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. В этом случае нужно развернуть A в u, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $<-FOLLOW(A).

Алгоритм 3.4. Построение таблиц предсказывающего анализатора.

Для каждого правила вывода A->u грамматики выполнить шаги 1 и 2

Шаг 1. Для каждого терминала a из FIRST(u) добавить A->u к M[A,a].

Шаг 2. Если e<-FIRST(u), добавить A->u к M[A,b] для каждого терминала b из FOLLOW(A). Если e<-FIRST(u) и $<-FOLLOW(A), добавить A->u к M[A,$].

Шаг 3. Положить все неопределенные входы равными error.

Пример 3.3. Применим алгоритм 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.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,

для которых 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
| Cont
Ex -> ...

Эта грамматика неоднозначна, что иллюстрируется рис. 3.7. Поскольку грамматика неоднозначна, она не является LL(1). Проблема, порождает ли грамматика LL-язык, алгоритмически неразрешима.

St St


St St


if E then if E then S else S if E then if E then S else S

а) б)

Рис. 3.7

3.2.5. Удаление левой рекурсии

Основная трудность при использовании предсказывающего анализа - это написание такой грамматики для входного языка, чтобы по ней можно было построить предсказывающий анализатор. Иногда с помощью некоторых простых преобразований не LL(1)-грамматику можно привести к LL(1)-виду. Среди этих преобразований наиболее очевидными являются левая факторизация и удаление левой рекурсии. Здесь необходимо сделать два замечания. Во-первых, не всякая грамматика после этих преобразований становится LL(1) и, во-вторых, после удаления левой рекурсии и левой факторизации получающаяся грамматика может стать трудно понимаемой.

Грамматика леворекурсивна, если в ней имеется нетерминал A такой, что существует вывод A=>+Au для некоторой строки u. Леворекурсивные грамматики не могут анализироваться методами сверху-вниз, поэтому необходимо удаление левой рекурсии.

Непосредственную левую рекурсию, т.е. рекурсию вида A->Au, можно удалить следующим способом. Сначала группируем A-правила:

A -> Au₁ | Au₂ | ... | Au_m | v₁ | v₂ | .... | v_n

где никакая из строк v_i не начинается с A. Затем заменяем A-правила на

A -> v₁A' | v₂A' | .... | v_nA'
A'-> u₁A' | u₂A' | .... | u_mA' | e

Нетерминал A порождает те же строки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шагов. Приведенный ниже алгоритм 3.5 позволяет удалить все левые рекурсии из грамматики.

Алгоритм 3.5. Удаление левой рекурсии.

Шаг 1. Упорядочиваем нетерминалы в произвольном порядке.
Шаг 2. for (i=1;i<=n;i++)
{for (j=1;j<=i-1;j++)
{/*По индукции v₁,...,v_k не имеют ссылок на A_i в начале*/
пусть A_j->v₁ | v₂ | ... | v_k - все текущие правила
для A_j;
заменить все правила вида A_i->A_ju на правила
A_i->v₁u | v₂u | ... | v_ku;
}
удалить непосредственную левую рекурсию
в правилах для A_i;
}

После (i-1)-й итерации внешнего цикла на шаге 2 для любого правила вида A_k->A_lu, где k<i, выполняется l>k. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле A_i->A_mu, пока не будет m>=i. Затем, удаляя непосредственную левую рекурсию для A_i-правил, делаем m больше i.

Алгоритм 3.5 применим, если грамматика не имеет циклов (выводов вида A=>+A) и e-правил (правил вида A->e). Как циклы, так и e-правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e-правила.

3.2.6. Левая факторизация

Oсновная идея левой факторизации в том, что, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно переделать A-правила так, чтобы отложить решение до тех пор, пока не будет досточно информации, чтобы принять правильное решение.

Если A->uv₁ | uv₂ - два A-правила и входная строка начинается с непустой строки, выводимой из u, мы не знаем, разворачивать ли по uv₁ или по uv₂. Однако можно отложить решение, развернув A->uA'. Тогда после анализа того, что выводимо из u, можно развернуть A'->v₁ или A'->v₂. Левофакторизованные правила принимают вид

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

Список файлов ответов (шпаргалок)