LR(1) 解析中 Shift/Reduce 冲突的定义

Question

表述是否正确：

" 当且仅当存在项目时，才会在 LR(1) 解析器中发生移位归约冲突：

A -> α .

A -> 阿尔法。测试版

使得 Follow(A) 与 First(beta) 不相交。

其中 A 是非终结符，alpha 和 beta 可能是语法符号的空序列。"

（直觉上这是因为没有办法根据栈顶和lookahead判断是shift还是reduce合适）

注意：如果你们认为这取决于 first/follow 评论定义的任何细节，我会提供。

Answer 1

不，那个说法不正确。

假设在一些语法中：

作品包括：
- A → α
- A → α β
跟随(A) ∩ 首先(β) ≠ ∅

这还不足以让语法产生移位归约冲突，因为它要求非终结符 A 在上下文中可达其中前瞻包括 FOLLOW(A) ∩ FIRST(β).

因此，只有当我们需要减少语法，或者至少不包含任何无法访问或无用的产生式时，上述足以产生移位减少冲突。

但是上面的条件并不是必要的因为没有要求移位和归约适用于同一个非终结符，甚至"related"非-终端。考虑以下简单语法：

prog → stmt
prog → prog stmt
stmt → expr
stmt → func
expr → ID
expr → '(' expr ')'
func → ID '(' ')' stmt

该语法（碰巧没有歧义）在包含 ID . ( 的状态中存在移位归约冲突，因为 ID 可以归约为 expr 然后 stmt 或 ( 可以作为 func → ID '(' ')' stmt.

的一部分移动

虽然这是一个侧面，但值得注意的是 FOLLOW 集仅用于构造 SLR(k) 语法。规范的 LR(k) 构造——甚至 LALR(k) 构造——将成功地为语法生成解析器，其中使用 FOLLOW 集而不是完整的前瞻计算将指示（不存在的）shift-reduce冲突。经典例子，取自龙书（我的例子4.39），用稍微更有意义的非终端名称编辑：

stmt → lvalue '=' rvalue
stmt → rvalue
lvalue → '*' rvalue
lvalue → ID
rvalue → lvalue

在这里，FOLLOW(rvalue) 是 {=, $}，并且作为状态 {stmt → lvalue · '=' rvalue, rvalue → lvalue ·} 的结果，似乎可以减少到 rvalue，从而导致错误的移位-减少冲突。

LR(1) 解析中 Shift/Reduce 冲突的定义

Definition of Shift/Reduce conflict in LR(1) parsing

theory

compiler-construction

parsing

lr