LC

Implement Keyword Recognition Using Hash Table

medium5/8

Identifier and Keyword Recognition Add Error Recovery: Skip Invalid Characters

Language

Compiler

2.0s Limit 256MB

Implementation

Implement keyword recognition using a hash table for O(1) lookup.

Requirements:

Create a hash function for strings (djb2 or sdbm algorithm)
Build a hash table with all C keywords (int, float, if, else, while, for, return, etc.)
Modify your lexer to use hash table lookup for identifiers
Return appropriate token type for keywords vs identifiers
Handle hash collisions (even with good hash functions)
Test with mixed identifiers and keywords

Why This Matters

GCC generates its keyword lookup with gperf, a perfect-hash generator, because a linear scan over dozens of keywords is measurable at the scale of compiling the Linux kernel. Building the hash-table version yourself shows why O(1) keyword dispatch matters and how tools like gperf earn their place in real build systems.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0