SE250:lab-8:llay008

Lab Eight - Parse Trees

Task One

Download parsetree.c. This was an easy start!

Task Two

I started by copying the code from the lab handout to see what the output would be if I used prefix_tree. It gave me

+(1 2)

From this I was able to generate -(-(a b)) using the code:

 p = mkNode('-', mkNode('-',mkNode('a',0),mkNode('b',0),0),0);

Task Three

I spent a lot of time on this task, trying to not only write the parse tree, but to write it in the clearest method possible instead of in one loooong line (which is hard to read and to debug).

Finally I succeeded...

 
    t1 = mkNode('>',mkNode('+',mkNode('a',0),mkNode('b',0),0),mkNode('c',0),0);
    t2 = mkNode('*',mkNode('z',0),mkNode('+',mkNode('y',0),mkNode('b',0),0),0);
	
    t3 = mkNode('=',mkNode('a',0),mkNode('2',0),0);
    t4 = mkNode('-',mkNode('x',0),mkNode('y',0),0);
    t5 = mkNode('-',mkNode('y',0),mkNode('x',0),0);
    t6 = mkNode('?',t3,t4,t5,0);

    tree = mkNode('?',t1,t2,t6,0);
    prefix_tree(tree);

This gave the desired output

?(>(+(a b) c) *(z +(y b)) ?(=(a 2) -(x y) -(y x)))

Task Four

I drew my expected tree and finally got print_to_tree to work (thanks Jason and Braedon)! And it was... exactly the same. I blame this on the amount of time spent on Task Three. The only thing I didn't have on my tree were the numbers but this is minor.

Task Five

From the lab handout:

The ? corresponds to the C conditional expression, which has the
form cond ? e1 : e2. Why does the parse tree not need to include
the colon (:)?

I haven't come across the form cond ? e1 : e2 in C so this is my interpretation - may be wrong!

The parse tree does not need to include the : because it is redundant. When the parse tree 'sees' the ? the : is implicitly implied - it separates what have become the different branches in the parse tree.