Tue 27 Oct 2015 16:00 - 16:30 at Grand Station 2 - Tools II and Closing Chair(s): Anya Helene Bagge

In this talk, I will explain that current parsers fail at a variety of tasks, and how to make parsers extensible so that users may overcome these hurdles by writing custom extensions.

Paper abstract: Parsing Expression Grammars (PEGs) define languages by specifying a recursive-descent parser that recognises them. The PEG formalism exhibits desirable properties, such as closure under composition, built-in disambiguation, unification of syntactic and lexical concerns, and closely matching programmer intuition. Unfortunately, state of the art PEG parsers struggle with left-recursive grammar rules, which are not supported by the original definition of the formalism and can lead to infinite recursion under naive implementations. Likewise, support for associativity and explicit precedence is spotty. To remedy these issues, we introduce Autumn, a general purpose PEG library that supports left-recursion, left and right associativity and precedence rules, and does so efficiently. Furthermore, we identify infix and postfix operators as a major source of inefficiency in left-recursive PEG parsers and show how to tackle this problem. We also explore the extensibility of the PEG paradigm by showing how one can easily introduce new parsing operators and how our parser accommodates custom memoization and error handling strategies. We compare our parser to both state of the art and battle-tested PEG and CFG parsers, such as Rats!, Parboiled and ANTLR.

Annotated version of the talk: http://norswap.com/making-parsers-extensible

Tue 27 Oct

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

15:30 - 17:00
Tools II and ClosingSLE at Grand Station 2
Chair(s): Anya Helene Bagge University of Bergen, Norway
The Whiley Rewrite Language (WyRL)
David J. Pearce Victoria University of Wellington
Parsing Expression Grammars Made Practical
Nicolas Laurent Université Catholique de Louvain, Belgium, Kim Mens Université Catholique de Louvain, Belgium
DOI Pre-print
Day closing