Косвенная левая рекурсия в моей грамматике?

Question

В моей грамматике есть случай косвенной левой рекурсии, рассмотренный по другому аналогичному вопросу, не может создать разумную связь между ними и моей грамматикой, я не могу понять, как ее решить.

A ::= A' a 
    | A 
    | b 

A' ::= c 
    | A 

A' вызывается из A но A' является c или A, это вызывает леворекурсивные, как это могло быть переставить к эквивалентной грамматике, устраняя леворекурсивные?

Answer 1

У вас есть следующие постановки:

1: A -> A' a 
2: A -> A 
3: A -> b 
4: A' -> c 
5: A' -> A 

Прежде всего заметим, что производство # 2 делает эта грамматика неоднозначна, и на самом деле своего рода бессмысленно. Удалим его.

1: A -> A' a 
3: A -> b 
4: A' -> c 
5: A' -> A 

«левая рекурсия» статья в Википедии содержит (Ссылки) algorithm to eliminate all left recursion, включая косвенную левую рекурсию. Давайте проигнорируем этот конкретный алгоритм и сосредоточимся на идее: сначала включите косвенную рекурсию в прямую рекурсию путем подстановки, затем разрешите прямую рекурсию, добавив хвост не терминал.

Например, мы можем заменить A' в производстве # 1, заменив его

6: A -> c a (see #1 and #4) 
7: A -> A a (see #1 and #5) 

Грамматика будет выглядеть следующим образом:

4: A' -> c 
5: A' -> A 
6: A -> c a 
7: A -> A a 

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

4: A' -> c 
5: A' -> A 
6: A -> c a T 
8: T -> epsilon 
9: T -> a T