# SPO Exercises - Lecture 3

## Individual Exercises (1 hour)

The following exercises you may prefer to do on your own, e.g. just after you have read the literature, and discuss the outcome with your group:

1. Do Fisher et al. exercise 3,4,6 page 54-55 (exercise 3,8,9 page 82-84 in GE)





2. Based on the grammar in Figure 2.1 construct the parse tree for each of the following:

a) i x x = 100 x = x + 30 p x

b) i x x = x + y p x

c) i x i y x = x - y p y

3. For each of the programs in exercise 2:

a) Construct the AST

b) According to the definition of ac, is the input semantically correct? If not, what changes to the ac language would render the program semantically correct

c) With ac changes in place that make the program semantically correct, show the code that would be generated from these programs

3. (optional but recommended)Follow the studio associated with Crafting a Compiler Chapter 2: A Simple Compiler http://www.cs.wustl.edu/~cytron/cacweb/Chapters/2/studio.shtml You can find the source zip file in the General_Course_Material directory https://www.moodle.aau.dk/pluginfile.php/2426933/mod_folder/content/0/Studio_Code.zip?forcedownload=1

## Group Exercises (1 hour)

The following exercises are best done as group discussions:

Do Fisher et al. Exercise 1,2,8,9,10,12 page 54-55 (exercise 4,5,6,10,12,13 on page 82-84 in GE)

You should limit the discussion to about 10 minutes per question.

(optional) Do the group exercise part of the studio associated with Crafting a Compiler Chapter 2: A Simple Compiler

(optional) Extend the ac grammar to allow parenthesis in expressions i.e. (4-3) + (2-1). How would this affect the ac compiler?

1. The CFG shown in Figure 2.1 defines the syntax of ac programs. Explainhow this grammar enables you to answer the following questions.

(a) Can an ac program contain only declarations (and no statements)?
- Assuming that an empty string implies that the stmt does not exist then the anwser is yes
-- Prog $\rightarrow$ Dcls Stms $
-- Prog $\rightarrow$ Dcl Dcls Stms $
-- Prog $\rightarrow$ Dcl lambda Stms $
-- Prog $\rightarrow$ Dcl lambda Lambda $
(b) Can a print statement precede all assignment statements?
- Yes

2. Sometimes it is necessary to modify the syntax of a programming language.
This is done by changing the CFG that the language uses. What
changes would have to be made to ac’s CFG (Figure 2.1) to implement
the following changes?
(a) All ac programs must contain at least one statement.
- Prog $\rightarrow$ Dcls Stmt Stmts
(b) All integer declarations must precede all float declarations.
- Remove Dcl & Dcls
- IntDcl $\rightarrow$ intdcl id
- FloatDcl $\rightarrow$ floatdcl id
- IntDcls $\rightarrow$ IntDcl IntDcls | $\lambda$
- FloatDcls $\rightarrow$ FloatDcl FloatDcls | $\lambda$
- Prog $\rightarrow$ IntDcls FloatDcls Stmts
(c.) The first statement in any ac program must be an assignment statement.
- AssignStmt $\rightarrow$ id assign Val Expr
- Prog $\rightarrow$ Dcls AssignStmt Stmts
- You could make it possible to have no statements at all

8. The grammar for ac shown in Figure 2.1 requires all declarations to
precede all executable statements. In this exercise, the ac language is
extended so that declarations and executable statements can be interspersed.
However, an identifier cannot be mentioned in an executable
statement until it has been declared.
(a) Modify the CFG in Figure 2.1 to accommodate this language extension.
- Unit $\rightarrow$ Dcl | Stmt
- Units $\rightarrow$ Unit Units | $\lambda$
- Prog $\rightarrow$ Units $
(b) Discuss any revisions you would consider in the AST design for ac.
(c) Discuss how semantic analysis is affected by the changes you envision
for the CFG and the AST.

9. The abstract tree design for ac uses a single node to represent a print
operation (see Figure 2.9). Consider an alternative design in which the
print operation always has a single id child that represents the variable to
be printed. What are the design and implementation issues associated
with the two approaches?
-

10. The code in Figure 2.10 examines an AST node to determine its effect on
the symbol table. Explain why the order in which nodes are visited does
or does not matter with regard to symbol-table construction.
- It does not have an effect on the symbol table

12. The last fragment of code generated in Figure 2.15 pops the dc stack and
stores the resulting value in register i.
(a) Why was register i chosen to receive the result?
(b) Which other registers could have been chosen without causing any
problems for code that might be generated subsequently?