LIPIcs.MFCS.2016.79.pdf
- Filesize: 493 kB
- 13 pages
Document
Symbolic Lookaheads for Bottom-up Parsing
Author
-
Part of:
Volume:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-19
Cite As Get BibTex
Paola Quaglia. Symbolic Lookaheads for Bottom-up Parsing. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.79
Abstract
We present algorithms for the construction of LALR(1) parsing tables, and of LR(1) parsing tables of reduced size. We first define specialized characteristic automata whose states are parametric w.r.t. variables symbolically representing lookahead-sets. The propagation flow of lookaheads is kept in the form of a system of recursive equations, which is resolved to obtain the concrete LALR(1) table. By inspection of the LALR(1) automaton and of its lookahead ropagation flow, we decide whether the grammar is LR(1) or not. In the positive case, an LR(1) parsing table of reduced size is computed by refinement of the LALR(1) table.
Subject Classification
Keywords
- LALR(1) grammars; LR(1) grammars; bottom-up parsing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Prentice Hall, 2006.
-
Alfred V. Aho and Jeffrey D. Ullman. Principles of Compiler Design. Addison-Wesley, 1977.
-
Frank DeRemer. Practical Translators for LR(k) Languages. PhD thesis, MIT, Cambridge, Mass., 1969.
- Frank DeRemer. Simple LR(k) Grammars. Commun. ACM, 14(7):453-460, 1971. URL: http://dx.doi.org/10.1145/362619.362625.
- Frank DeRemer and Thomas J. Pennello. Efficient Computation of LALR(1) Look-Ahead Sets. ACM Trans. Program. Lang. Syst., 4(4):615-649, 1982. URL: http://dx.doi.org/10.1145/69622.357187.
- Charles Donnelly and Richard Stallman. Bison: The Yacc-compatible Parser Generator (Ver. 3.0.4). 2015. URL: http://www.gnu.org/software/bison/manual/bison.pdf.
- François Pottier et Yann Régis-Gianas. Menhir. URL: http://pauillac.inria.fr/~fpottier/menhir/menhir.html.fr.
- J. Eve and Reino Kurki-Suonio. On Computing the Transitive Closure of a Relation. Acta Inf., 8:303-314, 1977. URL: http://dx.doi.org/10.1007/BF00271339.
- Stephen C. Johnson. Yacc: Yet Another Compiler-Compiler. Tech. Rep. CSTR 32, Bell Laboratories, Murray Hill, N.J., 1974. URL: http://dinosaur.compilertools.net/.
- Xavier Leroy, Damien Doligez, Alain Frisch, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon. The OCaml system release 4.02. 2014. URL: http://caml.inria.fr/pub/docs/manual-ocaml/.
-
David Pager. A Practical General Method for Constructing LR(k) Parsers. Acta Informatica, 7:249-268, 1977.
- Seppo Sippu and Eljas Soisalon-Soininen. Parsing Theory - Volume II: LR(k) and LL(k) Parsing, volume 20 of EATCS Monographs on Theoretical Computer Science. Springer, 1990. URL: http://dx.doi.org/10.1007/978-3-662-08424-3.
- Robert Endre Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.