parse/ast.sml

   1 (* L3 Compiler
   2  * Abstract Syntax Trees
   3  * Author: Alex Vaynberg
   4  * Modified: Frank Pfenning <fp@cs.cmu.edu>
   5  * Modified: Joshua Wise <jwise@andrew.cmu.edu>
   6  * Modified: Chris Lu <czl@andrew.cmu.edu>
   7  *
   8  * Uses pretty printing library
   9  * structure PP  -- see util/pp.sml
  10  *)
  11
  12 signature AST =
  13 sig
  14   type ident = Symbol.symbol
  15
  16   datatype vtype = Int
  17   type variable = ident * vtype
  18
  19   datatype oper =
  20      PLUS
  21    | MINUS
  22    | TIMES
  23    | DIVIDEDBY
  24    | MODULO
  25    | NEGATIVE                   (* unary minus *)
  26    | LSH
  27    | RSH
  28    | LOGOR
  29    | LOGAND
  30    | BITAND
  31    | BITXOR
  32    | BITOR
  33    | BITNOT
  34    | BANG                       (* logical not *)
  35    | NEQ
  36    | EQ
  37    | LT
  38    | LE
  39    | GE
  40    | GT
  41
  42   datatype exp =
  43      Var of ident
  44    | ConstExp of Word32.word
  45    | OpExp of oper * exp list
  46    | Marked of (* Kane *) exp Mark.marked
  47    | FuncCall of ident * (exp list)
  48   and stm =
  49      Assign of ident * exp
  50    | Return of exp
  51    | Nop
  52    | Break
  53    | Continue
  54    | If of exp * stm list * stm list option
  55    | For of stm option * exp * stm option * stm list
  56    | While of exp * stm list
  57    | MarkedStm of stm Mark.marked
  58
  59   datatype function =
  60      Extern of vtype * ident * (variable list)
  61    | Function of vtype * ident * (variable list) * (variable list) * stm list
  62
  63   type program = function list
  64
  65   (* print as source, with redundant parentheses *)
  66   structure Print :
  67   sig
  68     val pp_exp : exp -> string
  69     val pp_stm : stm -> string
  70     val pp_program : program -> string
  71   end
  72
  73 end
  74
  75 structure Ast :> AST =
  76 struct
  77   type ident = Symbol.symbol
  78
  79   datatype vtype = Int
  80   type variable = ident * vtype
  81
  82   datatype oper =
  83      PLUS
  84    | MINUS
  85    | TIMES
  86    | DIVIDEDBY
  87    | MODULO
  88    | NEGATIVE                   (* unary minus *)
  89    | LSH
  90    | RSH
  91    | LOGOR
  92    | LOGAND
  93    | BITAND
  94    | BITXOR
  95    | BITOR
  96    | BITNOT
  97    | BANG
  98    | NEQ
  99    | EQ
 100    | LT
 101    | LE
 102    | GE
 103    | GT
 104
 105   datatype exp =
 106      Var of ident
 107    | ConstExp of Word32.word
 108    | OpExp of oper * exp list
 109    | Marked of exp Mark.marked
 110    | FuncCall of ident * (exp list)
 111   and stm =
 112      Assign of ident * exp
 113    | Return of exp
 114    | Nop
 115    | Break
 116    | Continue
 117    | If of exp * stm list * stm list option
 118    | For of stm option * exp * stm option * stm list
 119    | While of exp * stm list
 120    | MarkedStm of stm Mark.marked
 121
 122   datatype function =
 123      Extern of vtype * ident * (variable list)
 124    | Function of vtype * ident * (variable list) * (variable list) * stm list
 125
 126   type program = function list
 127
 128   (* print programs and expressions in source form
 129    * using redundant parentheses to clarify precedence
 130    *)
 131   structure Print =
 132   struct
 133     fun pp_ident id = Symbol.name id
 134
 135     fun pp_oper PLUS = "+"
 136       | pp_oper MINUS = "-"
 137       | pp_oper TIMES = "*"
 138       | pp_oper DIVIDEDBY = "/"
 139       | pp_oper MODULO = "%"
 140       | pp_oper NEGATIVE = "-"
 141       | pp_oper LSH = "<<"
 142       | pp_oper RSH = ">>"
 143       | pp_oper LOGAND = "&&"
 144       | pp_oper LOGOR = "||"
 145       | pp_oper BITAND = "&"
 146       | pp_oper BITXOR = "^"
 147       | pp_oper BITOR = "|"
 148       | pp_oper BITNOT = "~"
 149       | pp_oper BANG = "!"
 150       | pp_oper NEQ = "!="
 151       | pp_oper EQ = "=="
 152       | pp_oper LT = "<"
 153       | pp_oper LE = "<="
 154       | pp_oper GT = ">"
 155       | pp_oper GE = ">="
 156
 157     fun pp_exp (Var(id)) = pp_ident id
 158       | pp_exp (ConstExp(c)) = Word32Signed.toString c
 159       | pp_exp (OpExp(oper, [e])) =
 160           pp_oper oper ^ "(" ^ pp_exp e ^ ")"
 161       | pp_exp (OpExp(oper, [e1,e2])) =
 162           "(" ^ pp_exp e1 ^ " " ^ pp_oper oper
 163           ^ " " ^ pp_exp e2 ^ ")"
 164       | pp_exp (OpExp(oper, _)) =
 165           pp_oper oper
 166       | pp_exp (FuncCall(id, l)) = pp_ident id ^ "(" ^ pp_expl l ^ ")"
 167       | pp_exp (Marked(marked_exp)) =
 168           pp_exp (Mark.data marked_exp)
 169
 170     and pp_expl nil = ""
 171       | pp_expl (e::a::l) = (pp_exp e) ^ ", " ^ (pp_expl (a::l))
 172       | pp_expl (e::l) = (pp_exp e) ^ (pp_expl l)
 173
 174     fun pp_stm (Assign (id,e)) =
 175         pp_ident id ^ " = " ^ pp_exp e ^ ";"
 176       | pp_stm (Return e) =
 177           "return " ^ pp_exp e ^ ";"
 178       | pp_stm Nop = ";"
 179       | pp_stm Break = "break;"
 180       | pp_stm Continue = "continue;"
 181       | pp_stm (If (e, s, NONE)) = "if ("^pp_exp e^")"^pp_block s
 182       | pp_stm (If (e, s, SOME s2)) = "if ("^pp_exp e^")"^pp_block s^" else "^pp_block s2
 183       | pp_stm (While (e, s)) = "while ("^pp_exp e^") "^pp_block s
 184       | pp_stm (For (so1, e, so2, s)) = "for ("^ (if (isSome so1) then pp_stm (valOf so1) else "") ^ pp_exp e ^ (if(isSome so2) then pp_stm (valOf so2) else "") ^ ")" ^ pp_block s
 185       | pp_stm (MarkedStm m) = pp_stm (Mark.data m)
 186
 187     and pp_block (nil) = ";"
 188       | pp_block (a::nil) = pp_stm a
 189       | pp_block (l) = let
 190           val contents = map pp_stm l
 191         in
 192           "{\n" ^ String.concat contents ^ "}\n"
 193         end
 194
 195     and pp_stms nil = ""
 196       | pp_stms (s::ss) = pp_stm s ^ "\n" ^ pp_stms ss
 197
 198     and pp_type Int = "int"
 199
 200     and pp_params nil = ""
 201       | pp_params ((i, t)::a::l) = (pp_ident i) ^ " : " ^ (pp_type t) ^ ", " ^ (pp_params (a::l))
 202       | pp_params ((i, t)::l) = (pp_ident i) ^ " : " ^ (pp_type t) ^ (pp_params l)
 203
 204     and pp_vars nil = ""
 205       | pp_vars ((i, t)::l) = "var " ^ (pp_ident i) ^ " : " ^ (pp_type t) ^ ";\n" ^ (pp_vars l)
 206
 207     and pp_function (Extern(t, n, pl)) = "extern " ^ (pp_type t) ^ " " ^ (pp_ident n) ^ "(" ^ (pp_params pl) ^ ");\n"
 208       | pp_function (Function(t, n, pl, vl, stms)) = (pp_type t) ^ " " ^ (pp_ident n) ^ "(" ^ (pp_params pl) ^ ")\n{\n" ^ (pp_vars vl) ^ (String.concat (map pp_stm stms)) ^ "\n}\n"
 209
 210     and pp_program (p) = String.concat (map pp_function p)
 211   end
 212 end