如何变换语法为自上而下解析的语法

Question

我有一个语法

S ‐> S a | S b a | a | S b c S | S b c b | c S | c b 

的这一部分，我需要使用它，以创建一些SD套，后来一解析表。

但是，在这之前，我应该将其转换为自上而下的可分析语法。

我的问题是你如何做到这一点？我知道你必须摆脱左递归，但我该如何去做呢？

我读了维基百科的文章和大学的其他文章，但是我无法将自己的头脑包裹在我应该怎么做。

你能给我一些帮助吗？

Answer 1

这里的一般agorithm：

每个规则像

A -> Aa 
A -> b 

成为

A -> bA' 
A'-> aA' 
A'-> e 

其中e意味着空（ε）。

所以对于你的情况，你可以用

S ‐> S a | S b a | a => S -> aS' , S' -> aS' | baS' | e 

开始，并找出其余