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

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

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. в виде пяти деревьев. Фокус в том, конечно, что

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

цепочкой.

NNNNN

||||

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

||||||||

NDNDNDND

||||

DDD5

||

33

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

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

вывода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Z ::= X X .. X

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