# SPO - Lecture 3

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

a) Can an ac program contain only declarations (and no statements)?
- Yes, but the program will not do anything, except set memory aside for the declarations. Rule 7 is used.
b) Can a print statement precede all assignment statements?
- Yes, syntactically. The rules for Stmts impose no contraints on the ordering of a sequence of instances of the Stmts.

## 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.
- Rule 1 is altered: Prog -> Dcls Stmts Stmt $

b) All integer declarations must precede all float declarations.
- Prog -> IntDcls FloatDcls Stmts $
- IntDcls -> intdcl id IntDcls
| λ
- FloatDcls -> floatdcl id FloatDcls
| λ

c) The first statement in any ac program must be an assignment statement. - Hjælp, kan begge disse ændringer fungere?
- Prog -> Dcls Assignment Stmts $
| Dcls $
- Assignment -> id assign Val Expr
- Stmt -> Assignment | print id
--
- Prog -> Dcls id assign Val Expr Stmts $
| Dcls $

## 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. - Hjælp, vi er i tvivl om declaration først og så executable statement
- option a) We state that "however" is part of semantics not CFG(context free):

Prog ->  Dcl Lines $
         | $
 Lines ->  Dcl Lines
         | Stmt Lines
         | λ
 Dcl ->    floatdcl id
         | intdcl id
 Stmt ->   id assign Val Expr
         | print id
 Expr ->   plus Val Expr
         | minus Val Expr
         | λ
 Val ->    id
         | inum
         | fnum

Vi tilføjer Lines da declarations og statements kan blive brugt sammen.

b) Discuss any revisions you would consider in the AST design for ac.
- Link 'id' node to the corresponding declaration node.

c) Discuss how semantic analysis is affected by the changes you envision for the CFG and the AST.
- We have to check if and when the variable has been declared. E.g. make a column in the symbol table for when a given variable is declared.

## 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?

- Normal approach: Allows only the specification of a single variable where the corresponding value will be printed.
- Alternative approach: Print a combination of variables. Give a list of variables that will yield a result, which will be printed. The implementation would be more complex/complicated.
3_3 .--.--.--.--.--.
- normal: it implies that the print token "IS" b, not that the id b is printed.
- alternative: Now instead, the print operation is done to the id b.

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

- The result of the call to LookUpSymbol does not depend on the order in which symbols are entered into the symbol table, the order in which declaration nodes are processed affects the look up process.
- If a symbol is declared twice, the error "duplicate declaration" is called regardless of the order in which they are processed. Since, they will always be saved in the same place in the symbol table according to their id/name.

## 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?
- i is chosen beacuse i is a keyword, and cannot be used as a variable name.
b) Which other registers could have been chosen without causing any problems for code that might be generated subsequently?
- f or p, as they are also keywords.