parsing - 如何修复后增量运算符的 YACC 移位/减少冲突？

Question

我正在用 YACC（实际上是 Bison）编写语法，并且遇到了移位/减少问题。它是由于包含后缀递增和递减运算符而产生的。这是语法的精简版：

%token NUMBER ID INC DEC

%left      '+' '-'
%left      '*' '/'
%right     PREINC
%left      POSTINC

%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     INC expr %prec PREINC
|     DEC expr %prec PREINC
|     expr INC %prec POSTINC
|     expr DEC %prec POSTINC
|     '(' expr ')'
;

%%

Bison 告诉我有 12 个移位/减少冲突，但如果我注释掉后缀递增和递减的行，它就可以正常工作。有谁知道如何解决这个冲突？在这一点上，我正在考虑迁移到 LL(k) 解析器生成器，这使它更容易，但 LALR 语法似乎总是更自然地编写。我也在考虑 GLR，但我不知道有什么好的 C/C++ GLR 解析器生成器。

Answer 1

%glr-parser如果您在选项部分指定，Bison/Yacc 可以生成 GLR 解析器。

Answer 2

试试这个：

%token NUMBER ID INC DEC

%left       '+' '-'
%left       '*' '/'
%nonassoc   '++' '--'
%left       '('
%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     '++' expr 
|     '--' expr 
|     expr '++'
|     expr '--'
|     '(' expr ')'
;

%%

关键是将后缀运算符声明为non associative。否则你将能够

++var++--

还需要优先考虑括号以最小化移位/减少警告

Answer 3

我喜欢定义更多的项目。你不应该需要 %left, %right, %prec 的东西。

simple_expr: NUMBER
 | INC simple_expr
 | DEC simple_expr
 | '(' expr ')'
;

term: simple_expr
 | term '*' simple_expr
 | term '/' simple_expr
;

expr: term
 | expr '+' term
 | expr '-' term
;

玩弄这种方法。

Answer 4

这个基本问题是您没有INCandDEC标记的优先级，因此它不知道如何解决涉及先行INCor的歧义DEC。如果你添加

%right INC DEC

在优先级列表的末尾（您希望一元的优先级更高，后缀高于前缀），它将修复它，您甚至可以摆脱所有PREINC/的POSTINC东西，因为它无关紧要。

Answer 5

preincrement 和 postincrement 运算符具有 nonassoc，因此在优先级部分和规则中定义，通过使用使这些运算符的优先级高%prec