Formal semantics of declarative disambiguation rules

Luka Miljak

Date: Wed, September 06, 2023
Time: 12:00
Room: Turing 0.E420
Note: This is a talk on ongoing research

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: |
Next: Ralf Lämmel, Eric Van Wyk |