parsing - LL(1) 解析表中有多个条目？

Question

鉴于此语法：

S → S ₁ S ₂

S ₁ → a | ε

S ₂ → ab | ε

因此，我们有

FIRST(S ₁ ) = { a, ε }

跟随(S ₁ ) = { 一 }

这是否意味着在解析表中，我将在 S ₁的行和 1 的列中有多个定义a？

Answer 1

对，那是正确的。（但是，请注意您的 FOLLOW 集是错误的；它还包含输入结束标记 $）。这里的问题是，如果解析器看到一个a，它无法判断那是否是因为它想要使用推导

S → S ₁ S ₂ → a S ₂

或者推导

S → S ₁ S ₂ → S ₂ → ab

要解决此问题，您可以注意您的语法仅生成字符串 { a, ab, aab }。因此，您可以为直接生成这三个字符串的语言语法构建一个 LL(1)：

S → aY

Y → ε | aZ

Z → ε | b

希望这可以帮助！