Faster way to read a keyword list

Question

I'm writing a simple lexer for a general purpose programming language and one of the token types is a 'keyword' that has some predefined control flow tokens such as 'if', 'else', 'while', 'return'.

I want to know the fastest way to check if some keyword is inside my list using x86 Standard C.

My idea was to use a jump table but C string comparisons is problematic since C strings are arrays of char type.

Answer 1

The fastest way is to hand-build a trie, or equivalently a state machine. Flex (or any other lex variant) would do that for you.

Answer 2

Theoretically a hash table provides lookup of O(1). However, I would implement a static look up table. Assuming the number of tokens you are searching for is small. A linear search of the table shouldn’t prove too costly.