regex - Find string to regular expression programmatically? -

given regular expression, is possible find string matches expression programmatically? if so, please mention algorithm that, assuming string exists.

bonus question: give performance/complexity of algorithm, if able.

---

ps: note not asking this: programmatically derive regular expression string. more asking reserve problem.

assume define regular expressions this:

r :=    <literal string>    (rr)    -- concatenation    (r*)    -- kleene star    (r|r)   -- choice 

then can define recursive function s(r) finds matching string:

s(<literal string>) = <literal string> s(rs) = s(r) + s(s) s(r*) = "" s(r|s) = s(r) 

for example: s(a*(b|c)) = s(a*) + s(b|c) = "" + s(b) = "" + "b" = "b".

if have more complex notion of regular expression, can rewrite in terms of basic primitives , apply above. example, r+ = rr* , [abc] = (a|b|c).

note if you've got parsed regular expression (so know syntax tree), above algorithm takes @ time linear in size of regular expression (assuming you're careful perform string concatenations efficiently).