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
The Symbol Table
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.
The different tree modules
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
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
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
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
SymbolicTreeModule.X. I.e. we need to transform a
NominalTreeModule.Program to 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
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 Nilthey 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
- 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
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