Analyzing Ambiguity of Context-Free Grammars

Claus Brabrand; Robert Giegerich; Anders Møller

Analyzing Ambiguity of Context-Free Grammars

Claus Brabrand, Robert Giegerich, Anders Møller

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

8 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proc. 12th International Conference on Implementation and Application of Automata
Number of pages	15
Publication date	2007
Publication status	Published - 2007
Event	12th International Conference on Implementation and Application of Automata - Prague, Czech Republic Duration: 16 Jul 2007 → 18 Jul 2007

Conference

Conference	12th International Conference on Implementation and Application of Automata
Country/Territory	Czech Republic
City	Prague
Period	16/07/2007 → 18/07/2007

Keywords

ambiguity
analysis
context-free grammars
deterministic finite automata
RNA analysis

Cite this

@inproceedings{06a371a00dc711dcbee902004c4f4f50,

title = "Analyzing Ambiguity of Context-Free Grammars",

abstract = "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. ",

keywords = "tvetydighed, analyse, kontekstfrie grammatikker, deterministiske endelige automater, RNA analyse, ambiguity, analysis, context-free grammars, deterministic finite automata, RNA analysis",

author = "Claus Brabrand and Robert Giegerich and Anders M{\o}ller",

year = "2007",

language = "English",

booktitle = "Proc. 12th International Conference on Implementation and Application of Automata",

note = "12th International Conference on Implementation and Application of Automata ; Conference date: 16-07-2007 Through 18-07-2007",

}

TY - GEN

T1 - Analyzing Ambiguity of Context-Free Grammars

AU - Brabrand, Claus

AU - Giegerich, Robert

AU - Møller, Anders

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - tvetydighed

KW - analyse

KW - kontekstfrie grammatikker

KW - deterministiske endelige automater

KW - RNA analyse

KW - ambiguity

KW - analysis

KW - context-free grammars

KW - deterministic finite automata

KW - RNA analysis

M3 - Article in proceedings

BT - Proc. 12th International Conference on Implementation and Application of Automata

T2 - 12th International Conference on Implementation and Application of Automata

Y2 - 16 July 2007 through 18 July 2007

ER -

Analyzing Ambiguity of Context-Free Grammars

Abstract

Conference

Keywords

Fingerprint

Cite this