Категория
Информатика
Тип
реферат
Страницы
11 стр.
Дата
13.11.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21097.zip — 15.62 kb
  • algoritm-nisxodjashhego-razbora-nisxodjashhie-raspoznavateli_21097_1.rtf — 81.96 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

1
Губанов Губанов
1. Задача разбора
Разбор сентенциальной формы означает построение вывода и, возможно
синтаксического дерева для нее. Программу разбора называют также рас познавателем, так как она распознает только предложения рассматривае мой грамматики. Именно это и является нашей задачей в данный момент.
Все алгоритмы разбора, которые бутут здесь описаны называются алгори тмами слева направо ввиду того, что они обрабатывают сначала самые ле вые символы обрабатываемой цепочки и продвигаются по цепочке только
тогда, когда это необходимо. Можно подобным способом определить разбор
справа налево, но он менее естественен. Инструкции в программе выполня ются слева направо, да и мы читаем слева направо.
Различают две категории алгоритмов разбора: нисходящий (сверху вниз)
и восходящий (снизу вверх). Их называют также разверткой и сверткой.
( В данном реферате будет рассмотрен процесс только нисходящего раз бора. ) Соотетственно, эти термины соответствуют и способу построения
синтаксического дерева. При нисходящем разборе дерево строится от корня
( начального символа ) вниз к концевым узлам. Метод восходящего разбора
состоит в том, что отправляясь от заданной цепочки, пытаются привести ее
к начальному символу. В качестве примера нисходящего разбора рассмотрим
предложение (1) в следующей грамматике целых чисел ( последовательностей
,
состоящих из одной и более цифр ):
N ::= D | ND
D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1)
На первом шаге непосредственный вывод N => ND будет строиться так,
как показано в первом дереве на рис. 1. На каждом последующем шаге
самый левый нетерминал V текущей сентенциальной формы xVy заменяется



Ваше мнение



CAPTCHA