In this lecture we study constraint-based static semantic analysis using the scope graph framework for name resolution. After first exploring the concepts, we then look at the realization of these concepts in the NaBL2 meta DSL. To illustrate NaBL2 we use excerpts from a definition of name and type analysis for the Tiger language.
Pierre Neron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth. A Theory of Name Resolution. ESOP 2015
This award winning paper introduces scope graphs for describing the binding and scoping facts of programs. A resolution calculus describes how references resolve to declarations in terms of a reachability and visibility relation. A resolution algorithm is shown to be sound and complete with respect to the calculus.
Hendrik van Antwerpen, Pierre Neron, Andrew P. Tolmach, Eelco Visser, Guido Wachsmuth. A Constraint Language for Static Semantic Analysis based on Scope Graphs. PEPM 2016
This paper introduces a constraint language for name and type analysis based on scope graphs, a semantics for the language, and an algorithm for solving constraints. The paper shows an example of constraint generation for a toy language. This approach is the basis for the design of the NaBL2 language, which supports the definition of rules that transform an AST to a collection of constraints. The paper coins the term ‘type-dependent name resolution’ to characterize name resolutions that interact with type analysis.