我语法中的间接左递归

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

维基百科上的"左递归"文章包含一个（无来源）算法来消除所有左递归，包括间接左递归。让我们忽略这个特定的算法，转而关注这个想法：首先通过替换将间接递归转换为直接递归，然后通过添加尾部非终端来解决直接递归。

例如，我们可以用代替生产#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