parse/l3.grm

   1 (* L3 Compiler
   2  * L3 grammar
   3  * Author: Kaustuv Chaudhuri <kaustuv+@cs.cmu.edu>
   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
   9 structure A = Ast
  10
  11 (* for simplicity, we only mark expressions, not statements *)
  12
  13 (* mark e with region (left, right) in source file *)
  14 fun mark (e, (left, right)) = A.Marked (Mark.mark' (e, ParseState.ext (left, right)))
  15 fun markstm (e, (left, right)) = A.MarkedStm (Mark.mark' (e, ParseState.ext (left, right)))
  16
  17 (* create lval from expression; here just an id *)
  18 (* generates error if not an identifier *)
  19 fun make_lval (A.Var(id)) ext = id
  20   | make_lval (A.Marked(marked_exp)) ext =
  21       make_lval (Mark.data marked_exp) (Mark.ext marked_exp)
  22   | make_lval _ ext = ( ErrorMsg.error ext "not a variable" ;
  23                         Symbol.bogus )
  24
  25 (* expand_asnop (exp1, "op=", exp2) region = "exp1 = exp1 op exps"
  26  * or = "exp1 = exp2" if asnop is "="
  27  * generates error if exp1 is an lval (identifier)
  28  * syntactically expands a compound assignment operator
  29  *)
  30 fun expand_asnop (exp1, NONE, exp2) (left, right) =
  31       A.Assign(make_lval exp1 NONE, exp2)
  32   | expand_asnop (exp1, SOME(oper), exp2) (left, right) =
  33       A.Assign(make_lval exp1 NONE,
  34                mark(A.OpExp(oper, [exp1, exp2]), (left, right)))
  35
  36 %%
  37 %header (functor L3LrValsFn (structure Token : TOKEN))
  38
  39 %term
  40    EOF
  41  | SEMI
  42  | INTNUM of Word32.word
  43  | IDENT of Symbol.symbol
  44  | RETURN
  45  | PLUS | MINUS | STAR | SLASH | PERCENT | LSH | RSH | LOGOR | LOGAND | BITAND | BITXOR | BITOR | BITNOT | BANG
  46  | ASSIGN | PLUSEQ | MINUSEQ | STAREQ | SLASHEQ | PERCENTEQ | LSHEQ | RSHEQ | BITANDEQ | BITXOREQ | BITOREQ
  47  | EQ | NEQ | LT | LE | GT | GE
  48  | IF | ELSE | WHILE | FOR | CONTINUE | BREAK
  49  | LBRACE | RBRACE
  50  | LPAREN | RPAREN
  51  | UNARY | ASNOP (* dummy *)
  52  | EXTERN | VAR | INT | COLON | COMMA
  53
  54 %nonterm
  55    program of A.program
  56  | stms of A.stm list
  57  | stm of A.stm
  58  | simp of A.stm
  59  | return of A.stm
  60  | exp of A.exp
  61  | explist of A.exp list
  62  | control of A.stm
  63  | asnop of A.oper option
  64  | block of A.stm list
  65  | simpoption of A.stm option
  66  | elseoption of A.stm list option
  67  | idents of A.ident list
  68  | vtype of A.vtype
  69  | extdecls of A.function list
  70  | extdecl of A.function
  71  | paramlist of A.variable list
  72  | param of A.variable
  73  | functions of A.function list
  74  | function of A.function
  75  | vardecl of A.variable list
  76  | vardecls of A.variable list
  77
  78 %verbose                                (* print summary of errors *)
  79 %pos int                                (* positions *)
  80 %start program
  81 %eop EOF
  82 %noshift EOF
  83
  84 %name L3
  85
  86 %left LOGOR
  87 %left LOGAND
  88 %left BITOR
  89 %left BITXOR
  90 %left BITAND
  91 %left EQ NEQ
  92 %left LT LE GT GE
  93 %left LSH RSH
  94 %left PLUS MINUS
  95 %left STAR SLASH PERCENT
  96 %right UNARY
  97 %left LPAREN
  98
  99 %%
 100
 101 program    : extdecls functions     (extdecls @ functions)
 102
 103 vtype      : INT                    (A.Int)
 104
 105 extdecls   :                        ([])
 106            | extdecl extdecls       (extdecl :: extdecls)
 107
 108 extdecl    : EXTERN vtype IDENT LPAREN RPAREN SEMI
 109                                     (A.Extern (vtype, IDENT, []))
 110            | EXTERN vtype IDENT LPAREN param RPAREN SEMI
 111                                     (A.Extern (vtype, IDENT, [param]))
 112            | EXTERN vtype IDENT LPAREN paramlist RPAREN SEMI
 113                                     (A.Extern (vtype, IDENT, paramlist))
 114
 115 paramlist  : param COMMA paramlist  (param :: paramlist)
 116            | param                  ([param])
 117
 118 param      : IDENT COLON vtype      (IDENT, vtype)
 119
 120 functions  :                        ([])
 121            | function functions     (function :: functions)
 122
 123 function   : vtype IDENT LPAREN RPAREN LBRACE vardecls stms RBRACE
 124                                     (A.Function (vtype, IDENT, [], vardecls, stms))
 125            | vtype IDENT LPAREN paramlist RPAREN LBRACE vardecls stms RBRACE
 126                                     (A.Function (vtype, IDENT, paramlist, vardecls, stms))
 127
 128 vardecls   :                        ([])
 129            | vardecl vardecls       (vardecl @ vardecls)
 130
 131 vardecl    : VAR idents COLON vtype SEMI
 132                                     (map (fn x => (x, vtype)) idents)
 133
 134 idents     : IDENT                  ([IDENT])
 135            | IDENT COMMA idents     (IDENT :: idents)
 136
 137 stms       :                        ([])
 138            | stm stms               (stm :: stms)
 139
 140 stm        : simp SEMI              (simp)
 141            | control                (control)
 142            | SEMI                   (A.Nop)
 143
 144 simp       : exp asnop exp %prec ASNOP
 145                                     (expand_asnop (exp1, asnop, exp2) (exp1left, exp2right))
 146
 147 control    : IF LPAREN exp RPAREN block elseoption
 148                                     (markstm ((A.If (exp, block, elseoption)), (IFleft, elseoptionright)))
 149            | WHILE LPAREN exp RPAREN block
 150                                     (markstm ((A.While (exp, block)), (WHILEleft, blockright)))
 151            | FOR LPAREN simpoption SEMI exp SEMI simpoption RPAREN block
 152                                     (markstm ((A.For (simpoption1, exp, simpoption2, block)), (FORleft, blockright)))
 153            | CONTINUE SEMI          (markstm ((A.Continue), (CONTINUEleft, SEMIright)))
 154            | BREAK SEMI             (markstm ((A.Break), (BREAKleft, SEMIright)))
 155            | RETURN exp SEMI        (markstm ((A.Return exp), (RETURNleft, SEMIright)))
 156
 157 elseoption : ELSE block             (SOME block)
 158            |                        (NONE)
 159
 160 simpoption :                        (NONE)
 161            | simp                   (SOME simp)
 162
 163 block      : stm                    ([stm])
 164            | LBRACE stms RBRACE     (stms)
 165
 166 exp        : LPAREN exp RPAREN      (exp)
 167            | INTNUM                 (mark (A.ConstExp(INTNUM),(INTNUMleft,INTNUMright)))
 168            | IDENT                  (mark (A.Var(IDENT), (IDENTleft,IDENTright)))
 169            | exp PLUS exp           (mark (A.OpExp (A.PLUS, [exp1,exp2]), (exp1left,exp2right)))
 170            | exp MINUS exp          (mark (A.OpExp (A.MINUS, [exp1,exp2]), (exp1left,exp2right)))
 171            | exp STAR exp           (mark (A.OpExp (A.TIMES, [exp1,exp2]), (exp1left,exp2right)))
 172            | exp SLASH exp          (mark (A.OpExp (A.DIVIDEDBY, [exp1,exp2]), (exp1left,exp2right)))
 173            | exp PERCENT exp        (mark (A.OpExp (A.MODULO, [exp1,exp2]), (exp1left,exp2right)))
 174            | exp LSH exp            (mark (A.OpExp (A.LSH, [exp1,exp2]), (exp1left,exp2right)))
 175            | exp RSH exp            (mark (A.OpExp (A.RSH, [exp1,exp2]), (exp1left,exp2right)))
 176            | exp LOGOR exp          (mark (A.OpExp (A.LOGOR, [exp1,exp2]), (exp1left,exp2right)))
 177            | exp LOGAND exp         (mark (A.OpExp (A.LOGAND, [exp1,exp2]), (exp1left,exp2right)))
 178            | exp BITOR exp          (mark (A.OpExp (A.BITOR, [exp1,exp2]), (exp1left,exp2right)))
 179            | exp BITAND exp         (mark (A.OpExp (A.BITAND, [exp1,exp2]), (exp1left,exp2right)))
 180            | exp BITXOR exp         (mark (A.OpExp (A.BITXOR, [exp1,exp2]), (exp1left,exp2right)))
 181            | exp EQ exp             (mark (A.OpExp (A.EQ, [exp1,exp2]), (exp1left,exp2right)))
 182            | exp NEQ exp            (mark (A.OpExp (A.NEQ, [exp1,exp2]), (exp1left,exp2right)))
 183            | exp LT exp             (mark (A.OpExp (A.LT, [exp1,exp2]), (exp1left,exp2right)))
 184            | exp LE exp             (mark (A.OpExp (A.LE, [exp1,exp2]), (exp1left,exp2right)))
 185            | exp GT exp             (mark (A.OpExp (A.GT, [exp1,exp2]), (exp1left,exp2right)))
 186            | exp GE exp             (mark (A.OpExp (A.GE, [exp1,exp2]), (exp1left,exp2right)))
 187            | IDENT LPAREN RPAREN    (mark (A.FuncCall(IDENT, []), (IDENTleft, RPARENright)))
 188            | IDENT LPAREN exp RPAREN
 189                                     (mark (A.FuncCall(IDENT, [exp]), (IDENTleft, RPARENright)))
 190            | IDENT LPAREN explist RPAREN
 191                                     (mark (A.FuncCall(IDENT, explist), (IDENTleft, RPARENright)))
 192            | MINUS exp %prec UNARY  (mark (A.OpExp (A.NEGATIVE, [exp]), (MINUSleft,expright)))
 193            | BITNOT exp %prec UNARY (mark (A.OpExp (A.BITNOT, [exp]), (BITNOTleft,expright)))
 194            | BANG exp %prec UNARY   (mark (A.OpExp (A.BANG, [exp]), (BANGleft,expright)))
 195
 196 explist    : exp                    ([exp])
 197            | exp COMMA explist      (exp :: explist)
 198
 199 asnop      : ASSIGN                (NONE)
 200            | PLUSEQ                (SOME(A.PLUS))
 201            | MINUSEQ               (SOME(A.MINUS))
 202            | STAREQ                (SOME(A.TIMES))
 203            | SLASHEQ               (SOME(A.DIVIDEDBY))
 204            | PERCENTEQ             (SOME(A.MODULO))
 205            | LSHEQ                 (SOME(A.LSH))
 206            | RSHEQ                 (SOME(A.RSH))
 207            | BITOREQ               (SOME(A.BITOR))
 208            | BITANDEQ              (SOME(A.BITAND))
 209            | BITXOREQ              (SOME(A.BITXOR))