为什么正则表达式((x,y)|(x,z))是不确定的？

Question

为什么正则表达式((x,y)|(x,z))是不确定的,正如"核心Java"这本书所说的那样？作者给出了他的观点:

当解析器看到x时,它不知道要采用哪两个替代方案.这个表达式可以以确定的形式重写为(x,(y | z))

任何人都可以给我一个解释吗？

Answer 1

要获得确定性形式,您只能在当前位置拥有最多一种可能的方式.假设你有一个字符串" x,y ".现在正则表达式引擎查看第一个字符" x ".在你的表达式中,你有两种可能性,你的字符串可以在第一个位置的" x " 之后接受你的输入.接下来有2种方法可供检查.如果字符串后跟" ,y "或" ,z ".

   , ? y
 ?
x
 ?
   , ? z

对于(x,(y | z)),你总是只有一种方式.如果" x "在位置1上,则转到位置2.同样在那里,只有" , ".最后他必须检查位置3上是否有" y "或" z "来接受这个词.从来没有两种方式.

x ? , ? (y or z)