我有一个奇怪的问题，至少我从来没有遇到过。我有一个先决条件，即客户具有与标签关联的简单正则表达式。标签是他们所关心的。我想做的是创建一个与这些正则表达式匹配的所有可能数字的列表。当列表超出某个阈值时，我会有逻辑会警告我。
下面是一个正则表达式的例子：34.25.14.(227|228|229|230|243|244|245|246)
假设这些 ip(s) 与 ACME 相关联。在用户选择 ACME（在我们的 UI 中）的幕后，我正在填写一个包含所有可能数字的过滤器对象，并将它们作为 OR 查询提交到高度专业化的 Vertica 数据库。
我只是无法确定从所述正则表达式创建数字列表的优雅方式。
另一个方面是，产品另一部分中的 java 代码使用这些正则表达式通过 java Pattern.compile() 显示 ACME，这意味着客户“可以”创建一个复杂的正则表达式。到目前为止，我只见过它们，使用如上所示的简单方法。
有没有一种方法可以根据正则表达式生成列表？
谢谢你的时间。
有关的：
生成与正则表达式匹配的数据的库（有限制）： http ://code.google.com/p/xeger/
几种解决方案，例如将正则表达式转换为语法： 使用正则表达式生成字符串而不是匹配它们
编辑：实际上，你可以让它工作！！！唯一要解决的问题是施加一些特定于域的约束，以防止像 a+ 这样的组合爆炸。
如果您向 Xeger 类添加如下内容：
public void enumerate() {
System.out.println("enumerate: \"" + regex + "\"");
int level = 0;
String accumulated = "";
enumerate(level, accumulated, automaton.getInitialState());
}
private void enumerate(int level, String accumulated, State state) {
List<Transition> transitions = state.getSortedTransitions(true);
if (state.isAccept()) {
System.out.println(accumulated);
return;
}
if (transitions.size() == 0) {
assert state.isAccept();
return;
}
int nroptions = state.isAccept() ? transitions.size() : transitions.size() - 1;
for (int option = 0; option <= nroptions; option++) {
// Moving on to next transition
Transition transition = transitions.get(option - (state.isAccept() ? 1 : 0));
for (char choice = transition.getMin(); choice <= transition.getMax(); choice++) {
enumerate(level + 1, accumulated + choice, transition.getDest());
}
}
}
... 和 XegerTest 类似的东西：
@Test
public void enumerateAllVariants() {
//String regex = "[ab]{4,6}c";
String regex = "34\\.25\\.14\\.(227|228|229|230|243|244|245|246)";
Xeger generator = new Xeger(regex);
generator.enumerate();
}
...你会得到这个：
-------------------------------------------------------
T E S T S
-------------------------------------------------------
Running nl.flotsam.xeger.XegerTest
enumerate: "34\.25\.14\.(227|228|229|230|243|244|245|246)"
34.25.14.227
34.25.14.228
34.25.14.229
34.25.14.243
34.25.14.244
34.25.14.245
34.25.14.246
34.25.14.230
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.114 sec
... 你猜怎么着。对于“[ab]{4,6}c”，它正确地产生了 112 个变体。
这确实是一个快速而肮脏的实验，但它似乎有效；）。
我会说技术答案是否定的，因为您可以在正则表达式中指定字符（数字）出现零次或多次。这个“或更多”可能意味着任意大量的数字。在实践中，您可能能够限制字符串的长度并根据您在正则表达式中找到的字符递归地构建字符串的超集，然后向它们发送文本以创建您的子集列表。
注释：正则表达式是一种可递归枚举的语言，因此存在一种可以枚举所有有效字符串的算法。
即使对于像 Java 这样更复杂的语言，也可以有一个算法来枚举所有 Java 程序；无论您的特定 Java 程序是如何编写的，该算法都会在有限时间内输出与您的程序完全匹配的 Java 程序。
但并非所有语言都可以这样枚举；那么它们就是我们知道存在但我们不能说的语言。它们永远躲避像我们这样的原始智能，它只是一台图灵机。
蛮力，多线程，CPU 负载 100%：
import java.util.regex.Pattern;
public class AllIP
{
public static void main( String[] args )
{
final Pattern p = Pattern.compile( "34.25.14.(227|228|229|230|243|244|245|246)" );
int step = 256 / Runtime.getRuntime().availableProcessors();
for( int range = 0; range < 256; range += step )
{
final int from = range;
final int to = range + step;
new Thread(){
public @Override void run(){
long atStart = System.currentTimeMillis();
for( int i = from; i < to ; ++i )
for( int j = 1; j < 255; ++j )
for( int k = 1; k < 255; ++k )
for( int l = 1; l < 255; ++l )
{
String ip = String.format( "%d.%d.%d.%d", i,j,k,l );
if( p.matcher( ip ).matches())
{
System.out.println( ip );
}
}
System.out.println( System.currentTimeMillis() - atStart );
}
}.start();
}
}
}
只是为了好玩...
经过时间：01:18:59
操作系统
中央处理器
英特尔至强 W3565 @ 3.20GHz 39 °C
Bloomfield 45nm 技术
内存
母板
这个问题太神奇了！
我用一个简单的 JavaCC 语法和 3 个类解决了它：Constant、Variable 和 Main。我用作输入的表达式是(34|45).2\d.14.(227|228|229|230|243|244|245|246)，请注意 \d 指定变量部分。
下面是 JavaCC 语法：
options
{
static = false;
FORCE_LA_CHECK = true;
LOOKAHEAD = 5;
}
PARSER_BEGIN( IPGeneratorFromRegExp )
package hpms.study.jj;
public class IPGeneratorFromRegExp
{
public final java.util.SortedSet< hpms.study.IPPart > _a = new java.util.TreeSet< hpms.study.IPPart >();
public final java.util.SortedSet< hpms.study.IPPart > _b = new java.util.TreeSet< hpms.study.IPPart >();
public final java.util.SortedSet< hpms.study.IPPart > _c = new java.util.TreeSet< hpms.study.IPPart >();
public final java.util.SortedSet< hpms.study.IPPart > _d = new java.util.TreeSet< hpms.study.IPPart >();
}// class IPGeneratorFromRegExp
PARSER_END( IPGeneratorFromRegExp )
SKIP :
{
" "
| "\r"
| "\t"
| "\n"
}
TOKEN :
{
< IPPARTX : (["1"-"9"] | "\\d" ) >
| < IPPARTXX : (["1"-"9"] | "\\d" ) (["0"-"9"] | "\\d" ) >
| < IPPART1XX : "1" (["0"-"9"] | "\\d" ) (["0"-"9"] | "\\d" ) >
| < IPPART2XX : "2" (["0"-"4"] | "\\d" ) (["0"-"9"] | "\\d" ) >
| < IPPART25X : "2" "5" (["0"-"5"] | "\\d" ) >
}
void part( java.util.SortedSet< hpms.study.IPPart > parts ):{ Token token = null; }
{
(
token=<IPPART25X>
| token=<IPPART2XX>
| token=<IPPART1XX>
| token=<IPPARTXX>
| token=<IPPARTX>
){
parts.add(
token.image.contains( "\\d" )
? new hpms.study.Variable( token.image )
: new hpms.study.Constant( token.image ));
}
}
void expr( java.util.SortedSet< hpms.study.IPPart > parts ):{}
{
"(" part( parts ) ( "|" part( parts ))+ ")"
}
void analyze() :{}
{
( part( _a ) | expr( _a )) "."
( part( _b ) | expr( _b )) "."
( part( _c ) | expr( _c )) "."
( part( _d ) | expr( _d ))
}
和 Main.java 的一个片段：
Reader source = new StringReader( _regExp.getText());
IPGeneratorFromRegExp ipGenerator = new IPGeneratorFromRegExp( source );
ipGenerator.analyze();
SortedSet< String > a = new TreeSet<>();
SortedSet< String > b = new TreeSet<>();
SortedSet< String > c = new TreeSet<>();
SortedSet< String > d = new TreeSet<>();
for( IPPart<?> part : ipGenerator._a ) part.expandTo( a );
for( IPPart<?> part : ipGenerator._b ) part.expandTo( b );
for( IPPart<?> part : ipGenerator._c ) part.expandTo( c );
for( IPPart<?> part : ipGenerator._d ) part.expandTo( d );
_result.clear();
for( String ac : a )
{
for( String bc : b )
{
for( String cc : c )
{
for( String dc : d )
{
_result.add( ac + '.' + bc + '.' + cc + '.' + dc );
}// for
}// for
}// for
}// for
以及生成的 Swing 应用程序的快照（响应速度非常快）：
整个 Eclipse 项目可以从lfinance.fr下载。