Declarative Disambiguation with Contextual Scoping
Context-free grammars are suitable for formalizing the syntax of programming languages concisely and declaratively, however, the natural and concise way of writing a context-free grammar is often ambiguous. In particular, ambiguities arise from combining operators with different precedence and associativity relations, causing either shallow conflicts that can be resolved locally or deep conflicts that require sophisticated non-local resolution techniques. Declarative disambiguation of operator precedence and associativity conflicts is an ongoing research topic, where guaranteeing safety and completeness properties is non-trivial. Safe disambiguation denotes that all valid inputs are accepted by the parser, i.e., if an input string belongs to the language covered by the grammar, then the parser should produce at least one tree. Complete disambiguation states that the declarative priority relations specified together with the grammar can disambiguate all combinations of operators, i.e., for any input constructed combining the operators from the grammar, at most one tree is produced.
Contextual grammars [de Souza Amorim et al. 2017] are a recent formalism that propose a general framework for solving deep priority conflicts, while guaranteeing both safety and completeness. The underlying approach relies on grammar transformations for generating additional productions that forbid deep conflicting patterns before parser generation. In this talk, we will introduce the foundations of contextual grammars, what problem they solve and what challenges still remain. In particular, we address how to increase the performance of parsing with contextual grammars by adapting ideas from name resolution theory [Antwerpen et al. 2016; Néron et al. 2015], paired with novel implementation techniques, while getting domain-specific debugging for free.
Sun 22 Oct
|14:00 - 14:30|
|14:30 - 15:00|
Vadim ZaytsevRaincode Labs, Belgium