ITU

Analyzing Ambiguity of Context-Free Grammars

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Standard

Analyzing Ambiguity of Context-Free Grammars. / Brabrand, Claus; Giegerich, Robert; Møller, Anders.

In: Science of Computer Programming, Vol. 75, No. 3, 2010, p. 176-191.

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Harvard

Brabrand, C, Giegerich, R & Møller, A 2010, 'Analyzing Ambiguity of Context-Free Grammars', Science of Computer Programming, vol. 75, no. 3, pp. 176-191.

APA

Brabrand, C., Giegerich, R., & Møller, A. (2010). Analyzing Ambiguity of Context-Free Grammars. Science of Computer Programming, 75(3), 176-191.

Vancouver

Author

Brabrand, Claus ; Giegerich, Robert ; Møller, Anders. / Analyzing Ambiguity of Context-Free Grammars. In: Science of Computer Programming. 2010 ; Vol. 75, No. 3. pp. 176-191.

Bibtex

@article{b6241c00df4911dea523000ea68e967b,
title = "Analyzing Ambiguity of Context-Free Grammars",
abstract = "It has been known since 1962 that the ambiguity problem for context-free grammarsis undecidable. Ambiguity in context-free grammars is a recurring problemin language design and parser generation, as well as in applications where grammarsare used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammarambiguity problem, and we show how to exploit this by presenting an ambiguityanalysis framework based on conservative language approximations. As a concreteexample, we propose a technique based on local regular approximationsand grammar unfoldings. We evaluate the analysis using grammars that occurin RNA analysis in bioinformatics, and we demonstrate that it is sufficientlyprecise and efficient to be practically useful.",
author = "Claus Brabrand and Robert Giegerich and Anders M{\o}ller",
year = "2010",
language = "English",
volume = "75",
pages = "176--191",
journal = "Science of Computer Programming",
issn = "0167-6423",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

T1 - Analyzing Ambiguity of Context-Free Grammars

AU - Brabrand, Claus

AU - Giegerich, Robert

AU - Møller, Anders

PY - 2010

Y1 - 2010

N2 - It has been known since 1962 that the ambiguity problem for context-free grammarsis undecidable. Ambiguity in context-free grammars is a recurring problemin language design and parser generation, as well as in applications where grammarsare used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammarambiguity problem, and we show how to exploit this by presenting an ambiguityanalysis framework based on conservative language approximations. As a concreteexample, we propose a technique based on local regular approximationsand grammar unfoldings. We evaluate the analysis using grammars that occurin RNA analysis in bioinformatics, and we demonstrate that it is sufficientlyprecise and efficient to be practically useful.

AB - It has been known since 1962 that the ambiguity problem for context-free grammarsis undecidable. Ambiguity in context-free grammars is a recurring problemin language design and parser generation, as well as in applications where grammarsare used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammarambiguity problem, and we show how to exploit this by presenting an ambiguityanalysis framework based on conservative language approximations. As a concreteexample, we propose a technique based on local regular approximationsand grammar unfoldings. We evaluate the analysis using grammars that occurin RNA analysis in bioinformatics, and we demonstrate that it is sufficientlyprecise and efficient to be practically useful.

M3 - Journal article

VL - 75

SP - 176

EP - 191

JO - Science of Computer Programming

JF - Science of Computer Programming

SN - 0167-6423

IS - 3

ER -

ID: 1036598