1 Search Results for "Quaglia, Paola"

Document

DOI: 10.4230/LIPIcs.MFCS.2016.79

Symbolic Lookaheads for Bottom-up Parsing

Authors: Paola Quaglia

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{quaglia:LIPIcs.MFCS.2016.79,
  author =	{Quaglia, Paola},
  title =	{{Symbolic Lookaheads for Bottom-up Parsing}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.79},
  URN =		{urn:nbn:de:0030-drops-64876},
  doi =		{10.4230/LIPIcs.MFCS.2016.79},
  annote =	{Keywords: LALR(1) grammars; LR(1) grammars; bottom-up parsing}
}

Refine by Author
1 Quaglia, Paola

Refine by Classification

Refine by Keyword
1 LALR(1) grammars; LR(1) grammars; bottom-up parsing

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Quaglia, Paola"

Symbolic Lookaheads for Bottom-up Parsing

Abstract

Cite as

Thanks for your feedback!

Could not send message