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
associativity of the fd and identifier tokens is the solution to the
problem, but I don't think I fully understand how they work as nothing
I come up with seems to have any positive effect.


I followed the manuals suggestion and made the variable sequence left
recursive, but I have also been thinking that making it right
recursive (and making the fd right associative as well) might be the
answer.


if you guys could point me in the right direction I would greatly
appreciate it. I'm pretty much out of my depth here, and no matter
how many times I read the documentation some things about this parser
business make no sense.


On a related note - does anyone have a documented example of something
a little less trivial than a _calculator_ ?




++++++++++++++++++++++++++++++++++ errors
++++++++++++++++++++++++++++++++++++


C:\code\tiny>bison --no-lines --verbose --name-prefix=monty_ --defines
bmonty.ypp
bmonty.ypp: conflicts: 2 shift/reduce
bmonty.ypp:49.14-33: warning: rule never reduced because of conflicts:
declaration: label_identifier
_seq
bmonty.ypp:50.11-51: warning: rule never reduced because of conflicts:
declaration: MONTY_STORE MONT
Y_FD label_identifier_seq


++++++++++++++++++++++++++++++++++ grammar file
++++++++++++++++++++++++++++++++++++




%union {
        double dval;
        int ival;
        char text[1024];
}


%token MONTY_FD
%token MONTY_CHAR
%token MONTY_UNSIGNED_INTEGER_NUMBER
%token MONTY_SINGLE_QUOTE
%token MONTY_IDENTIFIER
%token MONTY_STORE
%%


lines: fred
              ;


fred: declaration MONTY_FD declare_length
;


declare_length: MONTY_UNSIGNED_INTEGER_NUMBER MONTY_CHAR {
printf("\tlength is %d\n", $<ival>1 ); }
;


declaration: label_identifier_seq
| MONTY_STORE MONTY_FD label_identifier_seq
;


label_identifier: MONTY_SINGLE_QUOTE MONTY_IDENTIFIER
MONTY_SINGLE_QUOTE
        { printf("\tidentifier %s\n", $<text>2 ); }
;


label_identifier_seq: label_identifier
| label_identifier_seq MONTY_FD label_identifier
;




++++++++++++++++++++++++++++++++++ .output file
++++++++++++++++++++++++++++++++++++
Rules never reduced


        4 declaration: label_identifier_seq
        5 | MONTY_STORE MONTY_FD label_identifier_seq




State 7 conflicts: 1 shift/reduce
State 14 conflicts: 1 shift/reduce




Grammar


        0 $accept: lines $end


        1 lines: fred


        2 fred: declaration MONTY_FD declare_length


        3 declare_length: MONTY_UNSIGNED_INTEGER_NUMBER MONTY_CHAR


        4 declaration: label_identifier_seq
        5 | MONTY_STORE MONTY_FD label_identifier_seq


        6 label_identifier: MONTY_SINGLE_QUOTE MONTY_IDENTIFIER
MONTY_SINGLE_QUOTE


        7 label_identifier_seq: label_identifier
        8 | label_identifier_seq MONTY_FD
label_identifier




Terminals, with rules where they appear


$end (0) 0
error (256)
MONTY_FD (258) 2 5 8
MONTY_CHAR (259) 3
MONTY_UNSIGNED_INTEGER_NUMBER (260) 3
MONTY_SINGLE_QUOTE (261) 6
MONTY_IDENTIFIER (262) 6
MONTY_STORE (263) 5




Nonterminals, with rules where they appear


$accept (9)
        on left: 0
lines (10)
        on left: 1, on right: 0
fred (11)
        on left: 2, on right: 1
declare_length (12)
        on left: 3, on right: 2
declaration (13)
        on left: 4 5, on right: 2
label_identifier (14)
        on left: 6, on right: 7 8
label_identifier_seq (15)
        on left: 7 8, on right: 4 5 8




state 0


        0 $accept: . lines $end


        MONTY_SINGLE_QUOTE shift, and go to state 1
        MONTY_STORE shift, and go to state 2


        lines go to state 3
        fred go to state 4
        declaration go to state 5
        label_identifier go to state 6
        label_identifier_seq go to state 7




state 1


        6 label_identifier: MONTY_SINGLE_QUOTE . MONTY_IDENTIFIER
MONTY_SINGLE_QUOTE


        MONTY_IDENTIFIER shift, and go to state 8




state 2


        5 declaration: MONTY_STORE . MONTY_FD label_identifier_seq


        MONTY_FD shift, and go to state 9




state 3


        0 $accept: lines . $end


        $end shift, and go to state 10




state 4


        1 lines: fred .


        $default reduce using rule 1 (lines)




state 5


        2 fred: declaration . MONTY_FD declare_length


        MONTY_FD shift, and go to state 11




state 6


        7 label_identifier_seq: label_identifier .


        $default reduce using rule 7 (label_identifier_seq)




state 7


        4 declaration: label_identifier_seq .
        8 label_identifier_seq: label_identifier_seq . MONTY_FD
label_identifier


        MONTY_FD shift, and go to state 12


        MONTY_FD [reduce using rule 4 (declaration)]




state 8


        6 label_identifier: MONTY_SINGLE_QUOTE MONTY_IDENTIFIER .
MONTY_SINGLE_QUOTE


        MONTY_SINGLE_QUOTE shift, and go to state 13




state 9


        5 declaration: MONTY_STORE MONTY_FD . label_identifier_seq


        MONTY_SINGLE_QUOTE shift, and go to state 1


        label_identifier go to state 6
        label_identifier_seq go to state 14




state 10


        0 $accept: lines $end .


        $default accept




state 11


        2 fred: declaration MONTY_FD . declare_length


        MONTY_UNSIGNED_INTEGER_NUMBER shift, and go to state 15


        declare_length go to state 16




state 12


        8 label_identifier_seq: label_identifier_seq MONTY_FD .
label_identifier


        MONTY_SINGLE_QUOTE shift, and go to state 1


        label_identifier go to state 17




state 13


        6 label_identifier: MONTY_SINGLE_QUOTE MONTY_IDENTIFIER
MONTY_SINGLE_QUOTE .


        $default reduce using rule 6 (label_identifier)




state 14


        5 declaration: MONTY_STORE MONTY_FD label_identifier_seq .
        8 label_identifier_seq: label_identifier_seq . MONTY_FD
label_identifier


        MONTY_FD shift, and go to state 12


        MONTY_FD [reduce using rule 5 (declaration)]




state 15


        3 declare_length: MONTY_UNSIGNED_INTEGER_NUMBER . MONTY_CHAR


        MONTY_CHAR shift, and go to state 18




state 16


        2 fred: declaration MONTY_FD declare_length .


        $default reduce using rule 2 (fred)




state 17


        8 label_identifier_seq: label_identifier_seq MONTY_FD
label_identifier .


        $default reduce using rule 8 (label_identifier_seq)




state 18


        3 declare_length: MONTY_UNSIGNED_INTEGER_NUMBER MONTY_CHAR .


        $default reduce using rule 3 (declare_length)

Return to the comp.compilers page.
Search the comp.compilers archives again.