A Derivative-Based Parser Generator for Visibly Pushdown GrammarsIn-Person
Fri 22 Oct 2021 19:20 - 19:35 at Zurich B - Optimization - mirror Chair(s): Tony Hosking
In this paper, we present a derivative-based, functional recognizer and parser generator for visibly pushdown grammars. The generated parser accepts ambiguous grammars and produces a parse forest containing all valid parse trees for an input string in linear time. Each parse tree in the forest can then be extracted also in linear time. Besides the parser generator, to allow more flexible forms of the visibly pushdown grammars, we also present a translator that converts a tagged CFG to a visibly pushdown grammar in a sound way, and the parse trees of the tagged CFG are further produced by running the semantic actions embedded in the parse trees of the translated visibly pushdown grammar. The performance of the parser is compared with a popular parsing tool ANTLR and other popular hand-crafted parsers. The correctness of the core parsing algorithm is formally verified in the proof assistant Coq.
Fri 22 OctDisplayed time zone: Central Time (US & Canada) change
10:50 - 12:10 | |||
10:50 15mTalk | Copy-and-Patch Compilation: A Fast Compilation Algorithm for High-Level Languages and BytecodeVirtual OOPSLA DOI Pre-print | ||
11:05 15mTalk | VESPA: Static Profiling for Binary OptimizationVirtual OOPSLA Angelica Moreira Federal University of Minas Gerais, Guilherme Ottoni Facebook, Fernando Magno Quintão Pereira Federal University of Minas Gerais DOI | ||
11:20 15mTalk | A Derivative-Based Parser Generator for Visibly Pushdown GrammarsIn-Person OOPSLA Xiaodong Jia Pennsylvania State University, Ashish Kumar Pennsylvania State University, Gang (Gary) Tan Pennsylvania State University DOI | ||
11:35 35mLive Q&A | Discussion, Questions and Answers OOPSLA |
18:50 - 20:10 | |||
18:50 15mTalk | Copy-and-Patch Compilation: A Fast Compilation Algorithm for High-Level Languages and BytecodeVirtual OOPSLA DOI Pre-print | ||
19:05 15mTalk | VESPA: Static Profiling for Binary OptimizationVirtual OOPSLA Angelica Moreira Federal University of Minas Gerais, Guilherme Ottoni Facebook, Fernando Magno Quintão Pereira Federal University of Minas Gerais DOI | ||
19:20 15mTalk | A Derivative-Based Parser Generator for Visibly Pushdown GrammarsIn-Person OOPSLA Xiaodong Jia Pennsylvania State University, Ashish Kumar Pennsylvania State University, Gang (Gary) Tan Pennsylvania State University DOI | ||
19:35 35mLive Q&A | Discussion, Questions and Answers OOPSLA |