LL(k) - Грамматики

Страница 2

В определении LL(k)- грамматики утверждается, что для данной выводимой цепочки wAa цепочка w и непосредственно следующие за ней k входных символов однозначно определяют, какое применить правило для развертки нетерминала A. Поэтому на первый взгляд может показаться, что для определения нужного правила надо помнить всю цепочку w. Однако это не так. Докажем теорему, очень важную для понимания LL(k)-грамматик:

ТРМ: КС-грамматика G=(N,E,P,S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил A®b` и A®c` из P пересечение FIRST(b`a`)ÇFIRST(c`a`) пусто для всех таких wAa`, что SÞwAa`.

ДКВ: Необходимость. Допустим, что w, A, a`, b` и c` удовлетворяют условиям теоремы, а FIRST(b`a`)ÇFIRST(c`a`) содержит x. Тогда по определению FIRST для некоторых y и z найдутся выводы SÞwAa`Þwb`a`Þwxy и SÞwAa`Þwc`a`Þwxz. (Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных терминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k то y = z = e. Так как b` ¹ c`, то G не LL(k)- грамматика.

Достаточность. Допустим, что G не LL(k)- грамматика. Тогда найдутся такие два вывода SÞwAa`Þwb`a`Þwx и SÞwAa`Þwc`a`Þwy, что цепочки x и y совпадают в первых k позициях, но b`¹c`. Поэтому A®b` и A®c` - различные правила из P и каждое из множеств FIRST(b`a`) и FIRST(c`a`) содержит цепочку FIRST(x) совпадающую с FIRST(y). ЧТД.

ПРМ: Грамматика G из правила S®aS|a, не будет LL(1)- грамматикой, так как FIRST1(aS)=FIRST1(a)=a. Это можно объяснить так - видя только первый символ цепочки мы не можем определить какое правило необходимо применить (левое или правое). С другой стороны эта грамматика является LL2(k) грамматикой - что вполне очевидно.

ОПР: Пусть G=(N,E,P,S) - КС-грамматика. Определим FOLLOWk(b`) как множество терминальных символов, которые могут встречаться после нетеминала, являющегося аргументом функции.

ТРМ: КС-грамматика G=(N,E,P,S) является LL(1)-грамматикой тогда и только тогда, когда для двух различных правил A®b` и A®c` пересечение FIRST1(b` FOLLOW1(A))ÇFIRST1(c` FOLLOW1(A)) пусто при всех AÎN. (Без ДКВ).

Теорему можно выразить следующим : по первому символу после нетерминала необходимо выбрать применимое правило - следовательно эти символы различны и пересечение пусто. Эта теорема может применяться к LL(k)- грамматикам, но не всегда выполняться. Грамматики для которых выполняется теорема называются сильными, таким образом все LL(1) грамматики - сильные. Необходимо так же заметить что каждая LL(k)- грамматика однозначна, поэтому если имеется неоднозначная грамматика - то она не LL(k). Имеется неразрешимая проблема распознавания, существует ли для данной КС-грамматики G, не являющейся LL(k), эквивалентная ей LL(k)- грамматика. Однако в ряде случаев такое преобразование возможно. Применяется два способа:

Первый способ - устранение левой рекурсии.

ПРМ: Пусть G- грамматика S®Sa|b которая не является LL- грамматикой. Заменим правила на следующие:

S ®bS`

S`®aS`|e

получив при этом эквивалентную LL(1)- грамматику.

Другой способ - левая факторизация.

ПРМ: Рассмотрим LL(2)- грамматику G с двумя правилами S®aS|a. В этих двух правилах «вынесем влево за скобки» символ a, записав их в виде S®a(S|e). Иными словами, мы считаем что операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти правила на :

S®aA

A®S|e

тем самым получим эквивалентную LL(1)-грамматику.

Разбор для LL(1)- грамматик.

Ядром предсказывающего алгоритма является управляющая таблица. В этом и следующих разделах будет показано как построить корректную управляющую таблицу.

АЛГ 1: Управляющая таблица для LL(1)-грамматики.

Вход : LL(1)- грамматика .

Выход : Корректная управляющая таблица.

Метод : Будем считать, что $-маркер дна магазина. Таблица определяется следующим образом:

(1) Если A ® a` - правило из P с номером i, то M[A,a]=(a`,i) для всех a¹e, принадлежащих FIRST1(a`). Если eÎFIRST1(a`), то M[A,b]=(a`,i) для всех bÎFOLLOW1(A).

(2) M[a,a]=выброс для всех aÎE.

(3) M[$,e]=допуск.

(4) В остальных случаях M[X,a]=ошибка для XÎNÈEÈ{$} и aÎEÈ{e}.

ТРМ: Предложенный алгоритм строит корректную управляющую таблицу для LL(1)- грамматики G.

Разбор для LL(k)- грамматик.

Построим управляющую таблицу для произвольной грамматики. Если грамматика сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до k символов. В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме разбора в магазин помещались только символы из EÈN и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина и текущий входной символ. Для не сильных грамматик этого может оказаться недостаточно.

ПРМ: Возьмем грамматику

S®aAaa|bAba

A®b|e

Если даны нетерминал A и аванцепочка ba, то не известно, какое из правил надо применить.

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

ОПР: Пусть E - некоторый алфавит. Если L1 и L2 - подмножества E, то положим L1 Åk L2 = {

w | для некоторых xÎL1 и yÎL2

либо w = xy, если |xy| £k

либо w состоит из первых k символов цепочки xy

}

ЛМА: Для любой КС- грамматики G=(N,E,P,S) и любых a`, b`Î(NÈE) :

FIRSTk(a`b`)=FIRSTk(a`) Åk FIRSTk(b`)

ОПР: Пусть G=(N,E,P,S) - КС- грамматика. Для каждых AÎN и LÍE определим LL(k)- таблицу Ta,l, соответствующую A и L, как функцию T(u), значением которой служит :

(1) =ошибка, если в P нет такого правила A®a`, что FIRSTk(a`) Åk L содержит u;

(2) =(A®a`,<Y1,Y2 .Ym>), если A®a`- единственное правило из P, для которого FIRSTk(a`) Åk L содержит u;

(3) не определено, если в множестве найдутся два и более правила (эту ситуацию называют конфликтом между правилами)

На нормальном языке это означает что вырабатывается значение ошибка, если u вообще не является цепочкой грамматики, возвращается правило если оно существует и только одно и если несколько правил - то значение не определяется.

АЛГ 2: Построение LL(k)- таблиц.

Вход: LL(k)- грамматика G=(N,E,P,S).

Выход: Множество TG LL(k)- таблиц, необходимых для построения управляющей таблицы для G.

Метод:

(1) Построить LL(k)- таблицу T0, соответствующую S и {e}.