Re: grammar conflicts

"Xous - Jose R. Negreira" <xous@xouslab.com>
31 Mar 2005 23:35:25 -0500

          From comp.compilers

Related articles
grammar conflicts jean.morissette666@videotron.ca (Jean Morissette) (2005-03-27)
Re: grammar conflicts 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-03-31)
Re: grammar conflicts cfc@shell01.TheWorld.com (Chris F Clark) (2005-03-31)
Re: grammar conflicts xous@xouslab.com (Xous - Jose R. Negreira) (2005-03-31)
| List of all articles for this month |

From: "Xous - Jose R. Negreira" <xous@xouslab.com>
Newsgroups: comp.compilers
Date: 31 Mar 2005 23:35:25 -0500
Organization: Aioe.org NNTP Server
References: 05-03-114
Keywords: parse, LALR, comment

Hi Jean.


A Reduce/Reduce conflict, ocurrs where two rules has the exact right
part. The simplest example, iff you have two bnf rules


#1 nonterm1 -> IDENTIFIER
#2 nonterm2 -> IDENTIFIER


at syntatic analysis time, when an identifier arrives, what should the
analyzer do, an identifier is a NONTERM1, or a NONTERM2 ??


A shift/reduce conflict example would be


#1 nonterm1 -> expression + term
#2 nonterm1 -> expression + factor
#3 term -> factor


when arrives a "exp + factor", should this be a nonterm1 ?
or first should apply rule #3, so my string now is "exp + term", and
later convert it to nonterm1 ?


As you can see, your rules provide several paths to follow, that
confuses the syntactic analyzer, the path should be only one.


Regards,




--
Jose R. "Xous" Negreira
[ *xous*at*xouslab_dot_com* ]
XousLAB - http://www.xouslab.com
iptableslinux - http://www.iptableslinux.com






Jean Morissette escribió:
> Hi,
> I'm playing with JavaCUP and encounter some conflicts with my grammar (see
> below) and I don't know how to resolve these conflicts. Any help would be
> greatly appreciated.
>
> Thank
> -Jean
>
> main ::=
> identifier_chain
> | qualified_asterisk
> ;
>
> identifier_chain ::=
> identifier_chain PERIOD identifier
> | identifier
> ;
>
> qualified_asterisk ::=
> asterisked_identified_chain PERIOD asterisk
> ;
>
> asterisked_identified_chain ::=
> asterisked_identified_chain PERIOD
> | identifier
> ;
>
>
> *** Reduce/Reduce conflict found in state #5
> between asterisked_identified_chain ::= identifier (*)
> and identifier_chain ::= identifier (*)
> under symbols: {PERIOD}
> Resolved in favor of the second production.
>
> *** Shift/Reduce conflict found in state #5
> between asterisked_identified_chain ::= identifier (*)
> under symbol PERIOD
> Resolved in favor of shifting.
>
> *** Shift/Reduce conflict found in state #5
> between identifier_chain ::= identifier (*)
> under symbol PERIOD
> Resolved in favor of shifting.
>
> Checking for non-reduced productions...
> *** Production "asterisked_identified_chain ::= identifier " never
reduced
> [It's the usual LALR problem, the parser has to look more than one
> token ahead to figure out what it's parsing. In this case,
> identified_chain and asterisked_identified_chain are too similar. I'd
> suggest combining them and tell the difference semantically. -John]


Post a followup to this message

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