2 Search Results for "Vasudevan, Naveneetha"

Document
DOI: 10.4230/LIPIcs.ECOOP.2020.6
Don't Panic! Better, Fewer, Syntax Errors for LR Parsers

Authors: Lukas Diekmann and Laurence Tratt

Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)

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.
Cite as

Lukas Diekmann and Laurence Tratt. Don't Panic! Better, Fewer, Syntax Errors for LR Parsers. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 6:1-6:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{diekmann_et_al:LIPIcs.ECOOP.2020.6,
  author =	{Diekmann, Lukas and Tratt, Laurence},
  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 =	{Hirschfeld, Robert and Pape, Tobias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.6},
  URN =		{urn:nbn:de:0030-drops-131630},
  doi =		{10.4230/LIPIcs.ECOOP.2020.6},
  annote =	{Keywords: Parsing, error recovery, programming languages}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2012.142
Search-Based Ambiguity Detection in Context-Free Grammars

Authors: Naveneetha Vasudevan and Laurence Tratt

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop

Abstract
Context Free Grammars (CFGs) can be ambiguous, allowing inputs to be parsed in more than one way, something that is undesirable for uses such as programming languages. However, statically detecting ambiguity is undecidable. Though approximation techniques have had some success in uncovering ambiguity, they can struggle when the ambiguous subset of the grammar is large. In this paper, we describe a simple search-based technique which appears to have a better success rate in such cases.
Cite as

Naveneetha Vasudevan and Laurence Tratt. Search-Based Ambiguity Detection in Context-Free Grammars. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 142-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{vasudevan_et_al:OASIcs.ICCSW.2012.142,
  author =	{Vasudevan, Naveneetha and Tratt, Laurence},
  title =	{{Search-Based Ambiguity Detection in Context-Free Grammars}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{142--148},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.142},
  URN =		{urn:nbn:de:0030-drops-37788},
  doi =		{10.4230/OASIcs.ICCSW.2012.142},
  annote =	{Keywords: Ambiguity, Parsing}
}
  • Refine by Author
  • 2 Tratt, Laurence
  • 1 Diekmann, Lukas
  • 1 Vasudevan, Naveneetha

  • Refine by Classification
  • 1 Software and its engineering → Compilers
  • 1 Theory of computation → Parsing

  • Refine by Keyword
  • 2 Parsing
  • 1 Ambiguity
  • 1 error recovery
  • 1 programming languages

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact