TY - JOUR
T1 - Origin tracking in attribute grammars
AU - Williams, Kevin
AU - van Wyk, Eric
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - Origin tracking is a technique for relating the output of a transformation back to its input. In term rewriting systems, where this notion was developed, it relates subtrees in the resulting normal form term to the original term. The technique is useful in several settings, including program debugging and error reporting. We show how origin tracking can be integrated into higher-order attribute grammars, which construct new syntax trees during attribute evaluation. Furthermore, we extend origins with additional information to track sub trees that correspond to the redex and contractum of rewrite rules when implemented using attribute grammars. The computation of origins and their extensions is formally defined using big-step operational semantics. Finally we describe a program transformation framework as an example use of origin tracking in attribute grammars.
AB - Origin tracking is a technique for relating the output of a transformation back to its input. In term rewriting systems, where this notion was developed, it relates subtrees in the resulting normal form term to the original term. The technique is useful in several settings, including program debugging and error reporting. We show how origin tracking can be integrated into higher-order attribute grammars, which construct new syntax trees during attribute evaluation. Furthermore, we extend origins with additional information to track sub trees that correspond to the redex and contractum of rewrite rules when implemented using attribute grammars. The computation of origins and their extensions is formally defined using big-step operational semantics. Finally we describe a program transformation framework as an example use of origin tracking in attribute grammars.
UR - http://www.scopus.com/inward/record.url?scp=84921775278&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84921775278&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-11245-9_16
DO - 10.1007/978-3-319-11245-9_16
M3 - Article
AN - SCOPUS:84921775278
SN - 0302-9743
VL - 8706
SP - 282
EP - 301
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -