SE250:lab-8:bvic005
Lab 8
This lab was about mucking around with parse trees. I am currently sick(yay!) so was unable to make it to the lab session. Therefor i did it all at home, on Linux.
Initial Problems
There where (apparently) at least 3 errors in the code we where given, which was rather annoying, and wasted a considerable amount of my time. 1. The function "error" was used before being declared. 2. A nonexistent function "stricmp" is called. 3. The tree_to_graph function refuses to work, despite graphviz being installed, functional, and referenced in the code correctly.
The first two where easy to fix, as they compiler complained about them. However, it took considerable time to fix the third error. It was also perplexing that anyone using windows didn't seem to have this problem at all. After much hunting through code i only half understood, i found that "popen" was being called with a imaginary mode "wt", rather than "r" or "w", the only modes it should be able to take. After removing the t, the code worked. For why this only manifested itself on linux, see here: 250:lab-8:graphvizsoln.
Task1
The downloading worked, YAY!
Task2
In this task we had to construct a expression that prints out this sting:
-(-(a b))
We then had to graph the tree.
This was easy, and didn't take much code to do.
Code
void task2() {
ParseTree* t = mkNode('-', mkNode('-', mkNode('a', 0), mkNode('b', 0), 0), 0);
prefix_tree(t);
printf("\n");
tree_to_graph(t, "task2.jpg");
}
Graph
<html> <img src="http://www.resisty.com/task2.jpg"/> </html>
Task3
In this task we had to construct a considerably more complicated expression. Rather than doing the whole expression as a single line, i worked from the bottom up in smaller chunks.
Code
void task3() {
//third level expressions
ParseTree* add1 = mkNode('+', mkNode('a', 0), mkNode('b', 0), 0);
ParseTree* add2 = mkNode('+', mkNode('y', 0), mkNode('b', 0), 0);
ParseTree* sub1 = mkNode('-', mkNode('x', 0), mkNode('y', 0), 0);
ParseTree* sub2 = mkNode('-', mkNode('y', 0), mkNode('x', 0), 0);
ParseTree* equ1 = mkNode('=', mkNode('a', 0), mkNode('2', 0), 0);
//second level expressions
ParseTree* comp1 = mkNode('>', add1, mkNode('c', 0), 0);
ParseTree* mult1 = mkNode('*', mkNode('z', 0), add2, 0);
ParseTree* cond1 = mkNode('?', equ1, sub1, sub2, 0);
//first level expression
ParseTree* cond2 = mkNode('?', comp1, mult1, cond1, 0);
prefix_tree(cond2);
printf("\n");
tree_to_graph(cond2, "task3.jpg");
}
Task4
Here we had to draw a graph for the expression in task 3, and compare it to the graph produced by the code. There where no discrepancies between my graph and the program's graph.
Graph
<html> <img src="http://www.resisty.com/task3.jpg"/> </html>
Task5
In this task we had to explain why the parse trees don't need to include a colon in conditional expressions.
I am not entirely sure about this, but as far as i can tell, the colon is used in C to separate the two possible courses of action that could be taken. The the parse tree, this is not necessary as they are separated by being different children of the conditional operator.
Task6
Here we had to write a function to evaluate a parse tree, allowing for digits 0-9, and the basic +, -, * and / operators. This was more work than previous tasks, but still quite easy. Basically all that was needed was checks for allowed digits/operators, and checks for errors, like an operation having the wrong number of arguments, dividing by zero, etc.
With all my errors i simply printed an error message, ignored extraneous arguments or returned 0, and allowed the code to keep running. That way the code didn't just crash when it found a problem. If a function has multiple errors, both will show up on the first run, rather than the code crashing at the first one.
Eval Function
int eval(ParseTree* tree) {
if((tree->name >= '0') && (tree->name <='9')) {
if(tree->arity != 0)
error("Digit appears to have arguments. Ignoring arguments and continuing");
return tree->name - '0';
}
if(tree->arity > 2) {
error("Operation appears to have to many arguments. Ignoring extra arguments and continuing");
}else if (tree->arity < 2) {
error("Operation does not have enough arguments. Skipping operation");
return 0;
}
switch ( tree->name) {
case '+':
return eval(tree->arg[0]) + eval(tree->arg[1]);
case '-':
return eval(tree->arg[0]) - eval(tree->arg[1]);
case '*':
return eval(tree->arg[0]) * eval(tree->arg[1]);
case '/':
if(!eval(tree->arg[1])) {
error("Operation attempted to divide by 0. To preserve universe, skipping operation");
return 0;
}
return eval(tree->arg[0]) / eval(tree->arg[1]);
}
error("Operator/Digit \"%c\" not recognised. Skipping.", tree->name);
return 0;
}
Test Code
void task6() {
ParseTree* exp1 = mkNode('+', mkNode('1',0), mkNode('2',0), 0);
ParseTree* exp2 = mkNode('-', mkNode('1',0), mkNode('*', mkNode('3',0), mkNode('8',0), 0), 0);
ParseTree* exp3 = mkNode('-', mkNode('+', mkNode('3',0), mkNode('2',0), mkNode('7',0), 0), mkNode('4', mkNode('3',0), mkNode('8',0), 0), 0);
ParseTree* exp4 = mkNode('-', mkNode('+', mkNode('3',0), 0), mkNode('/', mkNode('3',0), mkNode('0',0), 0), 0);
ParseTree* exp5 = mkNode('h', mkNode('6',0), mkNode('4',0), 0);
printf("Expression 1: ");
prefix_tree(exp1);
printf("\nResult:\n");
printf("%d\n\n", eval( exp1 ));
printf("Expression 2: ");
prefix_tree(exp2);
printf("\nResult:\n");
printf("%d\n\n", eval( exp2 ));
printf("Expression 3: ");
prefix_tree(exp3);
printf("\nResult:\n");
printf("%d\n\n", eval( exp3 ));
printf("Expression 4: ");
prefix_tree(exp4);
printf("\nResult:\n");
printf("%d\n\n", eval( exp4 ));
printf("Expression 5: ");
prefix_tree(exp5);
printf("\nResult:\n");
printf("%d\n\n", eval( exp5 ));
}
Output
Expression 1: +(1 2) Result: 3 Expression 2: -(1 *(3 8)) Result: -23 Expression 3: -(+(3 2 7) 4(3 8)) Result: Operation appears to have to many arguments. Ignoring extra arguments and continuing Digit appears to have arguments. Ignoring arguments and continuing 1 Expression 4: -(+(3) /(3 0)) Result: Operation does not have enough arguments. Skipping operation Operation attempted to divide by 0. To preserve universe, skipping operation 0 Expression 5: h(6 4) Result: Operator/Digit "h" not recognised. Skipping. 0