A Formalisation of Parameterised Reference Attribute Grammars
Channel: Splash Conference 2017
Date: 2017-10-28

Scott Buckley, Anthony Sloane
The similarities and differences between attribute grammar systems are obscured by their implementations.

A formalism that captures the essence of such systems would allow for equivalence, correctness, and other analyses to be formally framed and proven. We present Saiga, a core language and small-step operational semantics that precisely captures the fundamental concepts of the specification and execution of parameterised reference attribute grammars.

We demonstrate the utility of Saiga by a) proving a meta-theoretic property about attribute caching, and b) by specifying two attribute grammars for a realistic name analysis problem and proving that they are equivalent.

The language, semantics and associated tests have been mechanised in Coq; we are currently mechanising the proofs.