Re:Syntax Tree Construction

Rob Thorpe <robert.thorpe@antenova.com>
14 Sep 2003 17:06:34 -0400

          From comp.compilers

Related articles
Sytnax Tree Construction chris@labino.net (2003-09-04)
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: Rob Thorpe <robert.thorpe@antenova.com>
Newsgroups: comp.compilers
Date: 14 Sep 2003 17:06:34 -0400
Organization: Compilers Central
References: 03-09-024
Keywords: parse
Posted-Date: 14 Sep 2003 17:06:34 EDT



In my view most language constructions are commands(+, if, procedure) or
erm "terminations of commands" (end if, while)
So in 4 + 5 the 4 and 5 demark the expression, + is the command, so
        +
      / \
    4 5


In IF x=12 PRINT "x=12" IF starts and the carriage return ends so
          IF
        / \
      = \
    / \ \
x 12 PRINT
                    \
                    "x=12"


DO
      .. everything else ..
LOOP WHILE x <> 20


becomes


            DO
          / \
        <> .. everything else ..
      / \
    X 20


ie the terminations of commands are not represented. There are still
choices to be made when doing things like this. This is similar to what
Yves Deweerdt suggested. Ripping ideas of various interpreters written
by Eric Raymond :-


This code makes


cons(DOWHILE, condition, everything_else);
cons(ADD, left, right);


etc produce the trees. This is one way of doing it anyway (call in the
lisp way). If your just doing this to learn (I hope you are) then only
write an optimizer if you need to learn how.


typedef struct node_t
{
          int type;
          val_t value;
          struct node_t *left;
          struct node_t *right;
}
node_t;


node_t *cons(int type, node_t left, node_t right)
{
          /* get a node */
          <get some memory typed to node_t and call it new>


          new->type = type;
          new->left = left;
          new->right = right;


          return(new);
}




node_t *atom(int type, int value, variable_t var)
{
          /* get a node */
          <get some memory typed to node_t and call it new>


          switch(new->type = type)
          {
          case TYPE_VAR:
new->value.var = var;
break;


          case TYPE_STR:
new->value.number = value;
break;
          <etc for every other type of variable>


          default:
<signal and error>
          }


          return(new);
}


Post a followup to this message

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