A Direct Semantics for Declarative Disambiguation of Expression Grammars

Eelco Visser

In this talk I present our recent work on proving the safety and completeness of a semantics for disambiguation of context-free expression grammars with associativity and priority declarations.

Abstract

Context-free grammars in reference manuals and academic papers are often ambiguous, yet, they provide concise descriptions and a direct correspondence between abstract syntax trees and grammar rules. A major part of such ambiguities arise from the subset of a grammar that specifies expressions. Disambiguation of expressions in context-free grammars by means of priority and associativity declarations enables a direct correspondence between grammar and abstract syntax trees, more concise grammars, and a better expression of intent than encoding associativity and priority in the grammar.

There is no standardized, declarative semantics of disambiguation with associativity and priority declarations. Indirect approaches to the semantics use a translation into another formalism (such as parse tables or tree automata), inhibiting generalization and/or understanding. A direct approach defines the semantics of priority and associativity declarations by means of subtree exclusion patterns, which are independent of a particular parsing algorithm or grammar transformation. However, existing definitions of direct approaches are not safe, and/or do not cover all cases of expression ambiguities.

In this paper, we provide the first direct semantics of disambiguation by means of associativity and priority declarations that is \emph{safe} and complete, and not limited to simple expression grammars. We define a semantics for safe disambiguation with priority and associativity in terms of shallow subtree exclusion patterns, filtering trees only when the input is ambiguous. We extend the semantics with a formal definition of deep priority conflicts, covering additional ambiguities in more complex expression grammars that cannot be solved by fixed-depth patterns, such as ambiguities due to low precedence prefix or postfix operators, dangling prefix, dangling suffix, longest match, and indirect recursion. We have implemented the semantics in a parser generator for SDF3, evaluating the approach by applying it to the grammars of five languages. Finally, we demonstrate that our approach is practical by measuring the performance of a parser that implements our disambiguation techniques, applying it to a corpus of real-world Java and OCaml programs.

---

Previous: | Scopes as Types
Next: Peter Mosses | Reuse and co-evolution in CBS language specifications