Simplified parsing expression derivatives

DOI10.1007/978-3-030-40608-0_30MaRDI QIDQ782605zbMATH OpenOpenAlexFDO

Authors Aaron Moss

Publication date 27 July 2020

Full work available at URL https://arxiv.org/abs/1808.08893

zbMATH Keywords

parsingderivative parsingparsing expression grammar

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Grammars and rewriting systems (68Q42)

Abstract: This paper presents a new derivative parsing algorithm for parsing expression grammars; this new algorithm is both simpler and faster than the existing parsing expression derivative algorithm presented by Moss. This new algorithm improves on the worst-case space and runtime bounds of the previous algorithm by a linear factor, as well as decreasing runtime by about half in practice. A proof of correctness for the new algorithm is included in this paper, a result not present in earlier work.

Recommendations

• Derivatives of parsing expression grammars
• Parsing with derivatives
• scientific article; zbMATH DE number 2145000
• Combinators for parsing expressions
• Some aspects of parsing expression grammar
• Partial derivatives of an extended regular expression
• Computation of regular expression derivatives
• Linear parsing expression grammars
• Derivatives for Enhanced Regular Expressions
• Bottom-Up derivatives of tree expressions

Cited in

(3)

• Derivatives of parsing expression grammars
• Manipulation of regular expressions using derivatives: an overview
• A Linear Parsing Algorithm For Parenthesis Terms

This page was built for publication: Simplified parsing expression derivatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782605)