Overview   -   Examples   -   Manual   -   Download   -   References   -   Contact
    

Examples


Here is an example of a parser for a small calculator which enforces the usual precedences between operators: 
%start main
%relation pi<pt<pp
%layout [' ' '\t']

%parser

main: expr "\n" { $1 }

expr:
  | ['0'-'9']+      { int_of_string $1 } pi
  | "-" expr(=pi)            { -$2 }     pi
  | "(" expr ")"             { $2 }      pi
  | expr(<=pp) "+" expr(<pp) { $1 + $3 } pp
  | expr(<=pp) "-" expr(<pp) { $1 - $3 } pp
  | expr(<=pt) "*" expr(<pt) { $1 * $3 } pt
  | expr(<=pt) "/" expr(<pt) { $1 / $3 } pt

Here is an example of a small language which accepts some limited extensions. A parser for this language is included in the distribution of dypgen.

This is the introduction of a specific syntax for binary trees in this language: 
define
  expr := "<" "|" expr(a) "|" ">" = Node(Leaf,a,Leaf)
  and expr := "<" expr(l) "|" expr(a) "|" ">" = Node(l,a,Leaf)
  and expr := "<" "|" expr(a) "|" expr(r) ">" = Node(Leaf,a,r)
  and expr := "<" expr(l) "|" expr(a) "|" expr(r) ">" = Node(l,a,r)
in

let rec comb t = match t with
  | <|a|>  -> <|a|>
  | <l|a|> -> < comb l |a|>
  | <l1|a| <l2|b|r2> > -> comb < <l1|a|l2> |b|r2>
in

comb <<<|1|>|2|<|3|>>|4|<<|5|>|6|<|7|>>>
The function comb returns a left comb tree, the interpreter outputs: 
= Node(Node(Node(Node(Node(Node(Node(Leaf,1,Leaf),2,Leaf),3,Leaf),4,Leaf),5,Leaf),6,Leaf),7,Leaf)

And this is the introduction of a specific syntax for lists: 
define
  list_contents := expr(x) = List(x,Nil)
  and list_contents := expr(x) ";" list_contents(y) = List(x,y)
  and expr := "[" "]" = Nil
  and expr := "[" list_contents(x) "]" = x
  and expr := expr(x) "::" expr(y) = List(x,y)
in

let rec append arg = match arg with
  | ([],list) -> list
  | ((head::tail),list) -> (head::(append (tail,list)))
in

define
  expr := expr(x)@expr(y) = append (x,y)
in

let rec reverse l = match l with
  | [] -> []
  | head::tail -> ((rev tail)@[head])
in

reverse [3;2;1;0]
The interpreter outputs: 
= List(0,List(1,List(2,List(3,Nil))))

The initial grammar of this language is inspired from a small subset of Caml. A documentation of the grammar follows. It is generated automatically from the definition file of the parser (.dyp file) by a script provided with dypgen. 
%relation p9<p8<p7<p6<p5<p4<p3<p2<p1<p0

%start main

let newline = ('\010' | '\013' | "\013\010")
let blank = [' ' '\009' '\012']
let lowercase = ['a'-'z' '\223'-'\246' '\248'-'\255' '_']
let uppercase = ['A'-'Z' '\192'-'\214' '\216'-'\222']
let identchar = ['A'-'Z' 'a'-'z' '_' '\192'-'\214' '\216'-'\246' '\248'-'\255' '\'' '0'-'9']
let backslash_escapes = ['\\' '"' '\'' 'n' 't' 'b' 'r']
let symbolchar = ['!' '$' '%' '&' '*' '+' '-' '.' '/' ':' '<' '=' '>' '?' '@' '^' '|' '~']

main lexer =

newline | blank + ->
lowercase identchar * -> LIDENT   
uppercase identchar * -> UIDENT   
['0'-'9']+ -> INT   
'"' -> STRING 

%parser

main: statements eof   

statements:
  |   
  | statements statement @  

statement:
  | expr ";" ";"   
  | "let" "rec" LIDENT LIDENT "=" expr ";" ";"
  | infix INT symbolchar+ ["," (symbolchar+)]* ";" ";" @  
  | "let" LIDENT (symbolchar+)<op> LIDENT "=" expr ";" ";" @
  | "define" define_cont ";" ";" @

infix:
  | "infix"    
  | "infixl"   
  | "infixr"   

expr:
  | expr(<=p4) "+" expr(<p4)    p4
  | expr(<=p4) "-" expr(<p4)    p4
  | expr(<=p5) "*" expr(<p5)    p5
  | expr(<=p5) "/" expr(<p5)    p5
  | "-" expr(=p9)  p9
  | "(" expr ")"   p9
  | "match" expr "with" "|"? match ["|" match]*
  | INT       p9
  | STRING    p9
  | expr "," expr(<p2)    p2
  | UIDENT expr    p3
  | UIDENT    p3
  | LIDENT    p9
  | "let" "rec" LIDENT LIDENT "=" expr "in" expr
  | LIDENT expr   
  | define_in expr   

match: expr "->" expr   

define_in:
  | "define" define_cont "in" @

define_cont:
  | LIDENT ":=" rhs "=" expr   
  | define_cont "and" LIDENT ":=" rhs "=" expr   

rhs:
  | LIDENT "(" LIDENT ")"   
  | UIDENT   
  | STRING   
  | LIDENT "(" LIDENT ")" rhs   
  | UIDENT rhs   
  | STRING rhs

Overview   -   Examples   -   Manual   -   Download   -   References   -   Contact