1 Requirements
2 Required Exercises (100 points)
Exercise 1: For the SDD in Figure 1, give annotated parse tree for the following expression
(the symbol ‘n’ is the end marker): (1 + 2 ∗ (3 + 4) + 5) ∗ 6n. [20 points]
Figure 1: Syntax-directed definition of a simple desk calculator
Figure 2: A dependency graph
• Is the SDD S-attributed? Why? [10 points]
• Is the SDD L-attributed? Why? [10 points]
Figure 3: An SDD for computing the structure of a type
Exercise 4: Below is a grammar for expressions involving operator + and integer or floatingpoint operands. Floating-point numbers are distinguished by having a decimal point. digit is a terminal representing a number in [0,9].
E → E + T | T
T → D · D | D
D → digit
1. Give an L-attributed SDD to compute the value of the expression E. [15 points]
2. Is possible to evaluate all the attributes during bottom-up parsing process? [5 points]
