The Kennedy-Warren algorithm revisited: ordering Attribute Grammars

J. Bransen; A. Middelkoop; A. Dijkstra; S.D. Swierstra

doi:10.1007/978-3-642-27694-1_14

The Kennedy-Warren algorithm revisited: ordering Attribute Grammars

J. Bransen, A. Middelkoop, A. Dijkstra, S.D. Swierstra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Attribute Grammars (AGs) are a powerful tool for defining an executable semantics of a programming language, and thus for implementing a compiler. An execution plan for an AG determines a static evaluation order for the attributes which are defined as part of an AG specification. In building the Utrecht Haskell Compiler (UHC), a large scale AG project, we discovered that the Ordered AG approach (Kastens, 1980) for building such plans becomes impractical: the additional dependencies between attributes introduced by this algorithm too often result in grammars for which no execution plan can be generated. To avoid such problems we have implemented a refined version of the algorithm of Kennedy and Warren (1976) as part of our purely functional AG system and show how this algorithm solves the problems that surface with the Ordered AG approach. Furthermore, we present the results of applying this algorithm to the UHC code and show that this approach in some cases also has a positive effect on the runtime of the resulting program.

Original language	English
Title of host publication	Practical Aspects of Declarative Languages
Editors	C. Russo, N.-F. Zhou
Publisher	Springer
Pages	183-197
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-27694-1_14
Publication status	Published - 23 Jan 2012

Access to Document

10.1007/978-3-642-27694-1_14

Cite this

@inproceedings{498fd3bdec014dc9b152046fb74317ef,

title = "The Kennedy-Warren algorithm revisited: ordering Attribute Grammars",

abstract = "Attribute Grammars (AGs) are a powerful tool for defining an executable semantics of a programming language, and thus for implementing a compiler. An execution plan for an AG determines a static evaluation order for the attributes which are defined as part of an AG specification. In building the Utrecht Haskell Compiler (UHC), a large scale AG project, we discovered that the Ordered AG approach (Kastens, 1980) for building such plans becomes impractical: the additional dependencies between attributes introduced by this algorithm too often result in grammars for which no execution plan can be generated. To avoid such problems we have implemented a refined version of the algorithm of Kennedy and Warren (1976) as part of our purely functional AG system and show how this algorithm solves the problems that surface with the Ordered AG approach. Furthermore, we present the results of applying this algorithm to the UHC code and show that this approach in some cases also has a positive effect on the runtime of the resulting program.",

author = "J. Bransen and A. Middelkoop and A. Dijkstra and S.D. Swierstra",

year = "2012",

month = jan,

day = "23",

doi = "10.1007/978-3-642-27694-1_14",

language = "English",

pages = "183--197",

editor = "C. Russo and N.-F. Zhou",

booktitle = "Practical Aspects of Declarative Languages",

publisher = "Springer",

}

TY - GEN

T1 - The Kennedy-Warren algorithm revisited: ordering Attribute Grammars

AU - Bransen, J.

AU - Middelkoop, A.

AU - Dijkstra, A.

AU - Swierstra, S.D.

PY - 2012/1/23

Y1 - 2012/1/23

N2 - Attribute Grammars (AGs) are a powerful tool for defining an executable semantics of a programming language, and thus for implementing a compiler. An execution plan for an AG determines a static evaluation order for the attributes which are defined as part of an AG specification. In building the Utrecht Haskell Compiler (UHC), a large scale AG project, we discovered that the Ordered AG approach (Kastens, 1980) for building such plans becomes impractical: the additional dependencies between attributes introduced by this algorithm too often result in grammars for which no execution plan can be generated. To avoid such problems we have implemented a refined version of the algorithm of Kennedy and Warren (1976) as part of our purely functional AG system and show how this algorithm solves the problems that surface with the Ordered AG approach. Furthermore, we present the results of applying this algorithm to the UHC code and show that this approach in some cases also has a positive effect on the runtime of the resulting program.

AB - Attribute Grammars (AGs) are a powerful tool for defining an executable semantics of a programming language, and thus for implementing a compiler. An execution plan for an AG determines a static evaluation order for the attributes which are defined as part of an AG specification. In building the Utrecht Haskell Compiler (UHC), a large scale AG project, we discovered that the Ordered AG approach (Kastens, 1980) for building such plans becomes impractical: the additional dependencies between attributes introduced by this algorithm too often result in grammars for which no execution plan can be generated. To avoid such problems we have implemented a refined version of the algorithm of Kennedy and Warren (1976) as part of our purely functional AG system and show how this algorithm solves the problems that surface with the Ordered AG approach. Furthermore, we present the results of applying this algorithm to the UHC code and show that this approach in some cases also has a positive effect on the runtime of the resulting program.

U2 - 10.1007/978-3-642-27694-1_14

DO - 10.1007/978-3-642-27694-1_14

M3 - Conference contribution

SP - 183

EP - 197

BT - Practical Aspects of Declarative Languages

A2 - Russo, C.

A2 - Zhou, N.-F.

PB - Springer

ER -

The Kennedy-Warren algorithm revisited: ordering Attribute Grammars

Abstract

Access to Document

Fingerprint

Cite this