Statically Scheduling Circular Remote Attribute Grammars

Abstract

Classical attribute grammars invented by Knuth have been the subject of extensive study. Over the years there have been various extensions introduced, each with the goal of making attribute grammar more useful for applications such as program analysis. The first extension described here is circular attribute grammar by Farrow. It is followed by remote attribute grammar, which was introduced separately by Boyland and Hedin. More recently, Hedin introduced circular remote attribute grammars and a proof of concept implementation with demand evaluation. Remote attribute grammars make it possible for semantic rules to access attributes of nodes that are not local, and circular attribute grammars make it possible to define and solve problems that are circularly defined. Combining these two extensions opens the door that enables users to define various circular tree problems in attribute grammars. Having the means to evaluate circular remote attribute grammars efficiently both in terms of space and time complexity is important for real-world applications. Unfortunately, demand evaluation methods lack in both aspects. However, another type of static evaluation called visit sequence evaluation was introduced earlier by Kastens for l-ordered subset of classical attribute grammars. This evaluation method is efficient as schedules are generated statically and not dependent on a particular derivation. The goal of this thesis is to statically schedule and evaluate circular remote attribute grammars, and lastly, implement these changes into APS which is a declarative attribute grammar system introduced by Boyland.