Re: Parser question

Max Hailperin <max@gustavus.edu>
Sat, 19 Jul 2008 20:17:27 -0500

          From comp.compilers

Related articles
Parser question mike@sesamgames.com (Mike \(News\)) (2008-07-11)
Re: Parser question avron2006b@yahoo.com (Aeran) (2008-07-13)
Re: Parser question max@gustavus.edu (Max Hailperin) (2008-07-13)
Re: Parser question DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-07-15)
Re: Parser question mikael@sesamgames.com (Mikael =?ISO-8859-1?Q?Str=F6m?=) (2008-07-17)
Re: Parser question max@gustavus.edu (Max Hailperin) (2008-07-19)
| List of all articles for this month |

From: Max Hailperin <max@gustavus.edu>
Newsgroups: comp.compilers
Date: Sat, 19 Jul 2008 20:17:27 -0500
Organization: Compilers Central
References: 08-07-024 08-07-029 08-07-032
Keywords: parse
Posted-Date: 19 Jul 2008 23:22:38 EDT

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



Post a followup to this message

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