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 OctDisplayed time zone: Tijuana, Baja California change
15:30 - 17:00 | |||
15:30 22mTalk | Adaptive LL(*) Parsing: The Power of Dynamic Analysis OOPSLA Terence Parr University of San Francisco, Sam Harwell University of Texas at Austin, Kathleen Fisher Tufts University Link to publication File Attached | ||
15:52 22mTalk | Automated Migration of Build Scripts using Dynamic Analysis and Search-Based Refactoring OOPSLA Milos Gligoric University of Illinois at Urbana-Champaign, Wolfram Schulte Microsoft, Chandra Prasad Microsoft, Danny van Velzen Microsoft, Iman Narasamdya Microsoft, Ben Livshits Microsoft Research Link to publication | ||
16:15 22mTalk | Mix10: Compiling MATLAB to X10 for High Performance OOPSLA Link to publication | ||
16:37 22mTalk | Staged Parser Combinators for Efficient Data Processing OOPSLA Manohar Jonnalagedda EPFL, Switzerland, Thierry Coppey EPFL, Switzerland; Google, Sandro Stucki EPFL, Switzerland, Tiark Rompf Purdue & Oracle Labs, Martin Odersky Ecole Polytechnique Federale de Lausanne Link to publication |