Yacc中布尔与算术表达式文法冲突问题求助

我在完成课程作业的编译器实现，目标语言需同时支持算术表达式与布尔表达式，但编写文法规则时遇到了冲突：两类表达式均可归约为变量访问操作，导致文法冲突，无法正常生成解析器。以下是复现问题的最简代码示例：

编译命令 #

• 生成语法分析器：yacc -v -d -Wcounterexamples y.tab.y（-Wcounterexamples是GNU Bison新版本专属参数，比POSIX Yacc更推荐使用）
• 生成词法分析器：lex -o lex.yy.c lex.yy.l（lex文件并非排查问题必需）

冲突的文法文件 y.tab.y #

%{
    extern int yylex(void);
    extern int yyerror(char *msg);
%}
%token MINUS PLUS DIVIDED_BY TIMES OPEN_PARENTHESIS CLOSED_PARENTHESIS INTEGER_CONSTANT
%token OR AND FALSE TRUE NOT DIFFERENT EQUAL INFERIOR STRICT_INFERIOR SUPERIOR STRICT_SUPERIOR
%token IDENTIFIER
%%
expression:
    arithmetic_expression
    | boolean_expression
    ;
arithmetic_expression:
    arithmetic_term 
    | arithmetic_expression MINUS arithmetic_term
    | arithmetic_expression PLUS arithmetic_term 
    ;
arithmetic_term:
    arithmetic_factor 
    | arithmetic_term DIVIDED_BY arithmetic_factor 
    | arithmetic_term TIMES arithmetic_factor
    ;
arithmetic_factor:
    OPEN_PARENTHESIS arithmetic_expression CLOSED_PARENTHESIS
    | INTEGER_CONSTANT
    | variable 
    ;
boolean_expression:
    boolean_term
    | boolean_expression OR boolean_term
    ;
boolean_term:
    boolean_factor
    | boolean_term AND boolean_factor
    ;
boolean_factor:
    FALSE
    | TRUE
    | NOT boolean_factor
    | arithmetic_expression comparison arithmetic_expression
    | OPEN_PARENTHESIS boolean_expression CLOSED_PARENTHESIS 
    | variable
    ;
comparison:
    DIFFERENT
    | EQUAL
    | INFERIOR 
    | STRICT_INFERIOR
    | SUPERIOR
    | STRICT_SUPERIOR
    ;
variable:
    IDENTIFIER
    ;

词法文件 lex.yy.l #

%{
    #include "y.tab.h"
%}
%%
- {return MINUS;}
\+ {return PLUS;}
\* {return TIMES;}
\( {return OPEN_PARENTHESIS;}
\) {return CLOSED_PARENTHESIS;}
\|\| {return OR;}
&& {return AND;}
false {return FALSE;}
true {return TRUE;}
! {return NOT;}
!= {return DIFFERENT;}
== {return EQUAL;}
<= {return INFERIOR;}
< {return STRICT_INFERIOR;}
>= {return SUPERIOR;}
> {return STRICT_SUPERIOR;}
[a-z][a-zA-Z0-9_]* {return IDENTIFIER;}
%%

问题根源 #

冲突核心在于variable同时属于arithmetic_factor和boolean_factor，当解析到IDENTIFIER时，Yacc/Bison无法确定该归约为算术表达式的一部分还是布尔表达式的一部分——因为顶层规则expression可以是两者之一，直接引发移进/归约冲突。

解决方法 #

方法1：合并表达式层级，用优先级消除歧义

将布尔表达式作为算术表达式的扩展，通过明确运算符优先级（布尔运算符 < 比较运算符 < 算术运算符），让解析器明确选择逻辑。修改后的文法如下：

%{
    extern int yylex(void);
    extern int yyerror(char *msg);
%}
// 优先级从低到高排列
%left OR
%left AND
%left NOT
%left EQUAL DIFFERENT
%left INFERIOR STRICT_INFERIOR SUPERIOR STRICT_SUPERIOR
%left PLUS MINUS
%left TIMES DIVIDED_BY
%token OPEN_PARENTHESIS CLOSED_PARENTHESIS INTEGER_CONSTANT
%token FALSE TRUE IDENTIFIER
%%
expression:
    expression OR expression
    | expression AND expression
    | NOT expression
    | expression EQUAL expression
    | expression DIFFERENT expression
    | expression INFERIOR expression
    | expression STRICT_INFERIOR expression
    | expression SUPERIOR expression
    | expression STRICT_SUPERIOR expression
    | expression PLUS expression
    | expression MINUS expression
    | expression TIMES expression
    | expression DIVIDED_BY expression
    | OPEN_PARENTHESIS expression CLOSED_PARENTHESIS
    | INTEGER_CONSTANT
    | TRUE
    | FALSE
    | IDENTIFIER
    ;
%%

这种方法直接合并所有表达式规则，通过优先级声明彻底消除冲突，是课程作业中最常用的解决方案。

方法2：保留分层结构，用上下文约束消除歧义

如果必须保留算术/布尔表达式的分层结构，可以通过明确上下文规则区分：比如仅在if条件、逻辑运算符操作数等布尔上下文解析布尔表达式，在赋值右侧等算术上下文解析算术表达式。示例如下：

// 添加语句规则，明确表达式的使用上下文
statement:
    IF OPEN_PARENTHESIS boolean_expression CLOSED_PARENTHESIS block
    | ASSIGNMENT IDENTIFIER EQUAL arithmetic_expression
    ;

这样解析器会根据上下文自动选择归约方向，避免冲突。

方法3：语义分析辅助（不推荐课程作业使用）

若文法层面无法完全消除冲突，可以让解析器接受冲突，在语义分析阶段检查表达式类型是否符合上下文要求。但这种方法会耦合语法与语义分析，课程作业中更推荐前两种方法。

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