我的语法中有间接左递归吗？

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

维基百科上的 "Left recursion" 文章包含一个（未出处）algorithm to eliminate all left recursion，包括间接左递归。让我们忽略这个具体的算法，转而关注这个想法：首先通过替换将间接递归转换为直接递归，然后通过添加尾部非终端来解决直接递归。

例如，我们可以将生产 #1 中的 A' 替换为

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

Indirect left recursion in my grammar?