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

Question

为什么正则表达式((x,y)|(x,z))是不确定性的，就像《Core Java》一书所说的那样？作者给出了他的观点：

当解析器看到x时，它不知道应该选择哪个选项。这个表达式可以重写为一个确定性的形式(x,(y|z))。

有人能给我解释一下吗？

- J.zhou

---

引用的解释对我来说相当清晰。在第一种情况下，遇到 x 会留下两种可能的选择，在第二种情况下则不会发生这种情况。 - biziclop

Answer 1

为了拥有确定性的形式，您只允许在当前位置有最多一种可能的方式。假设您有一个字符串“x，y”。现在正则表达式引擎查看第一个字符，“x”。在您的表达式中，有两种可能使您的字符串在第一个位置的“x ”之后继续接受您的输入。接下来有两种检查方式。要么检查字符串是否后跟“，y”，要么后跟“，z”。

   , ⇨ y
 ⬀
x
 ⬂
   , ⇨ z

对于 (x,(y|z))，你总是只有一种方法。如果 "x" 在位置1上，你将移动到位置2。同样，在那里，只需要使用 ","。最后，他必须检查位置3是否有 "y" 或 "z" 来接受该单词。从未存在过两种方法。

x ⇨ , ⇨ (y or z)

- Pinguin895

Answer 2

一个有限状态机被称为非确定性有限自动机(NFA)，如果给定一个特定的状态，它可以有多个具有相同符号的转移。这意味着你的语法(即正则表达式)可以导致对于同一表达式有2个推导树，并且我们不知道自动机选择的状态：

       x 
      / \
     /   \
    /     \
   ,       ,
   |       |
   |       | 
   y       z

- Paul K.

Answer 3

((x,y)|(x,z))

在这种情况下，当解析器看到 x 时，它不知道应该选择哪个组，即 x,y 还是 x,z（非确定形式）

(x,(y|z))

在这种情况下，解析器可以读取 x, 然后自由选择 y 或 z（确定形式）

- karthik manchala

Answer 4

我认为提到的问题只在涉及组匹配时才相关。

如果x是([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]))）。

在这种情况下，标准定义了管道符号左侧具有优先权。然后可以在第三个开括号中找到x的值。

如果现在输入变为例如pq,78，则x的匹配根本没有改变（仍为pq），但是现在匹配管道符号右侧，您将在第六个开括号中找到x的值。

这可以通过使用更稳定的正则表达式来避免，例如(([a-z][a-z]),(([0-6][0-6])|([3-9][3-9])))，其中x始终位于第二组中。

- Alfe