LARA

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

• 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 an 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. the 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 do that, we define a 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. Indeed, looking further in the file, you can see that we define two objects NominalTreeModule and SymbolicTreeModule, which instantiate the abstract types. Not only that, but all types within TreeModule are conceptually defined separately in each of the two implementations. I.e. there is a type called NominalTreeModule.Ite which is different from the type called SymbolicTreeModule.Ite. This is called a path-dependent type in Scala.

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.

The 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 (modules, then types, constructors, and functions) and then we 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 (and the populated symbol table). Therefore, during the last step, we also need transform the program and each of its subtrees from NominalTreeModule.X to SymbolicTreeModule.X. I.e. we need to transform a NominalTreeModule.Program to a SymbolicTreeModule.Program, a NominalTreeModule.Ite to a SymbolicTreeModule.Ite etc. 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 you have to type N.Plus and in the final tree 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 a function parameter.

Merge the stubs of the parser into your main branch by typing

git fetch –all

git merge origin/Lab04

(assuming that origin is the name of your remote repository).

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

amyc
 ├── Main.scala                (updated)
 │
 ├── analyzer   
 │    ├── SymbolTable.scala    (already there, time to use it now)
 │    └── NameAnalyzer.scala   (new)
 │
 ├── ast                         
 │    ├── Identifier.scala     (already there, time to use it now)
 │    ├── Printer.scala
 │    └── TreeModule.scala
 │
 ├── interpreter                     
 │    └── Interpreter.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        (slightly modified)
      └── UniqueCounter.scala
      

You have 3 weeks to complete this assignment.

Deadline: Tuesday 14 November, 23:59

IMPORTANT: Please remember to deliver the commit you want us to grade under https://larasrv13.epfl.ch/clp17/deliverables