CSE340-Project 2: Type Checking Solved

The     goal    of         this      project            is         to         give     you     experience    in         Hindley-Milner type     checking.

We      begin  by        introducing    the      grammar        of         our      language       which is based on       the      previous         project            with additional          constructs.     Then   we       will discuss          the      semantics      of         our      language       and     type     checking        rules. Finally we       will      go        over    a          few      examples       and     formalize        the      expected output.

1.   Lexical      Specification
2.   Grammar
Here    is         the      grammar        for       our      input   language:

3.   Language  Semantics
3.1.  Types
The                                                           language has  three  built-in      types:  int ,  real   and     bool .

3.2.  Variables
Programmers            can     declare           variables        either  explicitly         or         implicitly.

                                                   Explicit                             variables    are      declared      in         an       var_list                                           of                                        a   var_decl .

A variable          is         declared         implicitly         if          it          is         not      declared   explicitly         but      it          appears          in         the      program body.

Example
3.3.  Type System
Our      language       uses   structural       equivalence  for       checking        type     equivalence. Implicit            types   will      be inferred     from    the      usage (in       a          simplified       form    of Hindley-Milner          type     inference).

Here    are      all        the      type     rules/constraints      that     your    type     checker          will enforce          (constraints   are      labeled for     reference):

C1:    The     left       hand   side     of         an       assignment   should have   the      same  type           as        its        right    hand   side

C2:    The     operands       of         a          binary operator         ( PLUS ,          MINUS ,          MULT ,        DIV ,  GREATER ,      LESS ,            GTEQ ,            LTEQ ,            EQUAL and     NOTEQUAL )        should have   the      same  type     (it         can     be        any     type)

                                                                                       C3:                                                        The          operand         of                                                                    a                                                        unary        operator         ( NOT )                                                     should                                                      be           of         type     bool

4.   Output
There  are      two      scenarios:

There     is         a          type     error    in         the      input   program

There     are      no       type     errors  in         the      input   program

4.1.  Type Error
If          any     of         the      type     constraints    (listed in         the      Type   System           section above)            is         violated          in         the      input

4.2.  No     Type Error
If          there   are      no       type     errors  in         the      input   program,        then    you     should output type     information    for       all variables   in         the      input   program         in         the order   they    appear            in         the      program.        There  are      two      cases:

                                                                                                                                                                               If        the                                                                                                                                                           type         of                                                                                                                                                              the   variable                                                                                                                                                           is determined                                                                                                                                                        to        be                                                                                                                                                            one         of                                                                                                                                                              the     builtin                                                                                                                                                     types,       then                                                                                                                                                      output       one                                                                                                                                                           line         in

   If         the      type     of         the      variable          could  not      be        determined    to         be           one     of         the      builtin types,  then    you need       to         list       all        variables           that     have   the      same  type     as        the      target  variable          and     mark   all           of         them as          printed            (so       as        to         not      print    a          separate           entry   for       those  later).  You     should output one     line     in

5.   Examples
Given  the      following: