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

我有以下语法:

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)。请帮忙。

最佳答案

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

S→术语
条款→CoreTerm OptMore
CoreTerm→ (术语)
OptMore→ε|条款| +条款| * OptMore

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

小号
⇒学期
⇒CoreTerm OptMore
⇒OptMore
⇒学期
⇒CoreTerm OptMore
⇒一个(CoreTerm OptMore)OptMore
⇒一个(OptMore)OptMore
⇒a(a +项)OptMore
⇒a(a + CoreTerm OptMore)OptMore
⇒a(a +一个OptMore)OptMore
⇒a(a + a)OptMore
⇒a(a + a)* OptMore
⇒a(a + a)*项
⇒a(a + a)* CoreTerm OptMore
⇒a(a + a)*一个OptMore
⇒a(a + a)* a

要看到这是LL(1)语法，这是FIRST集:

FIRST(S)= {

FIRST(Term)= {a，(}

FIRST(CoreTerm)= {a，()

FIRST(OptMore)= {ε，a，(，+，*)

以下是FOLLOW集:

FOLLOW(S)= {$}

FOLLOW(Term)= {$，)}

FOLLOW(CoreTerm)= {a，(，+，*，$}

FOLLOW(OptMore)= {$，)}

现在，我们可以填写解析表:

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

因此，该语法确实是LL(1)。