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