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. Нисходящие разбор с возвратами
    Алгоритм нисходящего разбора строит синтаксическое дерево, как уже
    было сказано, начиная с корня, постепенно опускаясь до уровня предло-
    жения, как было показано ранее. Описание усложняется главным образом
    из-за необходимости вспомогательных операций, которые необходимы гла-
    вным образом для того, чтобы выполнять возвраты с твердой уверенностью,
    что все возможные попытки построения дерева были предприняты.
    Чтобы свести осложнеия к минимуму, давайте опишем этот алгоритм раз-
    бора образно. ............