Why does lexer has O(n) time complexity?

Question

According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a language. (there are some other reasons, e.g. to find the 'longest matching pattern' to distinguish between if a(keyword) and ifa(identifier))

Then, the lexer repeats this process until the input string ends, producing N tokens as a result. So I ended up with the conclusion that lexer has $\mathcal O(n^2)$ time complexity. But every resource and book says lexer takes linear time because the DFA has linear time complexity. What I am missing?

*Edit: What was wrong is that I assumed the lexer uses multiple DFAs for each token. In reality, the lexer forms a single DFA to represent all token types in a given regular language, and it can identify token types with it's final states. Thus it takes $\mathcal O(n)$.

Answer 1

Your assumption of execution is based on a suboptimal backtracking implementation based on NFA needing to explore all paths through it.

A more optimal implementation would have a bitset of all states the NFA is in simultaneously. This lets you represent all $2^n$ states without explicitly listing them all.

For a lexer doing tokenization you might not be doing keyword recognition yet and instead leave that to a next parser step that checks whether a potential keyword is an actual keyword. This makes the lexer DFA much smaller.

If however you need to differentiate between keywords and identifiers then you would put the final state after seeing the first character that cannot be part of a identifier. In most programming languages once you know you are in a identifier it lasts until the first non-alphabetic character, so there is no point in backtracking.

The lexer DFA doesn't have a final state per se (other than actual EOF) but instead a output transition that would emit a token to the output. When after the f of a if the next non-identifier character would make it emit a IF token, if instead the character possible as part of an identifier it would transition into a general IDENTIFIER state looping back into itself until it sees a non-identifier character.

Answer 2

If you wrote a lexer for C++ and the next character is an “a” then the token is asm, auto or an identifier. Three choices only. Processing an identifier with a length k should take no more than O(k).

A reasonable n would be the number of characters or code points in the input. Sure, with a million characters you could have 1000 identifiers of 1000 characters each. But you would have n = 1,000,000 and the time a smallish multiple of n, say 100 million nanoseconds.

And you don’t need the longest matching pattern to distinguish between if and ifa: Just three characters.