SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Thu 23 Oct 2014 15:30 - 15:52 at Salon F - Compilation Tools Chair(s): Robert Grimm

Despite the advances made by modern parsing strategies such as PEG, LL(), GLR, and GLL, parsing is not a solved problem. Existing approaches suffer from a number of weaknesses, including difficulties supporting side-effecting embedded actions, slow and/or unpredictable performance, and counterintuitive matching strategies. This paper introduces the ALL() parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down LL(k) parsers with the power of a GLR-like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets ALL() handle any non-left-recursive context-free grammar. ALL() is O(n^4) in theory but consistently performs linearly on grammars used in practice, outperforming general strategies such as GLL and GLR by orders of magnitude. ANTLR 4 generates ALL() parsers and supports direct left-recursion through grammar rewriting. Widespread ANTLR 4 use (5000 downloads/month in 2013) provides evidence that ALL() is effective for a wide variety of applications.

Slides from talk (ALL(*).pdf)1.45MiB

Thu 23 Oct
Times are displayed in time zone: Tijuana, Baja California change

15:30 - 17:00: Compilation ToolsOOPSLA at Salon F
Chair(s): Robert GrimmGoldman Sachs
15:30 - 15:52
Talk
Adaptive LL(*) Parsing: The Power of Dynamic Analysis
OOPSLA
Terence ParrUniversity of San Francisco, Sam HarwellUniversity of Texas at Austin, Kathleen FisherTufts University
Link to publication File Attached
15:52 - 16:15
Talk
Automated Migration of Build Scripts using Dynamic Analysis and Search-Based Refactoring
OOPSLA
Milos GligoricUniversity of Illinois at Urbana-Champaign, Wolfram SchulteMicrosoft, Chandra PrasadMicrosoft, Danny van VelzenMicrosoft, Iman NarasamdyaMicrosoft, Ben LivshitsMicrosoft Research
Link to publication
16:15 - 16:37
Talk
Mix10: Compiling MATLAB to X10 for High Performance
OOPSLA
Vineet Kumar, Laurie HendrenMcGill University
Link to publication
16:37 - 17:00
Talk
Staged Parser Combinators for Efficient Data Processing
OOPSLA
Manohar JonnalageddaEPFL, Switzerland, Thierry CoppeyEPFL, Switzerland; Google, Sandro StuckiEPFL, Switzerland, Tiark RompfPurdue & Oracle Labs, Martin OderskyEcole Polytechnique Federale de Lausanne
Link to publication