abstract syntax tree

abstract syntax tree is what happens when CFGs is applied to text (i.e., the parser traces the AST in time).

Building an AST

Generally, each production will have an action, which is the relevant computation.

X -> Y1... Yn { action }

Each symbol X admits an attribute X.val

for each terminal, val is the associated lexeme
for non-terminals, val is the expression’s value (i.e., from the values of the subexpressions)

you job is to compose the subexpressions’ values and stick it into X.val. Notably, cycles are not allowed because we typically parse bottom-up, left ot right.

actually doing it

For instance, consider:

E -> int { E.ast = mkleaf(int.lexval) }
   | E1 + E2 { E.ast = mkplus(E.ast, E2.ast) }
   | E.ast = E1.ast

s-attribute

…or synthesized attributes, are calculated from attributes of descendent in the parse tree. For instance, E.val is a synthesized attribute

inherited-attribute, which is rarer, is attributes parsed from teh parent.

declarative vs imperative style

Two parsing ordering styles…

Declarative style

resolution is not specified
parser figures it out

Imperative style

evalution is fixed
suppose action manipulates global state

an example

Consider the grammar

E -> Int | E + E | (E)

For instance:

E -> int { E.val = int.val }
   | E1 + E2 { E.val  = E1.val + E2.val }
   | ( E1 ) = { E.val = E1.val }

example

E -> int | (E) | E + E

and the string

5 + (2 + 3)

We would draw a tree

and crunch that into a data structure (where exprs can point to other structures.)