Description
Reading Assignment. Read the following sections in the textbook:
• Chapter 5: Memory Management
Programming Homework. The goal of this assignment is to perform semantic analysis over the
AST generated from your Parser implementation from HW-4. To complete the assignment, finish
the following steps. Note that you should get started on this assignment early to give yourself
enough time to ask questions (and receive a response) before the due date. If you wait until the last
minute and have issues, you will likely have to turn your homework in with the late penalty. If you
have questions, please ask them over Piazza or else via office hours with the instructor or graders.
1. Download the HW-5 Starter Code. Use the link provided in Piazza to accept the GitHub
Classroom assignment for HW-5. When accepting the assignment, please be sure to link your
account to your name in the roster (if you haven’t done so already). Accepting the assignment
will create a copy of the starter code and place it in a hw-4 repository for you. You will then
need to clone this repository to your local machine. As always, be sure to frequently add,
commit, and push your changes.
2. Add your previous files HW to your repository. You will need to copy some of your header and
cpp files from HW-4 into your HW-5 repository (and working directory). Note that modified
versions of ast.h and mypl_exception.h are provided in the starter code. A skeleton version
of type_checker.h is also provided along with a working version of symbol_table.h. You
must provide all other files needed (beyond those provided) to compile your program, to finish
your assignment, and for your submission to be graded.
3. Implement the TypeChecker class (in type_checker.h). Please see the discussion and notes
from class for more details. Note that this class implements the visitor interface from HW-4.
4. Testing your implementation. A set of basic test files are also provided in the test subdirectory. Note that you will need to generate additional tests to ensure your program works
correctly. The graders will also be testing your code for error cases (in addition to the cases
provided).
5. Submit your code. Be sure you have submitted all of your source code to your GitHub repo
for the assignment (again, you should get into the habit of frequently adding, committing,
and pushing your code). In addition to your source code, you must also submit each of
your extended and any additional test files you used for testing. For error cases, submit a
file that contains the error cases you tried (or else a script with the error cases themselves).
Note that all necessary files to compile and build your program must be checked in to your
repository. If your homework doesn’t compile, the graders won’t be able to test it for correctness
or completeness.
1
Homework Submission. All homework must be submitted through GitHub Classroom. A link
for each assignment will be posted on Piazza when the homework is assigned. Be sure all of your
code is pushed by the due date (which you can double check for your repository using the GitHub
website). Each programming assignment is worth 35 points. The points are allocated based on
the following.
• Correct and Complete (25 points). Your code must correctly and completely do the
requested tasks using the requested techniques. Note that for most assignments you will be
provided a partial set of test cases to help you determine a minimal level of correctness. If
your program fails any of the provided test cases you will only receive partial credit. Note
that passing the given test cases does not mean your work is complete nor correct. Your
assignment will also be graded with additional test cases (not provided to you) that will help
the graders determine the extent of your solution and your final score. Note that for C++
code, correctness also implies properly handling the creation and deletion of dynamic memory
(i.e., the absence of memory leaks).
• Evidence and Quality of Testing (5 points). As part of your homework assignments
you must develop additional test cases beyond those given to you to ensure your program is
correct and complete. These test cases must be turned in with your assignment. You will be
graded on the scope and quality of the additional test cases you provide.
• Formatting and Comments (5 points). Your code must be formatted consistently and
appropriately for the language used. For C++, you must follow the provided style guide (see
the course webpage). You must also comment your code and test cases, which at a minimum
must include a file heading (see examples provided), function comments, and meaningfully
selected variable, class, and function names.
2
Type Inference Rules. The following rules are designed to help clarify type inference in MyPL.
While the rules are more formal than a text-based description, some of the rules take liberties in
terms of notation. We use the notation e : t to say that expression e has type t. We assume nil has
type nil (i.e., nil : nil). In general, we use e to denote expressions, t to denote types, x to denote
variable names, s to denote structured type names, f to denote function names, and block to denote
statement lists (e.g., the body of a function). Function types are represented as ordered lists of type
with one type for each parameter and the last slot reserved for the return type. User-defined types
are represented as maps (dictionaries) with keys for variable names and values for corresponding
variable types.
c is a literal with type t
Γ ` c : t
(1)
Γ ` e1 : t Γ ` e2 : t t ∈ {int, double} op ∈ {+, -, *, \}
Γ ` e1 op e2 : t
(2)
Γ ` e : t t ∈ {int, double}
Γ ` neg e : t
(3)
Γ ` e1 : int Γ ` e2 : int
Γ ` e1 % e2 : int
(4)
Γ ` e1 : t1 Γ ` e2 : t2 t1, t2 ∈ {char, string}
Γ ` e1 + e2 : string
(5)
Γ ` e : t t 6= nil
Γ, var x = e ` x : t
(6)
Γ ` e : t t 6= nil
Γ, var x: t = e ` x : t
(7)
Γ ` e : nil
Γ, var x: t = e ` x : t
(8)
Γ, var x1 τ1 = e1 ` x1 : t1 . . . Γ, var xn τn = en ` xn : tn
Γ, type s var x1 τ1 = e1 . . . var xn τn = en end ` s : {x1 → t1, . . . , xn → tn}
†
(9)
Γ, block ` e : t
Γ, return e ∈ block ` block : t
(10)
Γ, return e 6∈ block ` block : nil
(11)
Γ ` block : t
0
t
0 ∈ {t, nil}
Γ, fun t f(p1 : t1, . . . , pn : tn) block end ` f : {t1, . . . , tn, t}
(12)
†where τi denotes an optional type expression “: ti”
3
Γ ` new s : s
(13)
Γ ` e : s Γ ` s : {. . . , xi → ti
, . . . }
Γ ` e.xi
: ti
(14)
Γ ` e1 : t1 . . . Γ ` en : tn Γ ` f : {t1, . . . , tn, t}
Γ ` f(e1, . . . , en) : t
(15)
Γ ` x : t
Γ, x = e ` e : t ∨ e : nil
(16)
Γ ` e1 : t Γ ` e2 : t t ∈ {int, double, bool, string, char, nil, s}
Γ `: e1 {=, !=} e2 : bool
(17)
Γ ` e1 : t Γ ` e2 : nil t ∈ {int, double, bool, string, char, s}
Γ `: e1 {=, !=} e2 : bool
(18)
Γ ` e1 : nil Γ ` e2 : t t ∈ {int, double, bool, string, char, s}
Γ `: e1 {=, !=} e2 : bool
(19)
Γ ` e1 : t Γ ` e2 : t t ∈ {int, double, char, string}
Γ `: e1 {<, >, <=, >=} e2 : bool
(20)
Γ ` e1 : bool Γ ` e2 : bool
Γ ` e1 and e2 : bool
(21)
Γ ` e1 : bool Γ ` e2 : bool
Γ ` e1 or e2 : bool
(22)
Γ ` e : bool
Γ ` not e : bool
(23)
Γ, while e do . . . end ` e : bool
(24)
Γ, if e then . . . end ` e : bool
(25)
Γ, if . . . elif e then . . . end ` e : bool
(26)
Γ ` e1 : int Γ ` e2 : int
Γ, for x = e1 to e2 do . . . end ` x : int
(27)
4
