Compiler Design Laboratory

8. Type Checking

8.1 Introduction

Type checking involves type inference of expressions by analyzing their AST. In principle, the type of a node is inferred based on the types of its descendants. We iterate some of the novelties that show up apart from a procedural language compiler:

• the location of members not only in the current class but also in the super class, in the case of inherited members;
• the substition in the context of calls or assignments the superclass instances with subclass instances;
• the chaining of the receivers in the context of a call;
• etc.

It can be noticed that the OOP concepts impact with different intensity the analysis and sinthesis processes.

8.2 The redesign of the language grammar

In order to define better the semantical actions we will proceed to reorganize the grammar proposed in the first laboratory work. Some of the redesign principles are:

• we will take into account the precedence of operators
• the expressions are of 3 categories:
  • logical expressions;
  • arithmetical expressions;
  • acesses and calls.
• one can notice that
  • a condition can be an arithmetical expression;
  • an arithmetical expression can be a call or an access;
  • this is drawback that helps the grammar to be without ambiguities;
  • an eventual seperation of the three expression categories can be derived as a call thus causing ambiguities in the grammar;
• the left recursion was eliminated since JavaCC is a parser generator that generates recursive descendant parsers;
• where Exp can be made more specific that specific version was used instead;
• array indexing and array element assignemnt is done only with integer expressions;

Obviously, this redesign represent only some guidelines and is used as a base for the further presentation.

Program ::= MainClass ClassDecl*

MainClass ::= class id { public static void main ( String [] id ) 
              { Statement }}

ClassDecl ::= class id { VarDecl* MethodDecl* }
          ::= class id extends id { VarDecl* MethodDecl* }

VarDecl ::= Type id ;

MethodDecl ::= public Type id ( FormalList ) 
               { VarDecl* Statement* return Exp ;}

FormalList ::= Type id FormalRest*
           ::= FormalRest 
           ::= ,Type id

Type ::= int []
     ::= boolean
     ::= int
     ::= id

Statement ::= { Statement* }						
          ::= if ( Condition ) Statement else Statement
          ::= while ( Condition ) Statement
          ::= System.out.println ( Exp ) ;
          ::= id= Exp ;
          ::= id[ ExpArm ]= ExpArm ;

Exp ::= Condition

Condition ::= ExpLog | ! ExpLog

ExpLog ::= ExpRel ExpLog2 | true ExpLog2 | false ExpLog2

ExpLog2 ::= OpLog ExpRel ExpLog2 | eps

OpLog ::= && | ||

ExpRel ::= (Condition ) | ExpArm OpRel ExpArm | ExpArm

OpRel ::= == | != | < | > | <= | >=

ExpArm ::= ExpTerm ExpArm2

ExpArm2 ::= OpAd ExpTerm ExpArm2 | eps

OpAd ::= + | -

ExpTerm ::= ExpFact ExpTerm2

ExpTerm2 ::= OpMul ExpFact ExpTerm2 | eps

OpMul ::= * | /

ExpFact ::= INTEGER LITERAL | ( ExpArm ) | Access

Access ::= Call [ ExpArm ] | Call

Call ::= CallTarget Call2

Call2 ::= .length | . id ( ExpList ) Call2 | eps

CallTarget ::= new int [ ExpArm ]
           ::= new id ()
           ::= id
           ::= this

ExpList ::= Exp ExpRest*
        ::=

ExpRest ::= ,Exp

8.3 Type Checking Rules

As we said earlier, the general purpose of the laboratory work is to infer type information for the nodes that form the expressions.

8.3.1 Rules for the instructions

if ( Condition ) Statement else Statement
while ( Condition ) Statement

• the type of Condition must be boolean;

id = Exp ;

• the type of id must be a supertype of Exp;

id [ ExpArm ]= ExpArm ;

• the type of id must be array of integers and the type of ExpArm in both its occurrences must be integer;

8.3.2 Rules for the logical expressions created with && and || logical operators

Exp ::= Condition

• the type of Exp must be equal with the type of Condition;

Condition ::= ExpLog | !ExpLog

• For the first branch:
• the type of Condition must be equal with the type of ExpLog;
• For the second branch:
• the type of Condition is boolean so the type of ExpLog must be boolean;

ExpLog ::= ExpRel ExpLog2 | true ExpLog2 | false ExpLog2

• For the first branch:
• the type of ExpLog is equal with the type of ExpRel if ExpLog2 does not exist;
• the type of ExpLog is boolean if ExpLog2 exists and the type of ExpLog2 must be boolean;
• For the second branch:
• the type of ExpLog is boolean if ExpLog2 does not exist;
• the type of Explog is boolean if ExpLog2 exists and the type of ExpLog2 must be boolean;
• For the third branch:
• the type of ExpLog is boolean if ExpLog2 does not exist;
• the type of ExpLog is boolean of ExpLog2 exists and the type of ExpLog2 must be boolean;

ExpLog2 ::= OpLog ExpRel ExpLog2 | eps

• For the first branch:
• the type of ExpLog2 is boolean and the type of ExpRel must be also boolean;

8.3.3 Rules for relational expressions created with ==,!=,<,>,<=,>= relational operators

ExpRel ::= ( Condition ) |  ExpArm OpRel ExpArm | ExpArm

• For the first branch:
• the type of ExpRel is equal with the type of Condition
• For the second branch:
• the type of ExpRel is boolean;
• the type of ExpArm must be integer in both its appearances;
• For the third branch:
• the type of ExpRel is equal with the type of ExpArm;

8.3.4 Rules for additive expressions created with +,- additive operators

ExpArm ::= ExpTerm ExpArm2

• the type of ExpArm is equal with the type of ExpTerm;
• the type of ExpTerm2 must be integer if ExpArm2 exists;
• the type of ExpArm2 must be integer if exists;

ExpArm2 ::= OpAd ExpTerm ExpArm2 | eps

• For the first branch:
• the type of ExpArm2 is integer;
• the type of ExpTerm must be integer;
• the type of ExpArm2 must be integer if exists;

8.3.5 Rules for multiplicative expressions created with *,/ multiplicative operators

ExpTerm ::= ExpFact ExpTerm2

• the type of ExpTerm is equal with the type of ExpFact;
• the type of ExpFact must be integer if ExpTerm2 exists;
• the type of ExpTerm2 must be integer if it exists;

ExpTerm2 ::= OpMul ExpFact ExpTerm2 | eps

• For the first branch:
• the type of ExpTerm2 is integer;
• the type of ExpFact must be integer;
• the type of ExpTerm2 must be integer if it exists;

8.3.6 Rules for factors

ExpFact ::= INTEGER LITERAL | ( ExpArm ) | Access

• for the first branch the type of ExpFact is integer;
• for the second branch the type of ExpFact is integer and the type of ExpArm must be integer;
• for the third branch the type of ExpFact is equal with the type of Access;

8.3.7 Rules for acceses

Access ::= Call [ ExpArm ] | Call

• for the first branch
• the type of Access is integer;
• the type of Call must be an integer array type;
• the type of ExpArm must be integer;
• for the second branch
• the type of Access must be equal with the type of Call;

8.3.8 Rules for calls

Together with the type attribute we will also infer a message attribute for each node. The message incapsulated the name of the called member (attribute or method) and the orderred list of actual parameter types that makes the call.

Call ::= CallTarget Call2

• the type of Call is equal with the type of CallTarget of Call2 does not exist;
• the type of Call is equal with the type of Call2 if it exists;
• the message of Call2 (called member) must be present in the members table of the CallTarget's type;
• the list of types from the message of Call2 must be a subtype of the signature of that message, because according to the substitution principle from OOP an instance of a subclass may be used instead of an instance of the superclass;
• we have to consider, in order, the subtype relation for each component from the orderred types list and obviously the number of formal and actual arguments must be equal;
• if the message of Call2 is length then the CallTarget type must be array of integers;

Call2 ::= . length | . id ( ExpList ) Call2 | eps

• for the first branch
• the type of Call2 is integer;
• for the second branch
• the type of Call2 nonterminal is the type of id if the Call2 call is derived in epsillon (eps);
• the type of the Call2 nonterminal is the type of Call2 call type if it is not derived in epsillon (eps);

CallTarget ::= new int [ ExpArm ] | new id () | id | this

• for the first branch
• the type of CallTarget is array of integers;
• the type of ExpArm must be integer;
• for the second branch
• the type of CallTarget is the type of id class;
• for the third branch
• the type of CallTarget is the type of id that can be: i) local variable; ii) formal parameter of the current method; iii) member of the current class; iv) member of the super class;
• for the fourth branch
• the type of the CallTarget is the type of the current class;

8.3.9 Rules for expression lists

• the type of a list of expressions id an orderred list of those types;

8.4 The checking strategy

For the implementation of a type checker it is recommended the use of the Visitor design pattern that helps type inference. Visiting the nodes imply semantical actions according to the previosly mentioned rules:

• to check the inferred types from the child nodes;
• to infer the type of the current node based on these;

The structure to be returned by the verifier methods must model the note type and in the case of call nodes the call's message.

8.5 Requirements

• Implement a type verifier according to the previously mentioned ruled for the MiniJava language.
• Assignments time: 3 weeks.