Re: Several parsing questions

Joachim Durchholz <>
17 Mar 2002 22:40:49 -0500

          From comp.compilers

Related articles
Several parsing questions (Agnes) (2002-03-09)
Re: Several parsing questions (2002-03-11)
Re: Several parsing questions (Joachim Durchholz) (2002-03-17)
Re: Several parsing questions (Joachim Durchholz) (2002-03-17)
| List of all articles for this month |

From: Joachim Durchholz <>
Newsgroups: comp.compilers
Date: 17 Mar 2002 22:40:49 -0500
Organization: Compilers Central
References: 02-03-034
Keywords: parse
Posted-Date: 17 Mar 2002 22:40:49 EST

Agnes wrote:
> * Ambiguous Grammar ?
> Is there a way (fixed syntax) to tell if a set of grammar rules is
> ambiguous ? e.g. in the case below, how do you tell that this grammar is
> ambiguous ?
> E --> E + E | E * E | (E) | id

No. There are a few well-known cases (the one you list above is one of
them), but there is no algorithm to determine whether a grammar is
ambiguous or not.

> * Conversion of Ambiguous Grammar to Unambiguous Grammar ?
> How do I go about converting an ambiguous grammar to one that is not ?

Experience. Again, no fixed algorithm exists.

> * NFA to DFA ?
> What is the usual practice to translate the inputted grammar into the
> parsing table ? Do I have to go through the process of converting the
> grammar from a NFA to a DFA, and from the DFA to (D)PDA ?

Why a push-down automaton? If it's a DFA, you're already optimal.

[I didn't understand the last question, so I left it unanswered.]

In practice, these questions are rarely relevant. You either construct
the language so that it is naturally LL or LALR, or you simply apply a
Tomita parser and don't worry too much about ambiguities (the parser
will tell you if a concrete input string has ambiguous parses, so you'll
be eventually notified if your grammar has ambiguity problems - unless,
of course, the first ambiguity is detected after your retreat from the
scientific community, at which point you don't care *g*).


Post a followup to this message

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