Случай 3: Допустим, что содержит хотя бы один нетерминальный символ. Тогда =?>* uBu tiuu, где щи/е, так как в этом выводе нетерминал на левом конце не заменяется на е. Итак, имеем два вывода

5 аАх cCipjPa

=Ф*г. apiUjBux=i> aP-U-uu.x

в которых a-fi = af) и ищщх = иу. В определении LR()-rpaM-матики требуется, чтобы aAu-uux-а>иВщх, т.е. aAu-u- Подставляя ар вместо ар, получаем Аии = рп5. Но это невозможно, так как иифе.

Заметим, что именно здесь используется условие, что W € EFFjij(PaE)- Если бы в формулировке теоремы мы заменили EFF на FIRST, то цепочка аи могла бы быть iiycTon, и тогда аАиииха-иВих (если иие и = е).

Достаточность, Допустим, что G -не LR()-rpaMMaTHKa. Тогда в пополненной грамматике есть два вывода

(5.2.1)

(5.2.2)

S aAw aw

S уВх уЬх = ay

для которых FlRST.([2/) = FIRSTji,(f/)-=w, но аАуФуВх. Эти выводы можно выбрать такими, что цепочка ар будет настолько короткой, насколько это возможно.

В силу леммы 5.2 можно считать, что у6ар. Пусть iii/i - последняя цепочка в выводе

S;yBx

такая, что длина ее открытой части не больше арЦ-1, т. е. а1Л<ар+1. Тогда вывод (5.2.2) можно записать в виде

(5.2.3)

где apjap. В силу нашего выбора цепочки аАу получаем I а I I ар I I уб j и, кроме того, на последнем шаге вывода р2/1=>г/ не участвует правило В->-е. Если бы это правило применялось последним, то aAyi не была бы последней цепочкой вывода 5=*урх, у которой длина открытой части не превосходит I ар IН- Е Таким образом, и FIRST;(f/) содержится в EFFa(P2 i), и можно заключить, что ситуация [Л-.-р-ра, ] допустима для ар, где v = FIRST/(у).

Из существования вывода (5.2.1) вытекает, что ситуация ГЛ-*-р, тоже допустима для ар, так что осталось доказать, что Л-PiPa отличается от Л->р. Итак, пусть Л-p-pg совпадает с Л-*-р.. Тогда вывод (5.2.3) имеет вид

5=Ф;а,Л, а,у

где aip = ap. Поэтому а, =а и аАу-аВх, что противоречит предположению о том, что G ие ЕР(/г)-грамматика. □

Чтобы построить детерминированный правый анализатор для LR()-rpaMMaTHKH, надо знать, как для всех активных префиксов найти все допустимые LR()-cHTyanHH.

Определение. Пусть G - КС-грамматнка и у - ее активный префикс. Определим V{y) как множество ЕР(/г)-ситуаций (относительно k и G), допустимых для у. Как и раньше, будем опускать индексы и G, если понятно, о чем идет речь. Назовем множество {-А \Л = Vk [у) для некоторого активного префикса у грамматики G} системой множеств допустимых ЪЯ{к)-сшпуаций, соответствующей грамматике G.

Теперь приведем алгоритм построения множества LR()-cHTya-ций, допустимых для произвольной заданной цепочки, а затем алгоритм построения системы всех таких множеств для любой грамматики G.

Алгоритм 5.8, Построение множества Vf(y).

Вход. КС-грамматика G-(N, 2, Р, S) и y6(Nu2)*. Выход. К?(у),

Метод. Если уХ-Х.. то для того, чтобы построить 1(у), построим У,{е), K,(XJ, У,{Х,Х,), ,,,, К,(ХД, ... Х„).

(1) Построим Vk{e) так:

(а) Если 5-аР, включить [S---а, е] в V(e).

(б) Если ситуация [А-у*Ва, и] уже включена в К(е) и В-р Р, то для каждой цепочки х FlRST(aw) включить ситуацию [S-»-.р, х] в У,г{е) при условии, что там ее еще нет,

(в) Повторять шаг (б) до тех пор, пока в У(е) нельзя будет включить новую ситуацию.

(2) Допустим, что мы уже построили V{XiX2 ... Х.) для i<n. Построим V{X,X . .. X,.):

(а) Если [А~а • Хр, и] Vi,{X .,, X, i), включить [ЛаХ,.р, и] в У,(Х, .,,Х,).

(б) Если ситуация [Л-• Sp, и] уже включена в У{Х. X,) И ВбР, включить в V;(X, ... X,-) ситуацию [В--б, х] для каждой цепочки xFIRST(pw)

при условии, что там ее еще нет.

Теперь покажем, что алгоритм 5.8 правильно вычисляет Kft(Y)-

(в) Повторять шаг (26) до тех пор, пока в Vk{Xy... X.) нельзя будет включить новую ситуацию. □

Определение. Повторные применения шагов (16) и (26) алгоритма 5.8 к некоторому множеству ситуаций будем называть операцией замыкания этого множества.

Определим на множествах ситуаций грамматики G(N, 2, Р, S) функцию GOTO. Если -такое множество ситуаций, что = Vk{y) для некоторой цепочки у (N1)2)* и X(NU2)*, то значением GOTO(, X) будет такое множество Л, что Л=У{уХ). На шаге (2) алгоритма 5.8 вычисляется

V, {Х,Х, ... X,) = ООТО(У,(Х,Х, ... X,.,), X,)

Заметим, что шаг (2) на самом деле зависит от множества Ka(Xi... Х, ,), а не от Х ... Х,. ,.

Пример 5.29. Построим множества Vi{e), Vy{S) и Ki(Sa) для пополненной грамматики

5 -SaSb S

(Заметим, однако, что алгоритм 5.8 не требует, чтобы грамматика была пополненной.) Сначала вычислим У{е) (шаг (1) алгоритма 5.8). На шаге (1а) в У(е) включим [S-.5,e]. На uiare (16) в У{е) включим [5~ SaSb, е] и [S-•, е]. Так как [S-SaSh, е] принадлежит теперь К(е), то надо включить в К(е) также и [S-SaSb, 4 [5 , х] для всех а; FIRSTgS) = {й}. Таким образом, vie) содержит ситуации

[5 .5, е]

[S SaSb, е\а]

[S,e\ai

Здесь мы пишем сокращенно [Л->-ар, xlx] вместо

[А~аф,х,1 [Ла.р.,], ,,.,[Л--сс.р, xJ. Чтобы получить V{S), вычислим GOTO (V(e), S). На шаге (2а) в V{S) включаются три ситуации: [S-5,e] и [S-S-aSb, е\а]. Вычисление замыкания не дает новых ситуаций, так что V{S) состоит из ситуаций

[5 -SaSb, е\а]

V{Sa) вычисляется как значение G0T0(l/(5), а) и состоит из шести ситуаций

SSa-Sb, е\а] SSaSb, a\b] S*,a\b] □

Теорема 5.10. LЩk)-cumyaцuя принадлежит множеству Vjt{y) после шага (2) алгоритма 5.8 тогда и только тогда, когда она допустима для у.

Доказательство. Достаточность. Предоставляем читателю доказать, что алгоритм 5.8 заканчивает работу и правильно вычисляет Vk{e)- Мы докажем, что если все допустимые для Xi... i-i ситуации и только они содержатся в У,,{Х-уХ.. -X-.j), то все допустимые для Х... Х- ситуации и только они содержатся в Vf,{Xi ... X,).

Предположим, что ситуация [A~f>yW,u] допустима для Xi . - - X,-. Тогда существует такой вывод "S * аЛш=> apipLc;, что офу - XjX ... X, и и = FlRSV{w). Надо рассмотреть два случая.

Пусть 3j = piX,-. Тогда ситуация [Л -»-pi.Xyp2, и] допустима для Xj ... Х у и по предположению индукции принадлежит У„{Ху.. .Xfy). На шаге (2а) алгоритма 5.8 [ЛрХ-р, w] включается в У(Х1...Х).

Допустим, что Pi = e, так что в этом случае a = Xi...X,.. Так как 5=>*аЛ[г;-правый вывод, то в нем найдется промежуточный шаг, на котором появился последний символ Х цепочки а. Поэтому можно писать 5 а5 =>.ауХб =>*ссЛи;, где ау Ху.. .Х у, и на каждом шаге вывода ayX;6f/=>* аЛш правило применяется к нетерминалу, стоящему справа от явно указанного символа X,.. Тогда ситуация fS у «Хб, v], где у -FIRST/f/), допустима для Х.-.Х,.! и по предположению индукции принадлежит K(Xi. . .X,. j). Следовательно, на шаге (2а) алгоритма 5.8 [S-yX--6, v] включается Кд(Х...Х-). Так как б =>*Лсс, то можно найти такие нетерминалы Dy, Z), н цепочки ..., 9„ (Nu 2)*, что б начинается нетерминалом Dy, AD и в Р для каждого 1<г<т есть правило

D,j6-i. Тогда в результате одного из применений шага (26) ситуация [Л-.рз, и] будет включена в l(Xi... X,), Читателю предоставляем доказать, что вторая компонента и этой ситуации удовлетворяет нужному условию.

Необходимость. Предположим, что ситуация [Л-р-ра, «] включена в Vj{Xy... Х). Индукцией по числу ситуаций, ранее включенных в K(Xi.. .Х), докажем, что она допустима для

. Xf.

Базис, когда в K(Xi . .. Х,) еще нет ситуаций, доказывается просто. В этом случае [Л-р-Рд, и] включается в Vi,{Xy,,.Xi) на шаге (2а), так что Pt = Pi,- и Pi,P2> "] содержится а, kii • • • Х у). Таким образом, 5=*аЛш=:>гар1Х-р2г£; и i=Xi ... Х у. Следовательно, ситуация [Л--р.р, и] допустима для Xi...X,.

D доказательстве шага индукции рассуждение то же, что и

Пример 5.30. Вычислим каноническую систему множеств ЕК(1)итуаций для грамматики G, если соответствующая ей пополненная грамматика состоит из правил

S -SaSb S -в

Начнем с вычисления Ла = У(е). (Это сделано в примере 5.29.) Л,: [5--..5. е]

[S SaSb, е\а] [S е\а]

Затем вычислим СОТО{Ла, X) для всехХ€{5, а, Ь}. Обозначим GOTO(./.„ S) через Л. Тогда

Л: [5~S., е]

[S -S.ccSb, е\а]

Оба множества GOTO(,,o> ) и GOTO(-../(,, b) пусты, так как ни а, ни b не являются активными префиксами грамматики G. Далее надо вычислить GOTO{di, X) для Х{5, а, Ь}. Множества GOTO(v/j. S) и ООТО(Л„ Ь) пусты, а GOTO(j, а)==Л, где Л: [S -у SuSb, е а]

[S- SaSby a\b]

[S-a\b]

Продолжая в том же духе, получаем множества Л: [S~SaS-b, е\а]

[S~>SaSby a{b] Л. [S-Sa-Sb, a\b]

[S~y*SaSb, а\Ь]

[S-., a\b] Л\ [S-SaSby e\a\ Л\ [S-SaS-b, a\b]

lS~S*aSb, a\b] Л,\ {SSaSby a\b\

Функция GOTO изображена в виде табл. 5.4. Заметим, что множество GOTO(/, X) будет всегда пусто, если в каждой ситуации из Л точка расположена на правом конце правила. Здесь примерами таких множеств служат Л и Л-,.

Обращаем внимание читателя на сходство между функцией GOTO в табл. 5.4 и функцией переходов LR(l)-aнaлизaтopa для грамматики G, приведенной на рис. 5.9. □

ДЛЯ базиса, если ситуация [Л Pi-pg, п] включается в Vkii. - .Х) на шаге (2а). Если она включается на шаге (26), то р -в и найдется ситуация [В ~уАЬ, v], ранее включенная вl/jt(Xi.. .А",), причем W Р1К5Т(6и). По предположению индукции ситуация [В УЛЬ, v] допустима ДЛЯ Xj. . .х, так что существует вывод 5=?>;аВ1/=Ф;.ауЛбу, где ау = х...х-. Тогда

s Xj...XiAby =4>;Xi...XAzX...х-рг

где ы = FIRSTj(2). Следовательно, ситуация [А--pg, и] допустима для Xi ... X,. □

Алгоритм 5.8 дает метод построения множества LR(A)-CHTya-ций, допустимых для произвольного активного префикса. При построении правого анализатора для LR()-rpaMMaTHKH G нас интересуют такие множества для всевозможных активных префиксов грамматики G, а именно система Множеств допустимых ситуаций для G. Так как грамматика содержит конечное множество правил, то число множеств ситуаций тоже конечно, но часто бывает очень большим. Если у - активный префикс правовыводимой цепочки уш, то, как будет показано, К(у) содержит всю информацию о у, необходимую для продолжения разбора цепочки yw.

Приведем алгоритм, обеспечивающий систематический метод вычисления множеств LR()-CHTyaHHft для G.

Алгоритм 5.9. Система множеств допустимых LR(fe)-c и т у а ци й для G.

Вход. КС-грамматика G -(N, 2, Я, S) и целое число k. Выход. -{Л\Л= Ук{У) и Y - активный префикс грамматики G}.

Метод. Вначале система пуста.

(1) Поместить Vk(e) в . Множество Ун() вначале „не отмечено".

(2) Если множество ситуаций Л системы не отмечено, отметить Лу вычислив для каждого X (N U 2) значение QOTO{d, X) (мож1Ю с помощью алгоритма 5.8). Если множество .yGOTO(, X) не пусто и еще не включено В(, то включить его в of в качестве неотмеченного множества ситуаций.

(3) Повторять итаг (2) до тех пор, пока все множества ситуаций системы не будут-отмечены. □

Определение, Если G - КС-грамматика, то систему множеств допустимых ЕК(/г)-ситуаций для пополненной грамматики будем называть канонической системой множеств LR()-cHTyanHH для G-

Заметим, что множество G0T0(4, S) никогда не потребуется вычислять, так как оно всегда будет пусто.