annotate lab4/parser.mly @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
rev   line source
0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
1 /* lab4/parser.mly */
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
2 /* Copyright (c) 2017 J. M. Spivey */
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
3
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
4 %{
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
5 open Optree
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
6 open Dict
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
7 open Tree
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
8 %}
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
9
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
10 %token <Dict.ident> IDENT
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
11 %token <Optree.op> MULOP ADDOP RELOP
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
12 %token <int> NUMBER
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
13 %token <char> CHAR
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
14 %token <Optree.symbol * int> STRING
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
15
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
16 /* punctuation */
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
17 %token SEMI DOT COLON LPAR RPAR COMMA SUB BUS
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
18 %token EQUAL MINUS ASSIGN VBAR ARROW
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
19 %token BADTOK IMPOSSIBLE
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
20
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
21 /* keywords */
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
22 %token ARRAY BEGIN CONST DO ELSE END IF OF
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
23 %token PROC RECORD RETURN THEN TO TYPE
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
24 %token VAR WHILE NOT POINTER NIL
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
25 %token REPEAT UNTIL FOR ELSIF CASE
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
26
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
27 %type <Tree.program> program
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
28 %start program
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
29
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
30 %{
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
31 let const n t = makeExpr (Constant (n, t))
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
32 %}
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
33
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
34 %%
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
35
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
36 program :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
37 block DOT { Prog ($1, ref []) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
38
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
39 block :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
40 decl_list BEGIN stmts END { makeBlock ($1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
41
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
42 decl_list :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
43 /* empty */ { [] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
44 | decl decl_list { $1 @ $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
45
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
46 decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
47 CONST const_decls { $2 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
48 | VAR var_decls { $2 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
49 | proc_decl { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
50 | TYPE type_decls { [TypeDecl $2] } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
51
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
52 const_decls :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
53 const_decl { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
54 | const_decl const_decls { $1 :: $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
55
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
56 const_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
57 IDENT EQUAL expr SEMI { ConstDecl ($1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
58
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
59 type_decls :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
60 type_decl { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
61 | type_decl type_decls { $1 :: $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
62
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
63 type_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
64 IDENT EQUAL typexpr SEMI { ($1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
65
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
66 var_decls :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
67 var_decl { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
68 | var_decl var_decls { $1 :: $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
69
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
70 var_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
71 ident_list COLON typexpr SEMI { VarDecl (VarDef, $1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
72
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
73 proc_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
74 proc_heading SEMI block SEMI { ProcDecl ($1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
75
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
76 proc_heading :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
77 PROC name params return_type { Heading ($2, $3, $4) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
78
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
79 params :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
80 LPAR RPAR { [] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
81 | LPAR formal_decls RPAR { $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
82
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
83 formal_decls :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
84 formal_decl { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
85 | formal_decl SEMI formal_decls { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
86
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
87 formal_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
88 ident_list COLON typexpr { VarDecl (CParamDef, $1, $3) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
89 | VAR ident_list COLON typexpr { VarDecl (VParamDef, $2, $4) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
90 | proc_heading { PParamDecl $1 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
91
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
92 return_type :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
93 /* empty */ { None }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
94 | COLON typexpr { Some $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
95
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
96 stmts :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
97 stmt_list { match $1 with [x] -> x
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
98 | xs -> makeStmt (Seq $1, 0) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
99
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
100 stmt_list :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
101 stmt { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
102 | stmt SEMI stmt_list { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
103
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
104 stmt :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
105 line stmt1 { makeStmt ($2, $1) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
106 | /* A trick to force the right line number */
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
107 IMPOSSIBLE { failwith "impossible" } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
108
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
109 line :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
110 /* empty */ { !Lexer.lineno } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
111
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
112 stmt1 :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
113 /* empty */ { Skip }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
114 | variable ASSIGN expr { Assign ($1, $3) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
115 | name actuals { ProcCall ($1, $2) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
116 | RETURN expr_opt { Return $2 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
117 | IF expr THEN stmts elses END { IfStmt ($2, $4, $5) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
118 | WHILE expr DO stmts END { WhileStmt ($2, $4) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
119 | REPEAT stmts UNTIL expr { RepeatStmt ($2, $4) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
120 | FOR name ASSIGN expr TO expr DO stmts END
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
121 { let v = makeExpr (Variable $2) in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
122 ForStmt (v, $4, $6, $8, ref None) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
123 | CASE expr OF arms else_part END { CaseStmt ($2, $4, $5) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
124
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
125 elses :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
126 /* empty */ { makeStmt (Skip, 0) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
127 | ELSE stmts { $2 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
128 | ELSIF line expr THEN stmts elses { makeStmt (IfStmt ($3, $5, $6), $2) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
129
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
130 arms :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
131 arm { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
132 | arm VBAR arms { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
133
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
134 arm :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
135 expr COLON stmts { ($1, $3) };
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
136
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
137 else_part :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
138 /* empty */ { makeStmt (Skip, 0) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
139 | ELSE stmts { $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
140
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
141 ident_list :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
142 IDENT { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
143 | IDENT COMMA ident_list { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
144
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
145 expr_opt :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
146 /* empty */ { None }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
147 | expr { Some $1 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
148
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
149 expr :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
150 simple { $1 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
151 | expr RELOP simple { makeExpr (Binop ($2, $1, $3)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
152 | expr EQUAL simple { makeExpr (Binop (Eq, $1, $3)) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
153
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
154 simple :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
155 term { $1 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
156 | simple ADDOP term { makeExpr (Binop ($2, $1, $3)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
157 | simple MINUS term { makeExpr (Binop (Minus, $1, $3)) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
158
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
159 term :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
160 factor { $1 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
161 | term MULOP factor { makeExpr (Binop ($2, $1, $3)) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
162
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
163 factor :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
164 variable { $1 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
165 | NUMBER { const $1 integer }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
166 | STRING { let (lab, len) = $1 in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
167 makeExpr (String (lab, len)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
168 | CHAR { const (int_of_char $1) character }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
169 | NIL { makeExpr Nil }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
170 | name actuals { makeExpr (FuncCall ($1, $2)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
171 | NOT factor { makeExpr (Monop (Not, $2)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
172 | MINUS factor { makeExpr (Monop (Uminus, $2)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
173 | LPAR expr RPAR { $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
174
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
175 actuals :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
176 LPAR RPAR { [] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
177 | LPAR expr_list RPAR { $2 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
178
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
179 expr_list :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
180 expr { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
181 | expr COMMA expr_list { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
182
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
183 variable :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
184 name { makeExpr (Variable $1) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
185 | variable SUB expr BUS { makeExpr (Sub ($1, $3)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
186 | variable DOT name { makeExpr (Select ($1, $3)) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
187 | variable ARROW { makeExpr (Deref $1) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
188
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
189 typexpr :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
190 name { TypeName $1 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
191 | ARRAY expr OF typexpr { Array ($2, $4) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
192 | RECORD fields END { Record $2 }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
193 | POINTER TO typexpr { Pointer $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
194
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
195 fields :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
196 field_decl opt_semi { [$1] }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
197 | field_decl SEMI fields { $1 :: $3 } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
198
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
199 field_decl :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
200 ident_list COLON typexpr { VarDecl (FieldDef, $1, $3) } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
201
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
202 opt_semi :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
203 SEMI { () }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
204 | /* empty */ { () } ;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
205
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
206 name :
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
207 IDENT { makeName ($1, !Lexer.lineno) } ;