Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 425 lines (352 sloc) 13.753 kb
ae5ad92c »
2010-03-16 Rudimentary code generator.
1 #!/usr/bin/env python
2
d2e01fb8 »
2010-03-29 Global variables.
3 from semantic import first_definition
4
ae5ad92c »
2010-03-16 Rudimentary code generator.
5 # REGISTERS
6 ZERO = 0 # always zero
7 AC1 = 1 # Accumulator 1
8 AC2 = 2 # Accumulator 2
9 AC3 = 3 # Accumulator 3
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
10 ST = 4 # Temporary storage
ae5ad92c »
2010-03-16 Rudimentary code generator.
11 FP = 5 # points to the start of the frame
12 SP = 6 # points to the top of the stack
13 PC = 7 # points to the next instruction
14
d2e01fb8 »
2010-03-29 Global variables.
15 # variable locations, done the same as in type checking
16 # a global stack of dictionaries.
17 variables = [{}]
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
18 # global dictionary of proc locations
19 procs = {}
d2e01fb8 »
2010-03-29 Global variables.
20
7b1b19d8 »
2010-03-28 Move code around for organization.
21 # Code generation utilities -------------------------------------------------
ae5ad92c »
2010-03-16 Rudimentary code generator.
22
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
23 def is_comment(inst5):
24 "Returns whether this 'instruction' is just a comment."
25 return type(inst5) is tuple and inst5[0] == 'comment'
26
27 def code_length(code5):
28 """Returns the length of the code with comments removed."""
29 return len([1 for inst5 in code5 if not is_comment(inst5)])
30
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
31 def push_register(reg):
32 """Creates code for pushing a register onto the stack."""
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
33 return [('LDA', SP, -1, SP, 'Move (push) the stack pointer'),
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
34 ('ST', reg, 0, SP, 'Store reg %s on the stack' % reg)]
35
36 def pop_register(reg):
37 """Creates code for popping a register off the stack."""
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
38 return [('LD', reg, 0, SP, 'Get reg %d off the stack' % reg),
39 ('LDA', SP, 1, SP, 'Move (pop) the stack pointer')]
40
41 def push_var(varname, vartype):
42 """Allocates room for a variable on the stack."""
43 return [('LDA', SP, -1, SP, "Make room for %s on the stack" % varname)]
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
44
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
45 def comment(comment):
f62430d1 »
2010-03-28 Comments and docstrings.
46 """Makes a comment line."""
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
47 return [('comment', 0, 0, 0, comment)]
bb16c1ac »
2010-03-16 Move stuff around.
48
7b1b19d8 »
2010-03-28 Move code around for organization.
49 def passthru(ast):
50 """
51 Code generated by this item is the sequential concatenation of its
52 children. Useful for statements, etc.
53 """
54 from operator import add
55 return reduce(add, [generate_code(c) for c in ast.children], [])
56
57 # NODE_TYPE RULES ---------------------------------------------------------
58
bb16c1ac »
2010-03-16 Move stuff around.
59 def literal(ast):
f62430d1 »
2010-03-28 Comments and docstrings.
60 """Generates code for literal constants."""
bb16c1ac »
2010-03-16 Move stuff around.
61 if ast.ice9_type == 'int' or ast.ice9_type == 'bool':
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
62 return [('LDC', AC1, int(ast.value), 0, 'load constant: %s' % ast.value)]
f62430d1 »
2010-03-28 Comments and docstrings.
63 elif ast.ice9_type == 'str':
64 # TODO: implement strings
65 pass
bb16c1ac »
2010-03-16 Move stuff around.
66
8ff61912 »
2010-03-16 Yay, write/writes work!
67 def writes(ast):
f62430d1 »
2010-03-28 Comments and docstrings.
68 """Handles writing to output."""
8ff61912 »
2010-03-16 Yay, write/writes work!
69 value = ast.children[0]
a1fa8340 »
2010-03-28 Support adding two values.
70 childcode = generate_code(ast.children[0])
8ff61912 »
2010-03-16 Yay, write/writes work!
71 if value.ice9_type == 'int':
a1fa8340 »
2010-03-28 Support adding two values.
72 return childcode + [('OUT', AC1, 0, 0, 'writing int')]
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
73 elif value.ice9_type == 'bool':
a1fa8340 »
2010-03-28 Support adding two values.
74 return childcode + [('OUTB', AC1, 0, 0, 'writing bool')]
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
75 else:
76 raise ValueError("unimplmented")
8ff61912 »
2010-03-16 Yay, write/writes work!
77
78 def write(ast):
f62430d1 »
2010-03-28 Comments and docstrings.
79 """Handles write command (contains a newline)."""
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
80 return writes(ast) + [('OUTNL', 0, 0, 0, 'newline for write')]
81
d2e01fb8 »
2010-03-29 Global variables.
82 def ident(ast):
83 varname = ast.value
84 memloc, relreg = first_definition(variables, varname)
85 return [('LD', AC1, memloc, relreg, 'Load %s to register 1' % varname)]
86
87 def assignment(ast):
88 var, val = ast.children
89 varname = var.value
90 code5 = comment('ASSIGN to %s:' % varname) + generate_code(val)
91 memloc, relreg = first_definition(variables, varname)
92 code5 += [('ST', AC1, memloc, relreg, 'STORE variable %s' % varname)]
93 code5 += comment('END ASSIGN TO %s' % varname)
94 return code5
95
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
96 def program(ast):
7b1b19d8 »
2010-03-28 Move code around for organization.
97 """Generates code for a whole program."""
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
98 # make sure variable and proc locations are reset
99 global variables, procs
d2e01fb8 »
2010-03-29 Global variables.
100 variables = [{}]
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
101 procs = {}
d2e01fb8 »
2010-03-29 Global variables.
102
103 code5 = comment("PREAMBLE")
104 # variable declarations:
105 i = 1
106 for var, type9 in ast.vars:
107 code5 += [('alloc', 1, 0, 0, var)] # (alloc, size, 0, 0, varname)
108 code5 += comment('DECLARE "%s"' % var)
109 variables[0][var] = i, ZERO
110 i += 1
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
111
112 children = ast.children
113 # general program code.
114 while len(children) > 0 and children[0].node_type == 'proc':
115 procnode = children.pop(0)
116 procname = procnode.value
117 proclocation = code_length(code5) + 1
118 procs[procname] = proclocation
119 code5 += generate_code(procnode)
120
121
122 code5.insert(1, ('JEQ', ZERO, code_length(code5), PC,
123 'skip variable and proc declarations'))
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
124
125 # set the stack pointer
126 code5 += [('LD', SP, ZERO, ZERO, 'Set the stack pointer')]
127
128 code5 += comment("END PREAMBLE")
129 code5 += comment("START OF PROGRAM")
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
130
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
131 code5 += passthru(ast)
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
132
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
133 code5 += comment('END OF PROGRAM')
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
134
135 # we need to go back and add all our proc call jumps
136 realcode5 = []
137 for inst5 in code5:
138 inst, r, s, t, com = inst5
139 if inst == 'call':
140 procname = r
141 memloc = procs[procname]
142 realcode5.append(('LDC', PC, memloc, ZERO, com))
143 else:
144 realcode5.append(inst5)
145
146 code5 = realcode5
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
147 return code5
a1fa8340 »
2010-03-28 Support adding two values.
148
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
149 # Binary operators ---------------------------------------------------------
150 def binary_operator(opinst, ast):
151 """
152 Generic binary operator handler. opinst should one of ADD, SUB, DIV or
153 MUL. ast is the AST including the operator node.
154 """
a1fa8340 »
2010-03-28 Support adding two values.
155 left, right = ast.children
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
156
157 # Store the result of the left operand on the stack.
a1fa8340 »
2010-03-28 Support adding two values.
158 code5 = generate_code(left)
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
159 code5 += push_register(AC1)
160
161 # store value of right operand is in AC1
a1fa8340 »
2010-03-28 Support adding two values.
162 code5 += generate_code(right)
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
163
164 # Get the left value off the stack and put it in AC2
165 code5 += pop_register(AC2)
166
167 # And add the two and store in AC1
168 code5 += [(opinst, AC1, AC2, AC1, '%s left and right.' % opinst)]
a1fa8340 »
2010-03-28 Support adding two values.
169 return code5
170
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
171 def add(ast):
799c0497 »
2010-03-28 Add support for boolean OR.
172 """Handles integer addition and boolean OR."""
173 if ast.ice9_type == 'int':
174 # integer addition
175 return binary_operator('ADD', ast)
176 else:
177 assert ast.ice9_type == 'bool'
178 # boolean OR
179 left, right = ast.children
180 leftcode = generate_code(left)
181 rightcode = generate_code(right)
182
183 code5 = comment('boolean OR')
184 code5 += leftcode
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
185 code5 += [('JNE', AC1, code_length(rightcode), PC, 'short circuit boolean OR')]
799c0497 »
2010-03-28 Add support for boolean OR.
186 code5 += rightcode
187 code5 += comment('end boolean OR')
188 return code5
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
189
190 def mul(ast):
f6f76ee2 »
2010-03-28 Boolean AND.
191 """Handles integer multiplication and boolean AND."""
192 if ast.ice9_type == 'int':
193 # integer multiplication
194 return binary_operator('MUL', ast)
195 else:
196 # boolean AND
197 assert ast.ice9_type == 'bool'
198 left, right = ast.children
199 leftcode = generate_code(left)
200 rightcode = generate_code(right)
201
202 code5 = comment('boolean AND')
203 code5 += leftcode
204 code5 += [('JEQ', AC1, code_length(rightcode), PC, 'short circuit boolean AND')]
205 code5 += rightcode
206 code5 += comment('end boolean AND')
207 return code5
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
208
209 def div(ast):
210 """Handles division."""
211 return binary_operator('DIV', ast)
212
213 def sub(ast):
214 """Handles both binary and unary subtraction."""
215 if len(ast.children) == 1:
6ec94fa1 »
2010-03-28 Boolean negation.
216 if ast.ice9_type == 'int':
217 # unary subtract, we really should just multiply by -1
218 return generate_code(ast.children[0]) + comment('integer negation:') + [
219 ('LDC', AC2, -1, ZERO, 'Prepare to invert sign.'),
220 ('MUL', AC1, AC1, AC2, 'Invert sign.')
221 ]
222 else:
223 # boolean negation
224 assert ast.ice9_type == 'bool'
225 return generate_code(ast.children[0]) + comment('boolean negation:') + [
226 ('LDC', AC2, -1, ZERO, 'Prepare invert sign.'),
227 ('MUL', AC1, AC1, AC2, 'Invert sign.'),
228 ('LDA', AC1, 1, AC1, 'Convert back to boolean.')
229 ]
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
230 else:
6ec94fa1 »
2010-03-28 Boolean negation.
231 # integer subtraction
5581f250 »
2010-03-28 Handle add/sub/mul/div properly.
232 assert len(ast.children) == 2, "Subtract should only have two nodes"
6ec94fa1 »
2010-03-28 Boolean negation.
233 assert ast.ice9_type == 'int', "Must be integer subtraction"
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
234 return binary_operator('SUB', ast)
235
259fd16d »
2010-03-29 Comparison operators.
236 def comparison(comparenode):
237 jumpinstrs = {'=': 'JEQ', '!=': 'JNE',
238 '>': 'JGT', '>=': 'JGE',
239 '<': 'JLT', '<=': 'JLE'}
240
241 op = comparenode.value
242 inst = jumpinstrs[op]
243
244 code5 = comment("BEGIN COMPARISON %s" % op)
245 code5 += binary_operator('SUB', comparenode)
246 code5 += [
247 (inst, AC1, 1, PC, 'skip set to false'),
248 ('LDC', AC1, 0, 0, 'comparison is bad, set reg 1 to false'),
249 ('JEQ', ZERO, 1, PC, 'skip set to true'),
250 ('LDC', AC1, 1, 0, 'compairson is good, set reg 1 to true'),
251 ]
252 code5 += comment("END COMPARISON %s" % op)
253 return code5
254
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
255 # end binary operators ------------------------------------------------------
256
1ecb18eb »
2010-03-28 Seem to have basic do loops!
257 # condition code ----------------------------------------------------------
fc449d2f »
2010-03-28 Seemed to get if-then-else statements.
258 def cond(ast):
259 children = ast.children
260
261 code5 = []
262
263 while len(children) > 1:
264 cond = children.pop(0)
265 dothen = children.pop(0)
266
267 stmtcode = generate_code(dothen)
268 condcode = generate_code(cond)
269
270 code5 += comment('IF condition:')
271 code5 += condcode
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
272 code5 += [('JEQ', AC1, code_length(stmtcode) + 1, PC, 'if false, jump to next cond')]
fc449d2f »
2010-03-28 Seemed to get if-then-else statements.
273 code5 += comment('IF was true, THEN:')
274 code5 += stmtcode
275 code5 += ['jumpend']
276
277 if len(children) == 1:
278 stmtcode = generate_code(children.pop(0))
279 code5 += comment("ELSE:") + stmtcode
280
281 # total number of instructions with comments excluded
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
282 codecount = code_length(code5)
fc449d2f »
2010-03-28 Seemed to get if-then-else statements.
283
284 # need to go back and replace our jump labels with the real instruction offsets
285 realcode5 = []
286 i = 0
287 for inst5 in code5:
288 if inst5 == 'jumpend':
289 # label telling us to jump to the end of the statement
290 numleft = codecount - i - 1
291 realcode5.append(('JEQ', ZERO, numleft, PC, 'jump to end of if-then-else'))
292 else:
293 realcode5.append(inst5)
294
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
295 if not is_comment(code5):
fc449d2f »
2010-03-28 Seemed to get if-then-else statements.
296 i += 1
297
298 code5 = realcode5
299
300 return code5
301
1ecb18eb »
2010-03-28 Seem to have basic do loops!
302 def do_loop(ast):
303 cond, stmt = ast.children
304 condcode = generate_code(cond)
305 stmtcode = generate_code(stmt)
306
307 code5 = comment('BEGIN DO COND')
308 code5 += condcode
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
309 code5 += [('JEQ', AC1, code_length(stmtcode) + 1, PC, 'jump if do cond is false')]
1ecb18eb »
2010-03-28 Seem to have basic do loops!
310 code5 += comment('cond true, DO:')
311 code5 += stmtcode
64f58b14 »
2010-03-28 Use a code_length method that ignores comments for easier jump calcul…
312 code5 += [('JEQ', ZERO, -code_length(condcode + stmtcode) - 2, PC,
313 'End of DO, go back to beginning')]
1ecb18eb »
2010-03-28 Seem to have basic do loops!
314
315 return code5
316
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
317 # proc stuff ---------------------------------------------------------------
318
319 def proc(procnode):
320 procname = procnode.value
321 code5 = comment('BEGIN PROC %s' % procname)
322
323 code5 += passthru(procnode)
324 code5 += comment('POP return address:')
325 code5 += pop_register(AC2)
326 code5 += [('LDA', PC, 0, AC2, 'Moving return address into PC')]
327 code5 += comment('END PROC %s' % procname)
328 return code5
329
330 def proc_call(pcnode):
331 # push the return address
332 procname = pcnode.value
333 code5 = comment('BEGIN PROC CALL %s' % procname)
334 code5 += [('LDA', AC2, 3, PC, 'Store return address in AC2')]
335 code5 += push_register(AC2)
336 code5 += [('call', procname, 0, 0, 'CALL %s' % procname)]
337 code5 += comment('END PROC CALL %s' % procname)
338 return code5
339
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
340 # core algorithm ---------------------------------------------------------
341
bb16c1ac »
2010-03-16 Move stuff around.
342 # the repeated callback paradigm
343 callbacks = {
344 'literal': literal,
8ff61912 »
2010-03-16 Yay, write/writes work!
345 'write': write,
346 'writes': writes,
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
347 'program': program,
a1fa8340 »
2010-03-28 Support adding two values.
348 'statements': passthru,
349 '+': add,
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
350 '*': mul,
351 '/': div,
352 '-': sub,
ce948e8f »
2010-03-28 ? support.
353 '?': passthru,
fc449d2f »
2010-03-28 Seemed to get if-then-else statements.
354 'cond': cond,
1ecb18eb »
2010-03-28 Seem to have basic do loops!
355 'do_loop': do_loop,
d2e01fb8 »
2010-03-29 Global variables.
356 'ident': ident,
357 'assignment': assignment,
259fd16d »
2010-03-29 Comparison operators.
358 '=': comparison,
359 '!=': comparison,
360 '<': comparison,
361 '<=': comparison,
362 '>': comparison,
363 '>=': comparison,
f5fac0e5 »
2010-03-29 Yay, got procs with no return values or addresses.
364 'proc': proc,
365 'proc_call': proc_call,
bb16c1ac »
2010-03-16 Move stuff around.
366 }
367
ae5ad92c »
2010-03-16 Rudimentary code generator.
368 def generate_code(ast):
369 """
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
370 Generates a list of 5-tuples describing instructions for TM code of the form
371 (inst, r, s, t, comment)
ae5ad92c »
2010-03-16 Rudimentary code generator.
372 """
bb16c1ac »
2010-03-16 Move stuff around.
373 def noop(ast):
374 # returns empty code
d2e01fb8 »
2010-03-29 Global variables.
375 return comment('NOOP')
bb16c1ac »
2010-03-16 Move stuff around.
376
426bf87a »
2010-03-16 Add support for comments. Kinda makes things a little grosser.
377 code5 = []
a1fa8340 »
2010-03-28 Support adding two values.
378 if ast.node_type == 'operator':
379 cb = callbacks.get(ast.value, noop)
380 else:
381 cb = callbacks.get(ast.node_type, noop)
7b1b19d8 »
2010-03-28 Move code around for organization.
382
a1fa8340 »
2010-03-28 Support adding two values.
383 # code 5 because callbacks return 5-tuples.
384 setattr(ast, 'code5', cb(ast))
385 return ast.code5
386
7b1b19d8 »
2010-03-28 Move code around for organization.
387 # STRING OUTPUT ------------------------------------------------------------
388
389 def code5str(code5):
390 """Converts from code5 to something actually usuable by TM."""
391 from itertools import count
392 output = []
393 linecounter = count()
394 for inst5 in code5:
395 inst, r, s, t, com = inst5
396 if inst in ('LDC', 'LDA', 'LD', 'ST', 'JLT', 'JLE', 'JEQ',
397 'JNE', 'JGE', 'JGT'):
398 ln = linecounter.next() # line number
399 output.append("%5d: %-9s %d,%d(%d)\t\t%s" % (ln, inst, r, s, t, com))
400 elif inst in ('HALT', 'IN', 'OUT', 'INB', 'OUTB', 'OUTC',
401 'ADD', 'SUB', 'MUL', 'DIV', 'OUTNL'):
402 ln = linecounter.next()
403 output.append("%5d: %-9s %d,%d,%d\t\t%s" % (ln, inst, r, s, t, com))
d2e01fb8 »
2010-03-29 Global variables.
404 elif inst == 'alloc':
405 size = r
406 for i in xrange(0, size):
407 ln = linecounter.next()
7b1b19d8 »
2010-03-28 Move code around for organization.
408 elif inst == 'comment':
409 output.append("* %s" % com)
410 else:
411 raise ValueError("Can't print this instruction: %s" % inst)
412
413 return "\n".join(output)
414
a1fa8340 »
2010-03-28 Support adding two values.
415 def generate_code_str(ast):
85220675 »
2010-03-28 Poorly handle binary operators. Add stack pointer preamble.
416 """Shorthand for creating the TM string code for the ast."""
a1fa8340 »
2010-03-28 Support adding two values.
417 return code5str(generate_code(ast))
ae5ad92c »
2010-03-16 Rudimentary code generator.
418
7b1b19d8 »
2010-03-28 Move code around for organization.
419 # ---------------------------------------------------------------------------
420
ae5ad92c »
2010-03-16 Rudimentary code generator.
421 if __name__ == '__main__':
422 from ice9 import compile
423 source = file('test.9').read()
424 print compile(source)
Something went wrong with that request. Please try again.