A general incremental evaluator for attrbiute grammars

AbstractThis paper describes a new evaluator capable of handling noncircular or circular attribute grammars. The evaluator combines recursive evaluation of attribute instances and dynamic determination of paths in the compound dependency graph for a given input. The compound dependency graph is not constructed. Instead, the production-labelled semantic tree of the input and the dependency graphs of the productions which implicitly represent the compound dependency graph are used. The incremental version of the evaluator is obtained by a simple modification. It avoids re-evaluation of those attribute instances whose values are not affected by the modifications of the input. The evaluator has time complexity linear in the number of attributes needed to specify the meaning of the input string, and has space complexity linear in the size of the parse tree