2026-08-17T23:51:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6487 2024-03-06T10:38:25Z ddc:004 open_access

Symbolic Lookaheads for Bottom-up Parsing Quaglia, Paola LALR(1) grammars; LR(1) grammars; bottom-up parsing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paola Quaglia 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.79 urn:nbn:de:0030-drops-64876 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.79 eng https://creativecommons.org/licenses/by/3.0/legalcode