Copenhagen Programming Language Seminar

Analyzing Ambiguity of Context-Free Grammars

Claus Brabrand
DAIMI, Aarhus Universitet

Monday, July 9th, Time: 15:00 - 16:00
IT University of Copenhagen, Rued Langgaards Vej 7, auditorium 3


It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures. We observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this to conservatively approximate the problem based on local regular approximations and grammar unfoldings. As an application, we consider grammars that occur in RNA analysis in bioinformatics, and we demonstrate that our static analysis of context-free grammars is sufficiently precise and efficient to be practically useful.

Scientific host: Lars Birkedal. Administrative host: Annette Enggaard. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU, KVL and RUC. COPLAS is sponsored by the FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body. For more information about COPLAS, see http://www.coplas.org/