Indexical attribute grammars

In this dissertation we define a new attribute grammar system--Indexical Attribute Grammars (IAG). In IAG we define attributes over an implicit indexical context space. The indexical context space is a multidimensional space which is the product of a tree dimension, a multitime dimension, and an identifier dimension. Attributes on the indexical context space are intensions, whose values vary over different contexts: nodes of a parse tree, multitime points, and symbols. Indexical attribute grammars with denotational semantics form a new class of attribute grammars.;Indexical attribute grammars allow non-local attribute dependencies by using node switching operators. The use of communication attributes can therefore be reduced substantially in indexical attribute grammars.;Indexical attribute grammars can define attributes based on iterative algorithms. The value of an attribute at a node on a given parse tree can be defined as a data stream (or a nested data stream for a nested iteration) over the multitime dimension. The value of an attribute at a time point can be viewed as the value of the attribute at a particular step of the iteration. The attributes defined by iterative algorithms are temporal attributes, varying over the multitime dimension. Circular attributes whose evaluation can be terminated can be defined as non-circular but temporal attributes using time switching operators.;In indexical attribute grammars, we can define an aggregate attribute at a node on a given parse tree as a collection of values, gathered from other nodes, which varies over the identifier dimension. The information about identifiers can be collected as elements at the corresponding identifier points in the aggregate attribute. An aggregated value in the identifier dimension is not monolithic, its individual elements can be referred to by other attribute definitions through context switching operators.;The attribute evaluation of indexical attribute grammars is based on the tagged demand-driven computation model. The definitions of attributes on a given parse tree form a dataflow graph. The evaluation of the attributes on the tree is the evaluation of the corresponding dataflow graph. Following the demand-driven method, only the values that are demanded at certain contexts are evaluated.