Symbolic Lookaheads for Bottom-up Parsing

Quaglia, Paola

doi:10.4230/LIPIcs.MFCS.2016.79

File

LIPIcs.MFCS.2016.79.pdf

Filesize: 493 kB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.MFCS.2016.79
URN: urn:nbn:de:0030-drops-64876

Author Details

Paola Quaglia

Cite AsGet 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.

Keywords

LALR(1) grammars; LR(1) grammars; bottom-up parsing

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.