Устранение цепных правил

Циклом (циклическим выводом) называется вывод вида А*А, где А – нетерминал грамматики. Циклический вывод бесполезен. Циклы возможны только в том случае, если в грамматике есть цепные правила вида АВ, где А и В – нетерминалы грамматики. В алгоритме устранения цепных правил будем использовать множество М^А – множество нетерминалов, достижимых из нетерминала А только применением цепных правил.

Алгоритм нахождения множества М^А.

1. Исключить из правил грамматики все нецепные правила.

2. Принять множество М^А ={А}, где А – нетерминал.

3. Если существует правило ВС и нетерминал В принадлежит множеству М^А, то нетерминал С включить в множество М^А .

4. Повторять п.3, пока множество М^А растёт.

5. Исключить нетерминал А из множества М^А.

Алгоритм устранения цепных правил.

1. Для каждого нетерминала А из множества нетерминалов грамма-тики найти множество М^А.

2. Исключить из множества правил грамматики все цепные правила.

3. Для правил А из множества правил грамматики добавить прави-ло В, если А принадлежит множеству М^В .

Пример.

Грамматика с цепными правилами:

1. SS+T 4. TE

2. ST 5. E(S)

3. TT*E 6. Ea

1. Для каждого нетерминала находим множество нетерминалов, дости-жимых применением только цепных правил. Очевидно М^S={T, E}, M^T={E} и M^E=.

2. Исключить из множества правил грамматики все цепные правила.

1. SS+T

3. TT*E

5. E(S)

6. Ea

3. Для правила 3. TT*E добавляем правило 3_1. ST*E, поскольку T принадлежит М^S={T, E}.

Для правила 5. Е(S) добавляем правило 5_1. S(S) и 5_2. T(S), поскольку E принадлежит М^S={T, E} и M^T={E}.

Для правила 6. Ea добавляем правило 6_1. Sа и 6_2. Та, поскольку Е принадлежит М^S={T, E} и M^T={E}.

В результате получим:

1. SS+T

3. TT*E 3_1. ST*E

5. E(S) 5_1. S(S) 5_2. T(S)

6. Ea 6_1. Sа 6_2. Та

Замена

Если грамматика содержит n правил А_i, где 1in и других правил с левой частью А нет, и в грамматике есть правило ВА, то его можно заменить на n правил вида В_i, где 1in. Такое преобразование грамматики называется заменой, а нетерминал А в правиле ВА - заменяемым.

Если в грамматике есть хотя бы одно правило А, такое, что цепочка  содержит в себе нетерминал А, то нетерминал А назовём саморекурсивным, в противном случае нетерминал А назовём несаморекурсивным.

Если грамматика содержит n правил А_i, где 1in, других правил с левой частью А нет, нетерминал А несаморекурсивный, то каждое вхождение нетерминала А в правые части правил можно заменить всеми способами на _i, где 1in, а правила с левой частью А исключить из грамматики. Если n=1, то правило А единственное с правой частью А. Такое правило называется одиночным. Левая часть одиночного правила является несаморекурсивным нетерминалом (иначе он бесплодный). Замена всех вхождений нетерминалов, являющихся левыми частями одиночных правил, называется одиночной заменой.

В правиле грамматики назовём самое левое вхождение символа в его правую часть краем правила (-правило края не имеет). Если заменяемый нетерминал является краем правила, то такая замена называется заменой края.

Примеры.

а) замена края.

Исходная грамматика: Результат замены края:

1. Аа 1. Аа

2. АВс 2_1. АаАс

3. ВаА 2_2. АbВс

4. BbВ 3. ВаА

4. BbВ

Заменяемый нетерминал В (край второго правила) саморекурсивный, поэтому третье и четвёртое правило остаются в множестве правил грамматики.

Исходная грамматика: Результат замены края:

1. АсА 1. АсА

2. АВс 2_1. АаАс

3. ВаА 2_2. Аbс

4. Bb

Заменяемый нетерминал В (край второго правила) несаморекурсивный, поэтому третье и четвёртое правило исключаются из множества правил грамматики.

б) одиночная замена.

Исходная грамматика: Результат одиночной замены :

1. АаВВ 1. Аа аАb аАb

2. АвВ 2. АbаАb

3. Ас 3. Ас

4. BаАb