# Token Scanner for programming Language(Lexical Analysis)

This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.

The Question is : Do i have to convert the entire given DFA to an ε-NFA(which will result in more states),add the keywords(with ε transitions too)and then convert back to a DFA or i just have to add the keywords so that the DFA becomes an NFA and then convert back to a DFA

• You can do whatever you want, as long as the resulting automaton behaves correctly. Dec 16 '18 at 19:59

There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's necessary to do so, and it's not because it's efficient to do so.

Thompson's construction has the following advantages:

• It's recursive on the structure of the regular expression.
• It's easy to convince yourself that the construction is correct.
• It's straightforward to incorporate certain extensions (e.g. the LEX lookahead operator "/").

Real-world implementations of regular expressions, even if they are based on Thompson's construction, typically optimise a dozen or so common base cases (e.g. Kleene closure of a character set; [a-zA-Z0-9_]* expands to something much bigger than it needs to be), saving Thompson's rules for higher levels.

• Another advantage is that every state has at most two out-transitions, and if it has two they are both epsilons. Given the memory constraints Thompson had to work within, this was a big help.
– rici
Dec 17 '18 at 1:44