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

1. Задача разбора

Разбор сентенциальной формы означает построение вывода и, возможно

синтаксического дерева для нее. Программу разбора называют также рас-

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

мой грамматики. Именно это и является нашей задачей в данный момент.

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

тмами слева направо ввиду того, что они обрабатывают сначала самые ле-

вые символы обрабатываемой цепочки и продвигаются по цепочке только

тогда, когда это необходимо. Можно подобным способом определить разбор

справа налево, но он менее естественен. Инструкции в программе выполня-

ются слева направо, да и мы читаем слева направо.

Различают две категории алгоритмов разбора: нисходящий (сверху вниз)

и восходящий (снизу вверх). Их называют также разверткой и сверткой.

( В данном реферате будет рассмотрен процесс только нисходящего раз-

бора. ) Соотетственно, эти термины соответствуют и способу построения

синтаксического дерева. При нисходящем разборе дерево строится от корня

( начального символа ) вниз к концевым узлам. Метод восходящего разбора

состоит в том, что отправляясь от заданной цепочки, пытаются привести ее

к начальному символу. В качестве примера нисходящего разбора рассмотрим

предложение (1) в следующей грамматике целых чисел ( последовательностей,

состоящих из одной и более цифр ):

N ::= D | ND

D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1)

На первом шаге непосредственный вывод N => ND будет строиться так,

как показано в первом дереве на рис. 1. На каждом последующем шаге

самый левый нетерминал V текущей сентенциальной формы xVy заменяется

на правую часть u правила V ::= u, в результате чего получается сле-

дующая сентенциальная форма. Этот процесс для предложения (1) предс-

тавлен на рис. 1. в виде пяти деревьев. Фокус в том, конечно, что

надо получить ту сентенциальную форму, которая сопадает с заданной

цепочкой.

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 существуют правила

Z ::= X X .. X | Y Y .. Y | Z Z .. Z

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 ? В этом

i i i

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

i

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

i i-1

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

i-1

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать