Yacc：布尔和算术表达式语法冲突

Question

我正在实现一个编译器作为类的一部分，用于一种应该支持算术和布尔表达式的语言。不幸的是，我在实施不冲突的规则时遇到了一些麻烦。

具体来说，两种类型的表达式都应该能够简化为访问变量。但这会导致冲突，我不知道如何解决。

这是一个最小的工作示例，它显示了问题：

（使用

yacc -v -d -Wcounterexamples y.tab.y

和

lex -o lex.yy.c lex.yy.l

进行编译，尽管 lex 文件不是查看问题所必需的。而且我认为

-Wcounterexamples

特定于最新版本的 GNU Bison，我强烈推荐它而不是 POSIX Yacc这个。）

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;}
%%

Answer 1

通过最近更新的 Windows WSL，我得到：

y.tab.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
y.tab.y: warning: reduce/reduce conflict on tokens $end, CLOSED_PARENTHESIS [-Wcounterexamples]
  Example: variable •
  First reduce derivation
    expression
    ↳ 1: arithmetic_expression
         ↳ 3: arithmetic_term
              ↳ 6: arithmetic_factor
                   ↳ 11: variable •
  Second reduce derivation
    expression
    ↳ 2: boolean_expression
         ↳ 12: boolean_term
               ↳ 14: boolean_factor
                     ↳ 21: variable •

在语法中，变量可以是

arithmetic_expression

以及

boolean_expression

。

您可能可以忽略此错误，但算术运算的实现必须处理潜在的布尔操作数。通常，

false

被视为

0

，

true

被视为

1

。相反：对于布尔运算，算术操作数必须强制为

true

或

false

。