bison/yacc: shift/reduce conflict using %prec for composition

Would someone explain why a simple grammar such as this:



expr: 'A'
    | expr expr %prec FUNCTION

causes a shift/reduce conflict in bison/yacc? Here is how I understand
my generated parser will work: all input must consist of a series of
the terminal 'A', which will be identified as an expr; when two exprs
are found adjacent, i.e., two 'A's, they will be reduced by the
left-to-right precedence declared by the %prec modifier. I thus see no
reason for a shift/reduce conflict.
[It's because precedences are attached to tokens, and there's no tokens
in that rule. -John]

6/25/2004 5:52:06 AM
comp.compilers 3310 articles. 0 followers. Post Follow

1 Replies

Similar Articles

[PageSpeed] 20

longjonathan@comcast.net (J Long) wrote
> Would someone explain why a simple grammar such as this
> %left FUNCTION
> %%
> expr: 'A'
>     | expr expr %prec FUNCTION
> ;
> causes a shift/reduce conflict in bison/yacc?
> [It's because precedences are attached to tokens, and there's no tokens
> in that rule. -John]

The esteemed moderator is almost right -- precedences are indeed on
tokens, but they are also on rules, which get precendences either from
their left-most token or from an explicit %prec declaration as above.

The problem in the above grammar is that 'A' has no precedence.

To understand this problem, you really need to understand in some
deatil how shift-reduce parsing works.  Basically, at each state in
the machine, the parser looks at the next token to decide if it should
shift that token or reduce some rule.  You get shift/reduce or
reduce/reduce conflicts if bison/yacc can't decide which it should be.
Precedence rules allow you to resolve these conflicts by telling it.

When there's a shift/reduce conflict, bison will compare the
precedence of the token to be shifted with the precedence of the rule
to be reduced.  Whichever is higher gets done.  So for the above
grammar, after having parsed two expressions, if it sees an 'A' it
needs to decide whether to reduce the two expressions to one, or shift
the A and parse more expressions.

So you neeed to give 'A' a higher precedence than FUNCTION, or, as it
declared `left', the same precedence.

To generalize this to more expressions, you need need to give any
token that might start an expression the same precedence as 'A'.  This
can cause problems if you have some token that might be both the first
token in an expression, and some sort of infix operator, such as '-'.
In this case, you really want to give '-' two different precedences
depending on context.  Unfortuntely there's no way to do that with
bison.  The only real solution then is to use new non-terminal rules
instead of precendences to deal with the ambiguities.

Chris Dodd
6/29/2004 12:00:42 AM

Similar Artilces:

yacc shift/reduce conflict
list : expr '\n' ; expr : expr ',' expr | SYMBOL { printf("%s\n", yytext); } I'm trying to describe the following with the above rules: identifier [,] ... in other words, either a single identifier or a list of identifiers that are comma-separated. so a; a,b; a,b,c,d,e,f,g,h,i; etc would all be valid. I would expect my rule to work, but it doesn't. My expression rule would do the following(to my mind), if it sees something that qualifies as a SYMBOL, reduce it to 'expr', if the next token is a comma then shift. Now if the next to...

Yacc shift/reduce conflicts
Hi. I'm updating a language grammar I wrote a while ago using MKS Yacc, which consists of one or more statements separated by semicolons, i.e. S1;S2;...SN .. One of the things I want to do is to allow for superfluous embedded and trailing semicolons, as in S1;;S2; I had a bit if trouble expressing this in rules without getting shift/reduce conflicts. I found that if I simplify the grammar down to the following: program: statements ; statements: statement | statements semicolon | statements semicolon statement ; statement: someterminal ; yacc reports no conflicts, but it looks a...

shift/reduce conflicts with cl-yacc
I'm trying to write a C parser with cl-yacc. This is the beginning: http://www.frank-buss.de/tmp/parser.lisp.txt For compiling, the ASDF packages lexer, regex and yacc are needed from the lispbuilder project http://sourceforge.net/project/showfiles.php?group_id=159740 But when compiling it, there are 96 Shift/Reduce and 68 Reduce/Reduce conflicts. I've used the grammar from http://www.lysator.liu.se/c/ANSI-C-grammar-y.html I've added some precedence rules, but still the same number of conflicts. Parsing simple C files doesn't work, it says: Error: Unexpected terminal YA...

reg debugging shift/reduce and reduce/reduce conflicts
Hi Everyone, I'm trying to develop a parser for a vCard decoder, i'm using lex and yacc. And to satisfy few type pf vCards i modifed a grammar and it resulted in shift/reduce and reduce/reduce conflicts. I used -v option of yacc to generate a y.output file and I was able to understand only a bit of the file... 141: shift/reduce conflict (shift 221, red'n 239) on 10 I understand that the conflict is in 141 state and yacc is in a confusion on token 10 as to whether shift to 221 state or reduce using a rule 239... this is followed by some grammar rules from Yacc and the...

shift/reduce conflicts in the YACC grammar of C99
The "old standard" ANSI/ISO C (C89) had a known shift-reduce conflict in its YACC grammar, because of the uncertainty of where to hang an else in nested if statements. This conflict was resolved to "shift" by YACC, which is fine for C's semantics. It appears that C99 introduced two new shift/reduce conflicts with these new derivations for postfix-expression: ( type-name ) { initializer-list } ( type-name ) { initializer-list , } This is called compound literals and allows things like: struct POINT p; p = (struct POINT) {x, y}; int *ap; ap = (int []...

Help with Yacc reduce/reduce conflict
I'm writing a tool for novice Java students to submit their programs on-line and get back warnings about common mistakes, e.g. if (x = y), and assignments where the == operator is used instead of =. I've started with the Yacc-based Java grammar at http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/java/parse.y and pruned it down to this: http://minnie.tuhs.org/Z/java.y I'm modifying the grammar to accept illegal Java constructs, so that they can be identified as mistakes. Right now I am trying to add the '==' operator to assignments, but I am getting 4 reduce/reduce conflicts....

A shift / reduce conflict on and
I tried to write a parser for the module part for standard ML. But I met a problem of conflict as following: sigwhereinstance : tyvarseq longtycon EQ ty ([(tyvarseq,longtycon,ty)]) sigwheretype : sigwheretype AND TYPE sigwhereinstance (sigwheretype @ sigwhereinstance) | TYPE tyvarseq longtycon EQ ty ([(tyvarseq,longtycon,ty)]) sigexp : SIG specseq_semicolon END (Absyn.SIGEXPBASIC(specseq_semicolon,(SIGleft,ENDright))) | ID (Absyn.SIGID(ID,(IDleft,IDright))) | sigexp WHERE sigwheretype (Absyn.SIGTYPEREALISATION(sigex...

How to process unary minus for constants by other way than expressions? (bison reduce/reduce conflict)
Dear compiler compilers, I'm trying to write simple expression evaluator in flex/bison. The aim is to evaluate math expr using infix operators + - / * ^, libm functions such as pow, sin ot atan2, named variables and 1.234e-56 like constants. The expression will be parsed once over a time and a produced tree will be then executed many times, so the tree should be nearly optimal. The general task is a holy simplicity itself, even given as an example in bison's docs. However, I'd like to tune one detail: unary minus for numbers. In lexer, I specify numbers without preceding optional...

which compiler was used to compile?
Is there a slick way to invent a constant in a program that tells you which compiler you used. I distribute both JET and JavaC versions of my code, and it helps to know on any error dump which version they were using. Right now I manually change a static final just before compiling. I thought there ought to be something less error prone. -- Canadian Mind Products, Roedy Green. Coaching, problem solving, economical contract programming. See http://mindprod.com/jgloss/jgloss.html for The Java Glossary. Roedy Green wrote: > Is there a slick way to invent a constant in a program that tell...

reduce/reduce conflict
Hi, I'm currently writing a grammar for a C/Pascal-like language using btyacc (bactracking yacc). The grammar is free from conflicts except for 1 shift/reduce conflict. When I tried using inherited attributes I got 1 reduce/reduce conflict. Is there any way I can get rid of it without having to rewrite the grammar ? [No. -John] TJB wrote: > > Hi, > > I'm currently writing a grammar for a C/Pascal-like language using > btyacc (bactracking yacc). The grammar is free from conflicts except > for 1 shift/reduce conflict. When I tried using inherited attributes I > got...

Solving Shift/Reduce conflict
I'm trying to solve a shift/reduce conflict (an occurrence of the "dangling else" situation, I believe) in a toy parser made with cl-yacc. From some googling, I tried to add (:precedence ((:left :elseif) (:left :else) )) but I must confess I have no formal education in lexing or parsing, so I'm kinda shooting in the dark here. Could I get some help in this issue? This is my parser so far: (yacc:define-parser ifparser (:start-symbol start) (:terminals (:if :else :elseif ...

shift/reduce conflict issues
I have trimmed my grammar down to as small as possible while still maintaining the error - I get shift/reduce conflicts that I can't get rid of no matter what I try. Basically I need to parse a line that may look like this. (a bunch of variable declarations). 'george', 'barney', 'wilma', 'pebbles', 25 CHAR what I _think_ is happening is that the last comma before the 25 is throwing it for a loop, as the parser doesn't know if another identifier is coming, or if the length is coming. I'm fairly confident that some combination of right an left as...

cant reove the shift reduce conflict..
%token NUMBER %token CD %token CD.. %token SHOWAVAILABLEINTERFACE %token LOCKPORT %token RELEASEPORT %token LISTSTDPACKET %token SHOWPACKET %token MODIFYPACKET %token LOAD %token MODIFYTRANSMITNFO %token SENDPACKET %token SETCAPTURECOUNT %token SETCAPTURETIME %token SETFILTERMAC %token STARTCAPTURE %token HELP %% cmd: /*Blank*/ {printf("blank command entered ");} | cmd_name args_list { char str[80]; strcpy (str,$1); strcat (str,'('); ...

resolve shift/reduce conflicts in ayacc
Hi i am using the tool ayacc to generate a parser. in the language i am writing there are these two rules : expr ::= expr 'OR' expr | expr 'AND' expr | identifier formula ::= expr | formula 'OR' formula | formula 'AND' formula this grammar is obviously ambiguous since the formula "b OR c" can be parsed as (1) formula 'OR' formula (2) expr 'OR' expr so ayacc naturally reports shift/reduce conflicts. in order to suppress the conflicts, i want to force the parser to parse the formula in the first way. is there a way t...