Compilers: Principles and Practice

6.8 Example: Type Checking in an Interpreter

As an interpreter has to immediately execute a given program, it should be able to do some preliminary type checking. We take an example of a simple interpretive language. Its grammar is:

program :  funcs END;
funcs   :  func
        |  func funcs
        ;  
func    :  typeid ‘(’ typeids ‘)’ ‘:’ expr ;
typeid  :  INT ID
        |  BOOL ID
        ;  
typeids :  typeid
        |  typeid ‘,’ typeids
        ;
expr    :  NUM
        |  ID
        |  expr ‘+’ expr
        |  expr ‘~’ expr
        |  IF expr THEN expr ELSE expr END
        |  ID ‘(’ exprs ‘)’
        |  LET ID ‘=’ expr IN expr END
        ;  
exprs   :  expr
        |  expr ‘,’ exprs
        ;

It is a small functional language, where the program is made up of function definitions. Each function declares its result type and the types and names of its arguments. Functions and variables have ...