cast.py
13.4 KB
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
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
# cast.py: extracted from cparse.py by Franck Pommereau (2018)
# ---------------------------------------------------------------
# cparse.py
#
# Atul Varma
# Python C Compiler - Parser
# $Id: cparse.py,v 1.2 2004/05/27 16:25:08 varmaa Exp $
# ---------------------------------------------------------------
# ---------------------------------------------------------------
# ABSTRACT SYNTAX TREE - NODES
# ---------------------------------------------------------------
class Node:
"Base class for all nodes on the abstract syntax tree."
def __init__ (self, lineno=0, colno=0, filename="<string>") :
self.lineno = lineno
self.colno = colno
self.filename = filename
def loc (self, col=False) :
if col :
return "%s:%s:%s" % (self.filename, self.lineno, self.colno)
else :
return "%s:%s" % (self.filename, self.lineno)
def getpos (self) :
return {"lineno" : self.lineno,
"colno" : self.colno,
"filename" : self.filename}
def is_null(self):
"""Returns whether the node represents a null node."""
return 0
def is_const(self):
"""Returns whether the node is a constant numeric number
(e.g., "5")."""
return 0
def has_address(self):
"""Returns whether the node has an address (i.e., is a valid
lvalue)."""
return hasattr(self, "has_addr")
def set_has_address(self):
"""Tells the node that has an address (is an lvalue).
Ultimately, the address of the node should be placed in the
output_addr attribute."""
self.has_addr = 1
self.output_addr = 0
def calculate(self):
"""Calculates the constant numeric value of the node and
its subnodes, if one exists. For instance, if a node
corresponds to the expression "5+3", then this method
would return 8."""
return None
def accept(self, visitor):
"""Accept method for visitor classes (see cvisitor.py)."""
return self._accept(self.__class__, visitor)
def _accept(self, klass, visitor):
"""Accept implementation. This is actually a recursive
function that dynamically figures out which visitor method to
call. This is done by appending the class' name to 'v', so if
the node class is called MyNode, then this method tries
calling visitor.vMyNode(). If that node doesn't exist, then
it recursively attempts to call the visitor method
corresponding to the class' superclass (e.g.,
visitor.vNode())."""
visitor_method = getattr(visitor, "v%s" % klass.__name__, None)
if visitor_method == None:
bases = klass.__bases__
last = None
for i in bases:
last = self._accept(i, visitor)
return last
else:
return visitor_method(self)
class NullNode(Node):
"""A null node is like a null terminator for AST's."""
def __init__(self, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.type = 'void'
def is_null(self):
return 1
class ArrayExpression(Node):
"""This is an expression with array notation, like "a[5+b]"."""
def __init__(self, expr, index, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = expr
self.index = index
class StringLiteral(Node):
"""A string literal, e.g. the string "Hello World" in
printf("Hello World")."""
def __init__(self, str, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self._str = str
self.type = PointerType(BaseType('char'))
def append_str(self, str):
self._str += str
def get_str(self):
return self._str
def get_sanitized_str(self):
"""Returns a 'sanitized' version of the string, converting
all carriage returns to '\n' symbols, etc."""
return self._str.replace('\n', '\\n')
class Id(Node):
"""An identifier, which can correspond to the name of
a function, variable, etc..."""
def __init__(self, name, lineno, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.name = name
class Const(Node):
"""A numeric constant (i.e., an integral literal), such as
the number 5."""
def __init__(self, value, type, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.value = value
self.type = type
def calculate(self):
return self.value
def is_const(self):
return 1
class Unaryop(Node):
"""Any generic unary operator. This is an abstract base class."""
def __init__(self, node, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = node
class Negative(Unaryop):
"""A negative unary operator, e.g. '-5'."""
def calculate(self):
val = self.expr.calculate()
if val is not None:
return -val
return None
class Pointer(Unaryop):
"""A pointer dereference, e.g. '*a'."""
pass
class AddrOf(Unaryop):
"""An address-of operator, e.g. '&a'."""
pass
class Binop(Node):
"""Any binary operator, such as that for arithmetic operations
(+/-/*), assignment operations (=/+=/-=), and so forth."""
# List of assignment operators.
ASSIGN_OPS = ['=', '+=', '-=']
def __init__(self, left, right, op, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.left = left
self.right = right
self.op = op
def calculate(self):
left = self.left.calculate()
right = self.right.calculate()
if left is not None and right is not None:
return int(eval("%d %s %d" % (left, self.op, right)))
else:
return None
class IfStatement(Node):
"""An if/then/else statement."""
def __init__(self, expr, then_stmt, else_stmt, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = expr
self.then_stmt = then_stmt
self.else_stmt = else_stmt
class BreakStatement(Node):
"""A break statement (used while in a loop structure to bust out
of it)."""
pass
class ContinueStatement(Node):
"""A continue statement (used while in a loop structure to bust
back to the beginning of it)."""
pass
class ReturnStatement(Node):
"""A return statement, used to exit a function and optionally
return a value."""
def __init__(self, expr, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = expr
class ForLoop(Node):
"""A for loop."""
def __init__(self, begin_stmt, expr, end_stmt, stmt, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = expr
self.stmt = stmt
self.begin_stmt = begin_stmt
self.end_stmt = end_stmt
class WhileLoop(Node):
"""A while loop."""
def __init__(self, expr, stmt, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.expr = expr
self.stmt = stmt
class NodeList(Node):
"""A list of nodes. This is an abstract base class."""
def __init__(self, node=None, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.nodes = []
if node is not None:
self.nodes.append(node)
def add(self, node):
self.nodes.append(node)
class ArgumentList(NodeList):
"""A list of arguments for a function expression. e.g., the list
'5,2,3' in 'a = my_func(5,2,3)'."""
pass
class ParamList(NodeList):
"""A list of parameters for a function prototype, e.g. the list
'int a, char b, char c' in 'int my_func(int a, char b, char c)'."""
def __init__(self, node=None, lineno=0, colno=0, filename="<string>"):
NodeList.__init__(self, node, lineno, colno, filename)
self.has_ellipsis = 0
class StatementList(NodeList):
"""Any list of statements. For instance, this can be the list of
statements in a function body."""
pass
class TranslationUnit(NodeList):
"""A list of nodes representing the program itself."""
pass
class DeclarationList(NodeList):
"""A list of variable declarations, such as the ones put
at the beginning of a compound statement (e.g., the beginning
of a function body)."""
pass
class FunctionExpression(Node):
"""An execution of a function, e.g. 'my_func(a,b,c)'."""
def __init__(self, function, arglist, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.function = function
self.arglist = arglist
class CompoundStatement(Node):
"""A compound statement, e.g. '{ int i; i += 1; }'."""
def __init__(self, declaration_list, statement_list, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.declaration_list = declaration_list
self.statement_list = statement_list
class FunctionDefn(Node):
"""A node representing a function definition (its declaration
and body)."""
def __init__(self, declaration, body, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
self.type = declaration.type
self.name = declaration.name
self.extern = declaration.extern
self.static = declaration.static
self.body = body
class Declaration(Node):
"""A node representing a declaration of a function or
variable."""
def __init__(self, name, type=None, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
if type is None:
type = NullNode()
self.extern = 0
self.static = 0
self.type = type
self.name = name
self.is_used = 0
def set_base_type(self, type):
if self.type.is_null():
self.type = type
else:
self.type.set_base_type(type)
def add_type(self, type):
type.set_base_type(self.type)
self.type = type
# ---------------------------------------------------------------
# ABSTRACT SYNTAX TREE - TYPE SYSTEM
# ---------------------------------------------------------------
class Type(Node):
"""A node representing the type of another node. For instance,
the Binop node representing '5 + a', where a is an int, will have
a Type node associated with it that represents the fact that
the result of the Binop is an int.
Types can also be nested, so that for instance you can have
a type like 'pointer(pointer(int))' which represents a
double-pointer to an int.
This is an abstract base class."""
def __init__(self, child=None, lineno=0, colno=0, filename="<string>"):
Node.__init__(self, lineno, colno, filename)
if child is None:
child = NullNode()
self.child = child
def set_base_type(self, type):
"""Set the base (innermost) type of a type. For instance,
calling this with a pointer(int) type on a pointer() type
will give you a pointer(pointer(int))."""
if self.child.is_null():
self.child = type
else:
self.child.set_base_type(type)
def get_string(self):
"""Return a string corresponding to the type, e.g.
'pointer(pointer(int))'."""
raise NotImplementedError()
def get_outer_string(self):
"""Return only the outermost type of a type. e.g.,
calling this on a pointer(pointer(int)) type will
return 'pointer'."""
raise NotImplementedError()
def is_function(self):
"""Returns whether or not this type represents a
function."""
return 0
class BaseType(Type):
"""A base type representing ints, chars, etc..."""
def __init__(self, type_str, child=None, lineno=0, colno=0, filename="<string>"):
Type.__init__(self, child, lineno, colno, filename)
self.type_str = type_str
def get_string(self):
return self.type_str
def get_outer_string(self):
return self.type_str
class FunctionType(Type):
"""A type representing a function (for function prototypes and
function calls)."""
def __init__(self, params=None, child=None, lineno=0, colno=0, filename="<string>"):
Type.__init__(self, child, lineno, colno, filename)
if (params == None):
params = NullNode()
self.params = params
def get_string(self):
param_str = ""
for param in self.params.nodes:
param_str += "," + param.type.get_string()
return "function(%s)->%s" % (param_str[1:], self.child.get_string())
def get_outer_string(self):
return 'function'
def is_function(self):
return 1
def get_return_type(self):
"""Returns the return type of the function. Internally,
this is stored as the nested type within the function."""
return self.child
def get_params(self):
"""Returns the list of parameters for the function."""
return self.params
class PointerType(Type):
"""A type representing a pointer to another (nested) type."""
def get_string(self):
return "pointer(%s)" % self.child.get_string()
def get_outer_string(self):
return 'pointer'