4 ms·
As to why using RE derivatives might be interesting, this if from Owens, Reppy and Turon's, "Regular-expression derivatives re-examined", which is cited in the
by todd8 11y ago
As to why using RE derivatives might be interesting, this if from Owens, Reppy and Turon's, "Regular-expression derivatives re-examined", which is cited in the originally referenced web site:
Specifically, RE derivatives have the following advantages:
• They provide a direct RE to DFA translation that is well
suited to implementation in functional languages.
• They support extended REs almost for free.
• The generated scanners are often optimal in the number of
states and are uniformly better than those produced by
previous tools.
- wolfgke 11y agoUnluckily there are regular languages where you can prove that the number of required states of a DFA is exponential in the input length of the regular expression describing it. That's why one should use NFAs for parsing REs, see https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html For an example of such a regular expression, consider [ab]*a[ab][ab]...[ab][ab] where the number of [ab] at the end is n-1. Then any DFA for this regular expression needs at least 2^n states, while there exists an NFA using only n+1 states (the proof is an easy exercise that any Computer Science student should easily be able to do on a whiteboard ;-) ).