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

sle2015
15:30 - 17:00: SLE - Tools II and Closing at Grand Station 2
Chair(s): Anya Helene BaggeUniversity of Bergen, Norway
sle201515:30 - 16:00
Talk
David PearceVictoria University of Wellington
DOI
sle201516:00 - 16:30
Talk
Nicolas LaurentUniversité Catholique de Louvain, Belgium, Kim MensUniversité Catholique de Louvain, Belgium
DOI Pre-print
sle201516:30 - 17:00
Day closing