4 ms·
I don't understand what he is talking about. A very simple one-pass recursive regex matcher is trivial to write. I wrote the one for asterisk in 2003. No fancy
by rurban 9y ago
I don't understand what he is talking about.
A very simple one-pass recursive regex matcher is trivial to write. I wrote the one for asterisk in 2003. No fancy CPS needed.
http://asteriskguru.com/archives/asterisk-dev-better-pattern-matcher-vt42988.html http://asteriskguru.com/archives/asterisk-dev-better-pattern...
- jabot 9y agoIt seems that "fancy CPS" is exactly what he is talking about. A simple regex matcher makes for a good example IMHO.
- tinkersleep 9y agoHmm, I have yet to see a trivial implementation for full-featured regex syntax, which was my goal. The idea was not to parse a simple dialect of regex, but to parse a full-featured dialect, including things like \d, \), [)] and multi-level (), like (a|(b|c\)d[e)f])*g|h)+, so, e.g., the simple approach of scanning for the closing ) when you find a ( does not really work. Just for parsing such regexs this requires a recursive scanner, and then, a recursive data structure to store the result of parsing the regexp, and this runs counter to matching at the same time. The linked code you provide assumes that you can first parse the whole pattern (like '(...)'), interpret that pattern, and then recurse to match it. There do not seem to be test cases in your code for the complex regexs cited above. So I don't think the approach of trivial recursion works with a full-featured standard regex grammar.
- rurban 9y agoI see, thanks. But practically such an parser explodes, and should not really be used. A simple one is still linear, and much faster than the current regcomp/regexec overkill.
- kmill 9y agoIf I am reading your code correctly, I don't see full backtracking search. The CPS version should implement this (though I find their particular CPS style rather difficult to skim, so I'm not confident without running it).