License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2020.6
URN: urn:nbn:de:0030-drops-131630
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13163/
Go to the corresponding LIPIcs Volume Portal

Diekmann, Lukas ; Tratt, Laurence

Don't Panic! Better, Fewer, Syntax Errors for LR Parsers

pdf-format:
LIPIcs-ECOOP-2020-6.pdf (1 MB)

Abstract

Syntax errors are generally easy to fix for humans, but not for parsers in general nor LR parsers in particular. Traditional "panic mode" error recovery, though easy to implement and applicable to any grammar, often leads to a cascading chain of errors that drown out the original. More advanced error recovery techniques suffer less from this problem but have seen little practical use because their typical performance was seen as poor, their worst case unbounded, and the repairs they reported arbitrary. In this paper we introduce the CPCT+ algorithm, and an implementation of that algorithm, that address these issues. First, CPCT+ reports the complete set of minimum cost repair sequences for a given location, allowing programmers to select the one that best fits their intention. Second, on a corpus of 200,000 real-world syntactically invalid Java programs, CPCT+ is able to repair 98.37%±0.017% of files within a timeout of 0.5s. Finally, CPCT+ uses the complete set of minimum cost repair sequences to reduce the cascading error problem, where incorrect error recovery causes further spurious syntax errors to be identified. Across the test corpus, CPCT+ reports 435,812±473 error locations to the user, reducing the cascading error problem substantially relative to the 981,628±0 error locations reported by panic mode.

BibTeX - Entry

@InProceedings{diekmann_et_al:LIPIcs:2020:13163,
  author =	{Lukas Diekmann and Laurence Tratt},
  title =	{{Don't Panic! Better, Fewer, Syntax Errors for LR Parsers}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{6:1--6:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Robert Hirschfeld and Tobias Pape},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13163},
  URN =		{urn:nbn:de:0030-drops-131630},
  doi =		{10.4230/LIPIcs.ECOOP.2020.6},
  annote =	{Keywords: Parsing, error recovery, programming languages}
}

Keywords: Parsing, error recovery, programming languages
Collection: 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Issue Date: 2020
Date of publication: 06.11.2020
Supplementary Material: ECOOP 2020 Artifact Evaluation approved artifact available at https://doi.org/10.4230/DARTS.6.2.17.

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