12
$\begingroup$

Let's say I've parsed a file of code into an AST, and now I want to walk the AST and type check it. My AST nodes have a signature like this (C++)

class ASTNode { 
    ...
    virtual void type_check(Scope &scope) = 0;

The Scope contains the mapping of names to info about variables, other functions, types, etc. Some ASTNode subtypes create nested Scopes or add names and info to existing Scopes.

Now my problem is that names in the target language can be used before they are declared or defined. For example, I can have code like this in my target language:

fun foo(i: Int, t: Thing) { 
    t.doStuff(i, "blah")
}
class Thing {
    fun doStuff(x: Int, s: String) { 
        bar(x)
        ...
    }
    ...
}
fun bar(num: Int) { ... }

So if I'm type checking the AST node for foo, I haven't seen Thing yet, and there is nothing in the Scope about it. Same with the uses of t.doStuff, and bar.

My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the Scopes. I'm not sure what to call this pass.

class ASTNode {
    virtual void gather_names(Scope &scope) = 0;
    virtual void type_check(Scope &scope) = 0;
    ...
}

I may remove the scope arguments and have the scopes be properties of the AST nodes, but you get the idea.

Is there a better way to handle this? Is there a typical way that existing compilers handle out of order declarations and definitions? Languages like C and C++ obviously don't handle it, but other languages do (Java, Swift, etc).

One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.

$\endgroup$

3 Answers 3

20
$\begingroup$

This pass is traditionally called the name resolution phase, and it is very common, though not ubiquitous, as part of the semantic analysis stage of the process.

Typically it involves walking entire trees and collecting names that will be in scope according to the language's name resolution rules, and then one of:

  • Annotating the syntax tree with pointers to the declaration of each name attached to the use site;
  • Producing a replacement tree where all names are fully-qualified;
  • Or creating a "scope" value to pass along to other phases.

Which one of these is most suitable will depend on the specifics of the implementation; in a pure functional system, mutation is unsuitable, while in other systems mutable annotations may be helpful.

Formal descriptions are usually in terms of rewriting, but some interpreters do only build up a chain of scopes with mappings from names to metadata. Large-scale compilers and interpreters often have many phases of iterative rewrites from the source through several intermediate layers, each adding more information, and name resolution is often a fairly early one.

Languages with more complex name resolution rules may need multiple phases of this. For example, there may be a resolution pass that precedes some type checking, and another afterwards for inherited names. Part of the value of an AST is often in making these transformations easy to write and use.

$\endgroup$
4
  • $\begingroup$ Good answer especially that name resolution itself may require multiple passes (not necessarily consecutive) when names may be dynamically added to the scope. $\endgroup$
    – Erik Eidt
    Sep 11, 2023 at 23:50
  • 1
    $\begingroup$ An example of note for "interleaved" name resolution + type checking is when calling a method M on the result of an expression E. First the names in the expression E are resolved, then from that the type of the expression E is deduced from the type of its sub-components and the top-level operator/function/method, and then based on the type of the expression E the scope in which to look-up the method M is known and name resolution proceeds. It's even more involved when type inference is more complicated. $\endgroup$ Sep 12, 2023 at 9:34
  • $\begingroup$ I'd call it global name resolution in contrast to other name resolution phases that might be required and that may follow different rules because they may need to elaborate declaration cycles. $\endgroup$
    – feldentm
    Sep 13, 2023 at 15:38
  • $\begingroup$ Is there a difference between name resolution and scope resolution? AFAIK scope resolution attaches scopes to names, and name resolution attaches defs to uses: they are almost the same, and name resolution requires scope resolution; but scope resolution doesn't look for defs, so it can skip names with explicit or obvious scopes. $\endgroup$
    – tarzh
    Sep 13, 2023 at 15:59
7
$\begingroup$

For languages which allow forward references to names which are not yet declared, I think it helps to split name resolution up into two separate parts:

  • Identify all the declarations which give meanings to names,
  • Identify, for each occurrence of a name, which declaration it refers to.

I don't know if these two things have proper names, so I'll call them name-finding and name-binding respectively.

When the language allows forward references, name-finding and name-binding must occur in separate passes, because a single pass can find some names which are not yet bound.

On the other hand, name-binding and type-checking often cannot occur in entirely separate passes, because in an expression like foo.bar(), the method bound to the name bar depends on the type of the variable bound to the name foo ─ that is, the compiler must bind the name foo, check its type, and then bind the name bar.

So yes, generally you do need two separate passes for name resolution and type-checking, but it's like this:

  1. Name-finding,
  2. Name-binding and type-checking (together).
$\endgroup$
6
$\begingroup$

My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the Scopes. I'm not sure what to call this pass.

I'd call it identifier binding, namely of (usages of) identifiers to their definitions, as within scope.  Logic systems have a notion of free (i.e. global) and bound (i.e. local) variables.

One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.

Yes, that's like doing a one pass assembler, which resolves forward label references from a list collected during a single pass.  Certainly can be made to work.

However, why bother?  You can't really do everything you want for type checking with unresolved identifiers.  Might as well have a separate identifier binding pass.  And only then move on to do type checking.

Also, you'll know for sure if you have 0, or > 0 unresolved identifiers and maybe limit error messages as a result during type checking / later passes.

While the list approach can certainly be made to work, I think the multi-pass approach might be less error prone as well as easier to code — you'll never have to deal with partially resolved expressions (or re-resolve expressions) except when there really are unresolved identifiers.


FYI, C# is a "two pass compiler" ;) as seen in these articles:

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .