Re: How to resolve a shift/reduce conflict in simple grammar

[Markus W. Weißmann]

On 27 Nov 2009, at 19:52, John Levine wrote:

>> The following grammar gives 2 shift/reduce conflicts. I have simplified 
>> it as good as possible. The intention of the grammar is to "collect" 
>> blocks of consecutive '0' and '1' characters from input until a 
>> semicolon occurs.
>> 
>> start       : sequences ';' ;
>> sequences   : sequences sequence | ;
>> sequence    : seq0 | seq1 ;
>> seq0        : '0' seq0 | '0' ;
>> seq1        : '1' seq1 | '1' ;
> 
> The short answer is that you don't have to do anything, since Bison
> takes the shift to resolve a S/R conflict.  Normally I would advise
> rewriting the grammar to get rid of the ambiguity, but in this case,
> all of the alternatives I can think of are ugly and complex.
> 
> You can put this in the header part to shut it up:
> 
> %expect 2
> 
> You could also use this to tell it that you expect conflicts on '0'
> and '1' and to resolve it by the shift:
> 
> %right '0' '1'
> 
> but it would mask any other conflicts involving 0 and 1, so I'd use the
> expect so you'll see any other unintended conflicts.
> 

If you have a classic flex/bison setup and want this greedy behavior, I'd 
recommend simply putting the sequences in the lexer:

flex:
- - - - - - - - - -
0+ { yylval.num = strlen(yytext); return ZEROS; }
1+ { yylval.num = strlen(yytext); return ONES; }
- - - - - - - - - -

bison:
- - - - - - - - - -
%union {
   int num;
   ...
}
%%
start: sequences ';'
sequences: sequences sequence | ;
sequence: ZEROS | ONES ;
- - - - - - - - - -

Give to lexer what is lexer's and to parser what is parser's. ;)


Regards

-Markus

-- 
Markus Weißmann, M.Sc.
Institut für Informatik
Technische Universität München
Raum 03.07.054, Boltzmannstr. 3, 85748 Garching

Tel. +49 (89) 2 89-1 81 05
Fax +49 (89) 2 89-1 81 07