资深导游：从不建议亲戚参加低价团 那是陷阱
百度 切切叮嘱两千多年来，修身、正己、立德一直是中国人做人处事、为官从政的根本出发点，也为长期关注党员干部为政之德的习近平所高度重视。Back when I was a grad student, I gave a guest lecture on regular expressions. I gave out a toy Java library that showed how to implement regular expression pattern-matching in Java using NFA-conversion and back-tracking search.
Related pages:
The library works by building the syntax for regular expressions out
of Java syntax.
A regular expression pattern r can be:
- A literal string:
"string" - A literal character:
'char' - A sequence of patterns:
s(r1,...,r2) - A choice of patterns:
or(r1,...,r2) - A zero-or-more repetition of a pattern:
rep(r)
(foo|bar|baz)*xoo
s(rep(or("foo","bar","baz")),"xoo")
The library works by converting each regular expression into an NFA on the fly. For whatever reason, I didn't implement it in a functional fashion, so you can't re-use a sub-expression in more than one regular expression. That is, the following breaks:
NFA foo = s("foo") ;
NFA pattern = s(foo,foo) ;
but
NFA pattern = s(s("foo"),s("foo")) ; // or s("foo","foo")
is just fine.
I don't code much in Java these days, but if I still did, I'd make it
purely functional, so that sub-expressions could be re-used.
The matching algorithm works by doing a straightforward graph search over a string. The complexity is exponential in theory, but very fast in practice.