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

  • Permalink
  • submit to reddit
  • Email
  • Follow


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? 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]

0
Reply longjonathan (1) 6/25/2004 5:52:06 AM

See related articles to this posting

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
cdodd@acm.org
0
Reply Chris 6/29/2004 12:00:42 AM
comp.compilers 3105 articles. 7 followers. Post

1 Replies
703 Views

Similar Articles

[PageSpeed] 7

  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

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...

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...

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...

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 []...

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...

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....

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...

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...

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...

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 ...

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...

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,'('); ...

Solving a shift/reduce conflict with an explicit precedence
I'm having a problem getting rid of a shift/reduce conflict in Bison, and would appreciate advice on how to set some precedences to do this. My basic problem is that, for simplicity, I have an ambiguous syntax. This will never cause a problem in real usage, but I can't convince Bison of that. I have rules of the form: dummy : NAME '=' const_expr | NAME '=' NAME ; const_expr : expr {..check that expr was actually constant..} ; expr : huge_number_of_sub_expr_productions ; last_sub_expr : NAME ; 'const_expr' is a compile-time constant expressio...

Applications using Lex/Flex & Yacc/Bison
Hi, I am trying to figure out hardware or software applications other then compiler-related that utilize yacc/bison and lex/flex respectively. This will help me register the range of these tools. Anyone curious enough to help ? Regards, Partha Sarathi Panda. Somewhere on Shadow Earth, at Thu, Nov 07, 2013 at 11:40:54PM -0800, Partha S Panda wrote: > I am trying to figure out hardware or software applications other then > compiler-related that utilize yacc/bison and lex/flex respectively. > > This will help me register the range of...

automatic detection and replacement of constructs causing shift/reduce conflicts
I built a system that reads a file written in ISO standard EBNF and builds a parse tree. Then it generates BNF equivalent to the EBNF and writes YACC. While it is generating BNF, it examines the EBNF to see if there are any of six types of construct that are known to cause shift/reduce conflicts. Alternate BNF constructs that do not change the language and do not cause a shift/reduce conflict are known for all six types. The system uses the alternate constructs while writing the YACC. The work was done for a real-world application in which there were 22 instances of the six sinful construct t...

ANSI C grammar without shift-reduce conflict on 'ELSE'
Hello, I'm trying to use the ANSI C Grammar from http://www.lysator.liu.se/c/ANSI-C-grammar-y.html and I'm getting a "shift - reduce on ELSE" error. I'm quite new with this, so it would really be useful if I could get a grammar that's conflict free. Any suggestions will help. Thanks Rares GalaN <ggrares@yahoo.com> wrote: > Hello, > > I'm trying to use the ANSI C Grammar from > http://www.lysator.liu.se/c/ANSI-C-grammar-y.html and I'm getting a > "shift - reduce on ELSE" error. I'm quite new with this, so it would > r...

Yacc/Bison: Trouble using struct in %union
In my Yacc .y file I defined: %union { int value; struct Symbol Sym; } The Symbol struct I defined in a header file I #included in the Prologue section of the .y file as: struct Symbol { char *SymName; /* Name of symbol/token */ int SymType; /* Symbol type */ int SymValue; }; However, on build I get: bison -d prog.y flex -t prog.l > prog.lex.c gcc -g -w -c prog.lex.c In file included from prog.l:10: prog.y:22: error: field `Sym' has incomplete type make: *** [prog.lex.o] Error 1 If in the %union I make Sym a pointer to struct Symbol the build erro...

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...

Bison reduce/reduce problem
Hello. I have been trying to figure out how to solve some of these reduce/reduce errors in bison and have looked through their manual on it and still don't have much luck. So, here is their example changed to show the type of problem I am having. %token ID %% def: param_spec {} | return_spec ',' {} ; param_spec: type {} | name_list ':' type {} ; return_spec: type {} | name ':' type ...

Reduce/Reduce conflict in Algol60 grammar
Hi folks :) As part of my current work I've been asked to find common conflicts that occur in grammars of some well known programming languages. As a start point, I've got the Algol60 revised report and typed the corresponding grammar. I've faced a difficult reduce-reduce conflict in the expression part, which is sthg like this: expression ::= arithmetic_expression | boolean_expression | designational_expression ; arithmetic_expression ::= simple_arithmetic_expression | if_clause simple_arithmetic_expression ELSE arithmetic_expression ; simple_arithmetic_expression ::= ...

Reduce/reduce conflicts on A -> e (empty) productions
Hello, I am writing an LALR(1) parser-generator for my own amusement using the "Efficient Construction of LALR Parsing Table" techniques from the dragon book. I have a question regarding reductions by productions with an empty RHS. To quote from the dragon book: "Reduction by A -> e is called for on input a if and only if there is a kernel item [B -> u.Cv, b] such that C => As for some s, and a is in FIRST(svb)." (Note, "e" means the empty string and "=>" means right-most derives in zero or more steps.) Take the following grammar: 1) S...

Bison conflict ?
Hello All: I am writing a parser to parse SQL (actually T-SQL for MS Sql Server). I am getting a shift/reduce conflict that I don't know how to solve. I know the reason of the conflict and I can give you 2 valid SQL statements that can be parsed in two different ways. I just don't know how to solve that in my grammar. Consider the following two valid SQL statements: Statement #1: select b from s where b not in ( (select a from t where a = 1), 8, 9 ); Statement #2: select b from s where b not in ( (select a from t where a = 1) union (select a from t wher...

Yacc = Bison???
Hi! Can someone tell me basic (if there is one) difference beetwen yacc and bison? I mean, are they the same only bison is a better version, do they use same input files? Thnx!!!! On 2006-03-29, Kamikazy <josip.hars@fer.hr> wrote: > Hi! Can someone tell me basic (if there is one) difference beetwen yacc and > bison? I mean, are they the same only bison is a better version, do they use > same input files? Bison is the GNU version of yacc (yacc predates GNU, and there are no doubt other yaccs). Bison does more than yacc, but should be upwardly compatible with files input ...

Does Python use a special home-made parser, or does it use Yacc?
Or some other pre-packaged parser tool? Robert wrote: > Or some other pre-packaged parser tool? None of them: it's not YACC, not a pre-packaged parser tool, and not a home-made parser. Instead, it uses pgen, a parser tool that is included in the Python distribution (whether *that* was made at home or at work, I don't know :-). Regards, Martin ...