Loading page…
Master the fundamental concepts of lexical analysis through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksWith 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.
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.
cLoading…
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.
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.
Replace linear keyword search with a chained hash table, and make its behaviour visible: for every lookup, report which bucket was probed and how many string comparisons it took.
cLoading…
h % 64.cLoading…
Hash the word, walk its bucket's chain from the head, and strcmp each entry until one matches or the chain ends. compares is the number of strcmp calls made: 0 for an empty bucket.
Whitespace-separated words (identifiers) on stdin, possibly over several lines.
First, one line describing the table after all 32 inserts:
cLoading…
U is the number of non-empty buckets and L the length of the longest chain. Then one line per input word:
cLoading…
Finally:
cLoading…
where C is the total number of strcmp calls across all lookups.
main is not a keyword but still costs one comparison: it hashes to bucket 42, which already holds struct.
Input:
cLoading…
Output:
cLoading…
Hidden tests look up words deep in collision chains (e.g. register, which shares bucket 10 with three other keywords), identifiers that land in occupied buckets, and repeated words.