Re: Several parsing questions

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*).


Regards,
Joachim

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