BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

Jeff Moser解释.NET正则表达式的工作方式

| 作者 Jonathan Allen 关注 612 他的粉丝 ,译者 赵劼 关注 5 他的粉丝 发布于 2009年4月3日. 估计阅读时间: 3 分钟 | ArchSummit北京2018 共同探讨机器学习、信息安全、微服务治理的关键点

Jeff Moser发表了一篇对.NET中正则表达式工作方式的深入解析。他的文章谈及了微软实现中的一些核心操作原理,如编译正则表达式时使用的机器码。

他首先透露,最近使用的15个正则表达式会被缓存起来。对于那些只使用1到2个正则表达式的小型的应用程序,这意味着没有必要每次都创建一个Regex对象。

在编译正则表达式的时候,首先会通过一个扫描器(scanner)来生成(emit)一个RegexTree。它的叶子节点就好像一种略加扩展的源代码,而下一步便是把它转换为正则表达式引擎所使用的机器码。

这些工作由EmitFragment函数完成,其中包含了大约250行的switch语句。这个函数把RegexTree打散成“碎片”再将它们转化为相对简单的RegexCode

[…]

这些工作生成一个用于描述RegexCode“操作码”及其参数的整数数组。例如,你可以看到一些例如“Setrep”的指令携带了一些字符串参数。这些参数指向了一个字符串表中的偏移量。这就是为什么说,正如我们之前看到的那样,把所有的东西打包成那些不规则字符串是很重要的原因。这是唯一可以传递指令信息的方法。

把代码数组分解之后,我们可以看到:

索引

指令

操作码/参数

字符串表的引用

描述

0

Lazybranch

23

 

延迟扩展至偏移量为21的Stop指令。

1

 

21

 

2

Setmark

31

 

把我们当前的状态放入栈中以便稍后进行回溯。

3

Multi

12

 

对字符串表中的第0项(即“http://”)进行一次多字符匹配。

4

 

0

"http://"

5

Setmark

31

 

把我们当前的状态放入栈中以便稍后进行回溯。 

6

Setrep

2

 

对于字符串表中位置为1的集合(即[^\s/])进行长度为1的反复匹配。

7

 

1

"\x1\x2\x1\x2F\x30\x64"

8

 

1

 

9

Setloop

5

 

在最多为Int32.MaxValue次的循环中对[^\s/]集合进行匹配。

10

 

1

"\x1\x2\x1\x2F\x30\x64"

11

 

2147483647

 

12

Capturemark

32

 

捕获组#1,即最近一次Setmark所标记的位置,到当前位置的字符串。

13

 

1

 

14

 

-1

 

15

Oneloop

3

 

在最多为1次的循环中匹配Unicode字符47。

16

 

47

 

17

 

1

 

18

Capturemark

32

 

 

捕获组#0,即第一次Setmark所标记的位置,到当前位置的字符串。

 

19

 

0

 

20

 

-1

 

21

Stop

40

 

停止匹配。

可以看到,正则表达式已经被转化为一个稍后可供运行的简单“程序”。

Jeff Moser的博客中描述了有关这个过程的更多信息。他的文章还讨论了:

  • 前缀优化
  • 解释器
  • 回溯
  • 已知错误

查看英文原文:Jeff Moser's How .NET Regular Expressions Really Work

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT