我是野牛解析的新手,我不完全理解它是如何工作的。我有以下简单的野牛语法来解析简单的语言:
%{
%}
%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 •
如何
冲突的发生是因为你的语法不明确——当输入是一个简单的
T_ID
且没有操作符字符时,没有办法判断它是否应该被解析为bool_expr
或arithm_expr
。
基本上有两种方法可以解决这个问题
不要输入语法——消除
bool_expr
和 arithm_expr
之间的区别,只使用可以在它们之间包含任何运算符的表达式。在解析之后,您可能需要一个语义类型检查过程(访问解析树)来检查表达式的类型一致性。这可以说是最好的方法,因为它将解析与类型检查分开,使事情变得更清晰,并且通常允许更好的错误消息。
直接确定 ID 的类型,并对布尔 ID 和算术 ID 使用不同的标记。这可以通过使用符号表来完成,该符号表记录范围内的定义并根据声明返回不同的标记。它通常要求声明始终在使用之前发生,但许多语言仍然要求这样做。