Главная | Обратная связь
МегаЛекции

Пункт 2. Устранение цепных правил.





Цепное правило – это правило вида , где . Цепные правила могут быть причиной нежелательных свойств грамматики, таких, например, как циклы. Алгоритм устранения цепных правил осуществляет замещение правой части каждого цепного правила, используя для этого не цепные правила.

АЛГОРИТМ:

Вход: КС-грамматика без -правил.

Выход: Эквивалентная КС-грамматика без цепных правил.

1. Для каждого нетерминала вычислить :

1.1. Положить .

1.2. Вычислить .

1.3. Если , то положить и перейти к пункту 1.2; иначе положить .

2. Построить множество так: если не является цепным правилом , то включать в правило для каждого , такого, что , то есть .

 

Пункт 3. Левая факторизация правил.

Левую факторизацию можно выполнять для правил грамматики, определяющих один и тот же нетерминал и имеющих одинаковое начало (префикс) правых частей. Цель такого преобразовании – устранение одинаковых префиксов. При проведении левой факторизации выполняются действия, подобные вынесению за скобки общего левого множителя в алгебраических выражениях. Алгоритм преобразования состоит в следующем.

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

Выход: Эквивалентная КС-грамматика без одинаковых префиксов в правых частях правил, определяющих нетерминал.

1. Записать все правила для нетерминала , имеющие одинаковые префиксы , в виде одного правила с альтернативами (вариантами):

;

2. Вынести за скобки влево префикс каждой строки-альтернативы: .

3. Обозначить новым нетерминалом выражение, оставшееся в скобках: .

4. Пополнить множество нетерминалов новым нетерминалом и заменить правила, подвергшиеся факторизации, новыми правилами для и .

5. Повторить пункты 1 – 4 для всех нетерминалов грамматики, для которых это возможно и необходимо.

 

Пункт 4. Устранение прямой левой рекурсии.

Нетерминал называют рекурсивным, когда существует вывод , где . Если указанный вывод получается за один шаг (имеется правило ), то говорят о прямой рекурсии. Если требуется более одного шага, то имеет место косвенная рекурсия (или рекурсивный цикл). В случае рекурсию называют левой, а в случае - правой. Частный случай соответствует понятию самовложения. Если , то получаем цикл .



При устранении рекурсии один вид рекурсии заменяется на другой, например, вместо левой рекурсии появляется правая. В приложениях теории формальных грамматик значительные неудобства часто создает именно левая рекурсия. Рассмотрим алгоритм устранения прямой левой рекурсии. Отметим, что если имеется несколько рекурсивных правил для одного нетерминала , то можно свести их к одному рекурсивному правилу путем левой факторизации. Возможна и последовательная обработка каждого из рекурсивных правил для .

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

Выход: Эквивалентная КС-грамматика без прямой левой рекурсии.

1. Вынести из грамматики все правила для рекурсивного нетерминала :

2. Ввести новый нетерминал так, чтобы он описывал любое окончание строки, порождаемой рекурсивным нетерминалом :

3. Заменить в рекурсивном правиле для правую часть, используя нетерминал и все не рекурсивные правила для , так, чтобы генерируемый язык не изменился:

4. Пополнить множество нетерминалов грамматики новым нетерминалом . Пополнить множество правил грамматики правилами, полученными в пункте 3.

5. Повторить действия пунктов 1 – 4 для всех рекурсивных нетерминалов грамматики, после чего полученные множества нетерминалов и правил принять в качестве и .

Замечание: если -правила не будут помехой в грамматике, то в пункте 2 алгоритма можно применить для правила

.

Тогда в пункте 3 будут получены такие правила:

.

 





Рекомендуемые страницы:

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