Нисходящий синтаксический анализ

Алгоритм левой факторизации

Вход. КС-грамматика.

Выход. Эквивалентная левофакторизованная грамматика

Алгоритм.

Для каждой переменной находим самое длинное начало строки , общее для двух или более правых частей.

Если, заменим все правила вида , где - представляет все варианты, не начинающиеся с , правилами

Здесь - новая переменная.

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

Метод рекурсивного спуска (с откатом)

- указатель входной строки (input pointer) – указывает на текущий символ входной строки.

может быть возвращен к уже прочитанной части входной строки, чтобы произвести повторный просмотр входной строки.

В начале анализа указывает на первый символ входной строки.

Начинаем строить дерево разбора для входной строки от корня, обозначенного начальным символом грамматики.

Если текущая вершина дерева разбора обозначена переменной грамматики, то выбираем одно из правил этой переменной и используем правую часть правила для построения дочерних вершин текущей вершины. Далее все дочерние вершины просматриваются слева направо.

Если текущая вершина дерева разбора терминал то сравниваем этот терминал с тем терминалом из входной строки, на который показывает указатель . Если они совпадают, то перемещаем по входной строке к следующему входному символу, а в дереве разбора переходим к следующему узлу.

Если терминал из текущей вершины дерева разбора и -терминал не совпадают, то – выбрано неподходящее правило для переменной. Совершаем откат, т.е. - откат по входному потоку, для переменной - выбрать другое правило и повторить попытку.

Пример.

- входная строка.

- вначале создаем ДР, состоящее из одного узла.

Правило для переменной одно. Им и воспользуемся. не перемещается.

- дочерние вершины просматриваем слева направо.

Лист

Совпали смещение по входной строке, переход к следующей вершине в ДР.

Дата добавления: 2013-12-14