compiler-construction - 如何将语法转换为自上而下的可解析语法

Question

我有这部分语法

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

我需要使用它来创建一些 SD 集，然后在解析表上创建。

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

我的问题是你是怎么做到的？我知道你必须摆脱左递归，但我该怎么做呢？

我阅读了维基百科的文章和其他一些来自大学的文章，但我无法理解我应该如何去做。

你能给我一些帮助吗？

Answer 1

这是一般算法：

每个规则都喜欢

A -> Aa
A -> b

变成

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

其中e表示空（epsilon）。

因此，对于您的情况，您可以从

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

找出其余的