I'm writing a compiler in Rust. I've reached the point where I have an AST and am ready to do symbol resolution, type-checking, etc. But, I'm unsure of how to represent an AST as containing "unresolved" symbols and "resolved" symbols.


To achieve separation of concerns, I'm first passing over the AST to resolve all symbols (variable names, type definitions, function names, etc.). This is essentially what I'm thinking:

AST<MaybeResolvedSymbol> --> resolve(...) --> AST<ResolvedSymbol>

As I move through the unresolved tree, I'll build a new one, piece by piece.

For context, here are simplified definitions of types and symbols:

enum MaybeResolvedType {
    Lookup(String), // Unresolved state
    Resolved(Type), // Resolved state

For simplicity purposes, imagine Type as an enum which can either be an extrinsic or intrinsic type.

Then, a Symbol is either resolved or unresolved based on the status of its type, e.g.,

type ResolvedSymbol = Symbol<Type>;
type MaybeResolvedSymbol = Symbol<MaybeResolvedType>;

The Problem

  • It doesn't feel right, because theoretically any type could be used as a symbol. For example, e.g. AST<usize>, which doesn't make sense. To remedy this, I could just implement a trait on the generic to restrict it, which feels almost like a bandaid.

  • Having a generic type on the AST means I have to implement that generic across every single one of my AST nodes. Not a huge problem, but definitely hurts readability.

  • This will require a lot of space during the resolution step because I'll have to build an identical tree with the exception of the symbol types.

When I go to type check the tree, I want the AST to be guaranteed to contain resolved symbols. If there were any symbols that couldn't be resolved, it would be caught in the resolution step as an error in the program.

I'd love to get some thoughts on this. Is this just something I'll need to deal with, or is there a better way of going about this?

  • "As I move through the unresolved tree, I'll build a new one, piece by piece." — Ok, then why the need for maybe resolved? Should go right from unresolved to resolved (or unresolvable/error), no?
    – Erik Eidt
    Commented Aug 31, 2023 at 23:58
  • @ErikEidt because intrinsic types can be resolved immediately without the need to query a symbol table. I added that level of indirection so all AST nodes can have that same type before symbol/type resolution
    – gmdev
    Commented Sep 1, 2023 at 0:15
  • Ok, but why is that useful/necessary? You're creating a whole new AST anyway..
    – Erik Eidt
    Commented Sep 1, 2023 at 1:00
  • @ErikEidt right, but I don't want to make a duplicate definition of each AST node just to change the type of the symbol. My question was largely in regards to architecture with generics.
    – gmdev
    Commented Sep 1, 2023 at 2:32
  • 1
    Sometimes, there isn't a very elegant solution. Here, you have the choice between creating different AST variants with macros, with generic parameters, or just having a single AST that might contain unresolved references. All of these suck to some degree, and the choice is up to personal preferences. I wrote up some thoughts regarding generic ASTs. In a recent project I wrote multiple AST enums by hand, but they differed in much more than just unresolved references. In your scenario, I'd probably sacrifice typesafety and use a single AST.
    – amon
    Commented Sep 2, 2023 at 16:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.