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

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

i

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

i i-1

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

i-1

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

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

i-1

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

i-2

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

1

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

1 2 n

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

1 m

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

1

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

1 2 i-1

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

1 2 i-1 i

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

i

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

неудаче.

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

1 1