-
Notifications
You must be signed in to change notification settings - Fork 0
/
ast.py
298 lines (227 loc) · 8.68 KB
/
ast.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
import ir
from ir_gen import IRGen
from symbol_table import CTypeInt, NewSymbolTable, ScopeType
class EmptyNode:
"""Empty node."""
def make_ir(self, *args, **kwargs):
pass
class Program:
"""Main node of the whole program."""
def __init__(self, nodes):
self.nodes = nodes
def make_ir(self, symbol_table, ir_gen, ctx):
for n in self.nodes:
n.make_ir(symbol_table, ir_gen, ctx)
class Declaration:
def __init__(self, node, body=None):
self.node = node
# only for function declaration
self.body = body
def __repr__(self):
return f'{self.node}: {self.body}'
def make_ir(self, symbol_table: NewSymbolTable, ir_gen: IRGen, ctx):
spec = self.node.spec
decl = self.node.decl
init = self.node.init
if isinstance(decl, Identifier):
# Do not allow multiple declaration for variable even in different scopes
if symbol_table.lookup(decl.identifier):
raise Exception(f'multiple declaration of {decl.identifier}')
if ctx.is_global:
val = symbol_table.add_variable(decl.identifier, CTypeInt, ScopeType.GLOBAL)
if type(init) != Number:
raise Exception('only constant values for global variables')
out = init.make_ir(symbol_table, ir_gen, ctx)
if type(out.literal) != int:
raise Exception(f'non integer literal for global variable: {decl.identifier}')
ir_gen.register_global(val, init.number)
else:
val = symbol_table.add_variable(decl.identifier)
ir_gen.register_local(val)
if init:
out = init.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Set(val, out))
elif isinstance(decl, Function):
ctx.set_global(False)
ir_gen.new_func(decl.identifier.identifier)
symbol_table.add_variable(decl.identifier.identifier, CTypeInt, ScopeType.GLOBAL)
for parm in decl.parms:
var = symbol_table.add_variable(parm.decl.identifier)
ir_gen.register_argument(var)
self.body.make_ir(symbol_table, ir_gen, ctx)
ctx.set_global(True)
else:
raise Exception(f'bullshit declaration: {self}')
class DeclarationRoot:
def __init__(self, spec, decl, init=None):
"""
Params:
spec - specifier like int, char
decl - declaration of the symbol, it might be Identifier or Function
init - initial value
"""
self.spec = spec
self.decl = decl
self.init = init
def __repr__(self):
return f'{self.spec} {self.decl} = {self.init}'
class Function:
def __init__(self, identifier, parms):
self.identifier = identifier
self.parms = parms
def __repr__(self):
return f'{self.identifier}: {self.parms}'
class FuncCall:
"""Represents function call."""
def __init__(self, func_name, args):
self._func_name = func_name
self._args = args
def make_ir(self, symbol_table, ir_gen, ctx):
if ctx.is_global:
raise Exception(f'can\'t call function {self._func_name} in global context')
if not symbol_table.lookup(self._func_name):
raise Exception(f'call to unknown function')
self._check_args(ir_gen)
args = [arg.make_ir(symbol_table, ir_gen, ctx) for arg in self._args]
out = ir.IRValue(CTypeInt)
ir_gen.add(ir.FuncCall(out, self._func_name, args))
return out
def _check_args(self, ir_gen):
func_parms = ir_gen.func_args.get(self._func_name)
if len(func_parms) != len(self._args):
raise Exception(f'wrong amount of arguments to function call: {self._func_name}')
class Compound:
"""List of expressions."""
def __init__(self, items):
self.items = items
def make_ir(self, symbol_table, ir_gen, ctx):
symbol_table.open_scope()
for item in self.items:
item.make_ir(symbol_table, ir_gen, ctx)
symbol_table.close_scope()
def __repr__(self):
r = '{\n'
for i in self.items:
r += str(i) + '\n'
r += '}'
return r
class Return:
def __init__(self, ret_expr):
self.ret_expr = ret_expr
def __repr__(self):
return f'return {self.ret_expr}'
def make_ir(self, symbol_table, ir_gen, ctx):
out = self.ret_expr.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Return(out))
class IfStatement:
def __init__(self, cond, stmt, else_stmt):
self.cond = cond
self.stmt = stmt
self.else_stmt = else_stmt
def make_ir(self, symbol_table, ir_gen, ctx):
# do no generate any code if both of statements is empty
if not((self.stmt and self.stmt.items) or (self.else_stmt and self.else_stmt.items)):
return
if not isinstance(self.cond, Relational):
# everything is true inside if statement if result of expression != 0
out = self.cond.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Cmp(out, ir.IRValue(CTypeInt, 0)))
cond_cmd = 'eq'
else:
self.cond.make_ir(symbol_table, ir_gen, ctx)
cond_cmd = self.cond.n_cond
lable_end = ir.Lable('end')
if self.else_stmt:
lable_else = ir.Lable('else')
ir_gen.add(ir.Jmp(lable_else, cond_cmd))
self.stmt.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Jmp(lable_end))
ir_gen.add(lable_else)
self.else_stmt.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(lable_end)
else:
ir_gen.add(ir.Jmp(lable_end, cond_cmd))
self.stmt.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(lable_end)
class Equals:
"""Expression for assignment."""
def __init__(self, left, right, op):
self.left = left
self.right = right
self.op = op
def __repr__(self):
return f'{self.left} {self.op} {self.right}'
def make_ir(self, symbol_table, ir_gen, ctx):
if not isinstance(self.left, Identifier):
raise Exception('only identifier could be on left side of equal sign')
dst = self.left.make_ir(symbol_table, ir_gen, ctx)
res = self.right.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Set(dst, res))
class ArithBinOp:
ir_cmd = None
def __init__(self, left, right, op):
self.left = left
self.right = right
self.op = op
def make_ir(self, symbol_table, ir_gen, ctx):
"""Create ir code for binary operation."""
if type(self.left) == Number and type(self.right) == Number:
return ir.IRValue(CTypeInt, self.left.number + self.right.number)
out = ir.IRValue(CTypeInt)
l_val = self.left.make_ir(symbol_table, ir_gen, ctx)
r_val = self.right.make_ir(symbol_table, ir_gen, ctx)
ir_cmd = self.ir_cmd(out, l_val, r_val)
ir_gen.add(ir_cmd)
return out
def __repr__(self):
return f'{self.left} {self.op} {self.right}'
class Plus(ArithBinOp):
ir_cmd = ir.Add
class Minus(ArithBinOp):
ir_cmd = ir.Sub
class Mul(ArithBinOp):
ir_cmd = ir.Mul
class Relational(ArithBinOp):
# cond shows when relational expression is NOT true => when to jump to different location
cond = None
def __init__(self, left, right, op):
super().__init__(left, right, op)
def make_ir(self, symbol_table, ir_gen, ctx):
l_val = self.left.make_ir(symbol_table, ir_gen, ctx)
r_val = self.right.make_ir(symbol_table, ir_gen, ctx)
ir_gen.add(ir.Cmp(l_val, r_val))
class LessThan(Relational):
cond = 'lt'
n_cond = 'ge'
class LessEqual(Relational):
cond = 'le'
n_cond = 'gt'
class BiggerThan(Relational):
cond = 'gt'
n_cond = 'le'
class BiggerEqual(Relational):
cond = 'ge'
n_cond = 'lt'
class NotEqual(Relational):
cond = 'ne'
n_cond = 'eq'
class Equal(Relational):
cond = 'eq'
n_cond = 'ne'
class Identifier:
def __init__(self, identifier):
self.identifier = identifier
def __repr__(self):
return f'{self.identifier}'
def make_ir(self, symbol_table, ir_gen, ctx):
var = symbol_table.lookup(self.identifier)
if not var:
raise Exception(f'unregistered identifier: {self.identifier}')
return var
class Number:
def __init__(self, number):
self.number = number
def __repr__(self):
return f'Number: {self.number}'
def make_ir(self, *args):
return ir.IRValue(CTypeInt, self.number)