Материал: Описание КР 1

X -> X S b | S a | b

S -> S b | X a | a

РЕШЕНИЕ

Это случай скрытой левой рекурсии.

ШАГ-01:

Сначала устраним левую рекурсию из правила X -> X S b | S a | b

Исключив левую рекурсию, получаем:

X-> S a X' | b X'

X' -> S b X' | ϵ

Теперь данная грамматика переписывается так

X -> S a X' | b X'

X' -> S b X' | ϵ

S -> S b | X a | a

ШАГ-02:

Подставляя продукции нетерминала X в S -> X a, получаем следующую грамматику

X-> S a X' | b X'

X' -> S b X' | ϵ

S -> S b | X a | a

S -> S b | S a X’ a | b X’ a | a

ШАГ-03:

Теперь, исключив левую рекурсию из продукций нетерминала S, получаем следующую грамматику:

X -> S a X'

| b X'

S -> b X' a S' | a S'

X' -> S b X' | ϵ

S' -> b S'

| a X' a S' | ϵ

Это окончательная грамматика после устранения левой рекурсии.

ЗАДАЧА № 10:

Исключить левую рекурсию из грамматики

S -> A a | b

A -> A c | S d |

РЕШЕНИЕ

Это случай скрытой левой рекурсии.

ШАГ-01:

Сначала устраним левую рекурсию вследствие использования продукции S -> A a | b

Это правило свободно от левой рекурсии.

ШАГ-02:

Подставляя постановки продукции S в правило A -> S d, получаем следующую грамматику:

S -> A a | b

A -> Ac | A a d | b d |

ШАГ-03:

Теперь, исключив левую рекурсию из A-правил, получаем следующую грамматику:

S -> A a | b

A -> b d A’ | A’

A’ -> c A’ | a d A’ |

Это окончательная грамматика после устранения левой рекурсии.

S -> A a

| b

A -> b d A' | A'

A' -> c A' | a d A' | ϵ