• 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 de nition of a simple desk calculator
Exercise 2: What are all the topological sorts for the dependency graph of Figure 2? One
sort mentioned during lecture is 1; 2; 3; : : : ; 9 (slide #16 of Chapter 4). [20 points]
1
SUSTech CS323 - Compilers November 29, 2022
Figure 2: A dependency graph
Exercise 3: Below is an SDD introduced during our lecture for computing the structure of
• type.
◦ Is the SDD S-attributed? Why? [10 points]
◦ Is the SDD L-attributed? Why? [10 points]
◦ Given the input float[3][4][5], please give an annotated parse tree and the evalua-tion order of the attributes (you may refer to the slide #39 of Chapter 4). [20 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 oating-point operands. Floating-point numbers are distinguished by having a decimal point. digit is a terminal representing a number in [0; 9].
E ! E + T j T
• ! D D j D D ! digit
2
SUSTech CS323 - Compilers November 29, 2022
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]
3
