如何解决Tiger语法解析中的移进-归约冲突？

ML-Yacc在LOOKAHEAD为FUNCTION时选择移进而非归约，核心原因是语法规则存在歧义：解析器认为继续移进FUNCTION能匹配一条更长的合法规则，而当前的exp op exp归约优先级不足，或者你的规则错误地让FUNCTION出现在了表达式上下文里。

以下是具体的排查和修复步骤：

1. 检查操作符的优先级与结合性声明 #

你大概率没给二元操作符（op）正确设置优先级和结合性。ML-Yacc通过%left（左结合）、%right（右结合）、%nonassoc（无结合）声明规则，优先级低的声明在前，高的在后。

如果FUNCTION相关的规则优先级被默认判定为高于二元操作符，解析器就会优先移进FUNCTION而非归约exp op exp。比如给Tiger的操作符设置正确优先级：

%left OR
%left AND
%nonassoc EQ NEQ LT LE GT GE
%left PLUS MINUS
%left TIMES DIVIDE

2. 修正表达式与声明的上下文边界 #

Tiger语言中，FUNCTION属于声明（dec），而非表达式（exp）的一部分。如果你的语法规则错误地允许exp推导出包含FUNCTION的结构（比如exp : exp FUNCTION ...），必然会导致歧义。

正确的语法结构应该分离声明和表达式：

%start program
program : dec_seq
dec_seq : dec dec_seq | /* 空 */
dec : FUNCTION id '(' tyfields ')' '=' exp | VAR id ':=' exp | ...
exp : exp op exp | id | num | '(' exp ')' | exp '(' exp_list ')' | ...

3. 分析状态132的项目集 #

用ML-Yacc的-v选项生成状态报告（默认输出为y.output），找到状态132，查看其中的项目集：

• 确认待归约的规则是否为exp : exp op exp .（点在末尾，处于待归约状态）
• 确认移进对应的规则是否为dec : . FUNCTION ...或者错误的exp : . FUNCTION ...

从项目集能明确看到歧义点：解析器无法判断当前是归约已匹配的exp op exp，还是移进FUNCTION匹配另一条规则。如果是后者，说明你混淆了声明和表达式的上下文。

4. 针对queens.tig的具体修复 #

queens.tig包含多个函数定义，冲突大概率出现在某个表达式结尾后紧跟FUNCTION声明的场景。比如解析器错误地认为FUNCTION是该表达式的后续部分，而非新的声明。此时需要确保：

• 表达式规则的结尾不会被误判为可以衔接FUNCTION
• 声明上下文只能出现在顶层或特定块级作用域内，而非表达式之后

内容的提问来源于stack exchange，提问作者Bridge