Formal semantics of declarative disambiguation rules

Luka Miljak

Plain context-free grammars are often ambiguous. Therefore, many syntax definition formalisms introduce declarative disambiguation rules such as priority (precedence) and associativity that allow the language developer to disambiguate their grammar. In this talk, I will present our ongoing research that answers the question: What are the formal semantics of declarative disambiguation rules?

In the current stage of the research, we introduce semantics that work for expression grammars. That is, context-free grammars with only one nonterminal. The semantics work by filtering parse trees in the ambiguous parse forest that match some illegal pattern. These patterns are generated by the disambiguation rules. We prove that these semantics are both safe and complete. Safety entails that applying the filter on a parse forest yields at least one parse tree, preserving the language. Completeness entails that applying the filter on a parse forest yields at most one parse tree, making the language completely unambiguous.

---

Previous: Ivar de Bruin | Improving Agda’s module system
Next: Ralf Lämmel, Eric Van Wyk | Invited Talks by Doctoral Committee Members