LR解析如何解析这个文法中的单词"a b"：S -> a b |在 ; T -> 一个
How does LR parsing parse the word "a b" in this grammar: S -> a b | a T ; T -> a
假设我有语法
S -> a b | a T
T -> a
显然，语法接受 {aa, ab}。但是我很困惑LR解析是如何解析单词“a b”的。天真地，它可以像这样工作，通过将第一个“a”减少到 T 然后它卡住或不得不回溯。
a a => T a => stuck or backtrack
LR 解析器如何知道它不应将第一个“a”缩减为 T？
在这种情况下，解析器永远不会尝试减少 T，因为产生式 T → a 未处于从 S 到达的任何状态。初始状态有项目：
S → • a b
S → • a T
并且在此状态下唯一可能的操作是使用令牌 a 的移位操作。因为 a 实际上是下一个输入字符，所以我们转换到项目集为
的状态
S → a • b
S → a • T
T → • a
这个状态也没有 reduce 动作，它有两个不同的 shift 动作：一个在 b 上，另一个在 a 上。由于下一个输入是 b，因此采取了移位操作，导致项目集为
的状态
S → a b •
其中只有折扣可用。
一个更有趣的例子是相当相似的语法
S → a b
S → T a
T → a
此处，初始状态的项集确实包括 T 的产生式：
S → • a b
S → • T a
T → • a
在初始状态下唯一可用的操作仍然是移位 a，但现在在进行移位后我们发现自己处于项目集为的状态：
S → a • b
T → a •
现在我们有两种可能的操作：移动 b 和减少 T → a。在这里，解析器需要使用它的能力来展望未来的一个标记（假设它是一个 LR(1) 解析器）。
但要让它这样做，我们需要做一个小的调整。在构造解析自动机之前，语法总是被“扩充”。增强语法通过添加一个唯一的 end-of-input 字符来添加对输入结束的显式识别，该字符也可以参与前瞻检查。增广文法为：
S'→ S $
S → a b
S → T a
T → a
在这个语法中，我们可以看到非终结符T后面只能跟着符号a，这个事实被编码到状态转换tables中，其中项目集中的每个项目实际上都用一组可能的前瞻性注释。 （在 table 构造期间，所有项目都被注释，但对于法律行为的计算，仅考虑减少的前瞻性；减少是一个项目，其 • 在末尾。）
经过这次修改，a移动后得到的项集是：
S → a • b
T → a • [ lookahead: { a } ]
并且前瞻性让应该选择哪个动作变得非常清楚。如果下一个输入是 b，它会被移位。如果下一个输入是a，则减少T。
该精度不适用于 LR(0) 解析，其中不使用先行。修改后的语法不是 LR(0)，正是因为你提到的原因：它不能决定是否减少 T。这个问题经常出现，这就是为什么 LR(0) 在实践中很少有用的原因。
给定示例输入“a b”...读取 'a' 后，解析器处于以下状态：
S -> a . b
S -> a . T
T -> . a
由于这些项目的 none 在生产结束时有点，状态不要求任何减少操作。唯一可用的操作是移位，因此解析器读取下一个符号。无需前瞻。
假设我有语法
S -> a b | a T
T -> a
显然，语法接受 {aa, ab}。但是我很困惑LR解析是如何解析单词“a b”的。天真地，它可以像这样工作，通过将第一个“a”减少到 T 然后它卡住或不得不回溯。
a a => T a => stuck or backtrack
LR 解析器如何知道它不应将第一个“a”缩减为 T？
在这种情况下，解析器永远不会尝试减少 T，因为产生式 T → a 未处于从 S 到达的任何状态。初始状态有项目：
S → • a b
S → • a T
并且在此状态下唯一可能的操作是使用令牌 a 的移位操作。因为 a 实际上是下一个输入字符，所以我们转换到项目集为
S → a • b
S → a • T
T → • a
这个状态也没有 reduce 动作，它有两个不同的 shift 动作：一个在 b 上，另一个在 a 上。由于下一个输入是 b，因此采取了移位操作，导致项目集为
S → a b •
其中只有折扣可用。
一个更有趣的例子是相当相似的语法
S → a b
S → T a
T → a
此处，初始状态的项集确实包括 T 的产生式：
S → • a b
S → • T a
T → • a
在初始状态下唯一可用的操作仍然是移位 a，但现在在进行移位后我们发现自己处于项目集为的状态：
S → a • b
T → a •
现在我们有两种可能的操作：移动 b 和减少 T → a。在这里，解析器需要使用它的能力来展望未来的一个标记（假设它是一个 LR(1) 解析器）。
但要让它这样做，我们需要做一个小的调整。在构造解析自动机之前，语法总是被“扩充”。增强语法通过添加一个唯一的 end-of-input 字符来添加对输入结束的显式识别，该字符也可以参与前瞻检查。增广文法为：
S'→ S $
S → a b
S → T a
T → a
在这个语法中，我们可以看到非终结符T后面只能跟着符号a，这个事实被编码到状态转换tables中，其中项目集中的每个项目实际上都用一组可能的前瞻性注释。 （在 table 构造期间，所有项目都被注释，但对于法律行为的计算，仅考虑减少的前瞻性；减少是一个项目，其 • 在末尾。）
经过这次修改，a移动后得到的项集是：
S → a • b
T → a • [ lookahead: { a } ]
并且前瞻性让应该选择哪个动作变得非常清楚。如果下一个输入是 b，它会被移位。如果下一个输入是a，则减少T。
该精度不适用于 LR(0) 解析，其中不使用先行。修改后的语法不是 LR(0)，正是因为你提到的原因：它不能决定是否减少 T。这个问题经常出现，这就是为什么 LR(0) 在实践中很少有用的原因。
给定示例输入“a b”...读取 'a' 后，解析器处于以下状态：
S -> a . b
S -> a . T
T -> . a
由于这些项目的 none 在生产结束时有点，状态不要求任何减少操作。唯一可用的操作是移位，因此解析器读取下一个符号。无需前瞻。