Reputation: 3289
I have came across many times that, text-based regex engines cannot support lazy quantifiers. But I could not find why. But I came to know that, they internally use DFAs, and they do not backtrack.
Then I sat down to draw a DFA for lazy quantifiers and this is what I got.
\/\*.*\*\/
(where * is lazy)(matches C comments correctly):
(regex form of below DFA to make sure it is behaving as expected)
For comparison, I also wrote the greedy quantifier version.
\/\*.*\*\/
(where * is greedy)(matches C comments incorrectly):
(regex form of below DFA to make sure it is behaving as expected)
Sorry, I forgot to add start state in the diagram. Consider left-most state as start in both of them.
Here, greedy version actually requires backing-up! Also, lazy quantifiers can be done with DFA. Did I did anything wrong? Why are there many saying text-based regex engines don't support lazy?
PS: To keep it simple, I did not complete both of the above DFAs. To complete them, just add all the non-existent moves from every state to a new error state. Once entered error state, no exiting from it.
Upvotes: 2
Views: 100