The Semantic Analyzer

Due:
11:00 pm, Friday April 23, 2021

Max grace days: 2

Overview

For this assignment you will write a semantic analyzer. Among other things, this involves traversing the abstract syntax tree and the class hierarchy. You will reject all Cool programs that do not comply with the Cool type system.

You will also write additional code to serialize the class map, implementation map, parent map, and annotated AST produced by your semantic analysis.

Specification

You must create two artifacts:

  1. A program that takes a single command-line argument (e.g., file.cl-ast). That argument will be an ASCII text Cool abstract syntax tree file. Your program must either indicate that there is an error in the input (for example, a type error) or emit file.cl-type, a serialized Cool abstract syntax tree, class map, implementation map, and parent map. If your program is called checker, invoking checker file.cl-ast should yield the same output as cool --type file.cl. Your program will consist of a number of OCaml files.
  2. A plain ASCII text file called README describing your design decisions and choice of test cases. See the grading rubric. A few paragraphs should suffice.

Considerations:

Remember that you do not have to match the English prose of the reference compiler's error messages at all. You just have to get the line number right.

Semantic checks are unordered — if a program contains two or more errors, you may indicate whichever you like. You can infer from this that all of our test cases will contain at most one error.

The .cl-type File Format

If there are no errors in file.cl-ast your program should create file.cl-type and serialize the class map, implementation map, parent map, and annotated AST to it.

The class and implementation maps are described in the Cool Reference Manual.

A .cl-type file consists of four sections:

  1. The class map.
  2. The implementation map.
  3. The parent map.
  4. The annotated AST.

Simply output the four sections in order, one after the other.

We will now describe exactly what to output for the class and implementation maps. The general idea and notation (one string per line, recursive descent) are the same as in the previous assignment.

The Class Map

The Implementation Map

The Parent Map

The Annotated AST

Detailed .cl-type Example

Now that we've formally defined the output specification, we can present a worked example. Here's the example input we will consider:

class Main inherits IO {
  my_attribute : Int <- 5 ;
  main() : Object {
    out_string("Hello, world.\n")
  } ;
} ;

Resulting .cl-type class map output with comments:

class_map                          
6              -- number of classes
Bool           -- note: includes predefined base classes
0                                   
IO                                  
0                                   
Int                                 
0                                   
Main                                
1              -- our Main has 1 attribute
initializer                         
my_attribute  -- named "my_attribute" Int with type Int
2              -- initializer expression line number
Int            -- initializer expression type
integer        -- initializer expression kind
5              -- which integer constant is it?
Object                              
0                                   
String                              
0

Resulting .cl-type implementation map output with comments:

implementation_map            
6                            --  six classes
Bool                         --  first is Bool
3                            --  - it has three methods
abort                        --  - first is abort()
0                            --  -- abort has 0 formal arguments
Object                       --  -- name of parent class from which Bool inherits abort()
0                            --  -- abort's body expression starts on line 0
Object                       --  -- abort's body expression has type Object
internal                     --  -- abort's body is an internal kind of expression (i.e., a system call; see above)
Object.abort                 --  -- extra detail on abort's body expression
copy                         --  - second of Bool's three methods is copy()
0                            --  -- copy has 0 formal arguments
Object                       --  -- name of parent class from which Bool inherits copy()
0                            --  -- copy's body expression starts on line 0
SELF_TYPE                    --  -- copy's body expression has type SELF_TYPE
internal                     --  -- copy's body is an internal kind of expression (i.e., a system call; see above)
Object.copy                  --  -- extra detail on copy's body expression
... many lines skipped ... 
Main                         --  another class is Main
8                            --  - it has 8 methods
... many lines skipped ...   --  
main                         --  - one of Main's methods is main()
0                            --  -- main has 0 formal arguments
Main                         --  -- the name of the class where Main.main() is defined
4                            --  -- the body expression of Main.main starts on line 4
SELF_TYPE                    --  -- the body expression of Main.main has type SELF_TYPE
self_dispatch                --  -- the body of Main.main() is a self_dispatch kind of expression
... many lines skipped ...

Finally, the resulting .cl-type parent map output with comments:

parent_map           
5            -- there are five classes with parents (Object is the sixth class)
Bool         -- Bool's parent ...
Object       -- ... is Object.
IO           -- IO's parent ...
Object       -- ... is Object.
Int          -- Int's parent ...
Object       -- ... is Object.
Main         -- Main's parent ...
IO           -- ... is IO.
String       -- String's parent ...
Object       -- ... is Object.

Commentary

You can do basic testing with something like the following:

linux> cool --parse file.cl
linux> cool --out reference --type file.cl
linux> my-checker file.cl-ast
linux> diff -b -B -E -w file.cl-type reference.cl-type

You should implement all of the typing rules in the Cool Reference Manual. There are also a number of other rules and corner cases you have to check (e.g., no class can inherit from Int, you cannot redefine a class, you cannot have an attribute named self, etc.). They are sprinkled throughout the manual. Check everything you possibly can.

Getting the Assignment

The starter code for the assignment is on the Linux server at the path:

/export/home/public/schwesin/csc310/semantic-analyzer-full-handout

Turning in the Assignment

You must turn in a zip file containing these files:

  1. ast.ml
  2. serialize.ml
  3. deserialize.ml
  4. semantic_analysis.ml
  5. main.ml
  6. README

There is a makefile provided with this assignment. To submit the assignment, execute the command:

    make submit

from within the assignment directory.

Grading Criteria

Grading (out of 100 points):

Extra Credit

You can receive extra credit for your final course grade by passing the positive test cases: