The Scanner and AST
scanner.mll
{ open Parser }
rule token =
parse [¡¯ ¡¯ ¡¯\t¡¯ ¡¯\r¡¯ ¡¯\n¡¯]
|¡¯+¡¯
| ¡¯-¡¯
|¡¯*¡¯
|¡¯/¡¯
| [¡¯0¡¯-¡¯9¡¯]+ as lit | eof
ast.mli
type operator = Add | Sub | Mul | Div
type expr =
Binop of expr * operator * expr
{ token lexbuf } {PLUS}
{ MINUS }
{ TIMES }
{ DIVIDE }
{ LITERAL(int_of_string lit) } { EOF }
| Lit of int
59
The Parser
parser.mly
%{ open Ast %}
%token PLUS MINUS TIMES DIVIDE EOF
%token
%left TIMES DIVIDE %start expr
%type
expr :
expr PLUS expr
| expr MINUS expr | expr TIMES expr | expr DIVIDE expr | LITERAL
{ Binop($1,
{ Binop($1,
{ Binop($1,
{ Binop($1,
{ Lit($1) }
Add, $3) } Sub, $3) } Mul, $3) } Div, $3) }
60
The Interpeter
calc.ml
open Ast
let rec eval = function Lit(x) -> x
| Binop(e1, op, e2) ->
let v1 = match op Add -> | Sub -> | Mul -> | Div ->
let_=
let lexbuf =
let expr = Parser . expr Scanner . token lexbuf in let result = eval expr in
print_endline (string_of_int result)
eval e1 and v2 = eval e2 in with
v1 + v2
v1 – v2
v1 * v2 v1 / v2
Lexing . from_channel stdin in
61
Compiling the Interpreter
$ ocamllex scanner.mll # create scanner.ml
8 states, 267 transitions, table size 1116 bytes
$ ocamlyacc parser.mly # create parser.ml and parser.mli $ ocamlc -c ast.mli # compile AST types
$ ocamlc -c parser.mli # compile parser types
$ ocamlc -c scanner.ml # compile the scanner
$ ocamlc -c parser.ml # compile the parser
$ ocamlc -c calc.ml # compile the interpreter
$ ocamlc -o calc parser.cmo scanner.cmo calc.cmo
$ ./calc
2*3+4*5
26
$
62
Compiling with ocamlbuild
$ ls
ast.mli calc.ml parser.mly scanner.mll
$ ocamlbuild calc.native # Build everything
Finished, 15 targets (0 cached) in 00:00:00.
$ ls
ast.mli _build calc.ml calc.native parser.mly scanner.mll $ ./calc.native
2*3+4*5
Ctrl-D
26
ocamlbuild -clean # Remove _build and all .native
63