请教大侠解释下这个正则返回的结果为什么是这样？

runsnake · 发表于 2013-1-28 23:55:20

(最近在学正则，所以问的问题都是这方面的，请大家包涵)


#include <Array.au3>
$sStr = "Chinese properties won"
$sRes = StringRegExp($sStr, "propertie|pro|proper|", 3)
_ArrayDisplay($sRes)

runsnake · 发表于 2013-1-28 23:58:01

我想象中，应该返回一个结果：propertie
或者三个结果：propertie、pro和proper

但返回的结果超出我的预期了。

annybaby · 发表于 2013-1-29 00:22:47

回复 2# runsnake

最后一个管道符号删除即可
因为那个符号后面没有东西,就相当于一个""空字符,在中间的单词properties前面每个字符之间(及开头与第一个字符之间)都有一个空字符""

runsnake · 发表于 2013-1-29 00:43:37

本帖最后由 runsnake 于 2013-1-29 00:45 编辑

回复 runsnake

最后一个管道符号删除即可
因为那个符号后面没有东西,就相当于一个""空字符,在中间的单 ...
annybaby 发表于 2013-1-29 00:22

annybaby · 发表于 2013-1-29 01:08:10

本帖最后由 annybaby 于 2013-1-29 15:43 编辑

回复 4# runsnake

等待H兄指正....

haijie1223 · 发表于 2013-1-29 08:15:31

最后一个“|”之后匹配了“空”了吧

3mile · 发表于 2013-1-29 13:01:06

楼主对比下$sRes = StringRegExp($sStr, "", 3)和
$sRes = StringRegExp($sStr, "propertie|pro|proper|", 3)的区别。
匹配为空，指针后移

happytc · 发表于 2013-1-29 15:28:17

回复 runsnake

是的,正如你所知,管道符"|"就是或的意思~~
想像一下它匹配的过程,正则干活不是像人那样,用眼睛看一下马上看到了properties,它是一个字符一个字符(包括空字符实际此时相当于一个位置),去匹配的,可以想像在开头处(就是"C"的前面,"C"与"h"之间也是)有一个空字符,当取p去匹配发现已经不成功了,然后就到下一个p(pro的那个),同理,失败,再第三个p,再失败,最后一个"|"后面可以匹配,成功;然后重复上述过程,直到空格后面,此时用p去匹配,发现可以,然后控制权交到p后面的r.......
annybaby 发表于 2013-1-29 01:08

其实你所说匹配过程是错误的（annybaby兄，实在不好意思，共同讨论学习提高)
看到大家对引擎工作原理（匹配过程）还是不熟，有必要再写一个长文，详细说明一下了。
由于脚本语言核心价值之一就是能方便地应用强大的正则表达式，若不能熟练地应用正则表达式，对学好au3这门脚本语言肯定逊色不少。
好了，现在下线去写这篇长文去，反正现在上班也没有什么事了，就当温故而知新了！

happytc · 发表于 2013-1-29 19:51:44

⑴ 背景简介
首先我们要了解，正则引擎原理是什么，或者说它的数学理论基础是什么，虽然有人会说，应该是一套算法。的确是一套算法来解析大家写的各种各样的正则表达式，但算法是基于数学模型上的。正则表达式是建立在有穷自动机（Finite Automaton）的理论基础上的，用户写完正则表达式之后，正则引擎会按照这个表达式构建相应的有穷自动机，通常所说正则引擎的不同，是指构建的有穷自动机的不同。要深入了解正则表达式，必须首先理解有穷自动机。若是计算机专业或数学专业的学生就会学《编译原理》或《理论代学》，其里面就有自动机原理的论述，非常抽象的东西。正则表达式引擎根据构建的有穷自动机的不同而分成两类：
一类称为DFA（Determinism Finite Automaton，确定性有穷自动机），DFA的另外一种通俗点的叫法是：文本导向的正则引擎
另一类称为NFA（Non-determinism Finite Automaton，非确定性有穷自动机），NFA的另外一种通俗点的叫法是：表达式导向的正则引擎
下面我简要说明一下其数学定义，若看不懂不要紧，接着看后面的例子就可以了。
有穷自动机（Finite Automate）是用来模拟实物系统的数学模型，它包括如下五个部分：
有穷状态集States 用Q表示
输入字符集Input symbols 用Σ表示
转移函数Transitions 用T表示：Q × Σ → P(Q) （这里的 P(Q) 指示 Q 的幂集）
起始状态Start state 用q0，有着 q0 ∈ Q
接受状态Accepting state(s) 用F表示，有着 F ⊆ Q
于是正则表达式的匹配过程就可以用下面的公式来表征：
T : Q × (Σ ∪{ε}) → P(Q) 这里的Q× Σ指的是Q 和Σ 的笛卡尔积或叉积
（ε指不消耗输入符号的到新状态的变换叫做ε转移，也就是正则里的空字符匹配。是无需考虑输入串（且无需消耗任何字符）就有可能发生的转换。它可看作是一个空串的“匹配”）

DFA里的所谓“确定性”指：目标文本中的每个字符只会检查（最多）一遍。
而NFA里的所谓“非确定性”指：目标文本中的某个字符可能被正则表达式中的不同部分重复检查（甚至有可能被同一部分反复检查）。
DFA和NFA里的所谓“有穷”指：下一个状态由当前状态和当前输入字符唯一给出的有穷自动机。也就是说，一个确定的状态和输入，仅有一个确定的状态对应。

好了，希望上面的数学符号不会把一堆人吓跑了。之所以在这里要秀这些让很多人看不懂的数学符号，是为了下面的图例和实例中一些表示方式和概念的由来。
下面由一个例子来看两种正则引擎是如何工作的，对于一个正则表达式 /a|ab/ （这里我们用“/.../”来示里面包括是正则表达式：a|ab）它们各别对的应的NFA和DFA
① NFA

② DFA

上两图中，单层圆圈代表上面所说的状态（state）。带有箭头的线代表由一个状态到另一个状态的转换（也就是上面所说的转移函数），该转换依赖于所标字符a或b的匹配。两图中的第一个箭头所指的单层圆圈代表上面所谓的初始状态（初始状态代表一个不来自任何地方的状态，指向它的箭头是不带任何标识的）。双层圆圈代表识别过程结束的状态，称作接受状态。
我们可以看到，两种引擎对同样的表达式 /a|ab/ 有着不同的处理方式。为了让人更容易理解，下面我们把DFA称为“文本导向的引擎”，而NFA称为“表达式导向的引擎”
两类引擎要顺利工作，都必须有一个正则表达式和一个文本串，一个拿在手里，一个用眼睛盯着。文本导向的引擎（DFA）是捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来，然后接着往下匹配，一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方（这也就是所谓的‘回溯’）。
针对上面的表达式 /a|ab/，我们来看看它们是怎样分别匹配字符串“abc”的。
文本为导向引擎DFA，它手里捏着文本，眼睛看着正则式，一个一个字符地吃。吃到/a/，就在手里的字符串 ‘a’ 上标记上，表示这个字符已经匹配上了，但DFA不会停，会尝试再匹配一次，这时候，第一个分支的子正则式已经匹配完了，于是就甩掉它，去看看第二分支子正则式的/b/。这下好了，又匹配上了，于是接着往下匹配，直到把正则式匹配完，到/b/为止，这时第二分支的子表达式已经匹配完了，于是向引擎报告说成功匹配了 ‘ab’（如上图2所示，这也是为什么这个图里两个双层圆圈了）。
表达式导向的引擎NFA，则以正则表达式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的匹配，匹配到“a”以后，就已经跟第一个分支的子表达式/a/已经匹配上了，这时第一分支的子表达式已经匹配完了，于是记录在案，于是向引擎汇报说成功匹配 ‘a’，就不再关心后面的，也就是不会尝试第二分支的那个子表达式/ab/，自然也就得不到那个更好的答案了。
所以我们可以看到两种引擎有下面的一些重大区别：
1. 文本导向的引擎对于文本串里的每一个字符只需扫描一次，比较快，但特性较少。awk(大多数版本)、egrep（大多数版本）、flex、lex、MySQL、Procmail都采用文本导向的引擎。表达式导向的引擎则要翻来覆去吞吐字符，速度慢，但是特性丰富，所以反而应用广泛，是当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是用表达式导向的引擎。而我们的au3所用的PCRE也是属于表达式导向的引擎。
2. 只有表达式导向的引擎才支持非贪婪（lazy）和回溯（backreference）等特性；
3. 表达式导向的引擎，是匹配优先的，也就是最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果（如上面的例子，只匹配了“a”，而错过了最佳匹配“ab”）；文本导向的引擎则是“最长的左子符串”原则，所以能匹配最长子串的子表达式优先匹配成功（这也是为什么上面例子中，文本导向的引擎匹配结果是“ab”子串了）。
4. 表达式导向的引擎缺省采用贪婪（greedy）量词和回溯（你可指定它为非贪婪的，如用/a*?/表示；也可用固定分组来指定不回溯，如用/(?>a*)/表示)，但正因为有这两项，可能会陷入递归调用的陷阱而表现得性能极差。如我们用au3来测：StringRegExp("-YY---------------------", "Y(.+)+Y", 3)，au3会报错，原因是堆栈超溢（stack overflow），或者超时退出。
5. 如果两台自动机能够接受的输入字符串（专业叫做“文法”或“词法”）完全相同，则这两台自动机是等价的。可以证明，对于每一个非确定有穷自动机（NFA），都存在与之等价的确定型有穷自动机（DFA）。证明中那一堆抽象数学符号让人看着就头晕，在此就省了吧。
针对 POSIX规范（Portable Operating System Interface可移植操作系统接口的缩写，而X则表明其对Unix API的传承)，NFA还可分为合符其规范的“POSIX NFA”和“传统型NFA”两类（au3的PCRE引擎属于后者）。区分“DFA”、“POSIX NFA”和“传统型NFA”这三类引擎很容易，我们可以用上面的/a|ab/来对字符串“abc”进行匹配来检测所用语言/工具所用的引擎是那类，若返回“a”的，肯定是“传统型NFA”（au3就是用的这类引擎）；若返回“ab”则要吗是“DFA”，要吗是“POSIX NFA”，因为POSIX规范里规定对多支结构：必须返回匹配最多字符的子表达式，这样也就意味着，POSIX DNF针对多支结构时，必须遍历所有分支，而“传统型NFA”和“DFA”则可能不需要。而区分是“DFA”还是“POSIX NFA”就更容易了，因为“DFA”不支持捕获型括号（capturing parentheses）和回溯（backreferences）

② 多支结构的实例
针对楼主上面的例子（如下）


        #include <Array.au3>
        $sStr = "Chinese properties won"
        $sRes = StringRegExp($sStr, "propertie|pro|proper|", 3)
        _ArrayDisplay($sRes)

运行一下，我们看到有15个返回值，其中前8个返回值为空值，第9个返回值为“propertie”，后面6个返回值也是空值。根据上面的背景介绍，我们知道au3所用的PCRE引擎是表达式导向的引擎，也是传统型NFA。首先要了解“|”两边的关系是平等的。正则引擎会按照这个表达式构建相应的有穷自动机，然后由引擎内部的算法把表达式解析成内部树，“|”两边的子表达式就是两棵平等的子树，在树上的匹配就是顺序匹配了（就是按照“|”两边出现的先后顺序，先出现的先匹配）。注意，因为这里的引擎是表达式导向的引擎，我们应该手里捏着/propertie|pro|proper|/，眼睛看着“Chinese properties won”
第一步：看着“C”，手里捏着第一分支表达式是/propertie/，用表达式的第一个字符/p/不能匹配眼里的“C”，于是我们放弃第一分支，再次用手捏着第二分支/pro/，同样其第一个字符/p/不能匹配眼里的“C”，于是也放弃，再次手里捏着第三分支/proper/，结果一样，于是再次手里捏着第四分支//（它是个空字符），我们眼里看到“C”的前面，也就是/^/所表示的位置是个空字符，匹配了第四分支//，于是缓存一个空值。
第二步：（每一步就是一次新的匹配过程）由引擎的‘传动装置’从字符串的“C”步移到“h”，同样我们眼里看着“h”，手里捏着第一分支表达式是/propertie/，用表达式的第一个字符/p/不能匹配眼里的“h”，于是我们放弃第一分支，再次用手捏着第二分支/pro/，同样其第一个字符/p/不能匹配眼里的“h”，于是也放弃，再次手里捏着第三分支/proper/，结果一样，于是再次手里捏着第四分支//（它是个空字符），我们眼里看到“h”的前面和“C”后面之间的位置是个空字符，匹配了第四分支//，于是再次缓存一个空值。
第三步：……
第四步：……
   .
   .
   .
第八步：……
第九步：这时前面八步已经返回了8个空值，我们到了字符串“p”的位置，同样手里捏着第一分支表达式是/propertie/，用表达式的第一个字符/p/匹配到了眼里的“p”，于是我们接着用手里第一分支的/r/去匹配眼里的字符串“p”后面的一个字符“r”，也匹配了，接着再用手里第一分支/r/后面的/p/去匹配眼里的字符串里“r”后面的“p”，也匹配成功，一直这样重复……，直到手里捏着第一分支表达式/propertie/的最后一个/e/，匹配到了眼里的字符串里“properties”里的最后一个“e”，这时第一分支表达式已经匹配完了，并且全部匹配成功了，然后就向报告匹配成功，缓存“propertie”。这时虽然还有第二、第三、第四分支还没有试过，但根据传统型表达式导向的引擎特性，将会抛弃后面的匹配测试，即使可能后面的分支可能有更好匹配结果。
第十步到第十五步，跟第一步等一样的匹配过程，都是匹配到第四个分支表达式，返回空值。到此，我们整个全局范围内的匹配完成，就把前面所有的缓存返回，就得到了一个数组（上面代码中的$sRes数组）

看到上面的匹配过程，就容易发现annybaby兄所说的匹配过程有点问题：想像一下它匹配的过程,正则干活不是像人那样,用眼睛看一下马上看到了properties,它是一个字符一个字符(包括空字符实际此时相当于一个位置),去匹配的,可以想像在开头处(就是"C"的前面,"C"与"h"之间也是)有一个空字符,当取p去匹配发现已经不成功了,然后就到下一个p(pro 的那个),同理,失败,再第三个p,再失败,最后一个"|"后面可以匹配,成功;然后重复上述过程,直到空格后面,此时用p去匹配,发现可以,然后控制权交到p后面的r.......
他所说的匹配过程很象文本导向的引擎的匹配过程：手里捏着字符串“Chinese properties won”，第一步先手里的串里的第一个字符“C”去查找各个分支中的子表达式，第二步手里捏着“h”去查找各个分支。若是对于au3的引擎，假设按这种方式匹配，前面可样会匹配到8个空值，但第九步根本不可能匹配到“propertie”，这一步里，当查找了前三个字母“pro”时，已经匹配到第二分支的表达式了，这时就应该返回值“pro”，而不会再去匹配第一分支的后半部分“pertie”了。但他所说的又不是文本导向引擎所匹配的过程，因为这种引擎会优先返回最左开始的最长子串。

dabaiyun · 发表于 2013-1-29 20:09:44

学习了嘿嘿

happytc · 发表于 2013-1-29 20:30:43

哎，这篇文章，还真不是那么好写的，从发#8楼帖到现在，除了吃晚饭一个小时外，剩下三个小时都在写它了。

另外，上面提到的编译原理的课程，要想了解一些计算机及编译器等其内部是如何工作的，可以去看两本书《Principles of Compiler Design》和《Compilers: Principles, Techniques and Tools》

《Principles of Compiler Design》
《Compilers: Principles, Techniques and Tools》

是非常权威的书，其作者对编译的理解非常透彻。前一本书因封面是一条绿龙，所以计算机系的学生又称它为绿龙书；第二本的封面是一条红龙，又被称为红龙书，两本合在一起统称为“龙书”，又被合称为“恐龙书”，因为里面的内容没有一定基础，让计算机系的学生谈之色变，大学时，也是计算机学生最怕的一门课程的考试，只要老师愿意，几乎可以把每位学生拉到红线以下去。

annybaby · 发表于 2013-1-29 22:27:17

回复 9# happytc

写了很多，感谢分享…

不知道坛友们看过之有没有看出来我们说的有什么不同（除了帖子的长度…）
我也是说：拿p去匹配C（也就是拿正则去匹配文本串）
至于按我说的会返回pro就更说不通了，明明第一个分支是可以匹配成功的，怎么会匹配到第二个分支呢？？
手机党，打字不方便，请继续指点，谢谢…

happytc · 发表于 2013-1-29 22:39:56

回复 happytc

写了很多，感谢分享…

不知道坛友们看过之有没有看出来我们说的有什么不同（除 ...
annybaby 发表于 2013-1-29 22:27

若是一样的，那就可能是我理解你说的话出了差错。
这样更好，大家所见略同。可以互相学习。

annybaby · 发表于 2013-1-29 23:18:30

回复 13# happytc

相互学习就谈不上了，谁都看得出来你比我高明N倍，理论基础扎实，我顶多是个业余灌水者，仰望你都觉得视力不好呢（真话来的），我自己平时也不常用正则，只是弄弄淘宝，新浪微博等会用下，也是不求甚解，达到目的就算了…

无论如何，感谢为大家科普，相信坛友们都可以从中获益…

手机党太蛋疼了……

ncgyx_dr · 发表于 2013-2-1 18:10:39

学习了,理论功力厚

		自动登录	找回密码
密码			加入

[AU3基础] 请教大侠解释下这个正则返回的结果为什么是这样？

相关帖子

评分

本帖子中包含更多资源

评分

本帖子中包含更多资源

标题