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.

Symbolic Lookaheads for Bottom-up Parsing / Quaglia, Paola. - ELETTRONICO. - 58:79(2016), pp. 7901-7913. ((Intervento presentato al convegno MFCS 2016 tenutosi a Krakow, Poland nel 22-26 August , 2016 [10.4230/LIPIcs.MFCS.2016.79].

Symbolic Lookaheads for Bottom-up Parsing

Quaglia, Paola
2016

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.
41st Int. Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Schloss Dagstuhl, Germany
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
978-3-95977-016-3
Quaglia, Paola
Symbolic Lookaheads for Bottom-up Parsing / Quaglia, Paola. - ELETTRONICO. - 58:79(2016), pp. 7901-7913. ((Intervento presentato al convegno MFCS 2016 tenutosi a Krakow, Poland nel 22-26 August , 2016 [10.4230/LIPIcs.MFCS.2016.79].
File in questo prodotto:
File Dimensione Formato  
LIPIcs-MFCS-2016-79.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 493.03 kB
Formato Adobe PDF
493.03 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11572/153185
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact