Заметим, что D вызывается, когда не оба вызова В и С оказались успешными. В дальнейшем мы исследуем другую систему разбора, в которой D вызывается только тогда, когда вызов В оканчивается неудачей. Заметим, что если S и С привели к успеху, то альтернатива D не вызывается. Эта особенность отличает ЯНРОВ-программу от общего алгоритма нисходящего разбора из гл. 4.

С операторалш вида А-*-а, А=е и Л=/ обращаются так:

(1) Если есть правило Л -а, в котором а 2, и Л вызывается для цепочки, начинающейся символом л, то цепочка а подходит Л, и Л сообщает об успехе. В противном случае А сообщает о неудаче.

(2) Если есть правило А-е, то вызов А всегда успешен и пустая цепочка всегда подходит Л.

. (3) Если есть правило Л-+f,To вызов Л всегда оканчивается неудачей.

Определим формально, как нетерминал «действует на входную цепочку».

Определеиие. Пусть Р -(2, Г, R, 5) -ЯНРОВ-программа. Зададим отношения между нетерминалами и парами вида {х.\у, г), где X и у-цепочки из 2*, а г - либо s (обозначает успех), либо f (обозначает неудачу). Метасимвол f используется для указания позиции текущего входного символа. Индекс Р будем опускать всюду, где можно.

(1) Если Л-

(2) Если Л

(3) Если А

-eR, то Лг1(йу, s) для всех шИК f€R, то Л=>(ау, /) для всех w2\ aR и fl2, то

(а) Az{a\ Ху s) для всех х € 2*;

(б) Л :г>*(, /) для всех 2* (включая е), не начинающихся с а.

(4) Пусть A~BC/DR. Тогда

(а) Л r>»+"+4-t. s), если

(i) B=>"(t£/Z, S).

(ii) С:г>"(£/г, s);

(б) Alu\v, s) для t=m-f/г-Ьр4-1, если

(i) B{x]y, 5),

(ii) С =>"(!(/, /),

(iii) D=(uv, s), где uv = xy\

(в) А=Ц\ху, f) для im + n-bp+l. если

(i) В=>"Чху, s),

(ii) CzMtf/, /).

(iii) D=>p{Uy, /);

17» 515

где л, в, с и D-нетерминалы, а а-терминал, пустая цепочка или специальный символ f (обозначающий неудачу).

Определение. ЯУРОВ-программой Р называется четверка (N, 2, R, 5). где

(1) N и 2 - конечные непересекающиеся множества нетерминалов и терминалов,

(2) R - последовательность ЯНРОВ-операторов, содержащая для каждого Л N не более одного оператора с левой частью Л (слева от стрелки),

(3) - начальный символ.

ЯНРОВ-прохрамму можно связать с грамматикой в специальной нормальной форме. Оператор вида Л -BC/D соответствует двум правилам Л - ВС и Л D, из которых первое всегда испытывается первым. Оператор вида Л-*а соответствует правилу Л->а, когда а2 или а = е. Если a = f,To нетерминал Л имеет специальный смысл, который мы разъясним позже.

ЯНРОВ-программу можно описать иначе как множество процедур (нетерминалов), вызываемых рекурсивно для некоторых входных цепочек в качестве аргументов. Выходом, или результатом, вызова нетерминала будет либо неудача (ни одни префикс входной цепочки не подходит данному нетерминалу), либо успех (некоторый префикс входной цепочки подходит ему).

Результатом вызова оператора вида Л BC/D для входной цепочки W будет следующая последовательность вызовов процедур:

(1) Сначала Л вызывает В для входной цепочки w. Если wxx и цепочка х подходит нетерминалу S, то В сообщает об успехе, т. е. результатом вызова Д будет успех. После этого А вызывает С для цепочки х.

(а) Если xyz н у подходит С, то С сообщает об успехе. Тогда Л тоже сообщает об успехе и о том, что ему подходит префикс ху цепочки w.

(б) Если никакой префикс цепочки х не подходит С, то С сообщает о неудаче. Тогда Л вызывает D для цепочки W. Заметим, что в этом случае успех вызова В аннулируется.

(2) Если А вызывает В для цепочкн w и оказывается, что никакой префикс цепочки w не подходит В, то В сообщает о неудаче. Тогда Л вызывает D для цепочки w.

(3) Если D был вызван для wuv и цепочка и подходите, то D сообщает об успехе. Тогда Л тоже сообщает об успехе и о том, что ему подходит префикс и цепочки w.

(4) Если D был вызван для цепочки w и никакой префикс цепочки w ему не подходит, то D сообщает о неудаче. Тогда А тоже сообщает о неудаче.

17* А, Ахо, Дж. УльмаН, т. 1

Возвращаясь теперь к вызову 5, вндим, что оба вызова Л и В успешны. Таким образом, цепочка aba подходит 5, и 5 со-обсЦает об успехе. Учитывая (4а), пишем S" {аЬа\, s). Поэтому abaL(P).

Нетрудно показать, что Ь{Р)-аЬ*а + Ь. □

Каждая ЯНРОВ-программа обладает одним важным свойством, а имение: ее результат для данного в.чода однозначен. Это до-. называет следующая лемма,

Лемма 6.1. Пусть P=-(N, 2, R, 8) - ЯВРОВ-проерамма, для которой Л="(л:1г/1, и Л =:>«>(x,t.- Гз), где Л€N, ад = = ЗД = г€2*. Тогда хх, УгУ ti гг-

Доказательство. Доказательство проводится простой индукцией по меньшему из чисел п и п. Без потери общности будем считать, что пп-:

Базис. «1 = 1. Применяется одно из правил Л->а, А~е или A~-*f. Отсюда сразу получаем нужное утверждение.

Шаг индукции. Допустим, что утверждение верно для/г < п, причем «1 > I. Пусть для Л есть-правило Л -BC/D. Допустим, что A"{Xi]yi, fl) для г=1 и ( = 2 получено в силу (4) нз B"(Ul\Vi, /,.) и (возможно) С (wjffЬ Q и/или D=»/ (Uivl, ti). Тогда mi<n£, так что, .применяя предположение индукции, заключаем, что пМа, fita " h = Рассмотрим отдельно два случая, зависящие от значения /j.

Случай 1: ti = t = f. Так как /г, то ulul vlvl и tl-tl. Поскольку в данном случае X/ = wJ, и fiti для

и г = 2, получаем нужный результат.

Случай 2: ti = ts. Тогда ulviv,- для ( = 1 и /==2. Так как ki<ni, то wl = w.2, v[ = v -и ([t.- Ест t[s, то XiUiUi, y.-vi и rs для il и i = 2; нужное заключение, таким образом, получено. При t[ = f рассуждаем для ui и итак же, как в случае 1. □

Отметим, что ЯНРОВ-программа не, обязана давать результат для каждой входной цепочки. Например, каждая программа, содержащая правило S-SS/S, где 5-начальный символ, не распознает ни одной цепочки (точнее, для иее отношение =Ф* пусто).

Представление ЯНРОВ-программ, которым мы пользовались до сих пор, выбрано для удобства изложения. На практике желательно иметь правила более общего вида. Для этого введем расширенные ЯНРОВ-правила и определим их смысл в терминах прежних правил:

(г) A:=»"-{xt у, S), если

(i) B:4Uy, /).

(ii) D:»(xti/, s);

(д) л =>«+«-1(х, /), если

(i) Bitx, f),

(ii) D-{\x, f).

(5) Отношение выполняется только в случаях, оговоренных в (1)-(4). «

Пункт (4а) учитывает тот случай, когда В и С оба приводят к успеху. В (46) и (4в) В успешен, но С неудачен. В последних четырех случаях вызывается D, и это оканчивается либо успехом, либо неудачей. Заметим, что число у стрелки указывает количество «вызовов», сделанных до того, как получен .результат. Еще отметим, что если Л (х у, f), то х - е, т. е. в случае неудачного вызова входной указатель переставляется туда, где оп находился перед вызовом.

Положим Л [х 1 у, г) тогда и только тогда, когда Л="(л:£/, г) для некоторого п1. Языком, определяемым программой Р, назовем множество LiP) = {w\S =:> (w \, s) и w 6 2*}.

Пример 6Л. Пусть P-({S, Л, В, С}, {а, &}, R, S} -ЯНРОВ-

программа, где R состоит из операторов

SAB/C А-а ВСВ/А С~Ь

Исследуем поведение программы Р на входной цепочке aba, используя введенные выше обозиачения. Вначале, благодаря правилу S-AB/C, S вызывает Л для цепочки аЬа.А распознает первый входной символ и сообщаетоб успехе. Учитывая (3) предыдущего определения, можно писать Л z>i (а ba, s). Далее S вызывает В для цепочки Ьа. Так как для В есть правило В~СВ/А, нужно заняться поведением С на цепочке &а. Оказывается, что b подходит С, так что С сообщает об успехе. В соответствии с (3) пишем C.z:{b\a, s).

Затем В рекурсивно вызывает себя для цепочки а. Однако С терпит неудачу на а, и потому С z=;> а, f). Тогда В вызывает Л для цепочки а. Так как а подходит Л, то Л i(at, s). Так как вызов Л успешен, то второй выаов В тоже успешен. В соответствии с (4г) пишем В-:(а\, s).

Возвращаясь к первому вызову В для цепочки Ьа, замечаем, что, так как вызовы С и S успешны, этот вызов В тоже успешен, н в соответствии с (4а) пишем В-=(Ьа\, s).

(1) Правило Л->-ВС заменяет два правила A-BCjD и D-где D-новый символ.

(2) Правило Л-В/С заменяет правила ABD/C и D-e.

(3) Правило А-у В заменяет правила А- ВС и С-е.

(4) Правило А--А-уА ... Л, для пу2 заменяет множество правил A-ABi, ВАВ, • •В„ ~А„ В„,

(5) Правило Л-ccj/aa/.. ./а„, где aj--цепочка нетерминалов, заменяет множество правил Л-i-BjC, С-BjCy С„ з--» B„JC , C„ jS„ i/S„ и Sj-a,, Sa-a, .,S„-a„. Если n - 2,. это множество состоит иЗ правил Л -у В-/В,

-а и В-а. Для lin в случае а- = 1 можно положить Bi==ai и исключить правило В-а-.

(6) Правило Л-j-aj/otg/.. ./а„, где а,- -цепочка нетерминалов и терминалов, заменяет множество правил Л ~>txJa!j.. ./ajj и Х-а для каждого терминала а, где - цепочка сс/, в которой каждый терминал а заменен нетермийалом Х.

Начиная с этого момента мы будем допускать включение в ЯНРОВ-программы расширенных правил указанного типа. Приведенные выше определения позволяют механически строить эквивалентную ЯНРОВ-программу, удовлетворяющую первоначальному определению.

Эти расширенные правила имеют естественный смысл. Например, если для Л есть правило ЛУ1К2 ... К„, то вызов Л успешен тогда и только тогда, когда вызов Yt успешен в той входной позиции, где был сделан вызов Л, вызов успешен там, где закончился вызов К, вызов Kg успешен там, где закончился вызов У, и т. д.

Аналогично, если для Л есть правило Аajaj.../а„, то вызов Л успешен тогда и только тогда, когда достигает успеха там, где вызван Л; либо когда приводит к неудаче, но ccj достигает успеха там, где вызван Л, и т. д.

Пример 6.2. Рассмотрим расширенную ЯНРОВ-программу Р = ({£, £, Г}, {а, (,), где R состоит из правил

E-T-j-E/T

T-FT/F

F-(E)/a

Читателю предлагаем убедиться в том, что L{P)=L{G), где G(,-наша стандартная грамматика для арифметических выражений.

Чтобы привести Р к стандартной форме, сначала, применяя (6), введем новые нетерминалы Х, Х, Х, Х+ и X*. Правила станут

такимк:

Е-Г-F-

х>-

->ТХ.,Е/Т FXT/F ХЕХ/Ка

Согласно (5), первое правило заменяется правилами Е В ГХуЕ. Учитывая (4), .заменяем Blc. Ву-ТВ. и В.ХЕ.

ламн

TBJD, няется иа Е-* ство правил

E/D и и С-

прави-

Затем заменяем их на Правило EBJT заме-

е. В результате получим множе-

~XJ/D

BfilXa X,B,lD EXD

Для простоты мы отождествили с нетерминалом С каждый нетерминал X, для которого получается правило Х-е, и с нетерминалом D каждый К, для которого V-□

Всякий раз, когда ЯНРОВ-программа распознает цепочку оу, можно сверху вниз построить „дерево разбора" этой цепочки, прослеживая последовательность ДНРОВ-операторов, выполняемых при распознавании т. • Внутренние вершины этого дерева соответствуют нетерминалам, вызываемым в ходе выполнения программы и сообщающим об успехе.

Алгоритм 6.]. Дерево разбора, соответствующее выполнению ЯНРОВ-п р о г р а ммы.

Вход. ЯНРОВ-программа P = {N, 2, Р, S) и такая цепочка we*, что 5=>"(йУ t, S).

Выход. Дерево, разбора цепочки w.

Метод. Ядро алгоритма образует рекурсивная процедура стройдерево, которая по утверждению вида Л =ф" (л: ,5) (это ее аргумент) строит дерево с корнем, помеченным Л, и кроной х. Вначале эта процедура вызывается для утверждения S=*(w],s).