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-01-01
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.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