Bison：Reduce/reduce 非令牌冲突

Question

所以我正在为 C 制作一个编译器——我目前正在制作文字表、变量表和函数表。

这条规则给我带来了 reduce/reduce 冲突：

lval: ID { check_var(); }
| ID { check_var(); } LBRACK NUM RBRACK
| ID { check_var(); } LBRACK ID { check_var(); } RBRACK;

错误如下：

parser.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
parser.y:104.6-21: warning: rule useless in parser due to conflicts [-Wother]
 | ID { check_var(); } LBRACK ID { check_var(); } RBRACK;
      ^^^^^^^^^^^^^^^^

我有优先规则来避免减少令牌上的错误，但现在它指向一个非令牌，所以不确定我应该做什么？

如果有任何帮助，这些是我的优先规则：

%token INPUT OUTPUT WRITE
%token  RETURN VOID IF ELSE WHILE ASSIGN SEMI COMMA
%token LPAREN RPAREN LBRACE RBRACE LBRACK RBRACK
%token NUM ID STRING INT
%left EQ NEQ GE LE GT LT
%left PLUS MINUS
%left TIMES OVER

Answer 1

Bison 不会检查语法中的两个自定义代码块是否相同。所以它基本上将你的语法视为：

lval: ID action_1
    | ID action_2 LBRACK NUM RBRACK
    | ID action_3 LBRACK ID action_4 RBRACK
;

而 Bison（默认情况下）充当 LALR(1) parser，这意味着它在做出决定之前只向前看一个标记。所以当它看到栈顶是一个ID令牌而look-ahead令牌是一个LBRACK令牌时，它无法决定是否应该执行action_2或action_3，没意识到这其实并不重要。

解决这个问题的方法是使用一个子规则来组合当 ID 后跟 LBRACK（以及其他情况）时应该发生的常见事情：

id_with_check: ID { check_var(); } ;

lval: id_with_check
    | id_with_check LBRACK NUM RBRACK
    | id_with_check LBRACK id_with_check RBRACK
;

Bison：Reduce/reduce 非令牌冲突

Bison: Reduce/reduce conflict on non-tokens

c

compiler-construction

parsing

bison