0
$\begingroup$

enter image description here 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

$\endgroup$
2
  • 1
    $\begingroup$ You can do whatever you want, as long as the resulting automaton behaves correctly. $\endgroup$ Dec 16, 2018 at 19:59
  • $\begingroup$ No need for any $\epsilon$. From the relevant states taken as roots, you can enter a tree-like automaton (in fact a trie) that recognizes the keywords. en.wikipedia.org/wiki/Trie $\endgroup$
    – user16034
    Jan 25, 2023 at 19:56

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – rici
    Dec 17, 2018 at 1:44
  • $\begingroup$ Out of curiosity, how do you incorporate the LEX "/" operator? $\endgroup$
    – Chaos
    Jul 30, 2023 at 21:40
  • $\begingroup$ The "/" operator is basically a different kind of end state that you backtrack back to. A full treatment would require understanding the exact semantics of that operator, which I don't remember. $\endgroup$
    – Pseudonym
    Jul 30, 2023 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.