Nondeterministic regular expressions library for Arc (don't miss the cartoon)(lisperati.com)
lisperati.com
Nondeterministic regular expressions library for Arc (don't miss the cartoon)
http://www.lisperati.com/arc/regex.html
4 comments
A bare-bones nondeterministic regular expression engine for Python in 14 lines http://paste.lisp.org/display/24849
That's cool- I'll have to study that code. But it does look like you need an explicit sequencing command. My version works within arbitrary code.
A bare-bones engine that interprets a regex
http://blog.thoughtfolder.com/2008-02-04-even-more-beautiful...
I don't know much Haskell (it's on my list), but am I right in thinking that code doesn't implement parenthetical grouping or alternation? eg:
(BTW: I didn't write the 14 line Python one, I'm just studying it).
(ab)*
a|b
(BTW: I didn't write the 14 line Python one, I'm just studying it).
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-h...
That'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).
Do you know of a proof that grouping and alternation cannot be implemented in this way? (formal or informal).
It 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.
"The only common languages that have this ability are arc and scheme, a close relative to arc."
Arc is common?
Arc is common?
:-) Well, compared to other languages with true continuations, like New Jersey SML.
For that matter, Ruby and C both have continuation support.
Ruby has continuations, but with significant limitations. Ruby continuations cannot roll back modified variables, from what I understand- I think my email example would fail in a ruby implementation.
As for C, I haven't seen any real continuation support- Just some partial simulations using longjmp.
As for C, I haven't seen any real continuation support- Just some partial simulations using longjmp.
fantastic work! many thanks