Joshua Wise's Git repositories - snipe.git/blob

1 (* L5 Compiler

2 * L5 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 structure T = Type

11 structure AU = AstUtils

12 structure AUP = AstUtils.Program

13

14 (* for simplicity, we only mark expressions, not statements *)

15

16 (* mark e with region (left, right) in source file *)

17 fun mark (e, (left, right)) = A.Marked (Mark.mark' (e, ParseState.ext (left, right)))

18 fun markstm (e, (left, right)) = A.MarkedStm (Mark.mark' (e, ParseState.ext (left, right)))

19 fun markfunction (e, (left, right)) = A.MarkedFunction (Mark.mark' (e, ParseState.ext (left, right)))

20 fun marktypedef (e, (left, right)) = T.MarkedTypedef (Mark.mark' (e, ParseState.ext (left, right)))

21

22 (* create lval from expression; here just an id *)

23 (* generates error if not an identifier *)

24 fun make_lval (A.Var(id)) ext = id

25 | make_lval (A.Marked(marked_exp)) ext =

26 make_lval (Mark.data marked_exp) (Mark.ext marked_exp)

27 | make_lval _ ext = ( ErrorMsg.error ext "not a variable" ;

28 Symbol.bogus )

29

30 %%

31 %header (functor L5LrValsFn (structure Token : TOKEN))

32

33 %term

34 EOF

35 | SEMI

36 | INTNUM of Word32.word

37 | IDENT of Symbol.symbol

38 | RETURN

41 | EQ | NEQ | LT | LE | GT | GE

42 | IF | ELSE | WHILE | FOR | CONTINUE | BREAK

43 | LBRACE | RBRACE

44 | LPAREN | RPAREN

45 | UNARY | ASNOP (* dummy *)

47 | PLUSPLUS | MINUSMINUS

48

49 %nonterm

50 program of A.program

51 | programx of A.program

52 | stms of A.stm list

53 | stm of A.stm

54 | simp of A.stm

55 | return of A.stm

56 | exp of A.exp

57 | explist of A.exp list

58 | control of A.stm

59 | asnop of A.oper

60 | block of A.stm list

61 | simpoption of A.stm option

62 | elseoption of A.stm list option

63 | idents of A.ident list

64 | vtype of T.vtype

65 | decls of A.program

66 | extdecl of A.ident * A.function

67 | paramlist of T.variable list

68 | param of T.variable

69 | typedecl of T.ident * T.typedef

70 | memberlist of (T.ident * T.vtype) list

71 | member of (T.ident * T.vtype)

72 | function of A.ident * A.function

73 | vardecl of T.variable list

74 | vardecls of T.variable list

75

76 %verbose (* print summary of errors *)

77 %pos int (* positions *)

78 %start program

79 %eop EOF

80 %noshift EOF

81

82 %name L5

83

84 %right QUESTION COLON

85 %left LOGOR

86 %left LOGAND

87 %left BITOR

88 %left BITXOR

89 %left BITAND

90 %left EQ NEQ

91 %left LT LE GT GE

92 %left LSH RSH

93 %left PLUS MINUS

94 %left STAR SLASH PERCENT

95 %right UNARY

96 %left LPAREN LBRACKET ARROW DOT

97

98 %%

99

100 program : programx (programx)

101

102 programx : decls (decls)

103 | programx function (AUP.append_function programx function)

104

105 vtype : INT (T.Int)

106 | IDENT (T.Typedef IDENT)

107 | vtype STAR (T.Pointer vtype)

108 | vtype LBRACKET RBRACKET

109 (T.Array vtype)

110

111 decls : (Symbol.empty, Symbol.empty)

112 | typedecl decls (AUP.append_typedef decls typedecl)

113 | extdecl decls (AUP.append_function decls extdecl)

114

115 extdecl : EXTERN vtype IDENT LPAREN RPAREN SEMI

116 (IDENT, markfunction (A.Extern (vtype, []), (EXTERNleft, SEMIright)))

117 | EXTERN vtype IDENT LPAREN paramlist RPAREN SEMI

118 (IDENT, markfunction (A.Extern (vtype, paramlist), (EXTERNleft, SEMIright)))

119

120 paramlist : param COMMA paramlist (param :: paramlist)

121 | param ([param])

122

123 param : IDENT COLON vtype (IDENT, vtype)

124

125 typedecl : STRUCT IDENT LBRACE RBRACE SEMI

126 (IDENT, marktypedef (T.Struct ([]), (STRUCTleft, SEMIright)))

127 | STRUCT IDENT LBRACE memberlist RBRACE SEMI

128 (IDENT, marktypedef (T.Struct (memberlist), (STRUCTleft, SEMIright)))

129

130 memberlist : member memberlist (member :: memberlist)

131 | member ([member])

132

133 member : IDENT COLON vtype SEMI (IDENT, vtype)

134

135 function : vtype IDENT LPAREN paramlist RPAREN LBRACE vardecls stms RBRACE

136 (IDENT, markfunction (A.Function (vtype, paramlist, vardecls, stms), (vtypeleft, RBRACEright)))

137 | vtype IDENT LPAREN RPAREN LBRACE vardecls stms RBRACE

138 (IDENT, markfunction (A.Function (vtype, [], vardecls, stms), (vtypeleft, RBRACEright)))

139

140 vardecls : ([])

141 | vardecl vardecls (vardecl @ vardecls)

142

143 vardecl : VAR idents COLON vtype SEMI

144 (map (fn x => (x, vtype)) idents)

145

146 idents : IDENT ([IDENT])

147 | IDENT COMMA idents (IDENT :: idents)

148

149 stms : ([])

150 | stm stms (stm :: stms)

151

152 stm : simp SEMI (simp)

153 | control (control)

154 | SEMI (A.Nop)

155

156 simp : exp ASSIGN exp %prec ASNOP

157 (A.Assign(exp1, exp2))

158 | exp asnop exp %prec ASNOP

159 (A.AsnOp(asnop, exp1, exp2))

160 | exp PLUSPLUS %prec ASNOP

161 (A.AsnOp(A.PLUS, exp, A.ConstExp(0w1)))

162 | exp MINUSMINUS %prec ASNOP

163 (A.AsnOp(A.MINUS, exp, A.ConstExp(0w1)))

164 | exp (markstm (A.Effect (exp), (expleft, expright)))

165

166 control : IF LPAREN exp RPAREN block elseoption

167 (markstm ((A.If (exp, block, elseoption)), (IFleft, elseoptionright)))

168 | WHILE LPAREN exp RPAREN block

169 (markstm ((A.While (exp, block)), (WHILEleft, blockright)))

170 | FOR LPAREN simpoption SEMI exp SEMI simpoption RPAREN block

171 (markstm ((A.For (simpoption1, exp, simpoption2, block)), (FORleft, blockright)))

172 | CONTINUE SEMI (markstm ((A.Continue), (CONTINUEleft, SEMIright)))

173 | BREAK SEMI (markstm ((A.Break), (BREAKleft, SEMIright)))

174 | RETURN exp SEMI (markstm ((A.Return exp), (RETURNleft, SEMIright)))

175

176 elseoption : ELSE block (SOME block)

177 | (NONE)

178

179 simpoption : (NONE)

180 | simp (SOME simp)

181

182 block : stm ([stm])

183 | LBRACE stms RBRACE (stms)

184

185 exp : LPAREN exp RPAREN (exp)

186 | INTNUM (mark (A.ConstExp(INTNUM),(INTNUMleft,INTNUMright)))

187 | IDENT (mark (A.Var(IDENT), (IDENTleft,IDENTright)))

188 | exp DOT IDENT (mark (A.Member(exp, IDENT), (expleft, IDENTright)))

189 | exp ARROW IDENT (mark (A.DerefMember(exp, IDENT), (expleft, IDENTright)))

190 | STAR exp %prec UNARY (mark (A.Dereference(exp), (STARleft, expright)))

191 | exp LBRACKET exp RBRACKET

192 (mark (A.ArrIndex(exp1, exp2), (exp1left, exp2right)))

193 | exp PLUS exp (mark (A.OpExp (A.PLUS, [exp1,exp2]), (exp1left,exp2right)))

194 | exp MINUS exp (mark (A.OpExp (A.MINUS, [exp1,exp2]), (exp1left,exp2right)))

195 | exp STAR exp (mark (A.OpExp (A.TIMES, [exp1,exp2]), (exp1left,exp2right)))

196 | exp SLASH exp (mark (A.OpExp (A.DIVIDEDBY, [exp1,exp2]), (exp1left,exp2right)))

197 | exp PERCENT exp (mark (A.OpExp (A.MODULO, [exp1,exp2]), (exp1left,exp2right)))

198 | exp LSH exp (mark (A.OpExp (A.LSH, [exp1,exp2]), (exp1left,exp2right)))

199 | exp RSH exp (mark (A.OpExp (A.RSH, [exp1,exp2]), (exp1left,exp2right)))

200 | exp LOGOR exp (mark (A.OpExp (A.LOGOR, [exp1,exp2]), (exp1left,exp2right)))

201 | exp LOGAND exp (mark (A.OpExp (A.LOGAND, [exp1,exp2]), (exp1left,exp2right)))

202 | exp BITOR exp (mark (A.OpExp (A.BITOR, [exp1,exp2]), (exp1left,exp2right)))

203 | exp BITAND exp (mark (A.OpExp (A.BITAND, [exp1,exp2]), (exp1left,exp2right)))

204 | exp BITXOR exp (mark (A.OpExp (A.BITXOR, [exp1,exp2]), (exp1left,exp2right)))

205 | exp EQ exp (mark (A.OpExp (A.EQ, [exp1,exp2]), (exp1left,exp2right)))

206 | exp NEQ exp (mark (A.OpExp (A.NEQ, [exp1,exp2]), (exp1left,exp2right)))

207 | exp LT exp (mark (A.OpExp (A.LT, [exp1,exp2]), (exp1left,exp2right)))

208 | exp LE exp (mark (A.OpExp (A.LE, [exp1,exp2]), (exp1left,exp2right)))

209 | exp GT exp (mark (A.OpExp (A.GT, [exp1,exp2]), (exp1left,exp2right)))

210 | exp GE exp (mark (A.OpExp (A.GE, [exp1,exp2]), (exp1left,exp2right)))

211 | NULL (mark (A.Null, (NULLleft, NULLright)))

212 | IDENT LPAREN RPAREN (mark (A.FuncCall(IDENT, []), (IDENTleft, RPARENright)))

213 | IDENT LPAREN explist RPAREN

214 (mark (A.FuncCall(IDENT, explist), (IDENTleft, RPARENright)))

215 | NEW LPAREN vtype RPAREN

216 (mark (A.New (vtype), (NEWleft, RPARENright)))

217 | NEW LPAREN vtype LBRACKET exp RBRACKET RPAREN

218 (mark (A.NewArr (vtype, exp), (NEWleft, RPARENright)))

219 | MINUS exp %prec UNARY (mark (A.OpExp (A.NEGATIVE, [exp]), (MINUSleft,expright)))

220 | BITNOT exp %prec UNARY (mark (A.OpExp (A.BITNOT, [exp]), (BITNOTleft,expright)))

221 | BANG exp %prec UNARY (mark (A.OpExp (A.BANG, [exp]), (BANGleft,expright)))

222 | exp QUESTION exp COLON exp

223 (mark (A.Conditional (exp1, exp2, exp3), (exp1left, exp3right)))

224

225 explist : exp ([exp])

226 | exp COMMA explist (exp :: explist)

227

228 asnop : PLUSEQ (A.PLUS)

229 | MINUSEQ (A.MINUS)

230 | STAREQ (A.TIMES)

231 | SLASHEQ (A.DIVIDEDBY)

232 | PERCENTEQ (A.MODULO)

233 | LSHEQ (A.LSH)

234 | RSHEQ (A.RSH)

235 | BITOREQ (A.BITOR)

236 | BITANDEQ (A.BITAND)

237 | BITXOREQ (A.BITXOR)