LR（1）表构造混乱

Question

我对如何使用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), $()

这将使正确的括号被延续到接下来的两个状态，并且我的语法将完美地解析。但是，我感到困惑的是，为什么应该在这里加上右括号？ $（）是否应从项目集1结转。此右括号从何而来？有人可以解释一下。谢谢

Answer 1

首先假设您正在尝试构建（规范的）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）机器，然后合并状态。但是结果是完全一样的，并且可以说合并算法更容易了解。）