Re: Parser question

Mikael StrC6m <mikael@sesamgames.com> writes:


....
> The above pseudo code makes me a bit wondering though: "return left"
> would return a leaf, and not the 'root' of the expression, correct?


No, incorrect. Take a look at what statements in the code assign a
value to the variable "left". To know what is returned by "return
left", you need to look at what the most recent assignment to that
variable is, at the time of the return statement. Except in the case
when the expression is a single term (with no '+' or '-' following
it), the most recent assignment will always be from these two lines,
or the corresponding ones for '-':


            newLeft = makenode_op('+', left, right)
            left = newLeft


So, the value being returned will be one of the nodes produced by
makenode_op, refuting your prediction that it would be a leaf. To see
more specifically that it is the root, consider an expression like


    a-b-c


where a, b, and c are terms. If for simplicity we assume that the term()
procedure returns just the characters 'a', 'b', 'c' for these terms,
then the values that the variable "left" will take on over the course
of the expr() procedure's execution are


  'a'
  makenode_op('-', 'a', 'b')
  makenode_op('-', makenode_op('-', 'a', 'b'), 'c')


Notice that the first of these values for left shows up as the second
parameter passed to makenode_op in constructing the second value for
left. And similarly, the second value for left shows up as the second
parameter passed to makenode_op in constructing the third value for
left. This is because in each case, the new value of left is being
computed as makenode_op('-', left, right). And the third value for
left, the one that is returned, is in fact the root of the tree.


> ... Again, thanks a lot!


You're welcome. -max

Return to the comp.compilers page.
Search the comp.compilers archives again.