Sytnax Tree Construction

chris@labino.net (Chris)
4 Sep 2003 22:46:02 -0400

          From comp.compilers

Related articles
Sytnax Tree Construction chris@labino.net (2003-09-04)
Re: Sytnax Tree Construction blackmarlin@asean-mail.com (2003-09-09)
Re: Sytnax Tree Construction yves@news.be (Yves Deweerdt) (2003-09-09)
Re: Syntax Tree Construction Martin.Ward@durham.ac.uk (Martin Ward) (2003-09-14)
Re:Syntax Tree Construction robert.thorpe@antenova.com (Rob Thorpe) (2003-09-14)
| List of all articles for this month |

From: chris@labino.net (Chris)
Newsgroups: comp.compilers
Date: 4 Sep 2003 22:46:02 -0400
Organization: http://groups.google.com/
Keywords: parse, question
Posted-Date: 04 Sep 2003 22:46:02 EDT

Hello everyone. I'm pretty new to compiler design, and have a few
questions about syntax tree's. First off, what is the difference
between a:


1)Parse Tree
2)(Abstract) Syntax Tree


Given that, im still slightly confused on the concept of a tree
representation of a program. I've been working on a BASIC compiler
for a while now, and have just been generating a simple intermediate
code, simmilar to three address code, straight from the parser (with
some bits of target code thrown in the intermediate representation).
This works, although im not very satisfied with the error
checking/reporting that I can handle through this method. From what I
gather, it seems that a syntax tree is "how things are done" these
days, and would be more efficient that the way im parsing the source
now. Before I dive in and try to re-write a whole bunch of my current
code, I'd like to "get it right" to an extent at least. I understand
the generation of a tree from an expression: 4+2*var:
      +
    / \
  4 *
        / \
      2 var


But for instance, how do you handle the actual language keywords. For
instance, how would a tree be build for the BASIC code:


DO
      x=x+2
      IF x=12
                PRINT "x=12"
      ELSEIF x=14
                PRINT "x=14"
      ELSE CALL function()
      ENDIF
LOOP WHILE x<>20


Would it all be translated into one tree, or split up into a bunch of
different tree's? How would an IF...ENDIF/DO...LOOP structure look on
a tree?...etc.


Once the tree is built, is it neccessary to translate that
representation into another intermediate representation in a
non-optimizing compiler, or would directly generating code be ideal?
Thanks for any help!
[There's lots of agreement about how the tree for an expression should look,
very little agreement on how the tree for anything else should look.
Depending on how much optimization you want to do, you might make a list
of nodes, one per statement, a tree to show the flow of control, e.g.
the loop would have one subtree for the list of statements, another for
the control expression. -John]



Post a followup to this message

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