Slide 4.4: Annotated parse trees

Slide 4.3: Syntax-directed definitions
Slide 4.5: Evaluation orders for SDDs
Home

Annotated Parse Trees

An annotated parse tree is a parse tree showing the value(s) of its attribute(s).

The attribute grammar (syntax-directed definitions) evaluating arithmetic expressions is given again on the right:

	Production	Semantic Rules
1.	`<L> ::= <E> n`	`Val(<L>) = Val(<E>)`
2.	`<E> ::= <E₁> + <T>`	`Val(<E>) = Val(<E₁>) + Val(<T>)`
3.	`<E> ::= <T>`	`Val(<E>) = Val(<T>)`
4.	`<T> ::= <T₁> * <F>`	`Val(<T>) = Val(<T₁>) × Val(<F>)`
5.	`<T> ::= <F>`	`Val(<T>) = Val(<F>)`
6.	`<F> ::= ( <E> )`	`Val(<F>) = Val(<E>)`
7.	`<F> ::= digit`	`Val(<F>) = Lexval(digit)`

The parse tree and annotated parse tree of the expression “3 * 5 + 4 n” are given as follows: