为什么正则表达式（（x，y）|（x，z））是不确定的？ [英] Why regular expression ((x,y)|(x,z)) is nondeterministic?

问题描述

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

Why regular expression ((x,y)|(x,z)) is nondeterministic as the book "Core Java" said? The author gives his point:

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

When the parser sees x, it doesn’t know which of the two alternatives to take.This expression can be rewritten in a deterministic form as (x,(y|z))

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

Could anyone can give me an explanation?

推荐答案

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

To have a deterministic form, you are only allowed to have a maximum of one possible way at your current position. Let's say you have a string "x,y". Now the regex engine looks at the first character, the "x". In your expression you have 2 possibilities how your string can go on after an "x" at the first position to accept your input. Next there are 2 ways to check. Either if the string is followed by ",y" or by ",z".

   , ⇨ y
 ⬀
x
 ⬂
   , ⇨ z

对于（x，（y | z）），你总是只有一种方法。如果 x 位于第1位，则转到第2位。同样，只有，。最后，他必须检查位置3上是否有 y 或 z 才能接受该单词。从来没有两种方式。

For (x,(y|z)) you always have just one way. If an "x" is on position 1 you go to position 2. Same there, just with the ",". Finally he has to check if there is a "y" or a "z" on position 3 to accept the word. There were never 2 ways.

x ⇨ , ⇨ (y or z)

这篇关于为什么正则表达式（（x，y）|（x，z））是不确定的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！