Example of building Parse Tree from Grammar

Let us use an example, given this grammar:

ex = ex op term | term
op = + | -
term = ( ex ) | id

which yields the following sentences:

id + id
id + ( id + ... ) + ... )))
( id + id ) - id

To write a parser, we need to rework the grammar to prevent left-recursion.

ex = term {op term}
op = + | -
term = ( ex ) | id

Here is a recursive descent parser for the above grammar.

op()
  if tok == +  match( + )
  else if tok == -  match( - )
  else error

term()
  if tok == (
     match( ( )
     ex()
     match( ) )
  else if tok == id
     match( id )
  else
     error

ex()
  term()
  if tok == + || tok == -
     op()
     term()

Now the parser is done.  We start to put in routines to build parse tree. (they are called "action routines")

Because of the way the grammar is written, we know that all operations are binary.  We also know that in nested operations, it is always in the (..).  So, the action routine to build parse tree need to do the following:

1) when parser reaches op +/-  remember it.
2) when parser reaches id remember it.
3) when two arguments are parsed we know that we can build a tree.

We use two stacks to remember things.  The first stack stores arguments (can be sub-tree). The second stack stores operators (can be nested).

Here are the basic operations:

push(arg)
pushop(op)
arg = pop()
op = popop()

Finally, we need basic operations to build a tree.

newatom()
cons()

We use stacks from "stmt.c" and build-tree from "list.c".  ystack is argument stack, zstack is op stack.

Here is the parser that include action routines.

op()
  if tok == + 
    match( + )
    zpush( + )
  else if tok == - 
    match( - )
    zpush( - )
  else error

term()
  if tok == (
     match( ( )
     ex()
     match( ) )
     makebintree()
  else if tok == id
     match( id )
     ypush( id )
  else
     error

ex()
  term()
  if tok == + || tok == -
     op()
     term()

makebintree()
  b = ypop()
  a = ypop()
  op = zpop()
  c = cons(op,cons(a,cons(b,NIL)))
  zpush(c)

You can find the whole source here.     ex-parse-tree.zip

last update 24 Sept 2016