WG211/M18Visser

Declarative Disambiguation of Deep Priority Conflicts, Eelco Visser

Disambiguation of context-free grammars for operator expressions 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. However, 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. The direct approach defines the semantics of priority and associativity declarations by means of subtree exclusion patterns. However, existing definitions of this direct approach are not safe and/or not complete.

In this paper, we provide the first direct semantics of disambiguation by means of associativity and priority declarations that is safe and complete, and not limited to one-level tree patterns. We define a semantics for safe disambiguation with operator priority and associativity in terms of one-level subtree exclusion patterns, i.e., one that only filters trees when the input is ambiguous. We extend the semantics with a formal definition of deep priority conflicts that are not covered by fixed-depth patterns. We show how this semantics can be used to resolve ambiguities such as dangling else and longest match. Furthermore, we extend the approach to productions with indirect recursion. We have implemented the semantics in a parser generator for SDF3 and we have evaluated the approach by applying it to the grammars of seven languages.