Re: grammar conflicts

Chris F Clark <cfc@shell01.TheWorld.com>
31 Mar 2005 23:31:31 -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: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 31 Mar 2005 23:31:31 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 05-03-114
Keywords: LALR, parse

You asked about conflicts in a LALR grammar (to which the moderator
replied), but I would like to flush out in more detail:


What is the SYNTACTIC difference between you two rules


identifier_chain ::=
                                identifier_chain PERIOD identifier
                | identifier
                ;


and


asterisked_identified_chain ::=
                                asterisked_identified_chain PERIOD
                | identifier
                ;


If the answer is none, then you see the gist of the problem.
Syntactically, these two productions describe the same strings. Now,
the two rules are used in the context (one of then indirectly), but
they are both used in this context:






main ::=
                                identifier_chain
                | qualified_asterisk // ::= asterisked_identified_chain PERIOD asterisk


                ;


Therefore, the parser generator cannot distinguish between and
identifier_chain and an asterisked_identified_chain when scanning from
the left-to-the-right. They both look the same and they both can be
used in the same context.


When you have two roles that look exactly the same, you need to ask
yourself, why are these two rules distinct? Because, in general
(although there are specific exceptions), if you have two rules that
look exactly the same, they will be the cause of grammar conflicts.


If you change your qualified_asterisk rule to use identifier_chain
rather than asterisked_identified_chain, I think you will find that
your grammar problems go away.


BTW, this is one of the reasons we put regular expressions in Yacc++,
Recursive rules to express regular expression tend to be the source of
conflict. Note that the Yacc++ rules:




identifier_chain :
                                (identifier PERIOD)* identifier
                ;


and


qualified_asterisk :
                                (identifier PERIOD)* identifier PERIOD asterisk
                ;


do not cause a conflict.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------


Post a followup to this message

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