Error recovery in parsing expression grammars through labeled failures and its implementation based on a parsing machine. (December 2018)

• Record Type: Journal Article
• Authors: Queiroz de Medeiros, Sérgio; Mascarenhas, Fabio
• Is Part Of: Journal of visual languages & computing. Volume 49(2018)
• Page Start: 17
• Page End: 28
• Publication Date: 2018-12
• Subjects: Parsing -- Error recovery -- Parsing expression grammars -- Parsing machine -- Natural semantics; Visual programming languages (Computer science) -- Periodicals; Visual programming (Computer science) -- Periodicals; Programming languages (Electronic computers) -- Semantics -- Periodicals; Langages de programmation visuelle -- Périodiques; Programmation visuelle -- Périodiques; Langages de programmation -- Sémantique -- Périodiques; Programming languages (Electronic computers) -- Semantics; Visual programming (Computer science); Visual programming languages (Computer science); Periodicals; Electronic journals; 005
• DOI: 10.1016/j.jvlc.2018.10.003
• Languages: English
• ISSNs: 1045-926X

Abstract

Highlights: We present an error recovery approach for Parsing Expression Grammars based on labeled failures and recovery expressions. We show a formalization of our error recovery approach and how to implement it by using a parsing machine. We evaluate our approach by implementing an error recovering parser for Lua. We compare the recovery done by our parser with the recovery done by a parser generated by ANTLR. We discuss how labeled failures with recovery expressions can encode other error recovering strategies. Abstract: Parsing Expression Grammars (PEGs) are a formalism used to describe top-down parsers with backtracking. As PEGs do not provide a good error recovery mechanism, PEG-based parsers usually do not recover from syntax errors in the input, or recover from syntax errors using ad-hoc, implementation-specific features. The lack of proper error recovery makes PEG parsers unsuitable for use with Integrated Development Environments (IDEs), which need to build syntactic trees even for incomplete, syntactically invalid programs. We discuss a conservative extension, based on PEGs with labeled failures, that adds a syntax error recovery mechanism for PEGs. This extension associates recovery expressions to labels, where a label now not only reports a syntax error but also uses this recovery expression to reach a synchronization point in the input and resume parsing. We give an operational semantics of PEGs with this recovery mechanism, as well as an operational semantics for a parsing machine that we can translate labeled PEGs with error recovery to, and prove the correctness of this translation. We use an implementation of labeled PEGs with error recovery via a parsing machine to build robust parsers, which use different recovery strategies, for the Lua language. We evaluate the effectiveness of these parsers, alone and in comparison with a Lua parser with automatic error recovery generated by ANTLR, a popular parser generator .