Thus if an AST node is called Node, these three field will be denoted as Node.Info, Node.Left and Node.Right. Get(Node) will create a new emplty AST node.
The method consists of adding a parameter to each of the procedures which will carry the (partial) AST from procedure to procedure, adding on to it as appropriate.
Consider the recursive descent procedure for an assignment statement:
Following this pseudo-code for the assignment statement:
{Assignment Variable = Expression}
PROCEDURE Assignment (Tree:AST)
{...
IF Next Token = Variable THEN
Get(Node)
Node.Info = Variable
Node.Left = Nil
Node.Right = Nil
Tree = Node
IF NextToken is "=" THEN
Get(Node)
Node.Info = "="
Node.Left = Tree
Node.Right = Nil
Tree = Node
Expression (Tree.Right)
....
}
A = B
we obtain the following abstract syntax tree, presuming the call to Expression(Tree.Right) returns a node whose information field contains B and Tree.Right is a pointer to it:
{Expression Term {+Term} }
PROCEDURE Expression (Tree:AST)
{...
Term(Tree)
WHILE Next Token = "+" DO
Get(Node)
Node.Info = "+"
Node.Left = Tree
Term (Tree.Right)
Tree = Node
...
}
{Term Factor {* Factor} }
PROCEDURE Term (Tree:AST)
{...
Factor(Tree)
WHILE Next Token = "*" DO
Get(Node)
Node.Info = "*"
Node.Left = Tree
Factor (Tree.Right)
Tree = Node
...
}
{Factor Const | ( Expression ) }
PROCEDURE Factor (Tree:AST)
{...
IF Next Token <> "(" THEN
Get(Node)
Node.Info = Token
Node.Left = Nil
Node.Right = Nil
Tree = Node
...
}
Try tracing this for A = B and A = B + C * D
Send questions and comments to: Karen Lemone