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

цепочкой.

N N N N N

| | | |

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

| | | | | | | |

N D N D N D N D

| | | |

D D D 5

| |

3 3

N => N D => D D => 3 D => 3 5

Рис. 1. Нисходящий разбор и построение

вывода

2. Нисходящие разбор с возвратами

Алгоритм нисходящего разбора строит синтаксическое дерево, как уже

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

жения, как было показано ранее. Описание усложняется главным образом

из-за необходимости вспомогательных операций, которые необходимы гла-

вным образом для того, чтобы выполнять возвраты с твердой уверенностью,

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

Чтобы свести осложнеия к минимуму, давайте опишем этот алгоритм раз-

бора образно. Вообразим, что на любом этапе разбора, в каждом узле уже

построенной части дерева находится по одному человеку. Люди, которые

находятся в терминальных узлах, занимают места соответственно символам

предложения.

Некоему человеку надлежит провести разбор предложения x. Прежде все-

го ему необходимо отыскать вывод Z => +x, где Z - начальный символ; сле-

довательно первым непосредственным выводом должен будет быть вывод

Z => y где Z ::= y - правило. Пусть для Z существуют правила