compiler-construction - 将上下文无关文法转换为 LL(1)

Question

我有以下语法：

S -> S+S|SS|S*|(S)|a

如何将其转换为 LL(1) 语法？

我试图消除左递归，所以我得到了

S->(S)S'|aS'
S'->+SS'|SS'|*S'|epsilon

我还尝试先进行左分解，然后消除左递归，我得到了类似的结果：

S->(S)S"|aS"
       S"->S'S"|epsilon
       S'->+S|*|S

但我仍然没有得到完美的答案。我觉得语法仍然不是 LL(1)。请帮忙。

Answer 1

尝试编写语法以便阅读一些完整的术语可能会有所帮助，然后可以选择尝试以某种方式扩展它。例如，您可以尝试这样的事情：

S → 术语

术语 → CoreTerm Opt更多

CoreTerm → 一个 | （学期）

选择更多 → ε | 学期 | + 术语 | * 选择更多

例如，您将得出 a(a+a)*a 为

小号

⇒ 学期

⇒ CoreTerm Opt更多

⇒ 一个选择更多

⇒ 一个术语

⇒ CoreTerm Opt更多

⇒ a(CoreTerm OptMore) OptMore

⇒ a(a OptMore) OptMore

⇒ a(a + Term) OptMore

⇒ a(a + CoreTerm OptMore) OptMore

⇒ a(a + a OptMore) OptMore

⇒ a(a + a) Opt更多

⇒ a(a + a)* OptMore

⇒ a(a + a)* 项

⇒ a(a + a)* CoreTerm OptMore

⇒ a(a + a)* a Opt更多

⇒ a(a + a)* a

要查看这是一个 LL(1) 语法，这里是 FIRST 集：

• 第一（S）= {
• FIRST(项) = { a, ( }
• FIRST(CoreTerm) = { a, ( }
• FIRST(OptMore) = { ε, a, (, +, * }

以下是 FOLLOW 集：

• 关注(S) = {$}
• 跟随（期限）= {$, )}
• FOLLOW(CoreTerm) = {a, (, +, *, $}
• 关注(OptMore) = {$, )}

所以现在我们可以填写解析表：

         | a                | (                | +      | *         | )   | $
---------+------------------+------------------+--------+-----------+-----+------
S        | Term             | Term             |        |           |     |
Term     | CoreTerm OptMore | CoreTerm OptMore |        |           |     |
CoreTerm | a                | (Term)           |        |           |     |
OptMore  | Term             | Term             | + Term | * OptMore | eps | eps

所以这个文法确实是LL(1)。