Multi-plan attribute grammars

Wuu Yang

doi:10.1109/APSEC.1997.640162

Multi-plan attribute grammars

Wuu Yang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to conference › Paper › peer-review

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, which says that all well-defined attribute grammars can be evaluated with static evaluators.

Original language	English
Pages	62-71
Number of pages	10
DOIs	https://doi.org/10.1109/APSEC.1997.640162
State	Published - 5 Dec 1997
Event	Proceedings of the 1997 Asia-Pacific Software Engineering Conference and International Computer Science Conference, APSEC'97 and ICSC'97 - Hong Kong, Hong Kong Duration: 2 Dec 1997 → 5 Dec 1997

Conference

Conference	Proceedings of the 1997 Asia-Pacific Software Engineering Conference and International Computer Science Conference, APSEC'97 and ICSC'97
City	Hong Kong, Hong Kong
Period	2/12/97 → 5/12/97

Access to Document

10.1109/APSEC.1997.640162

Cite this

@conference{1754f011bcab40e79cc484ca48c649d8,

title = "Multi-plan attribute grammars",

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, which says that all well-defined attribute grammars can be evaluated with static evaluators.",

author = "Wuu Yang",

year = "1997",

month = dec,

day = "5",

doi = "10.1109/APSEC.1997.640162",

language = "English",

pages = "62--71",

note = "Proceedings of the 1997 Asia-Pacific Software Engineering Conference and International Computer Science Conference, APSEC'97 and ICSC'97 ; Conference date: 02-12-1997 Through 05-12-1997",

}

TY - CONF

T1 - Multi-plan attribute grammars

AU - Yang, Wuu

PY - 1997/12/5

Y1 - 1997/12/5

N2 - 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, which says that all well-defined attribute grammars can be evaluated with static evaluators.

AB - 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, which says that all well-defined attribute grammars can be evaluated with static evaluators.

UR - http://www.scopus.com/inward/record.url?scp=0031356727&partnerID=8YFLogxK

U2 - 10.1109/APSEC.1997.640162

DO - 10.1109/APSEC.1997.640162

M3 - Paper

AN - SCOPUS:0031356727

SP - 62

EP - 71

T2 - Proceedings of the 1997 Asia-Pacific Software Engineering Conference and International Computer Science Conference, APSEC'97 and ICSC'97

Y2 - 2 December 1997 through 5 December 1997

ER -

Multi-plan attribute grammars

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this