Bison解析器shift/reduce冲突问题求助

你的冲突根源在于Lexpr和Expr的语法前缀重叠：head/tail既可以作为左值（Lexpr）的开头（比如head x := 5），也可以作为表达式（Expr）的前缀运算符（比如head x;）。LALR(1)解析器只能前瞻1个Token，无法预判后续是否会出现:=，因此产生了shift/reduce冲突。

下面是两种可行的解决方法：

方法1：修改语法消除前缀歧义（推荐新手） #

通过给左值的head/tail添加强制括号，让左值和表达式的语法前缀明确区分：

%token NUMBER
%token IDENTIFIER

%start Program

%%

Program: Stats;

Stats: Stats Stat ";"
    | /* Epsilon */
    ;

Stat: "var" IDENTIFIER ":=" Expr
    | Lexpr ":=" Expr
    | Expr;

// 左值的head/tail必须用括号包裹，避免和表达式前缀混淆
Lexpr: IDENTIFIER
    | "head" "(" Expr ")"
    | "tail" "(" Expr ")";

Expr: Term
    | UnaryOperatorChain Term;

UnaryOperatorChain: UnaryOperatorChain UnaryOperator
    | UnaryOperator;

UnaryOperator: "head" | "tail" | "not" | "islist";

Term:
    "(" Expr ")"
    | NUMBER
    | IDENTIFIER;

%%

修改后，head(x) := 5是合法的赋值语句，head x;是合法的表达式语句，解析器可以通过head后的(或其他Token明确区分两种场景，彻底消除冲突。

方法2：语法合并+语义检查（不改变原有语法结构） #

如果不想修改语法规则，可以将Lexpr合并到Expr中，把左值合法性检查放到语义阶段，而非语法阶段：

%token NUMBER
%token IDENTIFIER

%start Program

%%

Program: Stats;

Stats: Stats Stat ";"
    | /* Epsilon */
    ;

// 不再区分Lexpr，直接用Expr作为赋值左值
Stat: "var" IDENTIFIER ":=" Expr
    | Expr ":=" Expr
    | Expr;

Expr: Term
    | UnaryOperatorChain Term;

UnaryOperatorChain: UnaryOperatorChain UnaryOperator
    | UnaryOperator;

UnaryOperator: "head" | "tail" | "not" | "islist";

Term:
    "(" Expr ")"
    | NUMBER
    | IDENTIFIER;

%%

这种方法下，语法不再有冲突，但需要在语义动作中添加检查：当解析到Expr ":=" Expr时，判断左边的Expr是否是合法左值（比如是IDENTIFIER，或者是head/tail作用于Expr的形式），如果不是则抛出语义错误。

额外说明 #

如果一定要保留原有的无括号左值语法，还可以使用Bison的GLR解析器模式（添加%glr-parser声明），让解析器处理歧义语法，但这需要在语义动作中手动解决歧义，对新手来说复杂度较高，不推荐优先尝试。

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