Syntax Tree

What:

It’s a tree data structure representation of a programming language’s code, given that language’s specific grammar. It’s created in the Compiler Frontend (we made one in CW1 of CT).

Example:

Imagine the grammar

   Exp → Exp + Exp
   Exp → Exp * Exp
   Exp → Var | Num | ( Exp )
   Var → x | y | z
   Num → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Now imagine the input of 5*(x+3). For the Compiler Backend to operate on that, we need to actually know what it’s trying to achieve. We made progress on that by turning it into the tree from below.

• A Concrete Syntax Tree would be that.
  • But that’s really convoluted. It’s quite a big tree. Can we make it more concise? High entropy?
  • We can! We turn a CST into…
• An Abstract Syntax Tree would look like:
•