A Direct Semantics of Disambiguation by Associativity and Priority Rules

Eelco Visser

Associativity and priority rules provide a mechanism for disambiguation of context-free grammars that is based on concepts familiar to programmers from high-school mathematics. However, there is no standardized and declarative semantics for such rules, in particular for the disambiguation of the more complex expression grammars encountered in programming languages.

In recent work, we provide a direct semantics of disambiguation of expression grammars by means of associativity and priority declarations by defining the subtree exclusion patterns corresponding to each declaration. We introduce deep priority conflicts to solve ambiguities that cannot be captured by fixed-depth patterns such as ambiguities due to low priority prefix or postfix operators, dangling prefix, dangling suffix, longest match, and indirect recursion. We prove that the semantics is safe (preserves the language of the underlying context-free grammar) and complete (solves all ambiguities) for classes of expression grammars of increasing complexity that have only harmless overlap, provided a total set of disambiguation rules is provided.

In this talk, I will explain the problem and the approach to proving safety and completeness that I have developed in the last couple of months, focusing on the basic case of infix expression grammars.

---

Previous: Jasper Denkers | Early Validation and Global Optimization for Parametric Manufacturing Systems
Next: | Dynamix on the Frame VM: Declarative dynamic semantics on a VM using scopes as frames