Нормальная форма Грейбах

В любом порождающем правиле правая часть начинается с терминального символа.

S→S+T|T

T→T*F|F

F→(S)|a

Принцип: Удалить левую рекурсию.

A→A_β|γ

A→γB

B→βB|λ

При строгом рассмотрении λ не должна быть в НФГ, но часто такое допускается. Тогда это называется обобщенной НФГ.

A→Bγ

B→β1|β2|…

A→ β1γ; A→ β2γ; … продолжаем пока можем

Если осталась левая рекурсия, то получим зацикливание.

Однако кроме прямой левой рекурсии существует и косвенная левая рекурсия.

A→B β

B→Aγ

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

Отношение называется first.

A first B (А – нетерминальный символ, В – любой символ)

Бинарное отношение задается бинарной матрицей.

А отн1 В; В отн2 С => А отн1Хотн2 С

Находим транзитивное замыкание отношения. Единицы на главной диагонали косвенную и прямую левую рекурсию.

• Строим отношение first

• Транзитивное замыкание отношения

• Если есть косвенная левая рекурсия, сводим ее к прямой

• Избавление от прямой левой рекурсии

• Избавляемся от нуль-порождений, если они есть

нуль-порождение: B→λ

• Подстановками делаем замену до тех пор, пока любая правая часть не начинается с терминального символа

Пример:

Ll(1) анализ

LL(1) анализ – анализ сверху-вниз , «1» означает на сколько символов анализатор заглядывает вперед. Т.о. этот анализатор – самый слабый, но для практики походит.

Принцип работы:

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

Принцип построения таблицы: строки – верхний нетерминальный символ стека, столбцы – терминальные символы.

В большинстве случаев анализатора LL(1) вполне достаточно.

Трудоемкость: n*k.

Построение детерминированных анализаторов (разбор снизу-вверх) Грамматики простого предшествования (гпп)

< ^о , = ^о , ^о > - три вида отношений. Не более одного отношения для любой пары символов.

Если между символом стека и очередным входным сиvволом выполнить отношение < ^о = ^о, то выполняется перенос.

^о > Это значит, что верхняя часть стека содержит выражения и выполняется свертка.

Алгоритм перенос-свертка:

Сначала в стек помещается ограничитель.

Для определенности будем считать, что для любого нетерминального и терминального символа будет выполняться _|_ < ^о А.

Будем считать, что после входной цепочки помещается _|_ и для любого нетерминального и терминального символа будет выполняться А ^о > _|_

Процесс будет продолжаться до тех пор, пока цепочка не свернется к начальному символу S. Следующим за ним в стеке будет стоять _|_.

A < ^о B – правая часть начинается с B.

B=C=…=D – находимся в правой части

С ^о > K – где К – символ в входной цепочке.

Если = ^о или < ^о .то осуществляется перенос, т.е. входной символ записывается в стек.

Иначе, если верхняя часть стека содержит всю правую часть, то осуществляется свертка.

Для работы алгоритма нужна таблица построения отношений.

Каждое отношение определяется не для каждой пары символов.

Отношения Вирта-Вебера

V →…AB…

1. = ^о – если существует хотя бы одно правило вида А = ^о В, где А и В – терминальные/нетерминальные символы. Иначе отношение не существует.

2. А< ^о В Существует тогда и только тогда, когда существует порождающее правило вида V→…AW. W выводится за 1 и более шагов. Цепочка начинается с символа В. W=>⁺B…

3. А ^о> В Существует правило вида V →…UW… Где U – терминал, из которого можно вывести цепочку, заканчивающуюся на символ А U=>⁺…А

W либо совпадает с В, либо состоит из нетерминала (всегда!), из которого можно вывести цепочку, начинающуюся с В. W=>^*B…

First - элементарное отношение. Оно, как и last легко выводится просмотром правил:

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

Грамматика называется ГПП, если отношения заданы правильным образом и обратимы.

Свойство обратимости не такое уж строгое ограничение, т.е. если грамматика не обратима, то ее можно привести к обратимой.

Грамматика, которая является обратимой и в которой допускаются одновременно отношения < и =, но не допускаются одновременно отношения > и какое-либо другое, называется грамматикой нестрогого предшествования.

Преобразования грамматики нестрогого предшествования:

Введем дополнительный нетерминал и преобразуем правила:

Трудоемкость: n*m, где n – длина входной цепочки, m-количество нетерминальных символов.