×

zbMATH — the first resource for mathematics

An experimental ambiguity detection tool. (English) Zbl 1187.68282
Summary: Although programs convey an unambiguous meaning, the grammars used in practice to describe their syntax are often ambiguous, and completed with disambiguation rules. Whether these rules achieve the removal of all the ambiguities while preserving the original intended language can be difficult to ensure. We present an experimental ambiguity detection tool for GNU Bison, and illustrate how it can assist a grammatical development for a subset of Standard ML.

MSC:
68Q42 Grammars and rewriting systems
Software:
ANTLR; Elkhound; YACC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Tomita, M.: Efficient parsing for natural language, (1986)
[2] Earley, J.: An efficient context-free parsing algorithm, Communications of the ACM 13, No. 2, 94-102 (1970) · Zbl 0185.43401 · doi:10.1145/362007.362035
[3] Scott, E.; Johnstone, A.: Right nulled GLR parsers, ACM transactions on programming languages and systems 28, No. 4, 577-618 (2006) · Zbl 1094.68045
[4] Aho, A. V.; Johnson, S. C.; Ullman, J. D.: Deterministic parsing of ambiguous grammars, Communications of the ACM 18, No. 8, 441-452 (1975) · Zbl 0307.68002 · doi:10.1145/360933.360969
[5] C. Donnely, R. Stallman, Bison version 2.3, http://www.gnu.org/software/bison/manual/, 2006
[6] Cantor, D. G.: On the ambiguity problem of backus systems, Journal of the ACM 9, No. 4, 477-479 (1962) · Zbl 0114.33003 · doi:10.1145/321138.321145
[7] Chomsky, N.; Schützenberger, M. P.: The algebraic theory of context-free languages, Studies in logic, 118-161 (1963) · Zbl 0148.00804
[8] Floyd, R. W.: On ambiguity in phrase structure languages, Communications of the ACM 5, No. 10, 526 (1962) · Zbl 0227.68037
[9] Schmitz, S.: Conservative ambiguity detection in context-free grammars, Lecture notes in computer science 4596, 692-703 (2007) · Zbl 1171.68518 · doi:10.1007/978-3-540-73420-8_60
[10] Klint, P.; Lämmel, R.; Verhoef, C.: Toward an engineering discipline for grammarware, ACM transactions on software engineering and methodology 14, No. 3, 331-380 (2005)
[11] Milner, R.; Tofte, M.; Harper, R.; Macqueen, D.: The definition of standard ML, (1997)
[12] S.C. Johnson, YACC – Yet Another Compiler Compiler, Computing Science Technical Report 32, AT&T Bell Laboratories, Murray Hill, New Jersey, 1975
[13] S. Kahrs, Mistakes and Ambiguities in the Definition of Standard ML, Tech. Rep. ECS-LFCS-93-257, University of Edinburgh, LFCS, 1993, http://www.lfcs.inf.ed.ac.uk/reports/93/ECS-LFCS-93-257/
[14] P. Lee, Using the SML/NJ System, Carnegie Mellon University, 1997, http://www.cs.cmu.edu/ petel/smlguide/smlnj.htm
[15] A. Rossberg, Defects in the Revised Definition of Standard ML, Tech. Rep., Saarland University, Saarbrücken, Germany, 2006, http://ps.uni-sb.de/Papers/paper_info.php?label=sml-defects
[16] Čulik, K.; Cohen, R.: LR-regular grammars–an extension of \(LR(k)\) grammars, Journal of computer and system sciences 7, No. 1, 66-96 (1973) · Zbl 0253.68014 · doi:10.1016/S0022-0000(73)80050-9
[17] Baker, T. P.: Extending lookahead for LR parsers, Journal of computer and system sciences 22, No. 2, 243-259 (1981) · Zbl 0472.68049 · doi:10.1016/0022-0000(81)90030-1
[18] P. Boullier, Contribution à la construction automatique d’analyseurs lexicographiques et syntaxiques, Thèse d’État, Université d’Orléans, 1984
[19] Szymanski, T. G.; Williams, J. H.: Noncanonical extensions of bottom-up parsing techniques, SIAM journal on computing 5, No. 2, 231-250 (1976) · Zbl 0373.68048 · doi:10.1137/0205019
[20] Tai, K. -C.: Noncanonical \(SLR(1)\) grammars, ACM transactions on programming languages and systems 1, No. 2, 295-320 (1979) · Zbl 0449.68045
[21] Schmitz, S.: Noncanonical \(LALR(1)\) parsing, Lecture notes in computer science 4036, 95-107 (2006) · Zbl 1227.68044 · doi:10.1007/11779148_10
[22] Poplawski, D. A.: On LL-regular grammars, Journal of computer and system sciences 18, No. 3, 218-227 (1979) · Zbl 0411.68060 · doi:10.1016/0022-0000(79)90031-X
[23] T.J. Parr, The Definitive ANTLR Reference: Building Domain-Specific Languages, The Pragmatic Programmers, ISBN:0-9787392-5-6, 2007
[24] Billot, S.; Lang, B.: The structure of shared forests in ambiguous parsing, , 143-151 (1989)
[25] P. Klint, E. Visser, Using filters for the disambiguation of context-free grammars, in: G. Pighizzini, P. San Pietro (Eds.), ASMICS Workshop on Parsing Theory, Technical Report 126-1994, Università di Milano, pp. 89–100, 1994, http://citeseer.ist.psu.edu/klint94using.html
[26] Den Brand, M. Van; Scheerder, J.; Vinju, J. J.; Visser, E.: Disambiguation filters for scannerless generalized LR parsers, Lecture notes in computer science 2304, 143-158 (2002) · Zbl 1051.68874 · link.springer.de
[27] Mcpeak, S.; Necula, G. C.: Elkhound: A fast, practical GLR parser generator, Lecture notes in computer science 2985, 73-88 (2004) · Zbl 1125.68354 · doi:10.1007/b95956
[28] Heilbrunner, S.: Tests for the LR-, LL-, and LC-regular conditions, Journal of computer and system sciences 27, No. 1, 1-13. (1983) · Zbl 0512.68070 · doi:10.1016/0022-0000(83)90026-0
[29] Aho, A. V.; Ullman, J. D.: The theory of parsing, translation, and compiling. Volume I: Parsing, Series in automatic computation (1972) · Zbl 0264.68032
[30] Iii, H. B. Hunt; Szymanski, T. G.; Ullman, J. D.: Operations on sparse relations and efficient algorithms for grammar problems, , 127-132 (1974)
[31] Grune, D.; Jacobs, C. J. H.: Parsing techniques: A practical guide, (1990) · Zbl 1137.68350
[32] V. Makarov, MSTA (syntax description translator), 1999, http://cocom.sourceforge.net/msta.html
[33] Brabrand, C.; Giegerich, R.; Møller, A.: Analyzing ambiguity of context-free grammars, Lecture notes in computer science 4783, 214-225 (2007) · Zbl 1139.68348 · doi:10.1007/978-3-540-76336-9_21
[34] Reeder, J.; Steffen, P.; Giegerich, R.: Effective ambiguity checking in biosequence analysis, BMC bioinformatics 6, 153. (2005)
[35] Mohri, M.; Nederhof, M. -J.: Regular approximations of context-free grammars through transformation, Text, speech and language technology 17, 153-163 (2001) · Zbl 0989.68124
[36] Kernighan, B. W.; Ritchie, D. M.: The C programming language, (1988) · Zbl 0701.68014
[37] H.J.S. Basten, The usability of ambiguity detection methods for context-free grammars, in: J. Vinju, A. Johnstone (Eds.), LDTA’08, Electronic Notes in Theoretical Computer Science, 2008 (in press)
[38] F.W. Schröer, AMBER, An Ambiguity Checker for Context-free Grammars, Tech. Rep., compilertools.net, http://accent.compilertools.net/Amber.html, 2001
[39] , (1983)
[40] ISO, ISO/IEC 14882:1998: Programming Languages – C++, International Organization for Standardization, Geneva, Switzerland, 1998
[41] Gosling, J.; Joy, B.; Steele, G.: The \(Java^{TM}\) language specification, (1996) · Zbl 0865.68001
[42] Purdom, P.: The size of \(LALR(1)\) parsers, BIT numerical mathematics 14, No. 3, 326-337 (1974) · Zbl 0307.68007
[43] Lämmel, R.; Verhoef, C.: Semi-automatic grammar recovery, Software: practice experience 31, 1395-1438 (2001) · Zbl 1009.68889
[44] Caucal, D.: Graphes canoniques de graphes algébriques, RAIRO - theoretical informatics and applications 24, No. 4, 339-352 (1990) · Zbl 0701.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.