SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Fri 22 Oct 2021 11:20 - 11:35 at Zurich B - Optimization Chair(s): Fredrik Kjolstad
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 Oct

Displayed time zone: Central Time (US & Canada) change

10:50 - 12:10
OptimizationOOPSLA at Zurich B +8h
Chair(s): Fredrik Kjolstad Stanford University
10:50
15m
Talk
Copy-and-Patch Compilation: A Fast Compilation Algorithm for High-Level Languages and BytecodeDistinguished PaperVirtual
OOPSLA
Haoran Xu Stanford University, Fredrik Kjolstad Stanford University
DOI Pre-print
11:05
15m
Talk
VESPA: Static Profiling for Binary OptimizationVirtual
OOPSLA
Angelica Aparecida Moreira Federal University of Minas Gerais, Guilherme Ottoni Facebook, Fernando Magno Quintão Pereira Federal University of Minas Gerais
DOI
11:20
15m
Talk
A Derivative-Based Parser Generator for Visibly Pushdown GrammarsIn-Person
OOPSLA
Xiaodong Jia Pennsylvania State University, Ashish Kumar Pennsylvania State University, Gang Tan Pennsylvania State University
DOI
11:35
35m
Live Q&A
Discussion, Questions and Answers
OOPSLA

18:50 - 20:10
Optimization - mirrorOOPSLA at Zurich B
Chair(s): Tony Hosking Australian National University
18:50
15m
Talk
Copy-and-Patch Compilation: A Fast Compilation Algorithm for High-Level Languages and BytecodeDistinguished PaperVirtual
OOPSLA
Haoran Xu Stanford University, Fredrik Kjolstad Stanford University
DOI Pre-print
19:05
15m
Talk
VESPA: Static Profiling for Binary OptimizationVirtual
OOPSLA
Angelica Aparecida Moreira Federal University of Minas Gerais, Guilherme Ottoni Facebook, Fernando Magno Quintão Pereira Federal University of Minas Gerais
DOI
19:20
15m
Talk
A Derivative-Based Parser Generator for Visibly Pushdown GrammarsIn-Person
OOPSLA
Xiaodong Jia Pennsylvania State University, Ashish Kumar Pennsylvania State University, Gang Tan Pennsylvania State University
DOI
19:35
35m
Live Q&A
Discussion, Questions and Answers
OOPSLA