Алгоритм Кока-Янгера-Касами

УНИВЕРСАЛЬНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

Общие методы синтаксического анализа

Синтаксический анализ с возвратами

Домашнее задание: Самостоятельно рассмотреть алгоритмы восходя­щего и нисходящего анализа с возвратами.

Метод работает следующим образом. Пусть - КС-грамматика без пустых правил (ВСЕХ!) в нормальной форме Хомского. Пусть - входная цепочка, которую нужно разобрать согласно грамматике . Суть метода состоит в построении треугольной таблицы разбора , элементы которой обозначим , где , . Значениями переменных будут подмножества множества , т.е. . Нетерминал тогда и только тогда, когда , т.е. когда из выводятся входных символов, начиная с позиции . В частности, входная цепочка тогда и только тогда, когда .

Дата добавления: 2014-01-07