Using the SDD to draw syntax tree or DAG for a given expression

Posted by AJ × 07:24

• Draw the parse tree

• Perform a post order traversal of the parse tree

• Perform the semantic actions at every node during the traversal

– Creates a syntax tree if a new node is created each time functions Leaf and Node are called

– Constructs a DAG if before creating a new node, these functions check

whether an identical node already exists. If yes, the existing node is returned.

SDD to produce Syntax trees or DAG is shown below.

For the expression a + a * ( b – c) + (b - c) * d, steps for constructing the DAG is as below.

Widget by HandBit

All Syllabus