DIMACS TR: 93-61

Controlled Grammatic Ambiguity

Author: Mikkel Thorup


A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous grammars:

Construction of a parser that accepts all sentences generated by the grammar, and which always terminates in linear time.

Identification of the structural ambiguity: a finite set of pairs of partial parse trees is constructed; if for each pair the two partial parse trees are semantically equivalent, the ambiguity of the grammar is semantically irrelevant.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-61.ps

DIMACS Home Page