Re: Ambiguity for subsets of CFL?

Soren Dayton wrote:


>I was wondering if there were any results (and then implementations)
>that given:
>
> some C a subset of CFL that includes the regular languages and
> some grammar G with suitable restrictions and L(G) in C,
>
>tells us whether or not G is ambiguous?
>
>That is, are there restrictions on C and the structure of G such that
>the question of G's ambiguity is decidable?
>
>And then, assuming that there are theorems of relevance to the question,
>are there any free and implemented parsers for grammars like these?


There are various known restrictions to grammars that not only makes
the ambiguity question decidable, but actually guarantees
non-ambiguous grammars. The best known of these are LL(k) an LR(k)
grammars. For both of these, the easiest way to determine if a grammar
is in the requisite class is to make a parsetable for the parser
method in question. If the table is without conflicts, then the
grammar is non-ambiguous. However, a table with conflicts does not
imply that the grammar is ambiguous, only that it is not in the class
of grammars that the parsing method can handle unambiguously.


Torben Mogensen (torbenm@diku.dk)
--

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