Creating a Symbol Table w/o self-references

Hi all,

I’ve been working on a small compiler for the Compilers course at uni, using Rust c:

I’ve had no major stumbling blocks before what I’m making now, which is the Semantic Analysis step. I have the following problem: I need to make a Symbol Table to hold my function declarations. In particular, they should hold their name and arity at least. The Symbol Tables for every Scope should then be appended to every AST node that belongs to that Scope.

My problem arises with that: apparently, the usual way a Symbol Table is used is with references to the AST nodes. But that would instantiate reference cycles in the AST itself! I can’t (and don’t want to) do that in Rust. So I’m now working to just storing strings in the Symbol Tables. I’m sure I can make that work regardless.
But if anyone knows a more rustic, idiomatic way (hopefully using types instead of strings) to use Symbol Tables, I’d be very grateful if you could explain it to me :blush:

Thank you, and have a good week!

What I often see is instead of directly referencing an AST/IR node and having the cyclic references issue, you’ll use IDs.

If you look at the rustc::hir::Crate definition you’ll see it’s essentially a bunch of hashmaps mapping from HirId to item type (Item, TraitItem, etc). Internally these items will reference other items using their IDs, and so on.

You may also find The Rustc Guide and rustc's source code useful.

3 Likes

Jesus, that book is great! Such good documentation, I’ve never seen something like it for a compiler project of its scale :open_mouth:

That is exactly what I needed. I think I can solve this now. Thank you! :sparkling_heart:

2 Likes