LR(1)表结构混乱

Question

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

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

我知道有左递归，但我被告知对于LR(1)没有必要删除它。我的项目集看起来像这样：(逗号将语法与lookaheads分开)

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), $()

这将导致右括号被带到下两个状态，并且我的语法将被完美地解析。但是，我搞不懂的是，为什么这里应该有右括号？$(不应该从项目集1继续。这个右括号是从哪里来的？谁能解释一下。谢谢

Answer 1

让我们首先假设您正在尝试构建一个(Canonical) LR(1)机器，并考虑state (item set) 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)机器中，具有相同核心的项目集被合并。当我们合并两个项目集时，相应项目的lookaheads被替换为lookaheads的并集。因此，我们合并项目集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)机器，然后合并状态。但结果是完全相同的，合并算法可以说更容易理解。)