Specification of a Simple Type Checker

Specification of a Simple Type Checker

  • Specification of a simple type checker for a simple language in which the type of each identifier must be declared before the identifier is used.
  • The type checker is a translation scheme that synthesizes the type of each expression from the types of its subexpressions.
  • The type checker can handle arrays, pointers, statements, and functions.
  • Specification of a simple type checker includes the following:
    • A Simple Language
    • Type Checking of Expressions
    • Type Checking of Statements
    • Type Checking of Functions
 Specification of Type Checker

Specification of Type Checker

Simple Language

  • The following grammar generates programs, represented by the nonterminal P, consisting of a sequence of declarations D followed by a single expression E.
P -> D ; E
D -> D ; D | id : T
T -> char | integer | array[num] of T | ‡ T

A translation scheme for above rules:

P -> D ; E
D -> D ; D
D -> id : T { addtype(id.entry, T.type }
T -> char { T.type := char }
T -> integer { T.type := integer }
T -> ‡ T1 { T.type := pointer(T1.type) }
T -> array[num] of T1 { T.type := array(1..num.val, T1.type) }

Type Checking of Expressions

  • The synthesized attribute type for E gives the type expression assigned by the type system to the expression generated by E.
  • The following semantic rules say that constants represented by the tokens literal and num have type char and integer, respectively:
Rule Semantic Rule
E -> literal { E.type := char }
E -> num { E.type := integer}
  • A function lookup(e) is used to fetch the type saved in the symbol-table entry pointed to by e.
  • When an identifier appears in an expression, its declared type is fetched and assigned to the attribute type;
E -> id { E.type := lookup(id.entry}
  • The expression formed by applying the mod operator to two subexpressions of type integer has type integer; otherwise, its type is type_error. The rule is
E -> E1 mod E2 { E.type := if E1.type = integer and E2.type = integer

then integer

else typr_error}
  • In an array reference E1 [E2], the index expression E2 must have type integer, in which case the result is the dement type t obtained from the type array(s. t ) of E1; we make no use of the index set s of the array.
E -> E1 [ E2 ] { E.type := if E2.type = integer and E1.type = array(s,t)

then t

else typr_error}
  • Within expressions, the postfix operator ↑ yields the object pointed to by its operand. The type of E ‡ is the type ‡ of the object pointed to by the pointer E:
E -> E1 ‡ { E.type := if E1.type = ponter(t) then t

else typr_error}
 Type Checking

Type Checking

Type Checking of Statements

  • Since language constructs like statements typically do not have values, the special basic type void can be assigned to them.
  • If an error is detected within a statement, then the type type_error assigned.
  • The assignment statement, conditional statement, and while statements are considered for the type checking.
  • The Sequences of statements are separated by semicolons.
Statement Rule Semantic Rule
Assignment S -> id := E {S.type := if id.type = E,type then void

else type_error}
Conditional E -> if E then S1 { S.type := if E.type = Boolean then S1.type

else type_error}
While E -> while E do S1 { S.type := if E.type = Boolean then S1.type

else type_error}
Sequence E -> S1 ; S2 { S.type := if S1.type = void and S2.type = void then void

else type_error}
 Type Checking Statements

Type Checking Statements

Type Checking of Functions

  • The application of a function to an argument can be captured by the production
E -> E ( E )
  • An expression is the application of one expression to another. The rules for associating type expressions with nonterminal T can be augmented by the following production and action to permit function types in declarations.
T -> T1' -> T2' {T.type := T1.type -> T2.type}
  • Quotes around the arrow used as a function constructor distinguish it from the arrow used as the meta symbol in a production.
  • The rule for checking the type of a function application is
E -> E1 ( E2 ) { E.type := if E2.type = s and E1.type = s -> t

then t

else typr_error}
 Type Checking Functions

Type Checking Functions

Related Searches to Specification of a Simple Type Checker

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add wikitechy.com to your ad blocking whitelist or disable your adblocking software.