Syntax-Directed Translation Scheme for Typechecking PSub

program
  --> program id {curr_scope <- AddEntry(id.lexval, Nil);
                  UpdateType(curr_scope, Program, False)} ;
        var_decls subprogram_decls compound_statement .

var_decls
  --> var decl_list
    | epsilon

decl_list
  --> decl_list declaration
    | declaration

declaration
  --> identifier_list : type ;
        {UpdateTypeList(identifier_list.l, type.t, True)}

identifier_list
  --> identifier_list1 , id
        {identifier_list.l <-
         Cons(AddEntry(id.lexval, curr_scope), identifier_list1.l)}
    | id {identifier_list.l <- Cons(AddEntry(id.lexval, curr_scope), Nil)}

type
  --> standard_type {type.t <- standard_type.t}
    | array [ num .. num1 ] of standard_type
        {type.t <- Array(num.lexval, num1.lexval, standard_type.t)}

standard_type
  --> integer {standard_type.t <- Integer}
    | real {standard_type.t <- Real}
    | boolean {standard_type.t <- Boolean}

subprogram_decls
  --> subprogram_decls subprogram_declaration
    | epsilon

subprogram_declaration
  --> subprogram_head var_decls compound_statement ;
        {curr_scope <- Delete(curr_scope)}

subprogram_head
  --> function id {curr_scope <- AddEntry(id.lexval, curr_scope)}
        arguments : standard_type ;
        {UpdateType(curr_scope, Func(arguments.t, standard_type.t), False)}
    | procedure id {curr_scope <- AddEntry(id.lexval, curr_scope)}
        arguments ;
        {UpdateType(curr_scope, Proc(arguments.t), False)}

arguments
  --> ( parameter_list ) {arguments.t <- parameter_list.t}
    | epsilon {arguments.t <- Nil}

parameter_list
  --> parameter_list1 ; parameter
        {parameter_list.t <- Append(parameter.t, parameter_list1.t)}
    | parameter {parameter_list.t <- parameter.t}

parameter
  --> identifier_list : standard_type
        {parameter.t <-
         UpdateTypeList(identifier_list.l, standard_type.t, True)}
    | var identifier_list : standard_type
        {parameter.t <-
         UpdateTypeList(identifier_list.l, Var(standard_type.t), True)}

compound_statement
  --> begin statement_list end

statement_list
  --> statement_list ; statement
    | statement

statement
  --> variable := expression
        {if not Compat(variable.t, expression.t) then Error}
    | procedure_statement
    | compound_statement
    | if expression then statement else statement
        {if not Compat(Boolean, expression.t) then Error}
    | while expression do statement
        {if not Compat(Boolean, expression.t) then Error}
    | repeat statement_list until expression
        {if not Compat(Boolean, expression.t) then Error}
    | epsilon

variable
  --> id [ expression ]
        {if LookupType(id.lexval) = Array(m,n,s)
           and Compat(Integer, expression.t)
         then variable.t <- s
         else Error}
    | id {variable.t <- LookupType(id.lexval)}

procedure_statement
  --> id ( expression_list ) 
        {MatchProcArgs(LookupType(id.lexval), expression_list.t)}
    | id {MatchProcArgs(LookupType(id.lexval), Nil)}

expression_list
  --> expression_list1 , expression
        {expression_list.t <- Cons(expression.t, expression_list1.t)}
    | expression {expression_list.t <- Cons(expression.t, Nil)}

expression
  --> simple_expression relop simple_expression1
        {expression.t <-
         MatchBinOp(relop.lexval, simple_expression.t, simple_expression1.t)}
    | simple_expression {expression.t <- simple_expression.t}

simple_expression
  --> simple_expression1 add_operator term
        {simple_expression.t <-
         MatchBinOp(add_operator.lexval, simple_expression1.t, term.t)}
    | addop term {simple_expression.t <- MatchUnOp(addop.lexval, term.t)}
    | term {simple_expression.t <- term.t}

add_operator
  --> addop {add_operator.lexval <- addop.lexval}
    | or {add_operator.lexval <- or.lexval}

term
  --> term1 mul_operator factor
        {term.t <- MatchBinOp(mul_operator.lexval, term1.t, factor.t)}
    | factor {term.t <- factor.t}

mul_operator
  --> mulop {mul_operator.lexval <- mulop.lexval}
    | and {mul_operator.lexval <- and.lexval}
    | div {mul_operator.lexval <- div.lexval}
    | mod {mul_operator.lexval <- mod.lexval}

factor
  --> variable
        {if variable.t = Func(l,r) or variable.t = Over(l)
         then factor.t <- MatchFuncArgs(variable.t, Nil)
         else factor.t <- variable.t}
    | id ( expression_list )
        {factor.t <- MatchFuncArgs(LookupType(id.lexval), expression_list.t)}
    | num {factor.t <- TypeOf(num.lexval)}
    | ( expression ) {factor.t <- expression.t}
    | not factor1 {factor.t <- MatchUnOp(not.lexval, factor1.t)}

Notes

This translation scheme uses two global variables, symbol_table and curr_scope, as discussed in class. It assumes that the following types have been declared: Entry and Type, as well as the list types EntryList and TypeList. For the list types we have the empty list constant Nil:List and the cons and append operations Cons: T x TList -> TList and Append: TList x TList -> TList. For the type Type there are the following constructor functions:

  Integer, Real, Boolean, Program: Type
  Array: int x int x Type -> Type
  Func: TypeList x Type -> Type
  Proc, Over: TypeList -> Type

We assume the following functions for interacting with the symbol table and checking types:

• AddEntry: string x Entry -> Entry. This function creates a symbol table entry for the given identifier and scope; if the identifier has already been declared in this scope then it signals an error. The return value points to the entry, which still needs to have its type field assigned.
• UpdateType: Entry x Type x bool -> Void. This procedure inserts a type in the given symbol table entry; the boolean argument modifies the lvalue field of the type.
• UpdateTypeList: EntryList x Type x bool -> TypeList. For each entry in the list given as the first argument, the type given in the second argument is inserted in that entry, with lvalue field given by the third argument. A list of the proper number of copies of the type is returned, as required in the formal parameter section so that we may construct the type of the subprogram itself.
• LookupType:Entry -> Type. Returns the contents of the type field of the given symbol table entry.
• Delete: Entry -> Void. This procedure removes all of the symbol table entries whose scope field is the given entry (the entry for the name of the current subprogram); it returns the next outer scope.
• Compat: Type x Type -> Bool. Returns true if the second argument is type-compatible for assignment to a location whose type is the first argument (which must therefore be an lvalue). For PSub, this means that both types are identical atomic types or the first is Real and the second is Integer (which thus gets coerced to Real). This also handles the special case where the first type is a function type corresponding to the current scope, in which case the second type must be assignable to the return type of the function.
• MatchProcArgs: Type x TypeList -> Void. This procedure determines whether the first argument is a procedure type (perhaps by checking several overloaded options) whose list of argument types is assignment compatible with the provided list of types. If any of these conditions fail, then an error is signalled.
• MatchFuncArgs: Type x TypeList -> Type. This function is just like the previous one, except it is looking for a matching function type and it returns the appropriate return type if successful.
• MatchBinOp: string x Type x Type -> Type. Depending on the name of the operator, this function determines the result type of applying a binary operator to operands of the given types. In the case of Real operators it will allow coercion from Integer; for operators such as div and mod it will enforce Integer operands, and for the boolean operators and and or it will enforce Boolean operands.
• MatchUnOp: string x Type -> Type. Just as above, but for the unary operators +, -, and not.
• TypeOf: string -> Type. Recognizes whether the given string is an integer or a real constant (by the absence or presence of a decimal point or exponent).