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.)