SUPPORT ALGORITHMS FOR INCREMENTAL ATTRIBUTE EVALUATION OF ASYNCHRONOUS SUBTREE REPLACEMENTS

We attack the problem of incremental attribute evaluation for multiple asynchronous subtree replacements applicable to arbitrary noncircular attribute grammars. Our algorithm supports multiple independent editi ng cursors. Concurrent evaluation processes proceed independently as l ong as they cover disjoint regions of the derivation tree. Evaluation processes are merged when they overlap, to prevent unnecessary attribu te evaluations. The algorithm ensures that when evaluation terminates, the tree is consistently attributed. Our results solve two open probl ems in the original algorithm for asynchronous subtree replacements re ported by Kaplan and Kaiser.