next up previous
Next: Exercise 4. Up: Quiz7 Previous: Exercise 2.

Exercise 3.

We extend the grammar of Exercise 2 in order to handle unary functions with a single returned value. Here's a program showing these new features.
f: integer -> integer;
f(n: integer): integer == { 
  if n = 0 then {1} else {n * f(n-1)}; 
}
To do so, we add productions for generating the type of a function, the definition of a function, and a call to a function. Here's the enhanced grammar.
P $ \longmapsto$ DS
D $ \longmapsto$ DD
D $ \longmapsto$ $ \bf id$ :  T
T $ \longmapsto$ A
A $ \longmapsto$ $ \bf boolean$
A $ \longmapsto$ $ \bf integer$
T $ \longmapsto$ A1$ \bf\rightarrow$A2
E $ \longmapsto$ $ \bf literal$
E $ \longmapsto$ $ \bf num$
E $ \longmapsto$ $ \bf id$
E $ \longmapsto$ E1 $ \bf +$ E2
E $ \longmapsto$ E1 $ \bf =$ E2
E $ \longmapsto$ $ \bf id$$ \bf ($E1$ \bf )$
S $ \longmapsto$ S1S2
S $ \longmapsto$ E
S $ \longmapsto$ $ \bf id$ := S1
S $ \longmapsto$ $ \bf if$ E $ \bf then$ $ \bf\{$S1$ \bf\}$$ \bf else$ $ \bf\{$S2$ \bf\}$
S $ \longmapsto$ $ \bf while$ E $ \bf repeat$ $ \bf\{$S1$ \bf\}$
S $ \longmapsto$ $ \bf id$ $ \bf ($$ \bf id$ :  A1$ \bf )$$ \bf :$A2 = = $ \bf\{$S1$ \bf\}$
To keep things simple, observe that we impose the following constraints.
(C1)
The input type and the output type of a function can only be primitive types, that is boolean or integer. This appears in the above grammar.
(C2)
In our language, there is only one scope for variables and functions. In other words, every variable or function is global.
(C3)
In addition, each formal parameter of a function is viewed as a variable.
These constraints imply that only one symbol table is needed, as in the previous exercise. To denote the type of a function you can use a record of the form [in : T1, out : T2]. So, coming back to the above example Finally, since in this language every statement has a value (see the previous exercise), a function definition must have a value too. This value is simply the defined function. So, coming back again to the above example, the type of the statement corresponding to the function definition is just [in :  integer, out :  integer].

Question. Complete the type checker for the following rules. You can use any pseudo-code style that you like or even write sentences like if there exists an entry e with type T then T.

Answer 3  
\fbox{
\begin{minipage}{15 cm}
\begin{tabular}{l\vert ll}
$T \longmapsto A_1 {\...
... \\
& & {\sf else} ${\bf type\_error}$\ $\}$\ \\
\end{tabular}\end{minipage}}


next up previous
Next: Exercise 4. Up: Quiz7 Previous: Exercise 2.
Marc Moreno Maza
2004-12-02