In this lecture we study the declarative disambiguation of declarative syntax definitions using associativity and priority rules. As a prelimary to understanding disambiguation, we first study the semantics of context-free grammars in terms of sentence and tree derivation. We discuss the semantics of such rules in terms of subtree exclusion and how (simple) disambiguations can be expressed by means of grammar transformation.
We end with a discussion of disambiguation using layout constraints, in order to express layout-sensitive syntax.
Slides
References
-
Declarative specification of indentation rules: a tooling perspective on parsing and pretty-printing layout-sensitive languagesIn layout-sensitive languages, the indentation of an expression or statement can influence how a program is parsed. While some of these languages (e.g., Haskell and Python) have been widely adopted, there is little support for software language engineers in building tools for layout-sensitive languages. As a result, parsers, pretty-printers, program analyses, and refactoring tools often need to be handwritten, which decreases the maintainability and extensibility of these tools. Even state-of-the-art language workbenches have little support for layout-sensitive languages, restricting the development and prototyping of such languages. In this paper, we introduce a novel approach to declarative specification of layout-sensitive languages using layout declarations. Layout declarations are high-level specifications of indentation rules that abstract from low-level technicalities. We show how to derive an efficient layout-sensitive generalized parser and a corresponding pretty-printer automatically from a language specification with layout declarations. We validate our approach in a case-study using a syntax definition for the Haskell programming language, investigating the performance of the generated parser and the correctness of the generated pretty-printer against 22191 Haskell files.