Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

1 2 n 1 2 m 1 2 1

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

1 2 n

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

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

1 2 m

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

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

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

1 2 n

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

i 1 2 n i i

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

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

1 1 1 1

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

1 1

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

1

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

2

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

2 2 1 2

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

i-1 i

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

i i n

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

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