Мегаобучалка Главная | О нас | Обратная связь  


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




Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

.

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

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

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

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

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

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



A :: xAy

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

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

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

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

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

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

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

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

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

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

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




Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (481)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.005 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7