如何解决Happy编写Lua解析器时的Shift/Reduce、Reduce/Reduce冲突

1. not False and True的Shift/Reduce冲突 #

这个冲突源于运算符优先级未在语法规则中明确。Lua里not的优先级高于and，正确语法结构应为(not False) and True，但如果你的语法规则将not表达式与and表达式置于同一层级，Happy的LALR(1)分析器遇到and时，会陷入纠结：是先把not False归约为表达式，还是先移进and继续匹配后续内容。

解决方式：

• 在Happy中通过%left/%right声明运算符的结合性与优先级，给not设置更高优先级（例如%right not，%left and or）；
• 拆分表达式规则，分层定义：比如Expr → AndExpr，AndExpr → NotExpr | AndExpr and NotExpr，NotExpr → not NotExpr | PrimaryExpr，通过规则层级强制优先级顺序。

2. Functioncall的Reduce/Reduce冲突 #

Lua语法中，Functioncall确实兼具两种角色：既可以作为独立语句（如单独一行的foo()），也可以作为前缀表达式（如(foo())或foo().x）。LALR(1)是上下文无关的分析器，当遇到(时，无法判断当前处于语句上下文还是表达式上下文，因此会出现归约冲突——不知道该把前面的符号归约为Stat还是Prefixexp。

解决方式：

• 调整语法规则，拆分语句与表达式路径：将作为语句的函数调用单独定义为Stat → Functioncall，而Prefixexp下的Functioncall仅在表达式上下文触发；
• 利用Happy的冲突解决机制，给Prefixexp相关的归约设置更高优先级，确保在表达式上下文优先归约为Prefixexp，语句上下文则优先归约为Stat（可通过%prec指定优先级标记）。

3. Lua官方语法无冲突的原因 #

Lua官方并未使用LALR或其他自动生成的解析器，而是采用手写的递归下降解析器。递归下降解析器是上下文相关的，能够根据当前的解析状态（比如正在解析语句还是表达式）选择对应规则：

• 处于语句解析状态时，遇到符合函数调用的结构就按语句处理；
• 处于表达式解析状态时，就按前缀表达式处理。

这种手写解析器可以灵活处理语法中的上下文依赖，而自动生成的LALR(1)分析器仅能处理上下文无关的语法规则，因此直接照搬官方语法规则到Happy中会出现冲突。

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