<У1> Ут» ДЛЯ всех и 6FIRSTft(XoBiX,. . ©ft-- Каж-

дая таблица Tj - это ЬЬ(й)-таблица, соответствующая Bj и (l/m), так что нред]Юложение индукции выполняется для каждой последовательности тактов вида

Вставим такты, на которых из магазина выбрасываются Xj\ тогда {ХоУ11У2Х2---УттУ е)

1 • • УттУ fi 1\Т-iz- • -ГдаХда, /)

Н"* {УМ22- -УтХтУ* ТуХуТХ.. ..ТХ, с) Н* {1У2>2- • -УттУ ХуТХ,. . .Гл. il)

Из утверждения (5.1.3), в частности, вытекает, что если Sw, то {W, Т,$, е)\-Це, $, я). □

Пример 5.17. Рассмотрим ЬЬ(2)-грамматику 0 с правилами

S-S-Л-

е

аЬА Saa

(1) (2) (3) (4)

Построим сначала соответствующие ЕЬ(2)-таблицы. Начнем с T = Ts.{e) (см. табл. 5.3). Затем по Г найдем Г,=Гл,{е}.

потом Т.г=Т8,{аа) И, НаКОНец, Ts=TA,laa)- По ЭТИМ LL(2)-Ta6-

лицам получим управляющую таблицу, показанную на рис. 5.6.

2-предсказывающий алгоритм, управляемый этой таблицей, разберет входную цепочку аЬаа, проделав такую последовательность тактов:

{аЬаа, Т$, е) ~- {аЬаа, аЬТу$, 2) h- {baa, ЬТу$, 2) Н{аа, Г,5, 2) \-{аа, Таа<„ 23) [~{аа, аа$, 231) \-{а, а$, 231) h-(e. $. 231) □

В заключение этого раздела покажем, что /г-предсказывающий алгоритм разбирает каждую входную цепочку за линейное время.

Теорема 5,6. Число шагов, выполняемых k-предсказываюиим алгоритмом с управляющей таблицей, построенной алгоритмом 5.3 по 1Л.{к)-грамматике G, линейно зависит от п, где п-длина входной цепочки.

Доказательство. ЬЬ(/е)-грамматика G не может быть леворекурсивной. По лемме 4.1 максимальное число шагов в выводе вида А =f Ва меньше некоторой константы с. Таким образом, максимальное число шагов, которое может потратить /г-предсказывающий алгоритм Л на обработку одного входного символа вплоть до операции выброса, сдвигающей с этого сим-

Рнс. 5.6. Управляющая таблица для грамматики С?2.

всех 1€о(Л), повторить шаг (2) для всех различных пар Л-правил.

(3) Повторить шаги (1) и (2) для всех нетерминалов из N.

(4) Выдать ,да", если нарушений ЕЕ()-условия не обнаружено. □

Чтобы реализовать алгоритм 5.4, нужно уметь вычислять FIRSTft(P) для любой КС-грамматики G(N, 2, Р, S) и всех p(Nu2)*. Во-вторых, нужно уметь находить множества 0(Л). Сейчас мы дадим соответствующие алгоритмы.

Алгоритм 5.5. Вычисление функции FIRSTft(p).

Вход. КС-грамматика G(N, 2, Р, S) и цепочка р ХДз ... ...X„€(NU2)*. Выход. FIRST?(P). Метод. Так как по лемме 5.1

FIRST,(p) = FIRST,(X,) FIRST,(X,) ... ©FIRST,(X„)

TO достаточно показать, как найти F1RST.(X) для XN. Если Х€2и{е}, то очевидно, что FIRSTJX) - {X}.

Определим множества F(Х) для каждого X € N U 2 и возрастающих значений tO:

(1) Fi{a)={a] для всех и гО.

(2) Pg (Л) - {xJ x€ 2* и существует правило Л-ха из Р, для которого лиОо \x\ = k, либо x<fe и а = е].

(3) Допустим, что Fq, F, р уже определены для всех ЛeN. Тогда

Fi{A) = Fi i{A)U{x\A~Vj ... У„ принадлежит Р и

(4) Так как FiA) f ДЛ) 2** для всех Л и то в конце концов мы дойдем до такого i, что /.(Л) =/ДЛ) для всех Л N. Тогда положим ЕШ5Т,(Л) Е{А) для этого значения i. □

Пример 5.18. Построим множества Fi{X) для /е = 1 и грамматики G с правилами

S-BA

Л -- + бЛ I е

B-DC

D{S)\a

Вначале

f„(S) = f„(B) = 0

F,(C) = \*,e} fo(D) = {{, a]

вола входную головку, не превосходит с. Следовательно, при обработке входной цепочки длины п алгоритм d может проделать не более О (/г) шагов. □

5.1.6. Проверка LL }-условия

По отношению к произвольной данной грамматике G возникает ряд естественных вопросов. Во-первых, является ли G LL (й)-грамматикой для данного /е? Во-вторых, является ли G LL-грамматикой, т. е. существует ли такое k, что G- LL ()-грамматика? И наконец, так как для LL (1)-грамматики левые разборы строятся особенно просто, естествеппо спросить: если G не LL (1)-грамматика, то существует ли эквивалентная ей LL (1)-грамматика G, для которой L {G) = L(G)}

К сожалению, только для первого вопроса есть отвечающий на него алгоритм. Можно показать, что вторая и третья проблемы алгоритмически неразрешимы.

В этом разделе мы опишем алгоритм, проверяющий, является ли G LL (й)-грамматикой для заданного значения k. Если =1, можно воспользоваться теоремой 5.3. Для произвольного к можно применить теорему 5.2. Здесь мы рассмотрим общий случай. По существу надо просто показать, что алгоритм 5.3 успешно строит управляющую таблицу только тогда, когда G - LL (/е)-грамматика.

Напомним, что G (N, 2, Р, S) пе является ЕЕ(й)-грамма-тикой тогда и только тогда, когда для некоторой цепочки (NU2)*

(1) wAa,

(2) LF{RST,(a),

(3) (FIRST,(P)©,L)n(FIRST,(y)©,L)0 для некоторых Ру, для которых Л-+р и Л-> у-правила из Р.

Алгоритм 5.4. Проверка LL(/e)-y с л о в и я.

Вход. КС-грамматика G (N, 2, Р, S) и целое число k. Выход. „Да", если G -ЕЕ()-грамматика, и „нет" в противном случае. Метод.

(1) Для каждого нетерминала Л N, имеющего две или более альтернативы, вычислить а(Л) {L L 2* и существует такая цепочка а, что S]wAa и L FIRST,(a)}. (В дальнейшем будет дан алгоритм вычисления о(Л).)

(2) Если Л-j-p и А-у - различные Л-правила, то для каждого! ео(Л) вычислить/(L)=(F{RST,(P)©,L)n(FlRST,(y)©fcL). Если [{1)Ф0, остановиться и выдать „нет". Если f(L)0 для

Следующий алгоритм представляет собой метод вычисления для заданной грамматики G = (N, 2, Р, S) тех множеств L из 2*, для которых существуют такие w, А и а, что S=\wAa и FIRST,(a)-L.

Алгоритм 5.6. Вычисление о(Л). Вход. КС-грамматика G = (N, 2, Р, S).

Выход. 0(Л) = {112** и SlwAa, F{RSTj(a)-L для некоторых W и а].

Метод. Будем вычислять для всех Л и В нз N множества и А=>\хВа, I=.FIRST;,(a) для некоторых X и сс}. С этой целью будем строить множества оДЛ, В) для i О, 1, ...:

(1) Положим 0„(Л, В) 1 2**, Л-рЛсс принадлежит Р и LFIRST(a)}.

(2) Допустим, что о, ,(Л, В) уже построены для всех Л и В, Определим оДЛ, В) следующим образом:

(а) Если LOiy(A, В], то поместим L в о,(Л, В).

(б) Если в Р есть правило Л--Х, ... Х„, то в 0/(Л, В) поместим такой язык для которого найдутся такие 1<;/<пиГ€а, ,(Х/,В),что1 = 1Ш,РШЗТ,(Х,.,)е,...

... e,FIRST,{X„).

(3) В тот момент, когда о,(Л, В) = 0(-у{А, В) для некоторого i и для всех Л, В, по.аожим о{А, В)о,{А, В). Так как а; ,(Л, В)£0ДЛ, 5)5(2**) для всех i, то raivoe i должно найтись.

(4) Нужное нам множество о{А) есть g{S, Л). П

Теорема 5.8. L принадлежит множеству o{S, Л) построенному алгоритмом 5.6, тогда и только тогда, когда 5=>;и;Ла и LFlRST,(a) для некоторых wH* и a(Nu2)*.

Доказательство. Доказательство аналогично доказательству предыдущей теоремы; оставляем его в качестве упражнения. □

Пример 5.19. Проверим, выполняется ли ЬЕ(1)-условие для грамматики G с правилами

S-~AS\e AaA\b

Начнем с вычисления FIRSTi(S) = {е, а, Ь] и F{RST(Л) = {а, Ь}. Затем нужно вычислить G{S)--a{S, S) и 0(Л) = а(5, Л). На шаге (1) алгоритма 5.4 получаем

0,(S,S) = {M) М, S) = 0

<Jo(\ Л)~{{е, а, Ь}} o(M){W}

Затем Fi{B) = {(, а\ и Fy{X)f{X) для всех остальных X. Далее FiS) {(, а] и F{X) = Fy{X) для всех остальных X. Так как Fj{X) = F{X) для всех X, то

FIRST(5) - FIRST(B) - FIRST(D) {(, а} FlRST{A) = {-\-,e} FIRST(C)Ke} □

Теорема 5.7. Алгоритм 5.5 правильно вычисляет FIRSTj(4).

Доказательство. Заметим, что если r, i(X) = f/(X) для всех XNuS, то f-{X)Fj{X) для всех / > ( и всех X. Таким образом, мы должны доказать, что х FIRST.(/4) тогда и только тогда, когда xFj{A) для некоторого /.

Достаточность. Индукцией по / покажем, что Fj{A) РШ5Т;,(Л). Базис, /0, тривиален. Расслютрим фиксированное значение / и допустим, что наше утверждение верно для всех меньших значений /.

Если xFj{A), то либо xFj y{A) (и в этом случае сразу получается нужный результат), либо в Р можно найти такое правило А--Уу ... К„, что Xp£Fj y{Vp) для lpn и х = FlRSTft(Xi.. .х„). По предположению индукциилг FIRST(K,). Таким образом, для каждого р существует такой вывод Ур=* Ур, что Хр - FIRST,). Следовательно, А у . .. Теперь надо показать, что д:= F{RSTft(] ... i/„), и заключить отсюда, что xeFIRST;,().

Случай 1: \Ху ... х\<с k. Тогда Ур = Хр для каждого р, и х - у .. . Уп- Так как в этом случае у ... „ € ЕШ5Тй(Л), то xeFIRST,().

Случай 2: \Ху...х\<к для некоторого sO, но [л:, ... -s+il- Тогда Ур = Хр для ips и х состоит из первых k символов цепочки х, . . . x+i- Так как х у-префикс цепочки ys.i, то X - префикс цепочки у ... у.+у, а значит, и цепочки Уу ... Итак, х FlRST;t(4).

Необходимость. Пусть хЕШ5Т4(Л). Тогда А=Уу для некоторого г и x = FIRST(f/). Докажем индукцией по г, что xF{A). Базис, г=\, тривиален, так как хР{А). (На самом деле предположение индукции можно было бы несколько усилить, ио здесь это не к чему.)

Зафиксируем г и предположим, что наше утверждение верно для меньших значений г. Тогда

А=.>Уу ... V,=i>-y

где у=У1 Уп и УррУр для l<p<rt. Очевидно, р<-По предположению индукции xF у{Ур), где Xp=¥\RSlk(yp)-Таким образом, FIRST(Xi ... .v„) - хGГ(Л). □