Hi, I have a rule defined as follow:
comando : IF '(' exp ')' comando parte_else
| WHILE '(' exp ')' comando
| FOR '(' exp '=' exp ';' exp ';' exp ')' comando
;
parte_else : ELSE comando
| /* empty */
;
It's a more then famous shift/reduce problem, but the weird thing is that in my output is says the reduce is the default action, when I want to shift. I was told that bison would make shift default. How do I fix it?
grammar.output:
state 213
63 comando: IF '(' exp ')' comando .
64 | IF '(' exp ')' comando . ELSE comando
ELSE shift, and go to state 216
ELSE [reduce using rule 63 (comando)]
$default reduce using rule 63 (comando)
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
yacc and bison have the same output in this case. what I understand for that:
64 | IF '(' exp ')' comando . ELSE comando
ELSE shift, and go to state 216
ELSE [reduce using rule 63 (comando)]
$default reduce using rule 63 (comando)
Is that the next token is an ELSE I can shift to state 216 or reduce to state 63 and the default action is to reduce ( $default reduce using rule 63 (comando) ). Or Am I wrong? I'm newbee in yacc.
>> yacc and bison have the same output in this case.
Not the yacc version I use ;) (byacc). But similar, yes.
The output I would get is something similar to this :
213: shift/reduce conflict (shift 216, reduce 63) on ELSE
state 213
comando : IF '(' exp ')' comando . (63)
comando : IF '(' exp ')' comando . ELSE comando (64)
ELSE shift 216
<SNIP>
Can you show your entire grammar, and the entire grammar.output file ?
The way I usually fix a shift/reduce conflict is like this :
parte_else : ELSE comando
| %prec LOWER_THAN_ELSE
;
(so, using a dummy token LOWER_THAN_ELSE that has a lower precedence than the ELSE token, so if an ELSE is found, it always shifts).
To make the LOWER_THAN_ELSE token a lower precedence than the ELSE token, you have to add this before the first %% :
/* resolve shift/reduce conflict for ELSE */
%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
Your parser should automatically choose shift as default though (unless you configured it not to, by means of command line options or precedence rules or so)
Good. That works! If you could help me with the reduce/reduce problems on that grammar I can increase your points to 500. Can you?
The $default action that the parser says it takes on the reduce/reduce conflicts it the soluction I want. But yacc does not compile when you have reduce/reduce.
ps: when you have shift/reduce you can use %expect to say to the parser it's ok. But I dn't know any mean to do that on reduce/reduce.
>> ps: when you have shift/reduce you can use %expect to say to the parser it's ok. But I dn't know any mean to do that on reduce/reduce.
The default for reduce/reduce conflicts is to reduce by the earlier rule. But be careful to depend on the default, because reduce/reduce conflicts usually indicate a grammar problem (the grammar is ambiguous). Usually you should resolve the reduce/reduce conflict by rewriting the grammar.
About solving the reduce/reduce conflicts : I think you made a typo here :
exp : var
| LITERAL
| INTEGER
| FLOAT
| '(' exp ')'
| chamada
| '-' exp
| '&' exp <----- here (was : '&' var)
| INC_OP exp
| DEC_OP exp
Verifying that each specific part of your grammar complies with the C grammar (as a subset) would take a lot of time, because it's not structured like the standard C grammar.
Most likely there will be inconsistencies ... (maybe not harmful).
Is there any reason you work with a subset of the C grammar, or are you just doing that to make it easier ?
The C standard contains the complete grammar in annex A, and requires little changes to make it work with yacc. So you could base yourself on that grammar ...
I'm doing that just to make easier. To have something to base it on. I know but I thought C grammar too complex. And I'm doing this to learn how to write a grammar from scretch. I'll build an abstract tree and generate assembly code from that. Do you think I can solve those "inconsistencies" you talk about in my semantic analiser? Or that's a grammar problem?
>> Do you think I can solve those "inconsistencies" you talk about in my semantic analiser?
If this is just for learning, I wouldn't worry about making the parser 100% compatible with the standard C language. Especially since even different compilers are not 100% compatible in this respect.
Worry about getting your parser to work, and then throw some C code at it, and see what it does ...
If you followed the C syntax (as detailed by the C standard), you shouldn't notice too many problems (the C language doesn't have a complicated grammar).
Hi Infinity08, I still have a problem. Make | & exp does not make sense, what means the adderess of (a+b) for example. Or &(--a). It only make sense to & var where var is a rule that describes variables which are space in memory. You got me? Could you think of another way to solve those reduce/reduces conflicts without changing the | & var rule?
thanks
>> what means the adderess of (a+b) for example. Or &(--a).
The C language syntax allows that. Here's the relevant part of the standard (C99) syntax :
unary-expression:
postfix-expression
++ unary-expression
-- unary-expression
unary-operator cast-expression
sizeof unary-expression
sizeof ( type-name )
unary-operator: one of
& * + - ~ !
cast-expression:
unary-expression
( type-name ) cast-expression
BUT : it's not valid C, because it doesn't make sense to take the address of a temporary. So, the C standard added this constraint :
The operand of the unary & operator shall be either a function designator, the
result of a [] or unary * operator, or an lvalue that designates an object that
is not a bit-field and is not declared with the register storage-class specifier.
So, your parser can let it pass, but the constraint should be checked later.
Business Accounts
Answer for Membership
by: Infinity08Posted on 2008-03-31 at 02:11:51ID: 21244036
>> I was told that bison would make shift default.
I usually use yacc, and there the shift is indeed the default - I assume that that's the same for bison.
And it does, no ?
ELSE shift, and go to state 216
where state 216 is probably :
IF '(' exp ')' comando ELSE . comando
so, it does do the shift.
I think (I'm not familiar with bison's output, so I might be mistaken), that this part :
ELSE [reduce using rule 63 (comando)]
$default reduce using rule 63 (comando)
refers to the reduction of the comando rule., not the if rule. Meaning that we've just seen the comando rule, so we reduce it to the comando "token", and can then continue with the ELSE by shifting the ELSE, or reducing the if rule if no ELSE is seen.