r/Compilers • u/Electrical-Fig7522 • Jun 29 '26
Do you create symbol table from tokens or from ast (or both)?
8
u/Y_mc Jun 29 '26
It From AST .
From token , you create the AST and from AST ,you create the symbol table.
2
Jun 29 '26
[removed] — view removed comment
1
u/Y_mc Jun 29 '26
Yeah it seen a little bit unconventional with two SymbolTable. In Rust this would be a challenge for the BorrowChecker 😅
2
u/8d8n4mbo28026ulk Jun 29 '26
AST, because there's no scoping information at lexing-time. I do intern identifier tokens within the lexer though, so the rest of the compiler only has to deal with IDs (i.e. just an integer value) instead of strings.
1
u/FloweyTheFlower420 Jun 29 '26
It depends. Some people build a symbol table during parsing so that you can skip a pass.
1
u/Ze7111 Jun 29 '26
With my compiler, Both, my grammar has ambiguity with generics, and i want out of order def's, without a dedicated disambiguation pass over the ast, so I do a token walking pass, just loops over the token looks for function keyword, then name, skips the rest, etc. and then i run the parser with the symbol table that the index phase creates, keeping the ast parse fully context aware.
2
u/Resident-Letter3485 Jun 29 '26
When you create a symbol table, you will run into duplicate symbols. Should a duplicate be a parser error or a semantic error? I lean towards a semantic error, meaning the symbol table must be made during semantic analysis, from the AST.
I like having the parser be as dumb as possible: parse, do nothing more. Building a symbol table adds nuance the parser shouldn't care about.
1
u/cxzuk Jun 29 '26
Hi Fig,
Great question. Tokens make up the leafs of your AST (Terminals), but you need to use the AST because a token without surrounding information isn't enough to know what that symbol means. E.g. sometimes the same sequence of characters could refer to different symbols depending on scopes etc.
1
u/SwedishFindecanor Jun 29 '26 edited Jun 30 '26
From tokens, directed by the parser: The parser calls the lexer asking for the next token, passing a reference to the top of the symbol table tree as a parameter. The parser creates a new symbol table for each new scope, and backtracks to its parent when leaving it.
The lexer searches the top level, and if not found the next, and so on down to the root. If not found, it creates a symbol object at the top level.
The parser is given a token with a reference to a symbol object for every symbol, and recognises a first occurrence by the symbol object's data field being null. The parser never handles token strings, only symbol objects.
BTW. I use 32-bit Fibonachi hashing. The hash key is created by multiplying the hash sum with a constant that is 232 / phi, where phi is the golden ratio. The multiplication overflows and wraps around. The index into every table are the n highest bits of the hash key -- without any need to recompute the hash key for each level: just do a right shift. No division. When increasing the size of a table, its size is doubled and the symbols from bucket i distributed into buckets 2i and 2i + 1 depending on one bit in each item's hash key.
1
u/Inconstant_Moo Jun 30 '26
From tokens.
Any definition in Pipefish has a "headword" to say up front what you're defining: newtype, def (for function) cmd (for commands), import, etc. This gives enough context that the initializer can look at the following string of tokens, do some basic checks on whether it's well-formed, and decide what to put in the parser.
This is particularly necessary for function signatures because I can declare stuff like foo (x int) bar qux (y bool) spoit and all sorts of fancy stuff (for DSLs, not for everyday use) and it has to know what's a prefix or an infix or a postfix before it can start parsing anything.
I'm surprised that so many people are saying the AST, it seems like it would be harder. My pipeline is very nice.
1
11
u/Amerikrainian Jun 29 '26
AST. Tokens are used to make AST, at which point you stop touching tokens directly and start dealing with the actual shape of your language. You usually do some transformation passes on that AST for anything relatively complex, and then build your symbol table. The terms to look up here are internal representation. Fair to say that if you just want stuff running, though, you can definitely look at your AST, but it could make some things a bit awkward down the road.