Sourav Kannantha B
Sourav Kannantha B

Reputation: 3289

Why text-based regex engines cannot handle lazy quantifiers?

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

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

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

Answers (0)

Related Questions