Geek Answers Handbook

How to fix YACC switching / decreasing conflicts with post-increment operator?

I write grammar in YACC (actually Bison) and I have a shift / reduction problem. This is the result of including increment and postfix reduction operators. Here is a stripped 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 that there are 12 shift / decrease conflicts, but if I comment out the lines for incrementing and decreasing the postfix, it works fine. Does anyone know how to fix this conflict? Right now I'm considering moving to the LL (k) parser generator, which makes it a lot easier, but LALR grammars always seemed a lot more natural to write. I also consider GLR, but I don't know any good C / C ++ GLR parser generators.

+6
parsing bison yacc lalr shift-reduce-conflict
source share
5 answers

Bison / Yacc can generate a GLR analyzer if you specify %glr-parser in the options section.

+3
source share

Try the following:

 %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 statements as non-associative . Otherwise you can

 ++var++--

An advantage should also be given in parentheses to minimize shift / decrease warnings.

+2
source share

I like to define more elements. You do not need to use% 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 ;

Play with this approach.

0
source share

This main problem is that you have no priority for INC and DEC tokens, so he does not know how to resolve the ambiguities associated with viewing INC or DEC . If you add

 %right INC DEC

at the end of the priority list (you want unars to have a higher priority and a postfix above the prefix), it will fix it, and you can even get rid of all the PREINC / POSTINC , since it doesn't matter.

0
source share
Preincrement and postincrement statements

have nonassoc, therefore, determine that in the priority section and in the rules, the priority of these operators is higher using %prec

-one
source share

More articles:


All Articles