Three Improvements on an Incremental Algorithm for Automatic Semantic Analysis

The formalism of attribute grammars is a powerful tool for specifying the static semantics of programming languages, and attribute evaluation provides an effective approach to automatic semantic analysis. The author previously proposed a time-optimal algorithm for incremental evaluation of ordered attribute grammars. In this paper, three improvements are suggested upon the algorithm so that it not only allows multiple subtree replacements, but also cancels three auxiliary tables required before. For experimental purposes, the improved algorithm has been implemented in Pascal on Motorola 68010.