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 oper =
  17      PLUS
  18    | MINUS
  19    | TIMES
  20    | DIVIDEDBY
  21    | MODULO
  22    | NEGATIVE                   (* unary minus *)
  23    | LSH
  24    | RSH
  25    | LOGOR
  26    | LOGAND
  27    | BITAND
  28    | BITXOR
  29    | BITOR
  30    | BITNOT
  31    | BANG                       (* logical not *)
  32    | NEQ
  33    | EQ
  34    | LT
  35    | LE
  36    | GE
  37    | GT
  38
  39   datatype exp =
  40      Var of ident
  41    | ConstExp of Word32.word
  42    | OpExp of oper * exp list
  43    | Marked of (* Kane *) exp Mark.marked
  44    | FuncCall of ident * (exp list)
  45    | Member of exp * ident
  46    | DerefMember of exp * ident
  47    | Dereference of exp
  48    | ArrIndex of exp * exp
  49    | New of Type.vtype
  50    | NewArr of Type.vtype * exp
  51    | Null
  52    | Conditional of exp * exp * exp
  53   and stm =
  54      Assign of exp * exp
  55    | AsnOp of oper * exp * exp
  56    | Effect of exp (* Just side effect the expression *)
  57    | Return of exp
  58    | Nop
  59    | Break
  60    | Continue
  61    | If of exp * stm list * stm list option
  62    | For of stm option * exp * stm option * stm list
  63    | While of exp * stm list
  64    | MarkedStm of stm Mark.marked
  65
  66   datatype function =
  67      Extern of Type.vtype * (Type.variable list)
  68    | Function of Type.vtype * (Type.variable list) * (Type.variable list) * stm list
  69    | MarkedFunction of function Mark.marked
  70
  71   type program = Type.typedef Symbol.table * function Symbol.table
  72
  73   (* print as source, with redundant parentheses *)
  74   structure Print :
  75   sig
  76     val pp_exp : exp -> string
  77     val pp_stm : stm -> string
  78     val pp_program : program -> string
  79   end
  80 end
  81
  82 structure Ast :> AST =
  83 struct
  84   type ident = Symbol.symbol
  85
  86   datatype oper =
  87      PLUS
  88    | MINUS
  89    | TIMES
  90    | DIVIDEDBY
  91    | MODULO
  92    | NEGATIVE                   (* unary minus *)
  93    | LSH
  94    | RSH
  95    | LOGOR
  96    | LOGAND
  97    | BITAND
  98    | BITXOR
  99    | BITOR
 100    | BITNOT
 101    | BANG
 102    | NEQ
 103    | EQ
 104    | LT
 105    | LE
 106    | GE
 107    | GT
 108
 109   datatype exp =
 110      Var of ident
 111    | ConstExp of Word32.word
 112    | OpExp of oper * exp list
 113    | Marked of exp Mark.marked
 114    | FuncCall of ident * (exp list)
 115    | Member of exp * ident
 116    | DerefMember of exp * ident
 117    | Dereference of exp
 118    | ArrIndex of exp * exp
 119    | New of Type.vtype
 120    | NewArr of Type.vtype * exp
 121    | Null
 122    | Conditional of exp * exp * exp
 123   and stm =
 124      Assign of exp * exp
 125    | AsnOp of oper * exp * exp
 126    | Effect of exp (* Just side effect the expression *)
 127    | Return of exp
 128    | Nop
 129    | Break
 130    | Continue
 131    | If of exp * stm list * stm list option
 132    | For of stm option * exp * stm option * stm list
 133    | While of exp * stm list
 134    | MarkedStm of stm Mark.marked
 135
 136   datatype function =
 137      Extern of Type.vtype * (Type.variable list)
 138    | Function of Type.vtype * (Type.variable list) * (Type.variable list) * stm list
 139    | MarkedFunction of function Mark.marked
 140
 141   type program = Type.typedef Symbol.table * function Symbol.table
 142
 143   (* print programs and expressions in source form
 144    * using redundant parentheses to clarify precedence
 145    *)
 146   structure Print =
 147   struct
 148     fun pp_ident id = Symbol.name id
 149
 150     fun pp_oper PLUS = "+"
 151       | pp_oper MINUS = "-"
 152       | pp_oper TIMES = "*"
 153       | pp_oper DIVIDEDBY = "/"
 154       | pp_oper MODULO = "%"
 155       | pp_oper NEGATIVE = "-"
 156       | pp_oper LSH = "<<"
 157       | pp_oper RSH = ">>"
 158       | pp_oper LOGAND = "&&"
 159       | pp_oper LOGOR = "||"
 160       | pp_oper BITAND = "&"
 161       | pp_oper BITXOR = "^"
 162       | pp_oper BITOR = "|"
 163       | pp_oper BITNOT = "~"
 164       | pp_oper BANG = "!"
 165       | pp_oper NEQ = "!="
 166       | pp_oper EQ = "=="
 167       | pp_oper LT = "<"
 168       | pp_oper LE = "<="
 169       | pp_oper GT = ">"
 170       | pp_oper GE = ">="
 171
 172     fun pp_exp (Var(id)) = pp_ident id
 173       | pp_exp (ConstExp(c)) = Word32Signed.toString c
 174       | pp_exp (OpExp(oper, [e])) =
 175           pp_oper oper ^ "(" ^ pp_exp e ^ ")"
 176       | pp_exp (OpExp(oper, [e1,e2])) =
 177           "(" ^ pp_exp e1 ^ " " ^ pp_oper oper
 178           ^ " " ^ pp_exp e2 ^ ")"
 179       | pp_exp (OpExp(oper, _)) =
 180           pp_oper oper
 181       | pp_exp (FuncCall(id, l)) = pp_ident id ^ "(" ^ pp_expl l ^ ")"
 182       | pp_exp (Marked(marked_exp)) =
 183           pp_exp (Mark.data marked_exp)
 184       | pp_exp (Member(e, i)) = pp_exp e ^ "." ^ pp_ident i
 185       | pp_exp (DerefMember(e, i)) = pp_exp e ^ "->" ^ pp_ident i
 186       | pp_exp (Dereference(e)) = "*(" ^ pp_exp e ^ ")"
 187       | pp_exp (ArrIndex(e1, e2)) = pp_exp e1 ^ "[" ^pp_exp e2 ^ "]"
 188       | pp_exp (New t) = "new(" ^ Type.Print.pp_type t ^ ")"
 189       | pp_exp (NewArr (t, s)) = "new(" ^ Type.Print.pp_type t ^ "[" ^ pp_exp s ^ "])"
 190       | pp_exp Null = "NULL"
 191       | pp_exp (Conditional (q, e1, e2)) = "("^(pp_exp q)^"?"^(pp_exp e1)^":"^(pp_exp e2)^")"
 192
 193     and pp_expl nil = ""
 194       | pp_expl (e::a::l) = (pp_exp e) ^ ", " ^ (pp_expl (a::l))
 195       | pp_expl (e::l) = (pp_exp e) ^ (pp_expl l)
 196
 197     and pp_stm (Assign (e1,e2)) =
 198           pp_exp e1 ^ " = " ^ pp_exp e2 ^ ";\n"
 199       | pp_stm (AsnOp (oop, e1, e2)) =
 200           pp_exp e1 ^ " " ^ pp_oper oop ^ "= " ^ pp_exp e2 ^ ";\n"
 201       | pp_stm (Effect (e)) =
 202           pp_exp e ^ ";\n"
 203       | pp_stm (Return e) =
 204           "return " ^ pp_exp e ^ ";\n"
 205       | pp_stm Nop = ";\n"
 206       | pp_stm Break = "break;\n"
 207       | pp_stm Continue = "continue;\n"
 208       | pp_stm (If (e, s, NONE)) = "if ("^pp_exp e^")\n"^pp_block s
 209       | pp_stm (If (e, s, SOME s2)) = "if ("^pp_exp e^")\n"^pp_block s^"else\n"^pp_block s2
 210       | pp_stm (While (e, s)) = "while ("^pp_exp e^")\n"^pp_block s
 211       | 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 "") ^ ")\n" ^ pp_block s
 212       | pp_stm (MarkedStm m) = pp_stm (Mark.data m)
 213
 214     and pp_block (nil) = ";"
 215       | pp_block (a::nil) = pp_stm a
 216       | pp_block (l) = let
 217           val contents = map pp_stm l
 218         in
 219           "{\n" ^ String.concat contents ^ "}\n"
 220         end
 221
 222     and pp_stms nil = ""
 223       | pp_stms (s::ss) = pp_stm s ^ "\n" ^ pp_stms ss
 224
 225     and pp_params nil = ""
 226       | pp_params ((i, t)::a::l) = (pp_ident i) ^ " : " ^ (Type.Print.pp_type t) ^ ", " ^ (pp_params (a::l))
 227       | pp_params ((i, t)::l) = (pp_ident i) ^ " : " ^ (Type.Print.pp_type t) ^ (pp_params l)
 228
 229     and pp_vars nil = ""
 230       | pp_vars ((i, t)::l) = "var " ^ (pp_ident i) ^ " : " ^ (Type.Print.pp_type t) ^ ";\n" ^ (pp_vars l)
 231
 232     and pp_function (n, Extern(t, pl)) = "extern " ^ (Type.Print.pp_type t) ^ " " ^ (pp_ident n) ^ "(" ^ (pp_params pl) ^ ");\n"
 233       | pp_function (n, Function(t, pl, vl, stms)) = (Type.Print.pp_type t) ^ " " ^ (pp_ident n) ^ "(" ^ (pp_params pl) ^ ")\n{\n" ^ (pp_vars vl) ^ (String.concat (map pp_stm stms)) ^ "\n}\n"
 234       | pp_function (n, MarkedFunction d) = pp_function (n, Mark.data d)
 235
 236     and pp_program (types, funs) = String.concat ((map Type.Print.pp_typedef (Symbol.elemsi types)) @ (map pp_function (Symbol.elemsi funs)))
 237   end
 238 end