Re: Ambiguity for subsets of CFL?

Torben Mogensen <>
15 May 1998 22:33:53 -0400

          From comp.compilers

Related articles
Ambiguity for subsets of CFL? (Soren Dayton) (1998-05-12)
Re: Ambiguity for subsets of CFL? (Torben Mogensen) (1998-05-15)
| List of all articles for this month |

From: Torben Mogensen <>
Newsgroups: comp.compilers
Date: 15 May 1998 22:33:53 -0400
Organization: Compilers Central
Keywords: theory

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 (

Post a followup to this message

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