7 OCaml () 1. 2. () (compiler) (interpreter) 2 OCaml (syntax) (BNF,backus normal form ) 1 + 2; let x be 2-1 in x; ::= ; let be in ; ::= + - ::= * / ::= 7.1 ( (printable characters) (tokens) 1 (lexical analizer) let twice x=x*2; lettwicex=x*2; let (reserved word)twicex (identifier) =* (symbol)2 56: token type token = LET BE IN EOF ID of string NUM of int ONE of char 1 79
80 7. 57: gettoken(1) module P = Printf exception End_of_system (* *) let _ISTREAM = ref stdin let ch = ref ( ) let read () = (let c =!ch in ch := input_char!_istream; c) let skip () = (ch := input_char!_istream) let lookahead () =!ch (* *) let rec integer i = let c = lookahead () in if (c >= 0 && c <= 9 ) then integer (10*i+(Char.compare (read ()) 0 )) else i (* *) and identifier id = let c = lookahead () in if ((c >= a && c <= z ) (c >= A && c <= Z ) (c >= 0 && c <= 9 ) c == _ ) then identifier (id^(char.escaped (read ()))) else id (* *) and native_token () = let c = lookahead () in if ((c >= a && c <= z ) (c >= A && c <= Z ) c == _ ) then let id = identifier "" in match id with "let" -> LET "be" -> BE "in" -> IN _ -> ID (id) else if (c >= 0 && c <= 9 ) then NUM (integer 0) else ONE (read ()) (* *) and gettoken () = try let token = native_token () in match token with ONE -> gettoken () ONE \t -> gettoken () ONE \n -> gettoken () _ -> token with End_of_file -> EOF
7.1. 81 token LETBEEOFIN stringint char IDNUM ONE ID("fun")Num(1001)ONE( ; ) 58: type = 1 of 1 n of n i of i i ( i ) type i of i i i gettoken lookahead ch (look ahead) ch ch type (variant types) (C union ) (record type) () match with match with 1 -> 1 2 -> 2 59: match of n -> n input char ( ISTREAM 1 lookahead char read read() ch ch () gettoken native token gettoken native token gettoken 83: gettoken # gettoken ();; + - : ONE + # gettoken ();; 1 - : NUM 1 # gettoken ();; abd - : ID "abd"
82 7. gettoken 1 1 run() 60: run0 (* *) let print_token tk = match tk with (ID i) -> P.printf "ID(%s)" i (NUM n) -> P.printf "NUM(%d)" n (LET) -> P.printf "LET" (BE) -> P.printf "BE" (IN) -> P.printf "IN" (EOF) -> P.printf "EOF" (ONE c) -> P.printf "ONE(%c)" c (* *) let rec run () = flush stdout; let rlt = gettoken () in match rlt with (ONE $ ) -> raise End_of_system _ -> (print_token rlt; P.printf "\n"; run()) gettoken token () print token run gettoken while 2 while $ gettoken 2 SML while
7.2. 83 84: run() # run();; 1+2; NUM(1) ONE(+) NUM(2) ONE(;) let x be 10 in x; LET ID(x) BE NUM(10) IN ID(x) ONE(;) $ Exception: End of system. module module Lexer 61: module Lexer module Lexer = struct end 7.2 ( (parser tree) ) ::= ; Expr() let be in ; Def(,, ) ::= + App(Var +,Pair(, )) - App(Var -,Pair(, )) ::= * App( Var *,Pair(, )) / App( Var /,Pair(, )) ::= Num() Var() () (top down parser) (bottom up parser) 2
84 7. Knuth LL(k)(Left-to-right parse, Leftmost-derivation, k-symbol lookahead)lr(k)(left-to-right parse, Rightmost-derivation, k-symbol lookahead) P ET F P let be E in E ; P E ; E T E E + T E E T T F T T F T T / F F F E T E E + T E E T T F T T F T T / F 2, 3 (left recursive) LL(1) LL(1) E T E E + T E E T E E T T F T T F T T / F T T terminal symbolnon-terminal symbol 1.
7.2. 85 2. 1!tok match with tok!tok tok parse advance() x eat(x) eatid eatnum advance tok parse 85: prase # parse ();; let x be 20 in x; $ - : unit = () # parse ();; 1+2; $ - : unit = () $ E0F 1 $
86 7. 62: parse (* *) module L = Lexer (* tok *) let gettoken () = L.gettoken () let tok = ref (L.ONE ) let advance () = tok := gettoken() (* let advance () = (tok := gettoken(); L.print_token (!tok)) *) (* *) exception Syntax_error let error () = raise Syntax_error (* *) let eat t = if (!tok=t) then advance() else error() let eatid () = match!tok with (L.ID _) -> advance() _ -> error() let eatnum () = match!tok with (L.NUM _) -> advance() _ -> error() (* *) let rec parse () = (advance(); p()) and p () = match!tok with L.LET -> (eat(l.let); eatid(); eat(l.be); e(); eat(l.in); e(); eat(l.one ; )) _ -> (e(); eat(l.one ; )) and e () = (t(); e ()) and e () = match!tok with L.ONE + -> (eat(l.one + ); t(); e ()) L.ONE - -> (eat(l.one - ); t(); e ()) _ -> () and t() = (f(); t ()) and t () = match!tok with L.ONE * -> (eat(l.one * ); f(); t ()) L.ONE / -> (eat(l.one / ); f(); t ()) _ -> () and f() = match!tok with L.ID _ -> eatid() L.NUM _ -> eatnum() _ -> error() parse parse () ( ) definition( ) expr (
7.2. 87 ) 63: definition expr type definition = Def of string * expr * expr Expr of expr and expr = Num of int Var of string App of expr * expr Pair of expr * expr module 64: module Ast module Ast = struct end 86: ## let x be 10 in x ; $ Def(x,Num 10,Var x) ## 1+2; $ Expr(App(Var +,Pair(Num 1,Num 2))) ## let y be 10-3 in y/2; $ Def(y,App(Var -,Pair(Num 10,Num 3)),App(Var /,Pair(Var y,num 2))) let x be 10 in x; Def(x,Num 10,Var x) 1+2 Expr(App(Var +,Pair(Num 1,Num 2))) let y be 10-3 in y/2; Def(y,App(Var -,Pair(Num 10,Num 3)), App(Var /,Pair(Var y,num 2))) Def(x,Num 10,Var x) Def / \ x Num 10 Var x
88 7. 65: parse (* *) module L = Lexer module A = Ast (* tok *) let gettoken () = L.gettoken () let tok = ref (L.ONE ) let advance () = tok := gettoken() (* let advance () = (tok := gettoken(); L.print_token (!tok)) *) (* *) exception Syntax_error let error () = raise Syntax_error (* *) let eat t = if (!tok=t) then advance() else error() let eatid () = match!tok with (L.ID id) -> (advance(); id) _ -> error() let eatnum () = match!tok with (L.NUM num) -> (advance(); num) _ -> error() (* *) let rec parse () = (advance(); p()) and p () = match!tok with L.LET -> (eat(l.let); let _str = eatid() in (eat(l.be); let _e1 = e() in eat(l.in); let _e2 = e() in (eat(l.one ; ); A.Def (_str, _e1, _e2)))) _ -> let _e = e() in (eat(l.one ; ); A.Expr _e) and e () = let _t = t() in (e _t) and e _e = match!tok with L.ONE + -> (eat(l.one + ); let _pre = A.App(A.Var "+", A.Pair(_e, t())) in (e _pre)) L.ONE - -> (eat(l.one - ); let _pre = A.App(A.Var "-", A.Pair(_e, t())) in (e _pre)) _ -> _e and t () = let _f = f() in (t _f) and t _t = match!tok with L.ONE * -> (eat(l.one * ); let _pre = A.App(A.Var "*", A.Pair(_t, f())) in (t _pre)) L.ONE / -> (eat(l.one / ); let _pre = A.App(A.Var "/", A.Pair(_t, f())) in (t _pre)) _ -> _t and f() = match!tok with L.ID _ -> A.Var (eatid()) L.NUM _ -> A.Num (eatnum()) _ -> error()
7.2. 89 Expr(App(Var +,Pair(Num 1,Num 2))) Expr App / \ Var + Pair / \ Num 1 Num 2 Def(y,App(Var -,Pair(Num 10,Num 3)), App(Var /,Pair(Var y,num 2))) Def / \ y App App / \ / \ Var - Pair Var / Pair / \ / \ Num 10 Num 3 Var y Num 2 parse let E T E E + T E E T E E E + T E and e _e = match!tok with (L.ONE + ) -> (eat(l.one + ); let _pre = A.App(A.Var "+", A.Pair(_e,t())) in (e _pre)) parse
90 7. 87: parse # parse ();; let x be 20 in x; $ - : definition = Def ("x", Num 20, Var "x")val it = Def ("x",num 20,Var "x") # parse ();; 1+2; $ - : definition = Expr (App(Var "+",Pair (Num 1, Num 2))) module module Parser 66: module Parser module Parser = struct end
7.3. 91 7.3 (referential type) 67: # let x = 10;; val x : int = 10 # let f = fun x -> x;; val f : a -> a = <fun> 10 x (fun x -> x) f (procedural language) (imperative language) () +--------+ x 10 +--------+ x (reference) +---------+ x --> 10 +---------+ --> (C )x x OCaml 3 88: # let x = ref 10;; val x : int ref = contents = 10 # x;; - : int ref = contents = 10 # let y =!x;; val y : int = 10 # y;; - : int = 10 x ref 10 ref! (dereference ) y (assignment) 3 (garbage) (garbage collector) OCaml
92 7. 89: # x := 33;; - : unit = () # x;; - : int ref = contents = 33 #!x;; - : int = 33 # x := "true";; Characters 5-11: x := "true";; ŒŒ Error: This expression has type string but an expression was expected of type int := () ( x int) 4 ref (constructor) OCaml 90: ref # ref;; - : a -> a ref = <fun> 4 let