SE250:lab-8:Maintainers report
Introduction to lab
This week's lab was on parse trees.
Initial problems
The code had a few minor errors which needed to be fixed before it will compile
- The error function was called before it was defined and hence needed a prototype declaration (or moved above the expect function as some people did).
- "strcmpi" was misspelled as "strcimp"
- The dot converter part of the programme was still broken. However, Jhor053 put up a page on how to fix this problem, found here
Quite a few people mentioned running into these problems in their report - some spending a lot of time on fixing them. It would be nice to be given working code in the future.
Task One
Download parsetree.c from the SOFTENG 250 web site
Most people had no difficulty here as it was linked right on the lab page. However there was also a link to lab-8.c, which was completely unnecessary and may have thrown a few people off.
Task Two
Construct an expression (calling mkNode) that, when passed to prefix tree, produces the output
-(-(a b))
Graph the tree using tree_to_graph.
mkNode('-',mkNode('-',mkNode('a',0),mkNode('b',0),0),0);
And the output
<html><img src="http://studwww.cs.auckland.ac.nz/~hpan027/250-8-1.jpg" border="0" /></html>
- Common practice here seems to be copying the code from the example and making minor modifications.
- A few people also made the switch from Visual Studio as it was giving them problems.
Task Three
Now, construct an expression that produces
?(>(+(a b) c) *(z +(y b)) ?(=(a 2) -(x y) -(y x)))
Majority of the people went with one of these two approaches:
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);
- From npit006's report - doing each subtree separately and then combining them together
ParseTree* t2 = mkNode('?',mkNode('>',mkNode('+',mkNode('a',0),mkNode('b',0),0),mkNode('c',0),0),mkNode('*',mkNode('z',0),
mkNode( '+',mkNode('y',0),mkNode('b',0),0),0),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),0);
- Others (above code taken from rbha003) did it as a single tree with a range of formatting
- People who split the tree down generally found it easier
- As with the above task, trial and error works quite well here
- A few people drew the tree in advance and said it helped
Task Four
Draw a picture of what you expect the graph of this tree to look like, then graph the tree using tree to graph and compare the result with your prediction.
<html><img src="http://studwww.cs.auckland.ac.nz/~rwan064/lab8/task2.png" border="0" /></html>
- Image sourced from Rwan064's report
- Most of the people who did attempt to draw the tree had it right (or mostly right)
Task Five
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 (:)?
Aomr001: "the colon ":" is used in C to distinguish and separate different conditions.. the parse tree doesn't need to use that because the different conditions are in different branches of the parse tree."
Llay008: "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. "
- Not as many people had gotten up to this part
- The general consensus seems to be that ":" is only needed by the compiler to separate the statements 'e1' and 'e2'. However, in the parse tree this is done implicitly as 'e1' and 'e2' are in different branches
Task Six
Write a (recursive) function to evaluate a parse tree that consists of nodes that are either digits or the operators +, , * and /.
- Very few people got this far
- Below are the links to the report of people who have written some code at the time of writing this report:
- Task 6
- SE250:lab-8:npit006#Task_6
- SE250:lab-8:hpan027#Task_Six
- SE250:lab-8:rwan064#Task_6
- SE250:lab-8:bvic005#Task6
- SE250:lab-8:hlin079
- SE250:lab-8:dols008#Task_6
- SE250:lab-8:jsmi233
- SE250:lab-8:dcho040#task6
- The basic structure of everyone's code is very similar:
- Base case is a single digit leaf
- Using a switch or if statement to check for the symbols '+' '-' '*' '/'
- Calculate the subtrees with the appropriate operator
- Some people had addition error checking for things such as division by zero and unexpected number of children
- Of the people who dealt with an operator having more than two children, mostly everyone treated it as an error
- A few applied the operation to all the children, with left associativity. i.e. *(1 2 3) considered as 1 * 2 * 3
- Digits with arguments were ignored or treated as an error
Task Seven
- Practically no one got this far
Just from a glance at the grammar, it looks like it won't work because <E> ::= <E> <BinOp> <E> defines <E> recursively as itself (plus some other stuff). This will cause an infinite loop with <E> always attempting to match itself.
* his is not working because if 'tokens' is operation, this code will repeat forever.
ParseTree* lhs = recogniseE( tokens );
* and if there is '(', unless ')' is next character, program can't find ')', because code stop before find')'
- Nobody wrote the parser as of the time this report was written
After Lab Task
After the lab and before Thursday, read at the two reports immediately below yours in the wiki list1 and comment on .
- Seems like nobody saw this
Conclusions
- Generally, feedbacks for the lab were positive
- Four tasks were finished on average
- Most common problem mentioned was getting the code to compile
- Things to be improved
- Code which does not compile