3 ms·
groupings and alternation can't be implemented in such a simplistic regex engine that matches the target while parsing the regex. Here is a more sophisticated
by gregwebs 18y ago
groupings and alternation can't be implemented in such a simplistic regex engine that matches the target while parsing the regex. Here is a more sophisticated toy haskell engine that uses a real parsing library http://jcreigh.blogspot.com/2006/12/simple-regex-engine-in-haskell.html http://jcreigh.blogspot.com/2006/12/simple-regex-engine-in-h...
- 13ren 18y agoThat's very interesting, because I've always felt that it should be possible to parse the regex and match the target at the same time... (though nobody ever does it that way, instead doing it with 2 passes). Do you know of a proof that grouping and alternation cannot be implemented in this way? (formal or informal).
- gregwebs 18y agoIt is possible with the addition of back tracking capabilities (the most crude of which would be to just be able to look backwards in the regex). But at that point the implementation will be complex and the implementers should wonder why they did not implement a compile phase for the regex string. A compile phase also gives a chance for optimizations of the regex.