parsing - 私の文法での間接的な左再帰?

Question

私の文法には間接的な左再帰のケースがあるようで、他の同様の質問のいくつかを見て、それらと私の文法の間に精神的なつながりを完全に作ることができず、それを解決する方法について頭を悩ませることができません.

A  ::= A' a
     | A
     | b

A' ::= c
     | A

A'は from から呼び出されAますが、またはA'です。これは左再帰を引き起こしています。左再帰を排除しながら、これを同等の文法に再配置するにはどうすればよいでしょうか?cA

Answer 1

You have the following productions:

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

First note that production #2 makes this grammar ambiguous, and is actually kind of pointless. Let's remove it.

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

The "Left recursion" article on Wikipedia contains an (unsourced) algorithm to eliminate all left recursion, including indirect left recursion. Let's ignore this specific algorithm and focus on the idea instead: first turn indirect recursion to direct recursion through substitution, then resolve direct recursion by adding a tail non-terminal.

For instance, we can substitute A' in production #1 by replacing it with

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

The grammar becomes as follows:

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

and we've already turned all indirect recursion into direct recursion. All that remains is to remove the direct recursion for A:

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