LARA

This week, you will implement name analysis for Amy. Name analysis has three goals:

• To reject programs that do not follow the Amy naming rules.
• For correct programs, to assign a unique identifier to every name. Remember that trees coming out of the parser contain plain strings wherever a name is expected. This might lead to confusion as to what each name refers to. Therefore, during name analysis, we assign a unique identifier to each name at its definition. Later in the program, every reference to that name will use the same unique identifier.
• To populate the symbol table. The symbol table contains a mapping from identifiers to all information that you could need later in the program for that identifier. For example, for each constructor, the symbol table contains an entry with the argument types, parent, and an index for this constructor.

After name analysis, only name-correct programs should survive, and they should contain unique identifiers that correspond to the correct symbol in the program.

You can always find out what the correct behavior of your compiler is by invoking the reference compiler with the --printNames option.

The symbol table contains information for all kinds of entities in the program. You should populate it as you discover new symbols, as you will need the information contained there later.

The symbol table contains 3 kinds of methods:

• 'addX' methods will add a new object to the symbol table. They do a lot of work for you (e.g. creating fresh identifiers), so make sure to understand them properly.
• 'getX' methods which take an Identifier as argument. This is what you will be using to resolve symbols you find in the program from the next assignment moving forward, and if possible for this assignment as well.
• 'getX' methods which take two strings as arguments. These are only useful for name analysis and should not be used later: since during name analysis you have not assigned unique identifiers to everything from the start, sometimes you will need to look up something based on its own name and the name of its containing module. Of course you should not use these methods once you already have an identifier.

It is time to talk in detail about the different tree modules in the TreeModule file. As explained earlier, our goal is to define two very similar tree modules, with the only difference being how a (qualified) name is represented: In a nominal tree, i.e. one coming out of the parser, names are plain strings and qualified names are pairs of strings. On the other hand, in a symbolic tree, both kinds of names are unique identifiers.

To represent either kind of tree, we define a single Scala trait called TreeModule which defines two abstract type fields Name and QualifiedName. This trait also defines all types we need to represent Amy ASTs. Many of these types depend on the abstract types.

These abstract types are filled in when we instantiate the trait. Further down in the same file you can see that we define two objects NominalTreeModule and SymbolicTreeModule, which instantiate the abstract types. In addition all types within TreeModule are conceptually defined separately in each of the two implementations. As a result, there is a type called NominalTreeModule.Ite which is different from the type called SymbolicTreeModule.Ite.

The NameAnalyzer class is the focus of this assignment. Your task is to complete all missing implementations. Make sure to carefully look at the code already given first.

Name analysis is split into well-defined steps for you. The idea is the following: we first discover all definitions in the program in the correct order, i.e., modules, types, constructors, and, finally, functions. We then dive into function bodies and expressions.

Notice how name analysis takes as input the NominalTreeModule.Program output by the Parser, and returns a SymbolicTreeModule.Program along with a populated symbol table. During the last step we therefore also need to transform the program and each of its subtrees from NominalTreeModule.X into SymbolicTreeModule.X. For instance, a NominalTreeModule.Program will be transformed into a SymbolicTreeModule.Program, a NominalTreeModule.Ite into a SymbolicTreeModule.Ite and so forth. Notice that to save some typing, we have imported NominalTreeModule as N and SymbolicTreeModule as S. So to refer e.g. to a Plus in the original tree module you have to type N.Plus – to refer to one in the symbolic tree module you can use S.Plus.

Please remember to set the positions for the new trees. It will be important for your compiler to emit meaningful errors so you can debug it. This is already done for you in some cases.

Your compiler can emit a warning in the following cases:

• An identifier pattern is used which has the same name with a nullary constructor. E.g. if a user writes case Nil they probably meant case Nil(): In the first case, it is a pattern which matches against any value and binds it to the name Nil, which is probably not what we want if we have the constructor Nil() in scope.
• A local variable shadows (has the same name as) a function parameter.

As usual, you can find the skeleton on Courseware. This lab builds on your previous work, so assuming you already implemented the parser you will only unpack several files from the skeleton.

The structure of your project src directory should be as follows:

amyc
 ├── Main.scala                (updated)
 │
 ├── analyzer                  (new)
 │    ├── SymbolTable.scala
 │    └── NameAnalyzer.scala
 │
 ├── ast
 │    ├── Identifier.scala
 │    ├── Printer.scala
 │    └── TreeModule.scala
 │
 ├── parsing
 │    ├── ASTConstructor.scala
 │    ├── ASTConstructorLL1.scala
 │    ├── Parser.scala)
 │    ├── Lexer.scala
 │    └── Tokens.scala
 │
 └── utils
      ├── AmycFatalError.scala
      ├── Context.scala
      ├── Document.scala
      ├── Pipeline.scala
      ├── Position.scala
      ├── Reporter.scala
      └── UniqueCounter.scala
      

You have 2 weeks to complete this assignment.

Deadline: Tuesday 13 November, 23:59

Please use the Courseware interface to submit your solution and get some preliminary feedback from our automated tests.