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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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