Re: Problem solving shift/reduce conflict

Chris Dodd <cdodd@acm.org>
7 Jan 2003 23:24:38 -0500

          From comp.compilers
Related articles
Problem solving shift/reduce conflict ashwin21_99@hotmail.com (Ashwin) (2003-01-04)
Re: Problem solving shift/reduce conflict cdodd@acm.org (Chris Dodd) (2003-01-07)
Re: Problem solving shift/reduce conflict lars@bearnip.com (2003-01-07)
| List of all articles for this month |
From: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers
Date: 7 Jan 2003 23:24:38 -0500
Organization: Compilers Central
References: 03-01-011
Keywords: yacc
Posted-Date: 07 Jan 2003 23:24:38 EST

"Ashwin" <ashwin21_99@hotmail.com> wrote
> There is one shift/reduce problem I am stumped on.
> -----------------------------------------
>
> ArrayType: ReferenceType RankSpecifiers ;
> ReferenceType: ClassType | ArrayType ;
> ClassType: OBJECT |STRING ;
> RankSpecifiers: RankSpecifier | RankSpecifiers RankSpecifier ;
> RankSpecifier: LEFTBRACKET RIGHTBRACKET ;
                :
> state 7
> ArrayType -> ReferenceType RankSpecifiers . (rule 26)
> RankSpecifiers -> RankSpecifiers . RankSpecifier (rule 28)
>
> LEFTBRACKET shift, and go to state 6
> LEFTBRACKET [reduce using rule 26 (ArrayType)]


The error tells you that it doesn't know what to do when it sees the
sequence ReferenceType RankSpecifiers LEFTBRACKET. It turns out that
your grammar is ambigous in this case. If you have the sequence
ReferenceType RankSpecifier RankSpecifier (eg OBJECT [ ] [ ]), there
are two different ways to parse it:


[ use a fixed width font to make the parse trees look reasonable ]


                              ArrayType
                            / \
                          / RankSpecifiers
                        / | \
                      / RankSpecifiers \
                    / | \
        ReferenceType RankSpecifier RankSpecifier




                                      ArrayType
                                      / \
                        ReferenceType \
                                  | \
                          ArrayType RankSpecifiers
                        / \ \
                      / RankSpecifiers \
                    / | \
        ReferenceType RankSpecifier RankSpecifier




So to get rid of the conflict, you need to decide which if the above two
parse trees is correct, and fix the grammar to only produce that one.


Chris Dodd
cdodd@acm.org

Post a followup to this message

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