如何解决 YACC 移位/减少后增量运算符的冲突？

发布于 2024-07-21 07:40:41 字数 627 浏览 11 评论 0原文

我正在用 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 解析器生成器。

原文

I'm writing a grammar in YACC (actually Bison), and I'm having a shift/reduce problem. It results from including the postfix increment and decrement operators. Here is a trimmed down version of the grammar:

%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 tells me there are 12 shift/reduce conflicts, but if I comment out the lines for the postfix increment and decrement, it works fine. Does anyone know how to fix this conflict? At this point, I'm considering moving to an LL(k) parser generator, which makes it much easier, but LALR grammars have always seemed much more natural to write. I'm also considering GLR, but I don't know of any good C/C++ GLR parser generators.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

我还不会笑 2024-07-28 07:40:41

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

回复收藏 0 原文

本王不退位尔等都是臣 2024-07-28 07:40:41

试试这个：

%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 ')'
;

%%

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

++var++--

括号也需要被赋予优先级以最小化移位/减少警告

Try this:

%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 ')'
;

%%

The key is to declare postfix operators as non associative. Otherwise you would be able to

++var++--

The parenthesis also need to be given a precedence to minimize shift/reduce warnings

回复收藏 0 原文

画骨成沙 2024-07-28 07:40:41

我喜欢定义更多的项目。你不应该需要 %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
;

尝试一下这种方法。

I like to define more items. You shouldn't need the %left, %right, %prec stuff.

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
;

Play around with this approach.

回复收藏 0 原文

一场信仰旅途 2024-07-28 07:40:41

这个基本问题是您没有 INC 和 DEC 标记的优先级，因此它不知道如何解决涉及 前瞻的歧义INC 或 DEC。如果您

%right INC DEC

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

This basic problem is that you don't have a precedence for the INC and DEC tokens, so it doesn't know how to resolve ambiguities involving a lookahead of INC or DEC. If you add

%right INC DEC

at the end of the precedence list (you want unaries to be higher precedence and postfix higher than prefix), it will fix it, and you can even get rid of all the PREINC/POSTINC stuff, as it's irrelevant.

回复收藏 0 原文