Каждый (правый) вывод ......

5=?>5=ФС=>аС=»йЬ для

в пополненной грамматике G[ имеет вид

SS=D=yaDac для г>0

Вернемся к определению ЬН(1)-грамматики и допустим, что есть выводы S=±>*aAw=yaf>w и 5=* y5x=>;.apf/. Тогда, так как -праволинейная грамматика, должно быть ей/ x= е. Если FIRSTi(e2) FIRSTi(f/), то у= е. Надо теперь показать, что аАуВ, т. е. а=у и Пусть В-б - правило, приме-

ненное при переходе от уВх к аВу. Нужно рассмотреть следую-ui,He три случая:

Случай I: A=S (т. е. вывод S*aAw тривиален). Тогда а -е и р = 5. Из вида выводов в Gl следует, что правовыводимую цепочку S можно вывести лишь одним способом; поэтому уе и В S, что и требовалось доказать.

Случай 2: А~С. Тогда р -либо аС, либо Ь. В первом случае должно быть В=С, так как только в правилах для С w S правые части оканчиваются символолт С. Если B = S, то из вида выводов в Gi следует, что у=е. Тогда уВфсф. Таким образом, можно заключить, что В = С, Ь = аС и у=а. Во втором случае ФЬ) должно быть В=С, потому что только для С существует правило, оканчивающееся символом Ь. Отсюда снова непосредственно следует, что у = а и ВЛ.

Случай 3: Л-/). Этот случай симметричен случаю 2.

Заметим, что G не является LL-грамматикой. П

Пример 5.25. Пусть Gg лами

-леволинеиная грамматика с прави-

ть 5с Аа\е Bale

Заметим, что /.(G)-L(Gi), где G - грамматика из предыдущего примера. Однако G не является LR(г)-гpaммaтикoй ни для какого k.

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

S=,S;Aab=c>rab

Эти два вывода удовлетворяют условию из определения LR(ft) грамматики при а= е, р=е, waJb, у = е и у=ас. Но таккак

заключение неверно, т. е. АфВ, то G -не LR(/;)-rpaMMaTHKa. Более того, так как LR(fe)-ycлoвиe нарушается для всех k, то - LR-грамматика. □

Грамматика из примера 5.25 ие обратима, и хотя мы знаем, где в правовыводимой цепочке расположена основа, но, если вне правого конца основы разрешается просмотреть только ограниченное число терминальных символов, мы не всегда знаем, свернуть ли первую основу, которая является пустой цепочкой, к Л или к В.

Пример 5.26. Ситуация, в которой нель.зя однозначно определить положение основы, встречается в грамматике G3 с правилами

SAB Л - - B-CD\aE Cab Dbb E-bba

G3-не LR(l)-rpaMMaTHKa. Это можно усмотреть, взяв два правых вывода в пополненной грамл-татике

5 => 5 = Л й =Ф ACD =Ф ACbb =Ф Aabbb

SSAB АаЕ Aabba

Если известен только первый символ цепочки нельзя определить, где в правовыводимой цепочке Aabw находится правый конец основы - между b п w (когда w = bb) или справа от Aab (когда w-ba). Заметим, однако, что Gg-LR (2)-грамматика. □

Можно дать неформальное, но наглядное определение LR(ft)-грамматики в терминах деревьев выводов. Грамматика G будет LR(г)-гpaммaтикoй, если, просмотрев только часть кроны дерева вывода в этой грамматике, расположенную слева от данной внутренней вершины, и часть кроны, выведенную из нее, а также следующие k терминальных символов, можно установить, какое Правило было применено к этой вершине. Например, рассмотрев цепочки UV и FlRST(,(t2/) на рис. 5,10, можно точно определить, акое правило было применено к вершине Л. В отличие от этого определение ЕЕ(/с)-грамматики говорит о том, что правило, примененное к Л, можно определить по цепочкам и и FIRSTj(l[2;).

Рис. 5.10. Дерево разбора.

пока не будет виден последний входной символ, b или с. В гл. 8 мы попытаемся сделать аргументацию такого типа более строгой, но, хотя интуитивно идея понятна, ее довольно трудно формализовать.

5.2.3. Следствия определения 1к(У)-грамматики

Теперь займемся теорией, необходимой для конструирования ЬН(й)-анализаторов.

Определение. Допустим, что 5 =>* аЛ[г=;> арЕй-правый вывод в грамматике G. Назовем цепочку у активным префиксом грамматики G, если у - префикс цепочки ар, т. е. у - префикс некоторой правовыводимой цепочки, не выходящий за правый конец ее основы.

Ядро ЬН(/г)-анализатора составляют таблицы. Они аналогичны LL-таблицам для LL-грамматик, которые по данной аванцепочке подсказывали нам, какое правило надо применить следующим. Для LR(fe)-rpaMMaTHKH каждая таблица соответствует некоторому активному префиксу. Таблица, соответствующая активному префиксу у, для данной аванцепочки, состоящей из k символов, сообщает о том, достигнут ли правый конец основы. Если да, то она сообщает также, какова эта основа н какое правило надо применить для ее свертки.

Здесь возникает несколько проблем. Так как цепочка у может быть сколь угодно длинной, то неясно, можно ли обойтись конечным множеством таблиц. ЕН(й)-условие говорит о том, что основу правовыводимой цепочки можно определить однозначно, если известен весь отрезок этой цепочки слева от основы, а также/г

Грамматика из примера 5.25 не была ГН(/г)-грамматикой, потому что по первым k символам а нельзя было определить, какое нз правил Л-* в и В-применялось для вывода пустой цепочки в начале всей входной цепочки. Это нельзя решить,

очередных входных символов. Поэтому ие очевидно, что основу всегда можно определить, располагая только фиксированным количеством информации о цепочке, предшествующей основе. Кроме того, если S=laAw=aftw и можно ответить на вопрос: Кончается ли некоторый правый вывод цепочки арг; правилом р?", то еще неясно, можно ли вычислить таблицы, соответствующие аЛ, по таблицам, соответствующим ар, способом, „реализуемым" на МП-преобразователе (или, быть может, каким-нибудь другим удобным способом). Поэтому таблицы должны содержать достаточно информации, чтобы по таблице, соответствующей ар, можно было вычислить таблицу для аЛ, если aAw=aftw. Итак, мы приходим к следующему определению.

Определение- Пусть G=(N, 2, P,S) - КС-грамматика. Будем называть [Л-»-р,.р2, и] LR{k)-ситуацией (для данных й и G, но эти параметры не будут явно указываться, когда это не может привести к недоразумениям), если Л -hK - правило из Р и иХ*. Будем говорить, что ЕН(/г)-ситуация [Лррз, и] допустима для активного префикса ар,, если существует такой вывод S=*aAw=i;>afiw, что и = ЩБТ{ы1).

Заметим, что может быть pi=e и для каждого активного префикса найдется хотя бы одна допустимая для него ЕН(/г)-ситуация.

Пример 5.27. Рассмотрим грамматику Gj из примера 5.24. Ситуация [С-*а*С, е] допустима для ааа, так как существует вывод S=*f.aaC =Ф,.аааС, т. е. в этой пришре а -аа и w= е. □

Обратите внимание на сходство данного здесь определения ситуации с тем, что встречалось раньше при описании алгоритма Эрли. Между этими двумя понятиями возникает интересная связь, если алгоритм Эрли применяется к ЬН(й)-грамматике (см. упр. 5.2.16).

Представление о ЕН(/г)-ситуациях, соответствующих активным префиксам гралшатики, дает ключ к пониманию того, как работает детерминированный правый анализатор для ЬН(й)-грамматики. В некотором смысле основной интерес для нас представляют ЕН(й)-ситуации вида [Лр., и], в которых точка находится на правом конце правила. Эти*ситуации указывают, какие правила можно применить для свертки правовыводимых цепочек. В основе LR(fe)-pa36opa лежат следующие определение и теорема:

Определение. Определим функцию EFF (а) так (далее мы опускаем k и/или G, если ясно, о чем речь):

(1) если а начинается терминалом, то EFF(a) FIRST.(a),

(2) если а начинается нетерминалом, то EFF(a) = {w\w\RST.{a) и существует вывод a=>*p=?>.[гл:, где р Лей/х для ЛN}.

Таким образом, EFF(a) включает все элементы множества FIRST(a), при выводе которых нетерминал, стоящий на левом конце цепочки, не заменяется пустой цепочкой е (иначе говоря в правом выводе из цепочки а, начинающейся нетерминалом иа последнем шаге не должно применяться е-правило).

Пример 5.28. Рассмотрим грамматику G с правилами

АВа\е

ВСЬ\С

Сс\е

Здесь FIRSTo(5) {е, а, Ь, с, ab, ас, Ьа, са, сЬ}, EFF2(S) {са, сЬ]. □ "

Напомним, что в гл. 4 излагался восходящий алгоритм разбора, который не работал для грамматик, содержащих е-правила. В случае LR(ft)-pa36opa е-иравила в грамматике разрешаются, но надо быть осторожным при „свертке" пустой цепочки к нетерминалу.

Мы увидим, что функция EFF помогает правильно устанавливать, когда пустая цепочка является основой, к которой надо прил1енить свертку. Сначала, однако, введем слегка видоизмененное определение LR(fe)-rpaMMaTHKH. Два вывода, входящие в это определеиие, фактически играют взаимозаменяемые роли, и, следовательно, пе теряя общности, можно считать, что основа цепочки во втором выводе простирается по крайней мере так же далеко вправо, как в первом.

Лемма 5.2. Если G=-(N, 2, Р, S) - пополненная грамматика, которая не является LR(k)-zpaMMamuKou, то суиествуют выводы 5;аЛ[г;,аР1£ и S;уВх,уЬх = ау, где FlRST;,(tc;)-FIRSTfc(f/) и уб>ар1, но уВхфаАу.

Доказательство. Согласно LR(ft)-oпpeдeлeнию, люжно найти выводы, удовлетворяющие всем нужным условиям, за исключением, быть может, условия у6ар. Допустим поэтому, что уб<ар. Покажем, что LR(ft)-ycлoвиe нарушается для другого примера, в котором уб играет роль ар в первоначальном условии.

Так как дано, что уЬхау и уб < ар, то для некоторой цепочки гЕ можно записать арубг. Таким образом, есть выводы

S =*гУх j.ybx

5 =>i а Aw apw = ybzw

Далее, цепочка z была определена так, что x = zy. Так как FlRST,(te;)=:-FlRST,(f/), то FIRST,(x) - FIRST,(ei). LR()-ycлo-вие, если оно выполняется, говорит, что aAw = yBzw. Поэтому отцепляя" от обеих сторон равенства w, получаем aA = yBz, а „прицепляя" в новом равенстве у, получаем yBzy = аАу. YIq zy = x, и, значит, мы показали, что аАу = уВх, а это с самого начала предполагалось ложным. Если сопоставить два приведенных выше вывода с LR(г)-ycлoвиeм, окажется, что они удовлетворяют условиям леммы (разумеется, надо подходящим образом переименовать цепочки). □

Метод LR(ft)-pa36opa основан на следующей теореме.

Теорема 5.9. Грамматика G = (N, 2, Р, S) является LR(ft)-грамматикой тогда и только тогда, когда для каждой цепочки н2** выполняется такое условие. Пусть afi - активный префикс правовыводимой цепочки ajw пополненной грамматики G. Если ЪЯ{к)-ситуация [Л-»-р., и] допустима для ар, то нет другой К{к)-ситуации [Л -* PiPa, у], допустимой для ар, причем hEFF(p2), (Заметим, чтомооюет быть пустой цепочкой е.)

Доказательство. Необходимость. Пусть [Л-р., w] и [Л-»-рр2, v\-две различные ситуации, допустимые для ар, т. е. в пополненной грамматике существуют выводы

S :*aAw=yaw S =>* аЛл: -zj. аррл;

причем FlRST(w) = u, FlRST(x) = y и apaiP. Кроме того, х=>иу для некоторой цепочки и в этом (возможно, пустом) выводе нетерминал на левом конце никогда не заменяется пустой цепочкой.

Мы утверждаем, что G не может быть LR(ft)-rpaMMaTHKoft. Чтобы доказать это, исследуем три случая: (1) pg е, (2) Рз€2+ и (3) Рз содержит нетерминал.

Случай 1: Если - е, то u = v и выводы имеют вид

S =\aAwaw 5=; аЛл: аДл:

где FI RST([2;) = FIRSTi(x) = u = v. Так как рассматриваемые LR(/г)-cнтyaции различны, то либо АфА, либо рр;. В любом случае нарушается LR(ft)-ycлoвиe.

Случай 2: Если раг для некоторой цепочки 2, то

5=>аЛ[г/=> aw S =i>* аАуХ

где apz-a.Pi и F\RSTk(zx) = и. Но тогда G-не LR(ft)-rpaMMa-

тика, так как aAzx не может совпадать с аЛ л:, если г2+.