SE250:lab-8:npit006
Lab 8 - Parsing
Task 1 / Setup
It was incredibly painful to get prepared for this lab. I spent an hour and half finding a seat (there were plenty of randoms floating around in our designated area) and getting the provided source code working. From what I understand, it was designed for EMACS/Cygwin, but wouldn't even work out of the box for people using that environment. After battling all the errors Visual Studio threw at me when trying to compile it, I ended up with one error I simply couldn't eliminate. My final solution was to use Visual Studio to write my source code, but compile it with GCC.
Task 2
This was my code for Task 2. Fairly straightforward really.
ParseTree* ourTree = mkNode('-',mkNode('-',mkNode('a',0),mkNode('b',0),0),0);
<html>
<img src='http://img246.imageshack.us/img246/9116/83215320zo5.jpg'>
</html>
Task 3
This was my code for Task 3. I firstly broke down the string into 3 chunks, then after creating those chunks, added them all together. This question was slightly tedious, but not difficult.
// ?(>(+(a b) c) *(z +(y b)) ?(=(a 2) -(x y) -(y x)))
// ?(chunkX1 chunkX2 chunk X3)
ParseTree* chunkX1 = mkNode('>',mkNode('+',mkNode('a'),mkNode('b'),0),mkNode('c',0),0);
ParseTree* chunkX2 = mkNode('*',mkNode('z',0),mkNode('+',mkNode('y',0),mkNode('b',0),0));
ParseTree* chunkX3 = mkNode('?',mkNode('=',mkNode('a',0),mkNode('2',0),0),mkNode('-',mkNode('x',0),mkNode('y',0),0),mkNode('-',mkNode('y',0),mkNode('x',0),0),0);
ParseTree* ourTree2 = mkNode('?',chunkX1,chunkX2,chunkX3,0);
Task 4
Nothing unexpected here.
<html> <img src='http://img222.imageshack.us/img222/1062/24928304of5.jpg'> </html>
Task 5
In the C code 'cond? e1:e2', the colon represents different courses of action which can be taken based on the condition. In a parse tree, we deal with a C condition operator by inserting '?' into a node and giving it 3 immediate children. As shown above, Branch 0 deals with the condition itself. Branch 1 is the course of action we should take if the condition proves to be true. Branch 2 is the path we take if the condition is false.
We do not need to include a colon in our parse tree, because the idea that you can only take one branch is implied by the fact that Branch 1 is separate from Branch 2.
Task 6
This is my code for Task 6. It's a relatively straightforward recursive function which firstly decides whether the current node is an operator or an operand. If it is an operator, we perform a switch case on the node value to figure out what type of operation this is, and then perform the appropriate operation. If it is an operand, then we need to return an integer which is the result of converting a character to an integer.
I didn't get around to adding robust code checks (checking for division by zero etc).
int eval (ParseTree* treeToBeEvaluated){
if (treeToBeEvaluated->arity==2){
switch(treeToBeEvaluated->name){
case '+':
return eval(treeToBeEvaluated->arg[0]) + eval(treeToBeEvaluated->arg[1]);
break;
case '-':
return eval(treeToBeEvaluated->arg[0]) - eval(treeToBeEvaluated->arg[1]);
break;
case '*':
return eval(treeToBeEvaluated->arg[0]) * eval(treeToBeEvaluated->arg[1]);
break;
case '/':
return eval(treeToBeEvaluated->arg[0]) / eval(treeToBeEvaluated->arg[1]);
break;
default:
printf("\n Invalid operand \n");
}
}else if (treeToBeEvaluated->arity==0){
return (int)(treeToBeEvaluated->name-'0');
}else{
printf("\n Lulz the input parse tree is mucked up. Each node should have 0 or 2 children. This one has %d children",
treeToBeEvaluated->arity);
return 123451234512345;
}
}
Conclusion
I didn't get around to doing Tasks 7 and 8 which wasn't unexpected considering my earlier troubles. I'll most likely do them this weekend. It's a shame that the given code was incorrect, because the actual lab content was quite good.