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

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

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

Преобразование грамматики: введем дополнительный не терминал Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru , добавим правило Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru , заменим все вхождения символа B в правой части правил символом Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru , кроме самого правого вхождения B, тогда получим:

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

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

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

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

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

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

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

A :: xAy

Левую рекурсию, т.е.правила вида Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru можно устранить следующим способом: группируем А-правила:

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

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

Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru , где А’-новый нетерминал. Из А можно вывести теже цепочки,что и раньше.

2).Правило вида Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru -пустое правило.КС называется не укорачиваемой, если:

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

2.Схема грамматики возможно содержит одно пустое правило Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru , при этом -н.с. и I не встречается в правой части никакого правила.

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

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

Если в гркмм-ке есть правило Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru ,где I-н.с. и Iвходит в правую часть других правил,то вводим новый начальные символ I’ и заменяем Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru двумя новыми правилами Восходящие методы синтаксического анализа: преобразование грамматик для устранения конфликтов «перенос-сворачив ание» - student2.ru .

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

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

Наши рекомендации