Cactus - a Concrete to Abstract syntax Conversion Tool with User-friendly Syntax

This talk is about the parser generator Cactus, developed by Niklas Martinsson, an MSc student I supervised at Chalmers, spring 2001. When he first came to me with the idea, I was rather skeptical: there are so many parser generators already, so why design a new one? But in the end, I was pleased with the result.

With Cactus, you write one combined specification, from which the tool generates, a lexer, a parser and (using type inference) data types for the abstract syntax. This significantly reduces the amount of work required to implement a parser, compared to, say, using the parser generator Happy combined with the lexer generator Alex, and Haskell. Also, while common parser generators like Happy and Yacc support a very simple BNF grammar notation, Cactus also supports an EBNF-like notation.

Also, rather than allowing arbitrary code as semantic actions in the grammar, Cactus provides a restricted language of data constructors and simple built-in functions. This means that the code Cactus generates is always correct (no compiler errors) and makes it possible to generate parsers in different programming languages from the same specification. Back-ends for Haskell (using Alex and Happy) and C (using Yacc and Flex) have been implemented.


Thomas Hallgren