Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Алгоритм нисходящего разбора. Нисходящие распознаватели" Страница 2

(Назад) (Cкачать работу)

1 2n1 2m1 21

Сначала человек пытается определить правило Z ::= X X .. X . Если

1 2n

нельзя построить дерево, используя это правило, он делает попытку приме-

нить второе правило Z ::= Y Y ... Y . В случае неудачи он переходит к

1 2m

следующему правилу и т.д.

Как ему определить, правильно он выбрал непосредственный вывод

Z => X X .. X ? Заметим, что если вывод правилен, то для некоторых

1 2n

цепочек x будет иметь место x=x x .. x , где X => *x для i=1,...,n.

i1 2nii

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

M , который должен будет найти вывод X =>*x для любого x , такого,

1111

что x = x ... Если сыну M удастся найти такой вывод, он (и любой из

11

сыновей, внуков и т.д.) закрывает цепочку x в предложении x и сообща-

1

ет своему отцу об успехе. Тогда его отец усыновит M , чтобы тот нашел

2

вывод X => *x , где x = x x ... и ждет ответа от него и т.д. Как толь-

221 2

ко сообщил об успехе сын M,он усыновит еще и M , чтобы тот нашел

i-1i

вывод X => *x . Сообщение об успехе, пришедшее от сына M , означает

iin

что разбор предложения закончен.

Как быть, если сыну M не удается найти вывод X =>*x ? В этом

iii

случае M сообщает о неудаче своему отцу; тот от него отрекается и

i

дает старшему брату M ,Mтакое распоряжение: "Ты уже нашел вывод,

i i-1

но этот вывод неверен. Найди-ка мне другой". Если Mсумеет найти

i-1

другой вывод, он вновь сообщит об успехе, и все продолжится по-пре-

жнему. Если же Mсообщит о неудаче, отец отречется и от него, и

i-1

тогда уже старшего брата M, попросят предпринять еще одну попыт-

i-2

ку. Если придется отречься даже от M , значит, непосредственный вы-

1

вод Z => X X .. X был неверен, и человек, начинавший разбор, попы-

1 2n

тается воспользоваться другим выводом Z => Y .. Y .

1m

Как же действует каждый из M ? Положим, его целью является тер-

1

минал X . Входная цепочка имеет вид x=x x ..xT.. ,где символы в

1 2i-1

x ,x ,...,xуже закрыты другими людьми. M проверяет, совпадает

1 2i-1i

ли очередной незакрытый символ T с его целью X . Если это так, он

i

закрывает этот символ и сообщает об успехе. Если нет, сообщает об

неудаче.

Если цель M - нетерминал X , то M поступает точно так же, как

11

и его отец. Он начинает проверять правые части правил, относящихся к

нетерминалу, и, если необходимо, тоже усыновляет или отрекается от

сыновей. Есливсе его сыновья сообщают об успехе то M в свою очередь

i

сообщает об успехе отцу. Если отец просит M найти другой вывод, а це-

i

лью является нетерминальный символ, то M сообщает о неудаче, так как

i

другого такого вывода не существует. В противном случае M просит своего

i

младшего сына найти другой вывод и реагирует на его ответ также, как и

раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче свое-

му отцу.

Теперь, наверное, понятно, почему этот метод называется прогнозиру-

ющим или целенаправленным. Используется и название "нисходящий" из-за

способа построения синтаксического дерева. При разборе отправляются от

начального символа и нисходят к предложению (см рис. 2)

Z

|

*---*-------*

|||

F|T

|||

T|

||

F|

||

i+i*i

Рис. 2. Частичный нисходящий разбор предложения i+i*i.

Похожие работы