Re: Several parsing questions

Agnes <kidlim@yahoo.com> wrote in message news:02-03-034...
> * 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
>
> * Conversion of Ambiguous Grammar to Unambiguous Grammar ?
>
> How do I go about converting an ambiguous grammar to one that is not ?
> e.g.
>
> an ambiguous grammar :
> E --> E + E | E * E | (E) | id
>
> an unambiguous grammar :
> E --> E + T | T
> T --> T * F | F
> F --> (E) | id
>
> * 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 ?
>
> * CFG to a reduced CFG in translating grammar to parse table ?
>
> In the process of translating the inputted grammar into the parsing
> table, if given a CFG, do I have to convert the CFG to a reduced CFG,
> and from a reduced CFG to a alpha-free reduced CFG, and then reduce it
> to a unit-free CFG ?


As of your 1st question there are several reasons that make a grammar
ambigous one of them is left recursion. A production system is said to
be left recursive if a nonterminal can be expanded into a string that
begins with the same nonterminal. Due to this all the time the same
nonterminal gets replaced and there is no end to this.


In the examples you've given you can obseve that every time E gets
replaced by a string that starts with E in some the productions. Its
easy to see that if you can remove this deficiency from the production
systems you can remove ambiguity from the grammar.Unfortunately there
seems to be no procedure/algo which tells aparticular grammar is
ambigous or not. and your best bet in some cases may be your
intuition. I hope that this may be of some use for you.


And regards the question of converting NFA to DFA. i suppose that
convertion to DFA would get rid of any ambiguity in finding the path
to take from a particular node(in the context of parsing a sentence,
in finding out whether the token has been recognized). Any way the
concept of NFA and DFA are not related to parsing as we are intrested
only in CFGs and a PDA would take care of recognizing the given CFG.
You can use any of the parsing methods like brute force, recursive
descent, ll(1) etc to get your parsing act done. You can refer to
theory of compiler writing -trembley sorenson if you like. I hope that
this would be of some use to you, please follow up with a mail to me.

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