Monadification of Attribute Grammars

Eric Van Wyk

This work brings together aspects of structural operational semantics (SOS) and attribute grammars (AGs) for the concise specification of the typing and evaluation of programs that also handle error cases in an non-obtrusive way. SOS inference rules provide concise easy-to-read specifications, and they are a convenient formalism for reasoning about meta-theoretic properties. They are typically less useful for generating compilers and interpreters because they are, in a sense, incomplete. For typing, the inference rules provide a derivation only for type-correct programs; for evaluation, they provide a complete trace only for programs without run-time errors. There is no useful feedback to the programmer when their programs has typing or evaluation errors. AGs, however, are complete in that they compute attribute values for any syntactically correct tree, but the management of error conditions and error messages can clutter the specification, making it harder to read and reason about. Monads in functional programming provide a means for managing errors in computations, but the explicit use of monads, in the form of returns, binds, and do-notations, also clutter to specification. We describe a method for ``monadifying’’ an AG specification such that most equations defining attribute values are a direct transcription of SOS inference rules and the monadic constructs are only used when program errors are detected. We demonstrate this technique for concise typing and error reporting and easy specification of non-deterministic evaluation of expressions.

---

Previous: Eric Van Wyk | Attribute Grammars: Composable and Modular Language Specifications
Next: Elizabeth Scott | A romp through generalised syntax analysis