Exercise 6.

We consider the following grammar. As in the course, the nonterminals P, D, S, T, E stand for Program, Declaration, Statement, Type, Expression. The terminals id, boolean, integer, literal, num stand for identifier, boolean (as a type), integer (as a type), boolean literal (as a value), integer number (as a value).

P $\longmapsto$ D; S

D $\longmapsto$ D; D

D $\longmapsto$ $\bf id$bf: T

T $\longmapsto$ $\bf boolean$

T $\longmapsto$ $\bf integer$

E $\longmapsto$ $\bf literal$

E $\longmapsto$ $\bf num$

E $\longmapsto$ $\bf id$

E $\longmapsto$ E₁ $\bf +$ E₂

E $\longmapsto$ E₁ $\bf =$ E₂

S $\longmapsto$ S₁; S₂

S $\longmapsto$ E

S $\longmapsto$ $\bf id$ := S₁

S $\longmapsto$ $\bf if$ E $\bf then$ $\bf\{$S₁$\bf\}$

S $\longmapsto$ $\bf while$ E $\bf repeat$ $\bf\{$S₁$\bf\}$

There's one slight difference w.r.t. the grammar of the course in the Type checking chapter: each valid statement has a value and thus a type (rather than no value and type void). The following rules compute the value of a valid statement.

• if S₁ and S₂ are valid statements then the value of is that of S₂.
• if is a valid statement then its value is that of S₁.
• if is a valid statement then its value is that of S₁.
• if is a valid statement then its value is that of S₁.

We associate attributes T.type, E.type, S.type, to the grammar symbols T, E, S. Each of these attributes may be boolean, integer or type_error. Then, for instance, the statement is valid as soon as E.type = $\bf boolean$ and S₁.type $\neq$ $\bf type\_error$. The attribute $\bf id$.entry refers to the entry of $\bf id$ in the symbol table.

Question. Complete the following type checker for the above grammar.

Answer 6  

Note that only the type of the non-terminals E, T is required, not their value.