Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание»

Преобразование грамматики: введем дополнительный не терминал , добавим правило , заменим все вхождения символа B в правой части правил символом , кроме самого правого вхождения B, тогда получим:

.

После преобразования отсутствует.

Таким образом, чтобы преобразовать грамматику, содержащую конфликт «перенос-свертка» для каждого символа грамматики (для которого имеется конфликт) вводится дополнительный не терминал (например B₁) и новое правило . И заменить все вхождения символа B в правой части правил на B₁, кроме самых правых вхождений.

Рассмотренный способ устраняет конфликт перенос-свертка, но не устраняет конфликт для правил с одинаковой правой частью и конфликт суффиксов. Рассмотренные типы грамматик для построения ДВР не должны содержать пустых правил, способ исключения e правил рассмотрен раньше (см. неукорачивающиеся грамматики).

Способы преобразование КС-грамматик (устранение левой рекурсии и пустых правил, факторизация, приведение некоторых грамматик к праволинейному виду).

Устранение левой рекурсии

Нетерминал A называется рекурсивным, если существует вывод: Если x=e, то A называется леворекурсивным, если y=e, то праворекурсивным.

A :: xAy

Левую рекурсию, т.е.правила вида можно устранить следующим способом: группируем А-правила:

, где никакая из строк не начинается с А. Заменим этот набор правил на:

, где А’-новый нетерминал. Из А можно вывести теже цепочки,что и раньше.

2).Правило вида -пустое правило.КС называется не укорачиваемой, если:

1.Схема грамматики не содержит пустых правил;

2.Схема грамматики возможно содержит одно пустое правило , при этом -н.с. и I не встречается в правой части никакого правила.

Для каждой КС грамматики G’,содержащей пустые правила, можно построить эквивалентную ей не укорачивающуюся грамматику, такую что L(G’)=L(G).

Вводим дополнительное правило:

Если в гркмм-ке есть правило ,где I-н.с. и Iвходит в правую часть других правил,то вводим новый начальные символ I’ и заменяем двумя новыми правилами .

3).Допустим, грамматика имеет правила: . Подобные грамматики можно преобразовать к виду LL1 способом, который называется «Вынесение общей части» или факторизация.Введем дополнительный нетерминал А и правила преобразуем эквивалентно: . В общем виде преобразование будет выглядеть: .

4).Праволинейный вид. Каждому состоянию ставим в соответствие нетерминал. Если есть переход из состояния Х в состояние У по а, то добавим правило Х аХ. Д/конечных состояний добавляем правило Х е. Д/е-переходо-Х У.