以编程方式找到正则表达式的字符串? [英] Find string to regular expression programmatically?

问题描述

给定正则表达式，是否可以找到以编程方式匹配该表达式的字符串?如果是这样，请在假定存在字符串的情况下提及一种算法.

Given a regular expression, is is possible to find a string that matches that expression programmatically? If so, please mention an algorithm for that, assuming that a string exists.

奖金问题:如果可以，请给出该算法的性能/复杂性.

Bonus question: Give the performance/complexity of that algorithm, if able.

PS:请注意，我并不是在问这个问题:以编程方式派生常规字符串中的表达式.我更有可能问储备金问题.

PS: Note I am not asking this: Programmatically derive a regular expression from a string. More likely I am asking the reserve problem.

推荐答案

假设您定义这样的正则表达式:

Assume you define regular expressions like this:

R :=
   <literal string>
   (RR)    -- concatenation
   (R*)    -- kleene star
   (R|R)   -- choice

然后，您可以定义一个递归函数S(r)来找到匹配的字符串:

Then you can define a recursive function S(r) which finds a matching string:

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

例如:S(a*(b|c)) = S(a*) + S(b|c) = "" + S(b) = "" + "b" = "b".

如果您有一个更复杂的正则表达式概念，则可以根据基本原语重写它，然后应用上面的内容.例如，R+ = RR*和[abc] = (a|b|c).

If you have a more complex notion of regular expression, you can rewrite it in terms of the basic primitives and then apply the above. For example, R+ = RR* and [abc] = (a|b|c).

请注意，如果您具有已解析的正则表达式(因此您知道它的语法树)，那么上述算法最多只会占用正则表达式大小的线性(假设您谨慎执行字符串连接)高效地).

Note that if you've got a parsed regular expression (so you know its syntax tree), then the above algorithm takes at most time linear in the size of the regular expression (assuming you're careful to perform the string concatenations efficiently).

这篇关于以编程方式找到正则表达式的字符串?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！