0

我对如何使用 LR(1) 解析这个语法感到困惑：

S -> A
A -> A(A) | empty

我知道存在左递归，但有人告诉我没有必要为 LR(1) 删除它。我的项目集如下所示：（逗号将语法与前瞻分开）

item set 0:
s -> .A, $
A -> .A(A), $(
A -> ., $(

item set 1:
S -> A., $
A -> A.(A), $(

现在这是我感到困惑的地方：

item set 2:

A -> A(.A), $(  
A -> .A(A), )(
A -> ., )(

item set 3:
A -> A(A.), $(
A -> A. (A), )(

item set 4:
A -> A(A)., $(

我被告知要解析字符串“（（））”。当我这样做时，我意识到状态 4 需要有一个右括号“）”作为前瞻，这是有道理的。现在我追溯了这一点，发现这个右括号最初应该来自项目集 2 中的第一个语句。

A -> A(.A), $()

这将导致右括号被转移到接下来的 2 个状态，并且我的语法将完美解析。但是，我感到困惑的是，为什么这里应该有一个右括号？$( 不应该从项目集 1 结转。这个右括号是从哪里来的？有人可以解释一下。谢谢

4

1 回答 1

2

让我们首先假设您正在尝试构建（Canonical）LR（1）机器，并考虑状态（项目集）3：

item set 3:
A -> A(A.), $(
A -> A.(A), )(

有两个可能的后继：GOTO(S3, ')') 和 GOTO(S3, '('))：

item set 4: GOTO(S3, ')')
A -> A(A)., $(

item set 5: GOTO(S3, '(')
A -> A(.A), )(
A -> .A(A), )(
A -> .    , )(

请注意，项目集 5与项目集 2 不同，因为第一个项目的前瞻不同。

这正是让)您感到困惑的前瞻的来源，正如您在通过继续从状态 5 前进完成 LR(1) 状态机时看到的那样：

item set 6: GOTO(S5, A)
A -> A(A.), )(
A -> A.(A), )(

item set 7: GOTO(S6, ')')
A -> A(A)., )(

就是这样，因为GOTO(S6, '(')是项目集 5。

最有可能的是，您正在尝试构建（和解析）一台 LALR(1) 机器。在 LALR(1) 机器中，具有相同核心的项集被合并。当我们合并两个项目集时，相应项目的前瞻被替换为前瞻的并集。所以我们合并项目集 2 和 5：

  item set 2          item set 5          merged item set
A -> A(.A), $(      A -> A(.A), )(      A -> A(.A), $)(
A -> .A(A), )(      A -> .A(A), )(      A -> .A(A), )(
A -> .    , )(      A -> .    , )(      A -> .    , )(

同样，我们合并项目集 3 和 6，项目集 4 和 7

item set 3+6:
A -> A(A.), $)(
A -> A.(A), )(

item set 4+7:
A -> A(A)., $)(

（构造 LALR(1) 机器有一个更有效的算法，它不涉及构造整个 LR(1) 机器然后合并状态。但结果完全相同，合并算法可以说更容易理解。 )

于 2019-11-06T02:24:53.813 回答