William H. Maddox III

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-97-948

, 1997

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-948.pdf

Language-based programming environments provide some or all of the functionality of a compiler, an interactive debugger, a browser, and a configuration manager behind a unified user interface based on an editing paradigm. As the user edits a program, the changes are processed incrementally, allowing for low-latency updates to derived information. This information can be made available to interactive environment services, such as browsing, navigation, and "real time" error-reporting. <p>In this dissertation, we address an important subproblem in the construction of such environments, the generation of static semantic analyzers that operate in an incremental mode. Our work is embodied in the Colander II system, which introduces both a new metalanguage for the declarative specification of static semantic analyses and new techniques for generating an incremental analyzer from these specifications automatically. <p>Our specification metalanguage melds the advantages of traditional attribute grammars, including amenability to extensive generation-time analysis, with the expressiveness and client-independence characteristic of Ballance's Logical Constraint Grammars. In comparison to traditional attribute grammars, our metalanguage allows much more of the incrementality inherent in a particular analysis task to be exposed within the formalism itself, where it can be exploited automatically by our implementation. <p>Our incremental analysis algorithms exploit the attributed objects and function-valued attributes provided by our metalanguage, mapping these expressive notations onto a fine-grained incremental implementation. We are thus able to automatically generate incremental analyzers that handle long-distance dependencies and aggregate attributes efficiently. Our methods allow unusual freedom to control the granularity of incremental evaluation, allowing performance tradeoffs to be chosen as demanded by the needs of the application rather than as dictated by the a priori requirements of the algorithms. <p>We have also developed a static analysis and transformation on attribute grammars that accommodates a useful class of circular attribute dependencies, automating the "backpatching" method used in hand-coded compilers. The transformation is employed in Colander II, but is applicable to attribute grammars in general. <p>We have used the Colander II system to create a static semantic analyzer for the programming language Modula-2, which has revealed both strengths and weakness in our specification paradigm. Interestingly, the most significant difficulty that we encountered applies equally to traditional attribute grammars, but has not been widely appreciated in the attribute grammar literature. <p>Our work was performed in the context of the Ensemble project at UC Berkeley, which is constructing a prototype integrated multilingual language-based software development environment based on the editing of structured multimedia documents.

Advisors: Susan L. Graham

---

BibTeX citation:

@phdthesis{Maddox III:CSD-97-948,
    Author= {Maddox III, William H.},
    Title= {Incremental Static Semantic Analysis},
    School= {EECS Department, University of California, Berkeley},
    Year= {1997},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5887.html},
    Number= {UCB/CSD-97-948},
    Abstract= {Language-based programming environments provide some or all of the functionality of a compiler, an interactive debugger, a browser, and a configuration manager behind a unified user interface based on an editing paradigm. As the user edits a program, the changes are processed incrementally, allowing for low-latency updates to derived information. This information can be made available to interactive environment services, such as browsing, navigation, and "real time" error-reporting. <p>In this dissertation, we address an important subproblem in the construction of such environments, the generation of static semantic analyzers that operate in an incremental mode. Our work is embodied in the Colander II system, which introduces both a new metalanguage for the declarative specification of static semantic analyses and new techniques for generating an incremental analyzer from these specifications automatically. <p>Our specification metalanguage melds the advantages of traditional attribute grammars, including amenability to extensive generation-time analysis, with the expressiveness and client-independence characteristic of Ballance's Logical Constraint Grammars. In comparison to traditional attribute grammars, our metalanguage allows much more of the incrementality inherent in a particular analysis task to be exposed within the formalism itself, where it can be exploited automatically by our implementation. <p>Our incremental analysis algorithms exploit the attributed objects and function-valued attributes provided by our metalanguage, mapping these expressive notations onto a fine-grained incremental implementation. We are thus able to automatically generate incremental analyzers that handle long-distance dependencies and aggregate attributes efficiently. Our methods allow unusual freedom to control the granularity of incremental evaluation, allowing performance tradeoffs to be chosen as demanded by the needs of the application rather than as dictated by the a priori requirements of the algorithms. <p>We have also developed a static analysis and transformation on attribute grammars that accommodates a useful class of circular attribute dependencies, automating the "backpatching" method used in hand-coded compilers. The transformation is employed in Colander II, but is applicable to attribute grammars in general. <p>We have used the Colander II system to create a static semantic analyzer for the programming language Modula-2, which has revealed both strengths and weakness in our specification paradigm. Interestingly, the most significant difficulty that we encountered applies equally to traditional attribute grammars, but has not been widely appreciated in the attribute grammar literature. <p>Our work was performed in the context of the Ensemble project at UC Berkeley, which is constructing a prototype integrated multilingual language-based software development environment based on the editing of structured multimedia documents.},
}

EndNote citation:

%0 Thesis
%A Maddox III, William H. 
%T Incremental Static Semantic Analysis
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-97-948
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5887.html
%F Maddox III:CSD-97-948