TY - JOUR
T1 - Memoized zipper-based attribute grammars and their higher order extension
AU - Fernandes, João Paulo
AU - Martins, Pedro
AU - Pardo, Alberto
AU - Saraiva, João
AU - Viera, Marcos
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2019/3/15
Y1 - 2019/3/15
N2 - Attribute grammars are a powerfull, well-known formalism to implement and reason about programs which, by design, are conveniently modular. In this work we focus on a state of the art zipper-based embedding of classic attribute grammars and higher-order attribute grammars. We improve their execution performance through controlling attribute (re)evaluation by means of memoization techniques. We present the results of our optimizations by comparing their impact in various implementations of different, well-studied, attribute grammars and their Higher-Order extensions.
AB - Attribute grammars are a powerfull, well-known formalism to implement and reason about programs which, by design, are conveniently modular. In this work we focus on a state of the art zipper-based embedding of classic attribute grammars and higher-order attribute grammars. We improve their execution performance through controlling attribute (re)evaluation by means of memoization techniques. We present the results of our optimizations by comparing their impact in various implementations of different, well-studied, attribute grammars and their Higher-Order extensions.
KW - Attribute grammars
KW - Embedded domain specific languages
KW - Functional programming
KW - Memoization
KW - Zipper data structure
UR - http://www.scopus.com/inward/record.url?scp=85057128890&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057128890&partnerID=8YFLogxK
U2 - 10.1016/j.scico.2018.10.006
DO - 10.1016/j.scico.2018.10.006
M3 - Article
AN - SCOPUS:85057128890
SN - 0167-6423
VL - 173
SP - 71
EP - 94
JO - Science of Computer Programming
JF - Science of Computer Programming
ER -