./\.

а С в 5

Рнс. 6.1. Построение дерева разбора с помощью ЯН РОВ-программа.

Этот метод трансляции подобен синтаксически управляемой трансляции для контекстно-свободных грамматик. О нем еще будет идти р.ечь в гл. 9.

Корректность алгоритма 6.1 нельзя „доказать", потому что, как уже говорилось, он сам служит конструктивным определением дерева разбора, порождаемого ЯНРОВ-программой. Однако-легко показать, что кроййй этого дерева является входная цепочка. Индукцией по числу вызовов процедуры стройдерево можно показать, что если она вызывается для аргумента А=" (xfy, s), то результатом будет дерево с кроной х.

Некоторые из успешных результатов будут аннулированы. Иными словами, когда Л =Ф"(х1/2, s) и есть правило A-BC/D, может оказаться, что 5=" (х j yz, s), но С=Ф" (yz, /). Тогда-соотношение В- (xf yz, s) и все успешные шаги, с помощью которых оно было построено, иа самом деле не включаются в определение дерева разбора входной цепочки (не считая самого отрицательного результата). Эти успешные шаги не отражены в дереве разбора, как и вызов процедуры стройдерево для аргу-

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

Процедура стройдерево: Пусть Л -вход проце-

дуры.

(1) Если для Л есть правил© Л-*я Или Л-ё, то построить вершину с меткой А н для нее одног© ирямог© потомка, поме- -j ченного а или е соответственно. Остановиться.

(2) Если для Л есть правилр A-BC/D и х можно представить в виде ххх, такчто В{х xyyS) и С (Хд fs), то построить вершину, пвмеченную Л. Вьшолнить процедуру стройдерево для аргумента В= (х xy,s)y а затем для аргумента С=Ф" (Ха t y,s). Присоединить получившиеся при этом деревья к вершине, помеченной Л, так, чтобы корень дерева, получйвшегося в результате первого вызова, етал левым прямым-потомком этой вершины, а корень второг© дерева-правым. Остановиться.

(3) Если для Л есть правил® Л-+ВС/£>, н© (2) не выполняется, то должно быть О (xt/у,s). Вызвать процедуру стройдерево для этого аргумента и сделать корень получившегося дерева единственным потомком уже построенной вершины с меткой Л. Остановиться. □

Заметим, что процедура стройдерево вызывает вебя {рекурсивно только для меньших значений т, так что алгоритм 6.J должен в конце концов остановиться.

Пример 6.3, С помощью алгоритма 6.1 построим дерево разбора, порождаемое ЯНРОВ-программой Р из примера 6.1 для входной цепочки-aba.

Вначале вызовем процедуру стройдерево для утверждения .5=Ф(аЬа, s)b качестве ее аргумента. Правило 5ЛВ/С приво дпт к успеху, потому что Л и S успешно распознают цепочки а и Ьа соответственно. Затем вызовем эту процедуру дважды: сначала для аргумента Л (а f, s), а потом для аргумента В (6аf, s). Таким образом, построение дерева начнется так, как показано ,на рис. 6.1, а. Вызов Л для а сразу приводит к успеху, поэтому к вершине Л присоединяется одни прямой потомок, помеченный а. В приводит к успеху, потому что есть правило б-»-СЙ/Л и нетерминалы С н В приводят к успеху для а н b соответственно. Таким образом, предыдущее дерево вырастет до дерева, показанного на рис. 6.1,6.

С сразу приводит К успеху для &, так что вершина, помеченная С, получит одного потомка, помеченного Ь. Вызов В успешен для а, поскольку успешен вызов Л, так что В получает прямого потомка, помеченного Л, а он в свою очередь-потомка, помеченного а. Все дерево показано на рис. 6.1, е. □

Заметим, что если множество ЯНРОВ-правил трактуется как программа разбора, то всякий раз, когда нетерминал сообщает 520

Доказательство. Допустим, что М удовлетворяет лемме 6.2. Построим такую, расширенную ЯНРОВ-программу P(N, 2, R, 5), что X(P)=LM). Множество нетерминалов N состоит из

мента B="{xfyz,s). Но в него включаются все успешные шаги, которые в конечном счете приводят к успешному распоз* наванию входной цепочки.

6.1.2. ЯНРОВ и детерминированные КС-языки

Может оказаться довольно трудным установить, какой язык определяет ЯНРОВ-программа. Чтобы дать представление об определяющей силе ЯНРОВ-программ, докажем, что каждый детерминированный КС-язык с концевым маркером распознается некоторой ЯНРОВ-программой. Кроме того, существует тесная связь между деревьями разбора, порождаемь1Ми этой программой, и деревьями выводов в „естественной" КС-грамматике для этого языка, которая строится по соответствующему ДМП-автомату так, как описано в лемме 2.26. Лемма 6.2 позволяет упростить представление ДМП-автомата, используемое в этом разделе.

Лемма 6.2. Ясли Ь=Ь{Му) для ЩАП-автомата М, то L = Lg(M) для Ц,Ш1-автомата М, который на каждом своем шаге может увеличить длину магазина не более чем на 1.

Доказательство. Доказать это утверждение было предложено еще в упр. 2.5.3. Говоря неформально, надо вместо шага, заменяющего Z цепочкой ... для й > 2, сделать шаги, заменяющие Z на УХ/, У на У-±Х у, ..., К4 на УХ и Кз иа ХуХ. Все К,--это новые магазинные символы, причем верх магазина расположен слева. □

Лемма 6.3. Если L - детерминированный КС-язык и $-новый символ, то L$ = Lg(Al) для некоторого ]ХМП-автомата М.

Доказательство. Доказательство получается простой, модификацией доказательства леммы 2.22. Пусть. L = L (Mj). Тогда М моделирует храня в конечной памяти своего управляющего устройства очередной входной символ. Если переходит в заключительное состояние и $-очередной входной символ, то М стирает содержимое магазина. Так как никаких других шагов не требуется и они невозможны, то М-детерминированный МП-автомат. П

Теорема 6.1. Пусть M = {Q, 2, Г, 6, j,, Z, F)-ЛМП-аето-мат и EEg(М). Тогда существует такая ЯЮВ-программа Р, что Е-Е [Р).

(1) симйЬла S, .

(2) символов вида [qZp], где q, pQ.u ZTf

(3) символов вида [qZp], где q, Z н р tq же, что и в (2), и а2.

Идея состоит в том, что вызов нетерминала [qZp] успешен и приводит к распознаванию цепочки ш тогда и только тогда, когда {q, W, Z) Нм(р, е, е), а при всех других условиях, включая случай (q,w,Z)\-* {р,е,е) для, некоторого рФр, вызов [qZpl оканчивается неудачей. Вызов нетерминала [qZp] распознает цепочку W тогда и только тогда, когда {q, aw, Zj [-* [р, е, в). Правила (операторы) программы Р определяются так:

(1) Для 5 есть правило S-lq,Z,q,]/[q,Z,q,]/,, ./[q,Z,qfJ, где 0 ?!> - у qk-все состояния множества Q.

(2) Если б {q, е, Z) = [р, е), то для [qZp] есть правило [qZp]e, и для каждого рфр есть правило [qZp]f.

(3) Если 6{q, е, Z)ip, X), то для каждого [qZr], где rQ, есть правило [qZr]~-f[pXr].

(4) Если 8{q,e,Z) = {p,Xy), то для каждого [Zr], где rQ, есть правило [qZr][pXq,][q,yr]/[pXq,][q,yr]/., ./[pXqf,][qiyrl где q, . . qij-все состояния множества Q.

(5) Если 6{q, e,.Z)0, то пусть а, сг-символы из 2, для которых b{q,a, Z)=0. Тогда для каждого [q, Z, г], где г е Q, есть правило [qZrJ-a [qZr]aJa [qr]aj.. Ja [qZr\. Если /0, то правило имеет вид [qZr]-f.

(6) Если b{q, а, Z) = {p,e) для а2, то есть правило [qZp]-e и для рфр.есть правило [qZp]~->-f.

(7) Если 6(9,a,Z) = (p, X), то для каждого rQ есть правило [qZr]~[pXr].

(8) Если 6lq,a,Z)=={p,Xy), то для каждого rQ есть правило [qZr],~[pXq,]lq,yry[pXq,][q,yr]/.../[pXJ[?дКг].

Заметим, что так как автомат М детерминЦрованный, то эти. определения непротиворечивы; дл-я каждого нетерминала из N есть не более одного правила. Докажем утверждения:

(6.1.1) [qZp]=+ {w\ x,s) для любой цепочки х тогда и только тогда, когда {q,wx,Z)\--{p,x,e).

(6.1.2) Если {q,wx,Z)[- ip,x,e), то [qZp]:= {twx,f) для всех р Фр.

Докажем одновременно (6.1.2) и достаточность условия в (6.1.1) индукцией по числу шагов, сделанных автоматом М при переходе из конфигурации {q,wx,Z) в конфигурацию (р, л;, е). Если сделан один шаг, то b{q,a,Z) = {p,e), где а-это либо е, либо первый символ цепочки wx. В соответствии с (2) или (5) и(6) [qZp] + (а t г/, S), Tmay = wx,iA [qZp] =Ф+ ( f /) для всех рфр. Базис доказан.

[qXp]. Тогда <По- По пред-

Случай J: Для [Zp] . есть правило [qZp]~ 6{q, е, Z)={q\ X) и [?ад=Ф"(шх,8), где fii положению индукции (q\ шх, Х)\-- (р, х, е). Поэтому {q, wx, Z) - iP, X, е).

Случай 2: Для [Zp] есть правило [qZp]~-[qXqQ][qYpy... • • ./[qXqkllqkyp] Тогда w = wvi/ и дли некоторого р/ имееМ: [qXp]="{wisfx,s) и [pyp]:="iwtx,s), те vt меньше п,,. По предположению (£7,шЛ, ХУ) j-+ (:?,Wjc, У)\~-{р,х,е) В силу (4) б(, е, Z) = {q\Xy). Поэтому [q, wx, Z)\-- {р, х, е).

1) Счет шагов должен вестись после перехода от расширенных правил к правилам первоначального вида.

Предположим, что нужный результат верен для любого числа шагов, меньшего числа шагов, потребовавшегося при переходе из конфигурации (д, wx, Z) в (р, х, е). Пусть цу~аа;для неко-; торого ali\}{e). Тогда надо рассмотреть два случая.

Случай 1: Первый шаг-это (q, wx, Z)\-{q\ wx, X) для некоторого ХТ. По предположению индукции [qXp]=-(w*х, s) и lqZp]=i>+{wx,f) для рфр. Поэтому в силу (3) и (5), (7) [qXp]:=i>-.{wtx,s}H[gXp]=-ifwxJ) для всех рфр\ Аш строгого доказательства этих утверждений нужно сначала преобразовать расширенные правила программы Р в правила исход-i ного типа.

Случай 2: Для некоторых, УТ, предполагая, что w =yjjf,-имеем (, WX, Z) [~ [q\ wx, ХУ) {q\ w"x, У\ \~- {р, х, ё), где между конфигурациями {q\wx, ХУ) и (q*, w"x, У) магазин всегда содержит по крайней мере два символа. По предположениюии-дукции [qXq"]:: {y\w"x, s)vi [qYp]= {xsf\х, s). Кроме того, если р фд\ то [qXp*]- {\wx, f). Допустим сначала, что а Если взглянуть на (4) и воспользоваться определением расширенных ЯНРОВ-операторов, то окажется, что каждая последовательность вида [дР][рУр\ приводит к неудаче при рфсС. Однако, \ gX(i\\(fYp\ приводит к успеху, н потому, как и хотелось," [2!?] =ф+ (ш \ x,s).

Далее" заметим, что если рФр, то [(?К/з]=?>+(fo/x,/), и Потому все пары [qyp][pYp] приводят к неудаче. (Если р" Ф<(, то. к неудаче приводит \qXp"\, а если р\ц\ то к неудаче приво-. дит [j[7"Kp].) Таким образом, \qZp\(\wx,\) для рФр.Слу чай исследуется аналогично с помощью (5) и (8).

Теперь нужно доказать необходимость условия в утверждении (б.Ы). Если [qZp]=+ (wfx,s), то lqZp]="{Wix,s) для некоторого п). Докажем наше утверждение индукцией по п. Если то нужно применить (2) и. результат получится эле-

ментарно. Допустим, что ои верен для п<По, и пусть [qZpl= (t.s).

- *

Случай 3: Правило для [qZp] определяется в (5), т. е. б (9, е, Z) = 0. Тогда не может быть йУ = е, и потому пусть w=-aw\ Если для нетерминала [qZp] есть правило [qZph-то мы знаем, что 6(9, а, Z) = (p, е) и, следовательно, w =е, w - avi (q, W, Z)\-~{p, е). Ситуации, в которых правило для [qZp] определяется в (7) или (8), рассматриваются аналогично случаям 1 и 2 соответственно. Соответствующие рассуждения мы опускаем.

Чтобы завершить доказательство теоремы, заметим, что 5=Ф+(йУ, s) тогда и только тогда, когда [qZf,p]= {wU s) для некоторого р. Из утверждения (6.1.1) следует, что [qoZp] =>* (w t,s) тогда и только тогда, когда ((,< » о) Н"*" (Р» Таким образом,-L (Р) =L,(M). П

Следствие. Если L -детерминированный КС-язык и новый символ то Ь$-язык, распознаваемый ЯНРОВ-программой.

Доказательство. Получается из леммы 6.3. □

6.1.3. Обобщенный ЯНРОВ

Заметим, что если в ЯНРОВ-программе есть , оператор Л-уВС/D, то D вызывается, если либо 5, либо С терпит неудачу. Не существует способа передавать управление по-разному, когда В терпит неудачу и когда В приводит к: успеху, а С-к неудаче. Чтобы преодолеть этот недостаток, определим другой язык разбора, который назовем ОЯНРОВ, т. е. обобщенный язык нисхрдящего разбора с ограниченными возвратами. Программа, написанная на этом языке, представляет собой последовательность операторов видов

(1) A~B[C,D]

(2) Л -а {3) А-е (4) Л-/

Интуитивный смысл оператора Л-г*-Л [С, О] заключается в том, что если вызывается нетерминал Л, то он Вызывает В. Если В приводит к успеху, то вызывается, С. Если В терпит неудачу, то £) вызывается в той входной позиции, где был вызван Л. Результатом вызова Л является результат вызова С или D смотря по тому, какой из этих нетерминалов был на самом деле вызван. Заметим, что это соглашение отличается от того, которое было принято для оператора Л-BC/D, где D вызывается тогда, когда В приводит к успеху, но С терпит неудачу.

Операторы типов (2)-(4) имеют тот же смысл, что и в ЯНРОВ-программе.