Re: grammar conflicts

Chris F Clark <>
31 Mar 2005 23:31:31 -0500

          From comp.compilers

Related articles
grammar conflicts (Jean Morissette) (2005-03-27)
Re: grammar conflicts (Karsten Nyblad) (2005-03-31)
Re: grammar conflicts (Chris F Clark) (2005-03-31)
Re: grammar conflicts (Xous - Jose R. Negreira) (2005-03-31)
| List of all articles for this month |

From: Chris F Clark <>
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
Posted-Date: 31 Mar 2005 23:31:31 EST

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


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 ::=
                | 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


qualified_asterisk :
                                (identifier PERIOD)* identifier PERIOD asterisk

do not cause a conflict.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
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.