Concrete Syntax Tree Example

The following is an example of the construction of a concrete syntax tree for the statement if x < 0 then z := -x else z := x in the PL0 programming language.

  1. We start with the statement node as our root node as we are defining a PL0 statement.
  2. We know that it's a conditional statement (an IfStatement) so we add that node to the tree.
  3. We then expand the IfStatement node using the definitions in our grammar
    • Some of the blocks are terminal (as denoted by the boxes with sharp corners) which are the leaf nodes of our Concrete Syntax Tree
    • These are our lexical tokens
    • Our grammar describes that
      IfStatement→KW_IF Condition  KW_THEN  Statement  KW_ELSE  Statement\text{IfStatement} \rightarrow \text{KW\_IF} \text{ Condition } \text{ KW\_THEN } \text{ Statement } \text{ KW\_ELSE } \text{ Statement}
    • Given this, our CST is now:
  4. We expand the condition node using the following definitions in our grammar:
    • Condition→RelCondition\text{Condition} \rightarrow \text{RelCondition}
    • RelCondition→Exp [RelOp Exp]\text{RelCondition} \rightarrow \text{Exp [RelOp Exp]}
  5. We then expand the Expression nodes and RelOp node based on our grammar definitions
    • Expression→[PLUS∣MINUS] Term {(PLUS∣MINUS) Term}\text{Expression} \rightarrow [\text{PLUS} | \text{MINUS}] \, \text{Term}\ \{ (\text{PLUS} | \text{MINUS}) \, \text{Term} \}
    • Term→Factor {(TIMES∣DIVIDE) Factor}\text{Term} \rightarrow \text{Factor}\ \{ (\text{TIMES} | \text{DIVIDE}) \, \text{Factor} \}
    • Factor→LPAREN Condition RPAREN ∣ NUMBER ∣ LValue\text{Factor} \rightarrow \text{LPAREN} \, \text{Condition} \, \text{RPAREN} \,|\, \text{NUMBER} \,|\, \text{LValue}
    • LValue→IDENTIFIER\text{LValue} \rightarrow \text{IDENTIFIER}
    • RelOp→EQUALS ∣ NEQUALS ∣ LESS ∣ GREATER ∣ LEQUALS ∣ GEQUALS\text{RelOp} \rightarrow \text{EQUALS} \,|\, \text{NEQUALS} \,|\, \text{LESS} \,|\, \text{GREATER} \,|\, \text{LEQUALS} \,|\, \text{GEQUALS}
  6. We then expand the statement nodes based on the following grammar definitions
    • Statement→Assignment ∣ CallAssignment ∣ ReadStatement ∣ WriteStatement ∣ WhileStatement ∣ IfStatement ∣ CompoundStatement\text{Statement} \rightarrow \text{Assignment} \,|\, \text{CallAssignment} \,|\, \text{ReadStatement} \,|\, \text{WriteStatement} \,|\, \text{WhileStatement} \\ \,|\, \text{IfStatement} \,|\, \text{CompoundStatement}
    • Assignment→LValue ASSIGN Condition\text{Assignment} \rightarrow \text{LValue} \, \text{ASSIGN} \, \text{Condition}