减少/减少冲突野牛语法

Question

我是野牛解析的新手，我不完全理解它是如何工作的。我有以下简单的野牛语法来解析简单的语言：

%{

%}

%token T_ASSIGN T_ADD T_SUB T_MUL T_DIV T_MOD T_POW
%token T_EQ T_NE T_LT T_GT T_LE T_GE T_AND T_OR T_NOT
%token T_ENDLINE T_LPAR T_RPAR
%token T_INTEGER T_FLOAT T_BOOL
%token T_ID

%%

program: statement_list

statement_list:
            statement_list T_ENDLINE
            statement
        |   statement

statement: %empty | expr
expr: arthm_expr | bool_expr | assignment
arthm_expr:
            arthm_expr sum_op mul
        |   mul
sum_op: T_ADD | T_SUB
mul:
            mul mul_op power
        |   power
mul_op: T_MUL | T_DIV | T_MOD

power:
            armth_last T_POW power
        |   armth_last

armth_last:
            T_INTEGER
        |   T_FLOAT
        |   T_ID
        |   T_LPAR arthm_expr T_RPAR
assignment:
            T_ID T_ASSIGN expr
bool_expr:
            bool_expr T_OR bool_and
        |   bool_and
bool_and:
            bool_and T_AND bool_cmp_eq
        |   bool_cmp_eq
bool_cmp_eq:
            arthm_expr eq_op arthm_expr
        |   bool_cmp
eq_op: T_EQ | T_NE

bool_cmp:
            arthm_expr cmp_op arthm_expr
        |   bool_unary

cmp_op: T_LT | T_GT | T_LE | T_GE

bool_unary:
            T_NOT bool_unary
        |   bool_last

bool_last:
            T_BOOL
        |   T_ID
        |   T_LPAR bool_expr T_RPAR
%%

如您所见，

T_ID

既可以是布尔表达式，也可以是算术表达式。

当我编译语法时，它会产生以下减少/减少冲突（从野牛输出中提取）：

example.y: warning: 3 reduce/reduce conflicts [-Wconflicts-rr]
example.y: warning: reduce/reduce conflict on tokens $end, T_ENDLINE [-Wcounterexamples]
  Example: T_ID •
  First reduce derivation
    expr
    ↳ 6: arthm_expr
         ↳ 10: mul
               ↳ 14: power
                     ↳ 19: armth_last
                           ↳ 22: T_ID •
  Second reduce derivation
    expr
    ↳ 7: bool_expr
         ↳ 26: bool_and
               ↳ 28: bool_cmp_eq
                     ↳ 30: bool_cmp
                           ↳ 34: bool_unary
                                 ↳ 40: bool_last
                                       ↳ 42: T_ID •
example.y: warning: reduce/reduce conflict on token T_RPAR [-Wcounterexamples]
  Example: T_LPAR T_ID • T_RPAR
  First reduce derivation
    expr
    ↳ 6: arthm_expr
         ↳ 10: mul
               ↳ 14: power
                     ↳ 19: armth_last
                           ↳ 23: T_LPAR arthm_expr                     T_RPAR
                                        ↳ 10: mul
                                              ↳ 14: power
                                                    ↳ 19: armth_last
                                                          ↳ 22: T_ID •
  Second reduce derivation
    expr
    ↳ 7: bool_expr
         ↳ 26: bool_and
               ↳ 28: bool_cmp_eq
                     ↳ 30: bool_cmp
                           ↳ 34: bool_unary
                                 ↳ 40: bool_last
                                       ↳ 43: T_LPAR bool_expr                                  T_RPAR
                                                    ↳ 26: bool_and
                                                          ↳ 28: bool_cmp_eq
                                                                ↳ 30: bool_cmp
                                                                      ↳ 34: bool_unary
                                                                            ↳ 40: bool_last
                                                                                  ↳ 42: T_ID •

如何

Answer 1

冲突的发生是因为你的语法不明确——当输入是一个简单的

T_ID

且没有操作符字符时，没有办法判断它是否应该被解析为

bool_expr

或

arithm_expr

。

基本上有两种方法可以解决这个问题

1. 不要输入语法——消除

   bool_expr

   和

   arithm_expr

   之间的区别，只使用可以在它们之间包含任何运算符的表达式。在解析之后，您可能需要一个语义类型检查过程（访问解析树）来检查表达式的类型一致性。这可以说是最好的方法，因为它将解析与类型检查分开，使事情变得更清晰，并且通常允许更好的错误消息。

2. 直接确定 ID 的类型，并对布尔 ID 和算术 ID 使用不同的标记。这可以通过使用符号表来完成，该符号表记录范围内的定义并根据声明返回不同的标记。它通常要求声明始终在使用之前发生，但许多语言仍然要求这样做。