为什么正则表达式((x,y)|(x,z))是不确定性的,就像《Core Java》一书所说的那样?作者给出了他的观点:
当解析器看到x时,它不知道应该选择哪个选项。这个表达式可以重写为一个确定性的形式(x,(y|z))。
有人能给我解释一下吗?
当解析器看到x时,它不知道应该选择哪个选项。这个表达式可以重写为一个确定性的形式(x,(y|z))。
有人能给我解释一下吗?
为了拥有确定性的形式,您只允许在当前位置有最多一种可能的方式。假设您有一个字符串“x,y”。现在正则表达式引擎查看第一个字符,“x”。在您的表达式中,有两种可能使您的字符串在第一个位置的“x ”之后继续接受您的输入。接下来有两种检查方式。要么检查字符串是否后跟“,y”,要么后跟“,z”。
, ⇨ y
⬀
x
⬂
, ⇨ z
对于 (x,(y|z)),你总是只有一种方法。如果 "x" 在位置1上,你将移动到位置2。同样,在那里,只需要使用 ","。最后,他必须检查位置3是否有 "y" 或 "z" 来接受该单词。从未存在过两种方法。
x ⇨ , ⇨ (y or z)
x
/ \
/ \
/ \
, ,
| |
| |
y z
((x,y)|(x,z))
在这种情况下,当解析器看到 x
时,它不知道应该选择哪个组,即 x,y
还是 x,z
(非确定形式)
(x,(y|z))
在这种情况下,解析器可以读取 x,
然后自由选择 y
或 z
(确定形式)
([a-z][a-z])
,y是([0-6][0-6])
,z是([3-9][3-9])
,那么你会得到一个如下的正则表达式:((([a-z][a-z]),([0-6][0-6]))|(([a-z][a-z]),([3-9][3-9])))
pq,45
这样的输入,可以匹配管道符号的任一侧(即它同时匹配(([a-z][a-z]),([0-6][0-6]))
和(([a-z][a-z]),([3-9][3-9]))
)。pq,78
,则x的匹配根本没有改变(仍为pq
),但是现在匹配管道符号右侧,您将在第六个开括号中找到x的值。(([a-z][a-z]),(([0-6][0-6])|([3-9][3-9])))
,其中x始终位于第二组中。
x
会留下两种可能的选择,在第二种情况下则不会发生这种情况。 - biziclop