parsing - 我的语法中的间接左递归？

Question

我的语法似乎有间接左递归的情况，看了一些其他类似的问题，无法在它们和我的语法之间建立心理联系，我不知道如何解决它。

A  ::= A' a
     | A
     | b

A' ::= c
     | A

A'A从but A'is cor调用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

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

例如，我们可以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