# Jason’s musings

I just need a little time

## Python implementation of “The Generation of Optimal Code for Arithmetic Expressions”

with 3 comments

We recently covered the paper “The Generation of Optimal Code for Arithmetic Expressions” in compiler design class, so I thought I’d implement the first two algorithms described in it in Python.

The one and two functions are the names that he calls his procedures.

```
#!/usr/bin/env python
# encoding: utf-8
"""
optimal_code_for_arithmetic_expressions.py

Created by Jason McCandless on 2006-11-27.
Copyright (c) 2006 Jason McCandless All rights reserved.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
"""

class Node:
def __init__(self,label,left = None,right = None):
if left and right: #not a leaf
self.op = label
self.label = left.label + label + right.label
else:
self.label = label
self.left = left
self.right = right

def print_labels(self):
for node in self.postorder():
print node.label, node.L

def postorder(self):
if self.left:
for x in self.left.postorder():
yield x
if self.right:
for x in self.right.postorder():
yield x
yield (self)

def postorder(t):
if t:
for x in postorder(t.left):
yield x
for x in postorder(t.right):
yield x
yield (t)

def label(node,leftLeaf=False):
if node.left:
l = label(node.left,True)
if node.right:
r = label(node.right,False)
if not (node.left or node.right): #leaf
if leftLeaf:
node.L = 1
else:
node.L = 0
else:
if l != r:
node.L = max(l,r)
else:
node.L = l + 1

if node.L > 1:
if (not (node.left.left or node.left.right)) and (node.op == "+" or node.op == "*"): #left descentent is a leaf, commutative
node.left,node.right = node.right,node.left
node.right.L = 0
node.L = r

return node.L

memory = 0
def getMemory():
global memory
memory = memory + 1
return "m" + str(memory)

def one(root,n):
two(root,n,1)

def two(node,n,m):
if node.L == 1:
if not (node.left or node.right): #leaf
print "r" + str(m) + " := " + node.label
else:
two(node.left,n,m)
print "r" + str(m) + " := " + "r" + str(m) + node.op + node.right.label
else: #node.L > 1
if node.left.L >= n and node.right.L >= n:
two(node.right,n,m)
mem = getMemory()
print mem + " := " + "r" + str(m)
two(node.left,n,m)
print "r" + str(m) + " := " + "r" + str(m) + node.op + mem
memory = memory -1
else:
if node.left.L >= node.right.L:
higher, lower = node.left, node.right
else:
higher, lower = node.right , node.left
two(higher,n,m)
if (lower.L) > 0:
two(lower,n,m+1)
print "r" + str(m) + " := " + "r" + str(m) + node.op + "r" + str(m+1)
else:
print "r" + str(m) + " := " + "r" + str(m) + node.op + node.right.label

def main():
root = Node("-",Node("/",Node("a"),Node("+",Node("b"),Node("c"))),Node("*",Node("d"),Node("+",Node("e"),Node("f"))))
label(root)
root.print_labels(); print
one(root,2);

if __name__ == '__main__':
main()

```
Advertisements

Written by jasonmc

December 3, 2006 at 1:24 am

Posted in Computing

### 3 Responses

Subscribe to comments with RSS.

1. Your formatting breaks your theme in FF1.5.0.8. Gareth Stack

December 3, 2006 at 12:13 pm

2. And I thought nobody would notice… jasonmc

December 3, 2006 at 3:18 pm

3. Yes, there are people out here reading this :p Sarah

December 4, 2006 at 6:53 pm