License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SLATE.2016.5
URN: urn:nbn:de:0030-drops-60106
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6010/
Go to the corresponding OASIcs Volume Portal

Slivnik, BoĊĦtjan

LLLR Parsing: a Combination of LL and LR Parsing

pdf-format:
OASIcs-SLATE-2016-5.pdf (0.5 MB)

Abstract

A new parsing method called LLLR parsing is defined and a method for producing LLLR parsers is described. An LLLR parser uses an LL parser as its backbone and parses as much of its input string using LL parsing as possible. To resolve LL conflicts it triggers small embedded LR parsers. An embedded LR parser starts parsing the remaining input and once the LL conflict is resolved, the LR parser produces the left parse of the substring it has just parsed and passes the control back to the backbone LL parser. The LLLR(k) parser can be constructed for any LR(k) grammar. It produces the left parse of the input string without any backtracking and, if used for a syntax-directed translation, it evaluates semantic actions using the top-down strategy just like the canonical LL(k) parser. An LLLR(k) parser is appropriate for grammars where the LL(k) conflicting nonterminals either appear relatively close to the bottom of the derivation trees or produce short substrings. In such cases an LLLR parser can perform a significantly better error recovery than an LR parser since the most part of the input string is parsed with the backbone LL parser. LLLR parsing is similar to LL(^*) parsing except that it (a) uses LR(k) parsers instead of finite automata to resolve the LL(k) conflicts and (b) does not perform any backtracking.

BibTeX - Entry

@InProceedings{slivnik:OASIcs:2016:6010,
  author =	{Bo{\v{s}}tjan Slivnik},
  title =	{{LLLR Parsing: a Combination of LL and LR Parsing}},
  booktitle =	{5th Symposium on Languages, Applications and Technologies (SLATE'16)},
  pages =	{5:1--5:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-006-4},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{51},
  editor =	{Marjan Mernik and Jos{\'e} Paulo Leal and Hugo Gon{\c{c}}alo Oliveira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6010},
  URN =		{urn:nbn:de:0030-drops-60106},
  doi =		{10.4230/OASIcs.SLATE.2016.5},
  annote =	{Keywords: LL parsing, LR languages, left parse}
}

Keywords: LL parsing, LR languages, left parse
Collection: 5th Symposium on Languages, Applications and Technologies (SLATE'16)
Issue Date: 2016
Date of publication: 21.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI