学习现代编译器实现(1)

现代编译器实现，就是虎书，有3个版本c, java, ML.我看的是ML的版本。此书的网站地址，有代码提供: Modern Compiler Implementation
不过ML版是以SML实现的，ocaml与它有点不同，不过相差不大。大多是关键字不同。
学习第一章：简单介绍。程序练习的代码如下:
(* 表示单行程序 *)

(*
 * 语法：
 *   Stm -> Stm; Stm  (复合语句 CompoundStm)
 *   Stm -> id := Exp (赋值语句 AssignStm)
 *   Stm -> print (ExpList) (打印语句 PrintStm)
 * 
 *   Exp -> id    (标识符表达式 IdExp)
 *   Exp -> num   (数字表达式 NumExp)
 *   Exp -> Exp Binop Exp (二元表达式 OpExp)
 *   Exp -> (Stm, Exp)    (顺序表达式 EseqExp)
 *
 *   ExpList -> Exp, ExpList (表达式列表 PairExpList)
 *   ExpList -> Exp          (最后一个表达式 LastExpList)
 *
 *   Binop -> +   (Plus)
 *   Binop -> -   (Minus)
 *   Binop -> x   (Times)
 *   Binop -> /   (Div)
 *)

type id = string

type binop = Plus | Minus | Times | Div

type stm = CompoundStm of stm * stm
           | AssignStm of id * exp
           | PrintStm of exp list
and exp = IdExp of id
          | NumExp of int
          | OpExp of exp * binop * exp
          | EseqExp of stm * exp

(* 这个练习介绍了 环境(变量的符号表);抽象语法(表示程序语句的数据结构);
 * 树形数据结构的递归(在编译器的多个部分都有用);和函数式编程风格
 *)

(* 我们不关心解析(parsing)语言，因此直接使用数据构造器编写程序 *)
(* a := 5 + 3; b := (print (a, a-1), 10*a); print (b) *)              
let prog =
  CompoundStm (
    AssignStm ("a", OpExp (NumExp 5, Plus, NumExp 3)),
    CompoundStm (
      AssignStm ("b",
                 EseqExp (PrintStm [IdExp "a"; OpExp (IdExp "a", Minus, NumExp 1)],
                          OpExp (NumExp 10, Times, IdExp "a"))),
        PrintStm [IdExp "b"]))

(*
 * 练习程序
 * 不使用引用变量，数组，或赋值表达式等引用类型(带有副作用，会修改内部状态)的值来
 * 实现以下程序
 *)

(*******************************************************************************
 * 1.编写一个函数(maxargs : stm -> int) 返回stm语句中任意一个子表达式中的print语句的
 * 最大参数个数。 例如maxargs(prog)为2
 *******************************************************************************)
let maxargs st =
  (* 获得所有print函数的参数个数 *)
  let rec args_aux rs = function 
    | CompoundStm (stm1, stm2) ->
      let new_rs = args_aux rs stm1 in
      args_aux new_rs stm2
    | AssignStm (_, e) ->
      let rec match_exp rs = function
        | IdExp _
        | NumExp _ -> rs
        | OpExp (e1, _, e2) -> let new_rs = match_exp rs e1 in match_exp new_rs e2
        | EseqExp (s, e) -> let new_rs = args_aux rs s in match_exp new_rs e 
      in
      match_exp rs e
    | PrintStm l -> (List.length l) :: rs
  in
  let res = args_aux [] st in
  List.fold_left max 0 res ;;

maxargs prog;; (* 2 *)

(* 测试在exp中出现print的情况 *)                                           
let test = AssignStm (
  "test",
  OpExp (
    EseqExp (PrintStm [NumExp 8], NumExp 9),
    Plus,
    EseqExp (PrintStm [NumExp 1; NumExp 2; NumExp 3], NumExp 10)));;

maxargs test;; (* 3 *)

(*******************************************************************************
 * 2.编写一个函数 interp : stm -> unit 解释这个语言的程序。
 * 使用函数式风格，维护一个(variable, integer)列表,并在AssignStm
 * 处更新这个列表
 *******************************************************************************)

let print_assoc_lst lst = List.iter (fun (n, v) -> Printf.printf "%s %d\n" n v) lst

(*
 * 放在外边为了使用#trace
 *)  
let rec inter_stm tbl = function
  | CompoundStm (st1, st2) ->
    let new_tbl = inter_stm tbl st1 in
    (* print_assoc_lst new_tbl; *)
    let new_tbl = inter_stm new_tbl st2 in
    new_tbl
  | AssignStm (id, e) ->
    let v = inter_exp tbl e in
    (id, v) :: tbl
  | PrintStm exps ->
    let print_exp e = let v = inter_exp tbl e in  print_int v; print_string " " in
    List.iter print_exp exps; print_newline ();
    tbl
and inter_exp tbl = function
  | IdExp id -> List.assoc id tbl
  | NumExp n -> n
  | OpExp (e1, op, e2) ->
    let v1 = inter_exp tbl e1 in
    let v2 = inter_exp tbl e2 in
    inter_op v1 v2 op
  | EseqExp (st, e) ->
    let new_tbl = inter_stm tbl st in
    inter_exp new_tbl e
and inter_op v1 v2 = function
  | Plus -> v1 + v2
  | Minus -> v1 - v2
  | Times -> v1 * v2
  | Div -> v1 / v2

let interp st =
  ignore (inter_stm [] st);
  () ;;

(* 测试 *)
interp prog;;

interp test;;
关于
