Multi-plan attribute grammars

Author

Yang, Wuu

Author_Institution

Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan

fYear

1997

fDate

2-5 Dec 1997

Firstpage

62

Lastpage

71

Abstract

We identify a new class of non-circular attribute grammars, called the multi-plan attribute grammars, for which static evaluation plans can be computed. The class of multi-plan attribute grammars is larger than all currently known classes of non-circular attribute grammars with static evaluation plans. The decision procedure and the procedure for computing evaluation plans take essentially polynomial time under a new, more practical criterion (but the procedures still take exponential time based on the traditional criterion). The multi-plan attribute grammars lead to a new way to classify well-defined attribute grammars into a hierarchy based on the look-ahead behavior of the evaluators. Our work confirms a result of Riis and Skyum (1981), which says that all well-defined attribute grammars can be evaluated with static evaluators

Keywords

attribute grammars; computational complexity; graph grammars; graph theory; decision procedure; exponential time; graphs; look-ahead behavior; multiplan attribute grammars; noncircular attribute grammars; polynomial time; static evaluation plans; Computational Intelligence Society; Equations; Information science; Mars; Polynomials; Production; Statistics;

fLanguage

English

Publisher

ieee

Conference_Titel

Software Engineering Conference, 1997. Asia Pacific ... and International Computer Science Conference 1997. APSEC '97 and ICSC '97. Proceedings

Print_ISBN

0-8186-8271-X

Type

conf

DOI

10.1109/APSEC.1997.640162

Filename

640162