Homework Assignments Week 1.5: Name Resolution (Answers)

Name Resolution with Scope Graphs

The main aspects are:

• The name binding structure of a program is represented as a graph of scopes, references, and declarations.
• Resolving a reference is finding a path in the graph from the reference to a matching declaration.
• The paths used for resolution must be well-formed, which means the labels must match a given well-formedness regular expression.
• Disambiguation defines which declarations are visible if multiple matching declarations can be reached. Disambiguation is specified using an ordering on path labels.

Resolving in Scope Graphs

1. The resolution of f₈ involves an import of A₇. This import has two reachable declarations:

   • A₇ · R · #2 · P · #0 · D · A₂
   • A₇ · R · #2 · D · A₄

   According to the label order Ord, the path to A₄ shadows the path to A₂. Therefore, reference A₇ resolves to A₄.

   Given that, there is one reachable declaration for F₈, which is:

   • f₈ · R · #4 · I · #3 · D · f₆

   Because there is only a single resolution path, the reference is resolved to declaration f₆.

2. The import A₅ has one reachable declaration, which is:

   • A₅ · R · #0 · D · A₁

   Since there is only a single path, A₅ resolves to A₁.

   The import B₇ has one reachable declaration, which is:

   • B₇ · R · #3 · P · #0 · D · B₄

   Since there is only a single path, B₇ resolves to B₄.

   Finally, the reference has two resolution paths, which are:

   • f₈ · R · #3 · P · #0 · D · f₉
   • f₈ · R · #3 · I · #2 · I · #1 · D · f₃

   According to the label order Ord, the path via the imports takes precedence over the path via the lexical parent. Therefore, f₈ resolves to f₃.

Constructing Scope Graphs

1. The corresponding scope graph is given by:

   

2. The corresponding scope graph is given by: