‹Programming› 2018
Mon 9 - Thu 12 April 2018 Nice, France
Wed 11 Apr 2018 11:00 - 11:30 at Baie des Anges A + B - Session 1

Context. Context-free grammars are widely used for language prototyping. They allow formalizing the syntax of domain-specific or general-purpose programming languages concisely and declaratively. However, the natural and concise way of writing a context-free grammar is often ambiguous. Therefore, grammar formalisms support extensions in the form of declarative disambiguation rules, to address ambiguities from operator precedence and associativity.

Inquiry. Implementing support for declarative disambiguation within a parser typically comes with one or more of the following limitations in practice: a lack of parsing performance, or a lack of modularity (i.e., disallowing the composition of grammar fragments of potentially different languages). The latter subject is generally addressed by scannerless generalized parsers. We aim to equip scannerless generalized parsers with novel disambiguation methods that are inherently performant, without compromising the concerns of modularity and language composition.

Approach. In this paper, we present a novel low-overhead implementation technique for disambiguating deep associativity and priority conflicts in scannerless generalized parsers with lightweight data-dependency.

Knowledge. Ambiguities with respect to operator precedence and associativity arise from combining the various operators of a language. While shallow conflicts can be resolved efficiently by one-level tree patterns, deep conflicts require more elaborate techniques, because they can occur arbitrarily nested in a tree. Current state-of-the-art approaches to solving deep priority conflicts come with a severe performance overhead.

Grounding. We evaluated our new approach against state-of-the-art declarative disambiguation mechanisms. By parsing a corpus of popular open-source repositories written in Java and OCaml, we found that our approach yields speedups of up to 1.73x over related work when parsing programs with deep priority conflicts — with a modest overhead of 1% to 2% when parsing programs without deep conflicts.

Importance. A recent empirical study shows that deep priority conflicts are indeed wide-spread in practice. The study shows that in a corpus of popular OCaml projects on Github, up to 17% of the source files contain deep priority conflicts, which would benefit from efficient disambiguation.

Wed 11 Apr

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:30 - 12:00
10:30
30m
Talk
Scoped Extension Methods in Dynamically-Typed Languages
Research Papers
Guillermo Polito CNRS, Camille Teruel INRIA, Stéphane Ducasse INRIA Lille, Luc Fabresse Mines Douai
Link to publication DOI
11:00
30m
Talk
Towards Zero-Overhead Disambiguation of Deep Priority Conflicts
Research Papers
Luis Eduardo de Souza Amorim Delft University of Technology, Netherlands, Michael J. Steindorfer Delft University of Technology, Eelco Visser Delft University of Technology
Link to publication DOI
11:30
30m
Talk
Language-integrated provenance in Haskell
Research Papers
Jan Stolarek University of Edinburgh, UK, James Cheney University of Edinburgh, UK
Link to publication DOI