正则表达式的编译结构
Kobi 的回答是关于 Java 正则表达式(Sun/Oracle 实现)对于 case"^\\d{1}{2}$"
或"{1}"
.
下面是内部编译的结构"^\\d{1}{2}$"
:
^\d{1}{2}$
Begin. \A or default ^
Curly. Greedy quantifier {1,1}
Ctype. POSIX (US-ASCII): DIGIT
Node. Accept match
Curly. Greedy quantifier {2,2}
Slice. (length=0)
Node. Accept match
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match
看源代码
{
根据我的调查,该错误可能是由于未在私有方法中正确检查的事实sequence()
。
该方法sequence()
调用 来atom()
解析原子,然后通过调用 将量词附加到原子closure()
,并将所有带闭包的原子链接到一个序列中。
例如,给定这个正则表达式:
^\d{4}a(bc|gh)+d*$
然后顶级调用将接收, , , ,sequence()
的编译节点,并将它们链接在一起。^
\d{4}
a
(bc|gh)+
d*
$
考虑到这个想法,让我们看看从OpenJDK 8-b132sequence()
复制的源代码(Oracle 使用相同的代码库):
@SuppressWarnings("fallthrough")
/**
* Parsing of sequences between alternations.
*/
private Node sequence(Node end) {
Node head = null;
Node tail = null;
Node node = null;
LOOP:
for (;;) {
int ch = peek();
switch (ch) {
case '(':
// Because group handles its own closure,
// we need to treat it differently
node = group0();
// Check for comment or flag group
if (node == null)
continue;
if (head == null)
head = node;
else
tail.next = node;
// Double return: Tail was returned in root
tail = root;
continue;
case '[':
node = clazz(true);
break;
case '\\':
ch = nextEscaped();
if (ch == 'p' || ch == 'P') {
boolean oneLetter = true;
boolean comp = (ch == 'P');
ch = next(); // Consume { if present
if (ch != '{') {
unread();
} else {
oneLetter = false;
}
node = family(oneLetter, comp);
} else {
unread();
node = atom();
}
break;
case '^':
next();
if (has(MULTILINE)) {
if (has(UNIX_LINES))
node = new UnixCaret();
else
node = new Caret();
} else {
node = new Begin();
}
break;
case '$':
next();
if (has(UNIX_LINES))
node = new UnixDollar(has(MULTILINE));
else
node = new Dollar(has(MULTILINE));
break;
case '.':
next();
if (has(DOTALL)) {
node = new All();
} else {
if (has(UNIX_LINES))
node = new UnixDot();
else {
node = new Dot();
}
}
break;
case '|':
case ')':
break LOOP;
case ']': // Now interpreting dangling ] and } as literals
case '}':
node = atom();
break;
case '?':
case '*':
case '+':
next();
throw error("Dangling meta character '" + ((char)ch) + "'");
case 0:
if (cursor >= patternLength) {
break LOOP;
}
// Fall through
default:
node = atom();
break;
}
node = closure(node);
if (head == null) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
}
if (head == null) {
return end;
}
tail.next = end;
root = tail; //double return
return head;
}
注意行throw error("Dangling meta character '" + ((char)ch) + "'");
。如果+
, *
,?
悬空并且不是前面标记的一部分,则在此引发错误。如您所见,{
不属于抛出错误的情况。事实上,它并没有出现在 中的案例列表中sequence()
,编译过程将default
直接按案例进行atom()
。
@SuppressWarnings("fallthrough")
/**
* Parse and add a new Single or Slice.
*/
private Node atom() {
int first = 0;
int prev = -1;
boolean hasSupplementary = false;
int ch = peek();
for (;;) {
switch (ch) {
case '*':
case '+':
case '?':
case '{':
if (first > 1) {
cursor = prev; // Unwind one character
first--;
}
break;
// Irrelevant cases omitted
// [...]
}
break;
}
if (first == 1) {
return newSingle(buffer[0]);
} else {
return newSlice(buffer, first, hasSupplementary);
}
}
当进程进入atom()
时,由于{
马上遇到,所以会中断switch
并for
循环,并创建一个长度为 0 的新切片(长度来自first
,为 0)。
当这个切片被返回时,量词被 解析closure()
,得到我们所看到的。
对比 Java 1.4.0、Java 5 和 Java 8 的源代码,sequence()
和atom()
. 似乎这个错误从一开始就存在。
正则表达式的标准
引用IEEE 标准 1003.1 (或 POSIX 标准)的最高投票答案与讨论无关,因为 Java不实现BRE 和 ERE。
根据标准,有许多语法导致未定义的行为,但在许多其他正则表达式风格中是明确定义的行为(尽管它们是否同意是另一回事)。例如,\d
根据标准未定义,但它匹配许多正则表达式风格的数字(ASCII/Unicode)。
遗憾的是,正则表达式语法没有其他标准。
然而,有一个关于 Unicode 正则表达式的标准,它侧重于 Unicode 正则表达式引擎应该具有的功能。JavaPattern
类或多或少地实现了 1 级支持,如UTS #18:Unicode 正则表达式和 RL2.1 中所述(尽管有很多错误)。