Данный метод является наиболее простым, но трудоемким. Для любой продукции используемой грамматики с одинаковыми левыми частями перенумеруем правые части. A→α1 | … | αk и будем называть их альтернативами соответствующим нетерминалам. Т.к. для КС(контекстно-свободные) грамматик правая часть продукции может быть любой цепочкой терминальных и нетерминальных символов, до обозначений некоторых альтернатив α, так
α=x1, x2, x3 … xp; x1, x2, x3 … xp NUT
Замечание. Для упрощения метода предположим, что правая часть любой продукции не может быть пустой строкой.
Суть данного метода можно представить в виде следующей последовательности шагов, выполнение которых повторяется в процессе чтения входной цепи символов.
1. Определить корень дерева разбора и пометить его S N. Считать его активной вершиной.
2. Если активная вершина помечена некоторым нетерминированным символом A, то выбрать первую альтернативу этого нетерминированного α=x1, x2, x3 … xp и определить р новых вершин дерева разбора, являющихся непосредственно последовательностью вершины А, пометить их x1, x2, x3 … xp, соответственно (→) и сделать вершину х1 активной.
3. Если активная вершина помечена а T, то сравнить его с очередным символом входной цепочки.
Сравниваемые символы совпали, тогда сделать активной вершиной дерева (лист) правее а и перейти к следующим символам входной цепочки.
Символы не совпали, то выполним возврат к предыдущему уровню дерева разбора и соответствующему символу входной цепочки. Повторяя шаг 2 для следующего альтернативного нетерминала, если все альтернативы данного нетерминала исследованы, то возврат на более высокий уровень дерева и соответствующего символа и т.д.
4. Повтор пункта 2 и 3 до тех пор, пока не будет найден разбор входной цепочки или исследованы все возможные альтернативы.
Разбор завершён успешно если листья построенного дерева помечены терминальными символами и самый правый лист соответствует последнему символу входной цепочки. Замечание. Порядок нумерации альтернатив влияет на скорость работы метода. Пример.
S→E;
E→T+E | T;
T→i*T | i
Порождая арифметические выражения +, i, –, всегда завершаются « ; ».
Перенумеруем символы входной цепочки.
Это дерево показывает, что входная цепочка является цепочкой заданного языка и порождает следующие продукции грамматики: Замечание. Метод требует чтобы используемая КС грамматика не содержала продукции с левой рекурсией, т.е.:
т.к. это ведёт к зацикливанию метода.
Если бы в рассматриваемом случае грамматика содержала правила E→E+T, то Замечание. Существующий формальный алгоритм позволяет преобразовывать грамматику с левой рекурсией в эквивалентную ей грамматику без левой рекурсии. Замечание. Метод – учебный показывает идею, из-за его трудоёмкости на его базе разрабатывают практический метод разбора – метод рекурсивного спуска.
Исходники:
Опубликовал Kest
February 13 2010 07:51:56 ·
0 Комментариев ·
11404 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
