Mark: 44 revision(s)

2008-11-03T05:20:25Z

44 revision(s)

New page

[[SE250:lab-8 | Lab page.]]

== 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 [[250:lab-8:graphvizsoln | 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 [[SE250:lab-8:npit006 | 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 [[SE250:lab-8:rbha033 | 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 [[SE250:lab-8:rwan064 | 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 (:)?

[[SE250:lab-8:aomr001 | 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.'''"'''

[[SE250:lab-8:llay008 | 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

[[SE250:lab-8:dols008 | Dols008:]]

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.

[[SE250:lab-8:dcho040 | Dcho040:]]
* 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

SE250:lab-8:Maintainers report - Revision history

Mark: 44 revision(s)