Language-Parametric Incremental and Parallel Name Resolution

Static analyses and transformations are an important part of programming and domain specific languages. For example; integrated development environments analyze programs for semantic errors such as incorrect names or types to warn the programmer about these errors. Compilers translate high-level programs into programs of another language or machine code, with the purpose of executing the program. Programmers make frequent and small edits to code fragments during development, making it infeasible to do analysis of the entire program for every change. To cope with this, each change must only trigger re-analysis of the changed fragment and its dependencies while keeping a consistent knowledge base of the program. In other words, the analysis must be incremental. Most computers today have multiple CPU cores and the trend is that CPU performance will scale in the number of cores, not in the performance of the core itself. To make use of these cores, the analyses must also be executable in parallel. Traditionally, an incremental and/or parallel analysis is handcrafted for each language, requiring substantial effort. In this thesis, we present a framework for performing incremental and parallel static program analyses and transformations based on a name binding specification. If such a specification is given and the framework is used, the analyses and transformations are executed incrementally and in parallel. Additionally, name resolution is also derived from a name binding specification, reducing the implementation effort even more. To specify name binding, we present the Spoofax Name Binding Language, a declarative meta-language for the specification of name binding and scope rules, which departs from the programmatic encodings of name binding provided by regular approaches. The specification is implemented using a symbol table infrastructure that automatically traces dependencies, and a language-parametric name resolution algorithm that performs name resolution and incremental scheduling of analyses. The framework is integrated in the Spoofax Language Workbench. Several case studies have been conducted to evaluate the approach.SERGSoftware TechnologyElectrical Engineering, Mathematics and Computer Scienc