This week you will add name analysis to your Tool compiler. This will considerably ease the task of type checking that you will start next week or the week after. Your analyzer is due on Tuesday, Nov. 9th, 11.55pm (23h55). Note that the type checker will be due the following week, so make sure you start working on it as early as possible.

The description of this assignment is rather long. Don't panic :) Most of it is to help you avoid forgetting important points, and we give you a substantial amount of code.

The goal of name analysis is twofold: we want to reject programs which contain certain types of errors, and we want to associate symbols to all identifiers.

Symbols are values which uniquely identify all class, method and variable names in a program, by mapping their (multiple) occurrences to their (unique) definition. Identifiers are already present in the AST and contain names as well, but these are not sufficient to distinguish between a class member and a local variable with the same name, for instance. This week we will –among other things– add this missing information to the ASTs.

In the process of mapping occurrences to definitions, we will be able to detect the following kinds or errors:

• a class is defined more than once
• a class uses the same name as the main object
• a variable is defined more than once
• a class member is overloaded (forbidden in Tool)
• a method is overloaded (forbidden in Tool)
• a method argument is shadowed by a local variable declaration (forbidden in Java, and we follow this convention)
• two method arguments have the same name
• a class name is used as a symbol (as parent class or type, for instance) but is not declared
• an identifier is used as a variable but not is declared
• the inheritance graph has a cycle (eg. “class A extends B {} class B extends A {}”)
• (Note that we don't check that method calls correspond to methods defined in the proper class. We will need type-checking for this.)

Additionally, we want to you to emit a warning to the user when a declared variable is never accessed (read or written). This should really be a warning, not an error (ie. it should not prevent the compiler from proceeding to execute).

In order to attach symbols to trees, we define a new trait, Symbolic, and a new set of classes for the symbols. The Symbolic trait is parametrized by a class name which allows us to define the kind of symbols which can be attached to each kind of AST node (see Symbols.scala and Trees.scala later for examples).

You need to write your analyzer such that two nodes referencing the same symbol have the same symbol class instance attached to them (that is, reference equality, structural equality is not enough). We defined the Symbol class such that symbols automatically get a unique identifier attached to them at creation. This will allow you to check that you are attaching symbols correctly: you will add an option to your pretty-printer to be able to print these unique numbers along with the identifiers where they occur.

Note that Symbols are also Positional objects, which means you have to set them a correct position (you should do this by recovering the position from the correct parts of the trees). This is necessary to produce meaningful error messages such as “error: class Cl is defined twice. First definition here: …”.

When your compiler encounters an internal error (for example, a scope is not initialized as you expected, a symbol is null, etc.), you should not use the methods from the reporter trait. This will be counted as a mistake. You must use scala.Predef.error instead, which will throw an exception and show you the stack trace. The reason is that you shouldn't blame the user for internal errors. In fact, the user should never encounter an internal error. Of course, writing bug-free programs is hard…

We will take advantage of the fact that scopes in Tool are only of three kinds:

1. the global scope (the set of declared classes)
2. the class scopes (all members and methods within a class, plus the global scope)
3. the method scopes (the parameters and local variables, plus the corresponding class scope)

This in fact defines a hierarchy among symbols:

• all class symbols are defined in the global scope
• all methods are defined in a class scope
• variables are defined either in a method scope, as arguments or locals, or in a class scope

We encoded this hierarchy in the symbol classes. Therefore, if we have access to a class symbol, for instance, and all symbols were correctly set, we can access from there all method symbols and member variable symbols. This will allow us to easily check if a variable was declared, for instance.

Here is how we recommend you proceed for the implementation:

1. First, collect all symbols: create the symbol class instances, make sure all their fields are correctly set, and attach them to the nodes of the AST where the symbols are defined.
2. Make the appropriate changes to your pretty-printer and make sure you see the unique IDs next to the identifiers at the definition points.
3. Implement the second phase of your analyzer which consists in attaching the proper symbol to the occurrences of the identifiers. To simplify your task, start by writing lookup methods in the symbol classes: they will allow you to easily check whether an identifier was declared and to recover its symbol if it was. Make sure you properly encode the scope rules (including shadowing) in your lookup methods.
4. Use your pretty-printer to make sure you did things correctly.
5. Make sure that you throw errors and warnings when appropriate.

When analyzing the following file:

object Example {
  def main() : Unit = {
    println(new B().foo());
  }
}
 
class B extends A {
  def foo() : Int = {
    value = 42;
    return value;
  }
}
 
class A {
  var value : Int;
  def foo() : Int = {
    var value : Bool;
    value = false;
    return 41;
  }
}

The analyzer should output something like:

object Example#0 {
  def main() : Unit = {
    println(new B#1().foo#??());
  }
}
 
class B#1 extends A#2 {
  def foo#6() : Int = {
    value#3 = 42;
    return value#3;
  }
}
 
class A#2 {
  var value#3 : Int;
  def foo#4() : Int = {
    var value#5 : Bool;
    value#5 = false;
    return 41;
  }
}

Note that:

• Overriding methods have a different symbol than their overridden counterparts.
• Method names in method calls are unresolved symbols.

Here are all the constraints that your analyzer should enforce:¹⁾

• No two variables can have the same name in the same scope, unless one of the two cases of shadowing occurs.
• All variables used must be declared.

Shadowing can occur in two different situations:

1. a local variable in a method can shadow a class member
2. a method parameter can shadow a class member

All other types of shadowing are not allowed in Tool.

• Classes must be defined only once.
• When a class is declared as extending another one, the other class must be declared and cannot be the main object.
• The transitive closure of the “extends” relation must be irreflexive (no cycles in the inheritance graph).
• When a class name is used as a type, the class must be declared. The main object cannot be used as a type.

• Overloading is not permitted:
  • In a given class, no two methods can have the same name.
  • In a given class, no method can have the same name as another method defined in a super class, unless overriding applies.

• A method in a given class overrides another one in a super class if they have the same name and the same number of arguments.²⁾
• Fields can not be overridden.

As usual, here are some files to get you started:

• Symbols.scala contains the definition of symbols, GlobalScope and the Symbolic trait. You only have to write the body of the lookup methods.
• Analyzer.scala contains a stub for the analyzer.
• Trees.scala shows how you can adapt your Trees.scala file to attach symbols to the nodes. You should work on your own version of the file.
• TreePrinter.scala contains code to help you adapt your pretty-printer.
• Compiler.scala contains code to run the analyzer after the parser, and to print out a tree with symbols. You don't have to change anything in this file, and you can also keep Main.scala from the previous labs.

src
 └── toolc
      ├── Compiler.scala        (given this week)
      ├── Main.scala            (given in Lab 03)
      ├── Positional.scala      (given in Lab 03)
      ├── Reporter.scala        (given in Lab 03)
      ├── TreePrinter.scala     (adapt your work from Lab 04 to the new stub)
      │
      ├── analyzer
      │    ├── Analyzer.scala   (stub given this week)
      │    └── Symbols.scala    (stub given this week)
      │
      ├── lexer
      │    ├── Lexer.scala      (completed in Lab 03)
      │    └── Tokens.scala     (completed in Lab 03)
      │
      └── parser
           ├── Parser.scala     (completed in Lab 04)
           └── Trees.scala      (adapt your work from Lab 04 to the new stub)

You can use the reference compiler to check your results: if you use the option

--check-symbols

the reference compiler will accept identifiers with a unique ID appended (eg: i#12). It will then check that the numbers match for different occurrences of identifiers. Try for instance to run the reference compiler on the example output above, then change some of the ids and try again. Note that with the –check-symbols option, it still accepts unannotated identifiers, as well as identifiers annotated as i#?? for instance.

Submit a .zip file of your src directory through Moodle before Tuesday, Nov. 9th, 11.55pm (23h55). Make sure your compiler throws errors and terminates using the methods in the Reporter trait when it encounters problems.