New Generation Computing, 22(2004)37-60
Ohmsha, Ltd. and Springer-Verlag

Circular Attribute Grammars with Remote Attribute References and their Evaluators

Akira SASAKI
The Institute of Medical Science, The University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan
sasaki@ims.u-tokyo.ac.jp
Masataka SASSA
Tokyo Institute of Technology
2-12-1 O-okayama, Meguro-ku, Tokyo 152-8552, Japan
sassa@is.titech.ac.jp

Received 7 June 2002
Revised manuscript received 10 January 2003

Abstract

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as "goto" in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposes circular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called a mostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators.

Keywords:Attribute Grammars, Circular Attribute Grammars, Attribute Evaluators, Declarative Languages, Compiler Construction.

[Back]