Implement Keyword Recognition Using Hash Table

Fast Keyword Lookup

With dozens of reserved words, linear search over a keyword list is too slow for production lexers. GCC and Clang use hash tables or perfect hashing. A simple chained hash table keyed on the spelling gives O(1) average lookup and is what you will build here.

Hash Table Design

Insert each keyword at compile time (or lexer init) with its token type. At scan time, after reading an identifier spelling, hash the string, probe the bucket, and compare with strcmp. On match, return the keyword token; on miss, return an identifier.

cCopy
Loading…

• Hash function: djb2, FNV-1a, or simple polynomial rolling hash
• Collision resolution: chaining with linked lists or open addressing
• Pre-load the table with all language keywords at init time
• Only identifiers need table lookup; literals and operators skip it

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement a hash table that maps keyword spellings to TokenType values. This exercise requires inserting reserved words, handling collisions, and integrating lookup into your identifier scanner so keywords are recognized in constant time.