A Derivative-based Parser Generator for Visibly Pushdown Grammars
summary
A derivative-based parser generator converts visibly pushdown grammars to a deterministic PDA and produces a shared parse forest in linear time, with a verified core derivative-based conversion to a deterministic PDA and formally verified in Coq. A tagged-CFG validator and translator emit VPGs so semantic actions in the VPG yield original CFG trees. Evaluation reuses ANTLR lexers and reports parse forest in linear time and performance gains: 4x faster on JSON, 5x on XML, 4 orders of magnitude on HTML.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:13Visibly Pushdown Grammars
- 1:49An example VPG for XML
- 2:41A comparison of VPGs and CFGS
- 3:25Motivation
- 3:46Contributions
- 4:29The parser generator for VPGs
- 5:16The derivative-based recognition
- 7:26The derivative-based parser
- 9:24A surface grammar for VPG
- 10:32Applicability
- 11:23Performance comparison with ANTLR Experimental setup
- 12:04Performance comparison with JSON and XML hand- written parsers
- 13:10Conclusions
related talks
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
23mV-Star: Learning Visibly Pushdown Grammars from Program Inputs
14mFast Incremental PEG Parsing
44mParsing Text with a Virtual Machine
15mA Semantic Framework for PEGs
16mAutomatically Deriving Control-Flow Graph Generators from Operational Semantics
37mThe Art of Parsing
21mSynthesizing Formal Semantics from Executable Interpreters