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

MSc Thesis by Niklas Martinsson, Chalmers, Göteborg, 2001.

Tuesday seminar at OGI on 10 June, 2003 by Thomas Hallgren.

Why a new parser generator?

There are so many already!

Links to some of these tools

Goals for Cactus

• User friendly syntax
  • Brief
  • Modular
  • Robust
  • Non-intrusive
• User friendly error messages
• Generate parsers in several languages from one syntax specification.

A comparison

• SabelCC: a parser generator for Java
• Happy+Alex: parser+lexer generators for Haskell

Grammar:

expr ::= expr + term
       | expr - term
       | term

term ::= term * factor
       | term / factor
       | factor

factor ::= number
         | ( expr )

Happy+Alex example

• SimpleMathParser.y (26 lines)
• SimpleMathLexer.x (21 lines)
• SimpleMathAbsSyn.hs (7 lines)

SabelCC example

Package SimpleMath;

Tokens
  l_paren = '(';
  r_paren = ')';
  plus = '+';
  minus = '-';
  mult = '*';
  div = '/';
  number = ['0'..'9']+;
  blank = [' ' 9 12 8 11 13 10];

Ignored Tokens
  blank;

Productions
  expr   = {term}   term
         | {plus}   expr plus  term
         | {minus}  expr minus term ;
  term   = {factor} factor
         | {mult}   term mult factor
         | {div}    term div  factor ;
  factor = {number} number
         | {expr}   l_paren expr r_paren ;

Notes

SabelCC

• No semantic actions - parser constructs concrete parse trees
• No precedence declarations to resolve ambiguities
• Lexer+parser specified together, but all tokens still have to be enumerated

Happy+Alex

• Arbitrary Haskell expressions as semantic actions - can construct abstract syntax trees (or whatever is desired)
• Lexer generated by a separate tool. All tokens have to be "imported"
• Supports precedence declarations

A note on declaring all tokens

Cactus example

.blank = [" \t\f\b\v\r\n"]
.number :: Int = ['0'..'9']+

expr :: Expr
  = ..       ::= term
  | Add..    ::= expr '+' term
  | Sub..    ::= expr '-' term ;

term
  = ..       ::= factor
  | Mul..    ::= term '*' factor
  | Div..    ::= term '/' factor ;

factor
  = Number.. ::= number
  | ..       ::= '(' expr ')'

Cactus example notes

From the 13 lines of code on the previous slice, Cactus generates

The user needs to supply a function for converting the number strings to Int.

Cactus example made more verbose

.blank = [" \t\f\b\v\r\n"]
.number :: Int = ['0'..'9']+

expr :: Expr
  = term              ::= term
  | Add(expr1,term1)  ::= expr '+' term
  | Sub(expr,term)    ::= expr '-' term ;

term
  = $1         ::= factor
  | Mul($1,$3) ::= term '*' factor
  | Div($1,$3) ::= term '/' factor ;

factor
  = Number($1) ::= number
  | $2         ::= '(' expr ')'

%data Expr
  = Add(Expr, Expr)
  | Sub(Expr, Expr)
  | Mul(Expr, Expr)
  | Div(Expr, Expr)
  | Number(Int)

Cactus type inference

Cactus can infer many thing automatically:

Cactus example made slightly simpler

.blank = [" \t\f\b\v\r\n"]
.number :: Int = ['0'..'9']+

%left.6 = '+', '-'
%left.7 = '*', '/'

expr
  = Add..    ::= expr '+' expr
  | Sub..    ::= expr '-' expr
  | Mul..    ::= expr '*' expr
  | Div..    ::= expr '/' expr
  | Number.. ::= number
  | ..       ::= '(' expr ')' ;

Cactus example made even simpler

.blank = [" \t\f\b\v\r\n"]
.number :: Int = ['0'..'9']+

%left.6 = '+', '-'
%left.7 = '*', '/'

expr
  = Op..    ::= expr op expr
  | Number.. ::= number
  | ..       ::= '(' expr ')' ;

%expand op ::= '+' | '-' | '*' | '/' ;

• The %expand directive can be used to avoid conflicts in LR parsers that can arise when refactoring the grammar.
• The abstract syntax can be omitted from a rule.

Cactus supports EBNF

• exp+ (repetition, one or more)
• exp* (repetition, zero or more)
• exp? (optional part)
• exp (',' exp)* (parentheses with several parts)

Cactus references

Cactus supports several ways to refer to parts of the syntax tree when specifying the abstract syntax.

(In this example, $3 would work instead of $3.2)

Built-in types

• Int, Float: +, -, *, /
• Char, String
• Bool: True, False, &&, ||, !
• [_] (lists): :, ++
• (_,_) (tuples)
• _? (Maybe, optional values)

Bigger examples

• Cactus in Cactus
• Haskell in Cactus

Future work

• Adding a module system (and perhaps a library of reusable grammars modules).
• Support for parameterized nonterminals (to regain some of the power of parsing combinators).
• Support for parameterized data types.
• Support for Unicode (and other character sets).
• Specification (automatic generation) of pretty printers,
• Generation of syntax diagrams.
• Generation of tree traversal functions.
• Various options, e.g., to store position information in the abstract syntax tree.
• Add ways to specify nested comments
• ...

The end

• Questions?