Analyzing ambiguity of context-free grammars

Brabrand C, Giegerich R, Moller A (2010)
SCIENCE OF COMPUTER PROGRAMMING 75(3): 176-191.

Zeitschriftenaufsatz | Veröffentlicht| Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
Brabrand, Claus; Giegerich, RobertUniBi; Moller, Anders
Abstract / Bemerkung
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. (C) 2009 Elsevier B.V. All rights reserved.
Stichworte
Biosequence analysis; Context-free languages; Approximation
Erscheinungsjahr
2010
Zeitschriftentitel
SCIENCE OF COMPUTER PROGRAMMING
Band
75
Ausgabe
3
Seite(n)
176-191
ISSN
0167-6423
Page URI
https://pub.uni-bielefeld.de/record/1796697

Zitieren

Brabrand C, Giegerich R, Moller A. Analyzing ambiguity of context-free grammars. SCIENCE OF COMPUTER PROGRAMMING. 2010;75(3):176-191.
Brabrand, C., Giegerich, R., & Moller, A. (2010). Analyzing ambiguity of context-free grammars. SCIENCE OF COMPUTER PROGRAMMING, 75(3), 176-191. doi:10.1016/j.scico.2009.11.002
Brabrand, C., Giegerich, R., and Moller, A. (2010). Analyzing ambiguity of context-free grammars. SCIENCE OF COMPUTER PROGRAMMING 75, 176-191.
Brabrand, C., Giegerich, R., & Moller, A., 2010. Analyzing ambiguity of context-free grammars. SCIENCE OF COMPUTER PROGRAMMING, 75(3), p 176-191.
C. Brabrand, R. Giegerich, and A. Moller, “Analyzing ambiguity of context-free grammars”, SCIENCE OF COMPUTER PROGRAMMING, vol. 75, 2010, pp. 176-191.
Brabrand, C., Giegerich, R., Moller, A.: Analyzing ambiguity of context-free grammars. SCIENCE OF COMPUTER PROGRAMMING. 75, 176-191 (2010).
Brabrand, Claus, Giegerich, Robert, and Moller, Anders. “Analyzing ambiguity of context-free grammars”. SCIENCE OF COMPUTER PROGRAMMING 75.3 (2010): 176-191.