Analyzing Ambiguity of Context-Free Grammars

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Claus Brabrand, ITU, Denmark
  • Robert Giegerich, Bielefeld University, Germany
  • Anders Møller
  • Department of Computer Science

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 by presenting an ambiguity analysis framework based on conservative language approximations. As a concrete example, we propose a technique based on local regular approximations and grammar unfoldings. We evaluate the analysis using grammars that occur in RNA analysis in bioinformatics, and we demonstrate that it is sufficiently precise and efficient to be practically useful.

Original languageEnglish
JournalScience of Computer Programming
Volume75
Issue3
Pages (from-to)176-191
Number of pages16
ISSN0167-6423
DOIs
Publication statusPublished - 2010

    Research areas

  • CFG ambiguity, regular approximation, RNA analysis

See relations at Aarhus University Citationformats

ID: 18118758