您所在的位置： &
R语言进阶之2：文本（字符串）处理与正则表达式
R语言进阶之2：文本（字符串）处理与正则表达式
处理文本是每一种计算机语言都应该具备的功能，但不是每一种语言都侧重于处理文本。R语言是统计的语言，处理文本不是它的强项，perl语言这方面的功能比R不知要强多少倍。幸运的是R语言的可扩展能力很强，DNA/RNA/AA等生物序列现在已经可以使用R来处理。
R语言处理文本的能力虽然不强，但适当用用还是可以大幅提高工作效率的，而且有些文本操作还不得不用。高效处理文本少不了正则表达式（regular expression），虽然R在这方面先天不高效，但它处理字符串的绝大多数函数都使用正则表达式。
0、正则表达式简介：
正则表达式不是R的专属内容，所以用0编号，这里也只简单介绍，更详细的内容请查阅其他文章。
正则表达式是用于描述/匹配一个文本集合的表达式。
1. &所有英文字母、数字和很多可显示的字符本身就是正则表达式，用于匹配它们自己。比如 'a' 就是匹配字母 'a' 的正则表达式
2. &一些特殊的字符在正则表达式中不在用来描述它自身，它们在正则表达式中已经被&转义&，这些字符称为&元字符&。perl类型的正则表达式中被转义的字符有：. \ | ( ) [ ] { } ^ $ * + ?。被转义的字符已经有特殊的意义，如点号 . 表示任意字符；方括号表示选择方括号中的任意一个（如[a-z] 表示任意一个小写字符）；^ 放在表达式开始出表示匹配文本开始位置，放在方括号内开始处表示非方括号内的任一字符；大括号表示前面的字符或表达式的重复次数；| 表示可选项，即 | 前后的表达式任选一个。
3. &如果要在正则表达式中表示元字符本身，比如我就要在文本中查找问号&?&， 那么就要使用引用符号（或称换码符号），一般是反斜杠 '\'。需要注意的是，在R语言中得用两个反斜杠即 &\\&，如要匹配括号就要写成 &\\(\\)&
4. &不同语言或应用程序（事实上很多规则都通用）定义了一些特殊的元字符用于表示某类字符，如 \d 表示数字0-9， \D 表示非数字，\s 表示空白字符（包括空格、制表符、换行符等），\S 表示非空白字符，\w 表示字（字母和数字），\W 表示非字，\& 和 \& 分别表示以空白字符开始和结束的文本。
5. &正则表达式符号运算顺序：圆括号括起来的表达式最优先，然后是表示重复次数的操作（即：* + {} ），接下来是连接运算（其实就是几个字符放在一起，如abc），最后是表示可选项的运算（|）。所以 'foot|bar' 可以匹配&foot&或者&bar&，但是 'foot|ba{2}r'匹配的是&foot&或者&baar&。
一、字符数统计和字符翻译
nchar这个函数简单，统计向量中每个元素的字符个数，注意这个函数和length函数的差别：nchar是向量元素的字符个数，而length是向量长度（向量元素的个数）。其他没什么需要说的。
&x&&c(&Hellow&,&&World&,&&!&)&&nchar(x)&[1]&6&5&1&&length('');&nchar('')&[1]&1&[1]&0&
另外三个函数用法也很简单：
&DNA&&&AtGCtttACC&&&tolower(DNA)&[1]&&atgctttacc&&&toupper(DNA)&[1]&&ATGCTTTACC&&&chartr(&Tt&,&&Uu&,&DNA)&[1]&&AuGCuuuACC&&&chartr(&Tt&,&&UU&,&DNA)&[1]&&AUGCUUUACC&&
二、字符串连接
paste应该是R中最常用字符串函数了，也是R字符串处理函数里面非常纯的不使用正则表达式的函数（因为用不着）。它相当于其他语言的strjoin，但是功能更强大。它把向量连成字串向量，其他类型的数据会转成向量，但不一定是你要的结果：
&paste(&CK&,&1:6,&sep=&&)&[1]&&CK1&&&CK2&&&CK3&&&CK4&&&CK5&&&CK6&&&x&&list(a=&aaa&,&b=&bbb&,&c=&ccc&)&&y&&list(d=1,&e=2)&&paste(x,&y,&sep=&-&)&&&&&#较短的向量被循环使用&[1]&&aaa-1&&&bbb-2&&&ccc-1&&&z&&list(x,y)&&paste(&T&,&z,&sep=&:&)&&&#这样的结果不知合不合用&[1]&&T:list(a&=&\&aaa\&,&b&=&\&bbb\&,&c&=&\&ccc\&)&&[2]&&T:list(d&=&1,&e&=&2)&&
短向量重复使用，列表数据只有一级列表能有好的表现，能不能用看自己需要。会得到什么样的结果是可以预知的，用as.character函数看吧，这又是一个字符串处理函数：
&as.character(x)&[1]&&aaa&&&bbb&&&ccc&&&as.character(z)&[1]&&list(a&=&\&aaa\&,&b&=&\&bbb\&,&c&=&\&ccc\&)&&[2]&&list(d&=&1,&e&=&2)&&&
paste函数还有一个用法，设置collapse参数，连成一个字符串：
&paste(x,&y,&sep=&-&,&collapse=';&')&[1]&&aaa-1;&bbb-2;&ccc-1&&&paste(x,&collapse=';&')&[1]&&&&ccc&&
三、字符串拆分
strsplit函数使用正则表达式，使用格式为：strsplit(x, split, fixed = FALSE, perl = FALSE, useBytes = FALSE)
参数x为字串向量，每个元素都将单独进行拆分。
参数split为拆分位置的字串向量，默认为正则表达式匹配（fixed=FALSE）。如果你没接触过正则表达式，设置fixed=TRUE，表示使用普通文本匹配或正则表达式的精确匹配。普通文本的运算速度快。
perl=TRUE/FALSE的设置和perl语言版本有关，如果正则表达式很长，正确设置表达式并且使用perl=TRUE可以提高运算速度。
参数useBytes设置是否逐个字节进行匹配，默认为FALSE，即按字符而不是字节进行匹配。
下面的例子把一句话按空格拆分为单词：
& text &- &Hello Adam!\nHello Ava!&
& strsplit(text, ' ')
[1] &Hello& & & & &&Adam!\nHello& &Ava!& & & & & & &
R语言的字符串事实上也是正则表达式，上面文本中的\n在图形输出中是被解释为换行符的。 & &&
& strsplit(text, '\\s')
[1] &Hello& &Adam!& &Hello& &Ava!& &
strsplit得到的结果是列表，后面要怎么处理就得看情况而定了：
& class(strsplit(text, '\\s'))
[1] &list&
有一种情况很特殊：如果split参数的字符长度为0，得到的结果就是一个个的字符：
& strsplit(text, '')
[1] &H& &&e& &&l& &&l& &&o& && & &&A& &&d& &&a& &&m& &&!& &&\n& &H& &&e& &&l& &&l&&
[17] &o& && & &&A& &&v& &&a& &&!&&
从这里也可以看到R把 \n 是当成一个字符来处理的。
四、字符串查询：
1、grep和grepl函数：
这两个函数返回向量水平的匹配结果，不涉及匹配字符串的详细位置信息。
grep(pattern,&x,&ignore.case&=&FALSE,&perl&=&FALSE,&value&=&FALSE,&&&&&&fixed&=&FALSE,&useBytes&=&FALSE,&invert&=&FALSE)&grepl(pattern,&x,&ignore.case&=&FALSE,&perl&=&FALSE,&&&&&&&fixed&=&FALSE,&useBytes&=&FALSE)&
虽然参数看起差不多，但是返回的结果不一样。下来例子列出C:\windows目录下的所有文件，然后用grep和grepl查找exe文件：
&files&&list.files(&c:/windows&)&&grep(&\\.exe$&,&files)&&[1]&&&8&&28&&30&&35&&36&&57&&68&&98&&99&101&110&111&114&116&&grepl(&\\.exe$&,&files)&&&[1]&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&&TRUE&FALSE&FALSE&FALSE&FALSE&FALSE&&[14]&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&FALSE&#......&
grep仅返回匹配项的下标，而grepl返回所有的查询结果，并用逻辑向量表示有没有找到匹配。两者的结果用于提取数据子集的结果都一样：
&files[grep(&\\.exe$&,&files)]&&[1]&&bfsvc.exe&&&&&&&&explorer.exe&&&&&fveupdate.exe&&&&HelpPane.exe&&&&&[5]&&hh.exe&&&&&&&&&&&notepad.exe&&&&&&regedit.exe&&&&&&twunk_16.exe&&&&&[9]&&twunk_32.exe&&&&&uninst.exe&&&&&&&winhelp.exe&&&&&&winhlp32.exe&&&&[13]&&write.exe&&&&&&&&xinstaller.exe&&&files[grepl(&\\.exe$&,&files)]&&[1]&&bfsvc.exe&&&&&&&&explorer.exe&&&&&fveupdate.exe&&&&HelpPane.exe&&&&&[5]&&hh.exe&&&&&&&&&&&notepad.exe&&&&&&regedit.exe&&&&&&twunk_16.exe&&&&&[9]&&twunk_32.exe&&&&&uninst.exe&&&&&&&winhelp.exe&&&&&&winhlp32.exe&&&&[13]&&write.exe&&&&&&&&xinstaller.exe&&
2、regexpr、gregexpr和regexec
这三个函数返回的结果包含了匹配的具体位置和字符串长度信息，可以用于字符串的提取操作。
&text&&c(&Hellow,&Adam!&,&&Hi,&Adam!&,&&How&are&you,&Adam.&)&&regexpr(&Adam&,&text)&[1]&&9&&5&14&attr(,&match.length&)&[1]&4&4&4&attr(,&useBytes&)&[1]&TRUE&&gregexpr(&Adam&,&text)&[[1]]&[1]&9&attr(,&match.length&)&[1]&4&attr(,&useBytes&)&[1]&TRUE&[[2]]&[1]&5&attr(,&match.length&)&[1]&4&attr(,&useBytes&)&[1]&TRUE&[[3]]&[1]&14&attr(,&match.length&)&[1]&4&attr(,&useBytes&)&[1]&TRUE&&regexec(&Adam&,&text)&[[1]]&[1]&9&attr(,&match.length&)&[1]&4&[[2]]&[1]&5&attr(,&match.length&)&[1]&4&[[3]]&[1]&14&attr(,&match.length&)&[1]&4&
五、字符串替换
虽然sub和gsub是用于字符串替换的函数，但严格地说R语言没有字符串替换的函数，因为R语言不管什么操作对参数都是传值不传址。
&text&[1]&&Hello&Adam!\nHello&Ava!&&&sub(pattern=&Adam&,&replacement=&world&,&text)&[1]&&Hello&world!\nHello&Ava!&&&text&[1]&&Hello&Adam!\nHello&Ava!&&
可以看到：虽然说是&替换&，但原字符串并没有改变，要改变原变量我们只能通过再赋值的方式。
sub和gsub的区别是前者只做一次替换（不管有几次匹配），而gsub把满足条件的匹配都做替换：
&sub(pattern=&Adam|Ava&,&replacement=&world&,&text)&[1]&&Hello&world!\nHello&Ava!&&&gsub(pattern=&Adam|Ava&,&replacement=&world&,&text)&[1]&&Hello&world!\nHello&world!&&
sub和gsub函数可以使用提取表达式（转义字符+数字）让部分变成全部：
& sub(pattern=&.*(Adam).*&, replacement=&\\1&, text)
[1] &Adam&
六、字符串提取
substr和substring函数通过位置进行字符串拆分或提取，它们本身并不使用正则表达式，但是结合正则表达式函数regexpr、gregexpr或regexec使用可以非常方便地从大量文本中提取所需信息。两者的参数设置基本相同：
substr(x,&start,&stop)&substring(text,&first,&last&=&1000000L)&
第 1个参数均为要拆分的字串向量，第2个参数为截取的起始位置向量，第3个参数为截取字串的终止位置向量。但它们的返回值的长度（个数）有差 别：substr返回的字串个数等于第一个参数的长度；而substring返回字串个数等于三个参数中最长向量长度，短向量循环使用。先看第1参数（要 拆分的字符向量）长度为1例子：
&x&&&&&&substr(x,&c(2,4),&c(4,5,8))&[1]&&234&&&substring(x,&c(2,4),&c(4,5,8))&[1]&&234&&&&&&&45&&&&&&&&2345678&&
因为x的向量长度为1，所以substr获得的结果只有1个字串，即第2和第3个参数向量只用了第一个组合：起始位置2，终止位置4。
而substring的语句三个参数中最长的向量为c(4,5,8)，执行时按短向量循环使用的规则第一个参数事实上就是c(x,x,x)，第二个参数就成了c(2,4,2)，最终截取的字串起始位置组合为：2-4, 4-5和2-8。
请按照这样的处理规则解释下面语句运行的结果：
&x&&c(&&,&&abcdefghijklmnopq&)&&substr(x,&c(2,4),&c(4,5,8))&[1]&&234&&&de&&&&substring(x,&c(2,4),&c(4,5,8))&[1]&&234&&&&&&&de&&&&&&&&2345678&&
用substring函数可以很方便地把DNA/RNA序列进行三联拆分（用于蛋白质翻译）：
&bases&&c('A','T','G','C')&&DNA&&paste(sample(bases,&12,&replace=T),&collapse='')&&DNA&[1]&&CCTTTACGGTGT&&&substring(DNA,&seq(1,10,by=3),&seq(3,12,by=3))&[1]&&CCT&&&TTA&&&CGG&&&TGT&&
用regexpr、gregexpr或regexec函数获得位置信息后再进行字符串提取的操作可以自己试试看。
七、其他：
比如strtrim、strwrap、charmatch、match和pmatch等，甚至是 %in% 运算符都是可以使用的。R的在线帮助很全，自己看吧，就当学习E文。
原文链接：
【编辑推荐】
【责任编辑： TEL：（010）】
关于的更多文章
R语言是大数据分析和挖掘重要的工具，R是用于统计分析、绘图的语
作为移动开发者，WOT2016移动互联网技术峰会，绝对有你不得不来的理由。
9月的工作日被法定假日拆的零零散散，不知道各位的工
总结一下Java I/O文件读写基本类相关知识和概念。对于
今天是被国际上众多科技公司和软件企业承认的业内人士
本书是讲解C++语言程序设计的优秀教程。全书围绕C++语言来组织，开始章节介绍编程的普通感念，接下来详细介绍C++中的继承、多态
51CTO旗下网站商品编号：
京 东 价：
[定价：￥]
支　　持：
搭配赠品：
选择套装：
服务支持：
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
精通正则表达式（第3版）
加载中，请稍候...
商品介绍加载中...
扫一扫，精彩好书免费看
　　★“如果你的工作需要用到正则表达式（即便你已经有本很不错的关于开发语言的书），我还是要向你强烈推荐本书。”　　——Dr.ChrisBrown,LinuxFormat&　　★“毫不夸张地说，《精通正则表达式（第3版）》是学习该工具的不二选择，也是每个程序员必备的杰作。”　　——JasonMenard.JavaRanch&　　★“所有关于正则表达式的书中，找不到比这更好的了。”　　——ZakGreant,PlanetPHP
京东商城向您保证所售商品均为正品行货，京东自营商品开具机打发票或电子发票。
凭质保证书及京东商城发票，可享受全国联保服务（奢侈品、钟表除外；奢侈品、钟表由京东联系保修，享受法定三包售后服务），与您亲临商场选购的商品享受相同的质量保证。京东商城还为您提供具有竞争力的商品价格和，请您放心购买！
注：因厂家会在没有任何提前通知的情况下更改产品包装、产地或者一些附件，本司不能确保客户收到的货物与商城图片、产地、附件说明完全一致。只能确保为原厂正货！并且保证与当时市场上同样主流新品一致。若本商城没有及时更新，请大家谅解！
权利声明：京东上的所有商品信息、客户评价、商品咨询、网友讨论等内容，是京东重要的经营资源，未经许可，禁止非法转载使用。
注：本站商品信息均来自于合作方，其真实性、准确性和合法性由信息拥有者（合作方）负责。本站不提供任何保证，并不承担任何法律责任。
印刷版次不同，印刷时间和版次以实物为准。
价格说明：
京东价：京东价为商品的销售价，是您最终决定是否购买商品的依据。
划线价：商品展示的划横线价格为参考价，该价格可能是品牌专柜标价、商品吊牌价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品在京东平台上曾经展示过的销售价；由于地区、时间的差异性和市场行情波动，品牌专柜标价、商品吊牌价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：如无特殊说明，折扣指销售商在原价、或划线价（如品牌专柜标价、商品吊牌价、厂商指导价、厂商建议零售价）等某一价格基础上计算出的优惠比例或优惠金额；如有疑问，您可在购买前联系销售商进行咨询。
异常问题：商品促销信息以商品详情页“促销”栏中的信息为准；商品的具体售价以订单结算页价格为准；如您发现活动商品售价或促销信息有异常，建议购买前先联系销售商咨询。
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
浏览了该商品的用户还浏览了
加载中，请稍候...
联系供应商
七日畅销榜
新书热卖榜
iframe(src='///ns.html?id=GTM-T947SH', height='0', width='0', style='display: visibility:')如何从零写一个正则表达式引擎？
按投票排序
是的, 首先要确定实现的目标, 有几个关键目标是会影响你的实现的- 要不要支持完整的正则文法? (如果不支持 "|", 几十行就能搞定, 如果要支持完整的正则文法, 就需要一个能力超越正则的解析器, 如果要编写一个高效的 one-pass 正则编译器, 还是要学不少编译技术的...)- 要不要支持 unicode 及 unicode character class? (扫描 UTF-8/16 码点会比较蛋疼, 容易一点的做法是转换成 UTF-32 做), 要对 unicode 做完整支持的话, 很多传统正则引擎里基于字节的匹配方式就不能做了, 一些 DFA 节点的表示方式和压缩手段也会受限制.- 要不要支持 back reference? (如果你要实现 back reference 的话, 你不能用
里描述的 ThompsonVM/PikeVM 的, thread list 占有的内存会随着状态数指数增长而爆裂) 支持 back reference 的正则基本很多会退回去扩展最原始那个 Henry Spencer VM...- 要做成 NFA based, DFA based, 还是一个字节码虚拟机? 对虚拟机的解决方案, 你要学习字节码解释器的基本构造, 可能会用 direct threading 等技术去做优化. 字节码可以看作线性化的 NFA, 相比构造 NFA 节点会减少一些 cache miss 但是相应的就不能使用很多节点压缩和优化的手段了.- 要不要做一个 JIT 引擎? 这个更令人兴奋, 可以参考 )- 要不要兼容 POSIX 标准里的正则部分? (估摸至少 4000 行代码, 自己考虑工作量咯)- 要不要做 extended 正则?所谓 extended 正则, 就是还支持补集和交集运算, 正则语言这么搞完结果还是个正则语言, 就是实现 grep -v 之类的可以简单一些, 可以尝试 - 要不要做 Online Parsing?online parsing 常用于语法高亮和大文件解析中. 其意思是输入一部分内容就匹配一部分, 有新内容输入的时候你不该重头匹配一遍 (每敲一个字符重新着色一遍太慢了), 而是做最低限度的回溯. 如果要做 online parsing, 那么怎么暂停你的 VM, 怎么缓存回溯都是要考虑的问题. 而且正则的语法会有限制.- 要不要支持超巨大的正则表达式?有些 network filter 例如联邦的防火墙, 会有几十万条规则, 你会发现普通的办法在 20G 内存的机器上都编译不了这个正则... 不过用小内存支持 DFA 千万节点的方法已经有人研究出来了: D^2FA... 为了编译出这么大的 D^2FA, 其编译期算法也有人研究过了: - 要不要支持以下各种正则引擎的 fancy feature?-- \X 匹配字素-- 递归 named group-- capture history-- nested capture-- atomic group-- greedy vs reluctant vs possessive...每一项都相当有难度... 尤其是 greedy/reluctant/possessive 的区别有可能从根本上颠覆你这个正则引擎的实现, 很多人的正则引擎做完 DFA/NFA 就停下来了, 也是因为搞不动这些 feature.---OK, 目标明确了, 开始代码之前要先夹沟夹沟哦, 建议: 不要一开始就想把它做得很高效率, 要把问题拆得足够小足够简单的来做, 只要决定好大方向不错, 就不用推倒重来很多次了...现在的正则引擎的构造比各种 parser generator 都要复杂, good luck!推荐书籍:
Parsing Techniques - A Practical Guide
2008 (讲得比较全了, 就是缺少 coroutine based parser 的构建)推荐课程:
(为什么要 beyond CFG 呢? 因为现在正则引擎的能力已经 beyond CFG 啦)推荐代码: Henry Spencer's regexp engine
是很多现代流行的正则引擎的始祖, 解释器实现, 很多新 feature 能扩展得得进去, 也有混合 DFA 的优化Onigmo
是 Ruby 的正则引擎, 特点是 encoding aware 兼容多种语法和 feature, 如果要做 unicode character class 可以抄它的...
写了个80行的C++模板版。注意啊，regex的定义包括了concatenation，alternation（“|”），Kleene closure（“*”），还得有一个ε字符（可近似认为“?”），expression还要能嵌套（“(”“)”）。有些例子里缺了alternation和嵌套那就不该叫regex了。之所以这么短是因为压根没有parsing，parsing多无聊啊。直接构造regex的AST，根本不去打NFA的主意。想加什么功能就直接加type就行了。这个是compile time regex，所以跑起来是raw speed，很快。你要是要运行时的regex，把那几个模板特化改为一个树状variant结构，在树上走就行了，算法（包括那个continuation的trick）都是一样的。建NFA那套做法是Ken Thompson推出来的“标准”算法，但是就玩玩而已应该从更简单的学起。学一下CPS变换又不会死。另外把程序写短小紧凑的诀窍就是写成FP style。我的80行中所有函数都只有一个return语句。
好吧，我将
的C++的版本改成了JS版本。偏特化用类实现，模板匹配用switch+instanceof 语句实现，字符串结尾判断用s[i] === undefined 实现因为不到40行，就把代码直接放上来吧// from c++ version: /timshen91/f6a3f040e5b5b0685b2a
// author: wangxiaochi
function ConcatExpr (Left,Right) {this.Left = Left;this.Right=Right} // ab
function AltExpr(Left,Right) {this.Left = Left;this.Right=Right} // a|b
function RepeatExpr(SubExpr) {this.SubExpr= SubExpr;} // a*
function OptionalExpr(SubExpr) {this.SubExpr= SubExpr;} // a?
function MatchExpr(ch) {
this.ch= ch
MatchImplApply = function (expr, target, i, cont) {
switch (true) {
case expr instanceof ConcatExpr:
return MatchImplApply(expr.Left, target, i, (rest,ri) =&
MatchImplApply(expr.Right, rest, ri, cont))
case expr instanceof AltExpr:
return (MatchImplApply(expr.Left, target, i, cont) ||
MatchImplApply(expr.Right, target, i, cont))
case expr instanceof RepeatExpr:
return MatchImplApply(expr.SubExpr, target, i, (rest,ri) =&
(MatchImplApply(expr, rest, ri, cont) || cont(rest,ri))
) || cont(target, i)
case expr instanceof OptionalExpr:
return MatchImplApply(expr.SubExpr, target, i, cont) || cont(target, i)
case expr instanceof MatchExpr:
return target[i] !== undefined && target[i] == expr.ch && cont(target, i+1) // end of string, match a char
throw "no expression type"
RegexMatch = (RegExpr,target) =& // all match
MatchImplApply(RegExpr, target,0, (rest,i) =& rest[i] === undefined)
RegexSearch = (RegExpr,target,i) =& // partial match from begining
MatchImplApply(RegExpr, target,i, (rest,i) =& true) ||
(target[i] !== undefined && RegexSearch(RegExpr, target, i+1))
console.assert(RegexMatch(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b')), "ab"));
console.assert(RegexMatch(new AltExpr(new MatchExpr('a'), new MatchExpr('b')), "a"));
console.assert(RegexMatch(new AltExpr(new MatchExpr('a'), new MatchExpr('b')), "b"));
console.assert(RegexMatch(new RepeatExpr(new MatchExpr('a')), "aaaaa"));
console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')),
"aaaaab"));
console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')),
console.assert(RegexSearch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')),
"aaaaabb", 0));
console.assert(RegexMatch(new OptionalExpr(new MatchExpr('a')), "a"));
console.assert(RegexMatch(new OptionalExpr(new MatchExpr('a')), ""));
console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b'))),
console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b'))),
by Russ Cox
来来来诚心安利FP大法好，五行带你写regexp matcher(不要问我为啥要用SML咱学校就任性就只叫这个= =datatype regexp =
Char of char
| Times of regexp * regexp
| Plus of regexp * regexp
| Star of regexp
fun match (Char(a)) cs k = (case cs of
nil =& false
| (c::cs') =& (a=c) andalso k(cs'))
| match (One) cs k = k cs
| match (Zero) _ _ = false
| match (Times(r1,r2)) cs k = match r1 cs (fn cs' =& match r2 cs' k)
| match (Plus(r1,r2)) cs k = match r1 cs k orelse match r2 cs k
| match (Star(r)) cs k =
k cs orelse
match r cs (fn cs' =& not (cs = cs') andalso match (Star(r)) cs' k)
代码的核心在于他保证了如下性质:match r cs k returns true
cs can be split as cs == p@s,
with p representing a string in L(r)
and k(s) evaluating to true.这里传的cs和k就是传说中的cps啦知乎网页版挂了= =...回头加代码高亮
咋都写的是matcher？ 考虑过parser的感受吗？简单写了个Swift版本的Parser， 支持() ，| , + , ? , *
以及各种嵌套，parse的结果就是AST。有了AST，才能用前面的菊苣们写的matcher呀！依赖：基于我自己写的一个Swift版的简化Parsec ： ， 这里定义了最基本的Combinator。let reserved = "+?()|*"
indirect enum Regex{
case Char(Character)
case Concat(Regex,Regex)
case Alter(Regex,Regex)
case ZeroOrOne(Regex)
case ZeroOrMore(Regex)
case OneOrMore(Regex)
func notReserved(c : Character) -& Bool{
return reserved.characters.indexOf(c) == nil
func rchar()-&Parser&Regex&{
return satisfy(notReserved) &&= { c in
pure(.Char(c))
func regop(c : Character) -& (Regex-&Regex)?{
if c == "?"{
return { reg in
.ZeroOrOne(reg)
}else if c == "*"{
return { reg in
.ZeroOrMore(reg)
}else if c == "+"{
return { reg in
.OneOrMore(reg)
return nil
func rexp() -& Parser&Regex&{
return (rtrm() &&= {term in
symbol("|") &&= { _ in
rexp() &&= { exp in
pure(.Alter(term,exp))
}) +++ rtrm()
func ratm() -& Parser&Regex&{
return rchar() +++ (symbol("(") &&= { _ in
rexp() &&= { reg in
symbol(")") &&= { _ in
func rfac() -& Parser&Regex&{
return (ratm() &&= {atm in
satisfy({sc in sc == "*" || sc == "?" || sc == "+"}) &&= {c in
pure(regop(c)!(atm))
+++ ratm()
func rtrm() -& Parser&Regex&{
return (rfac() &&= { reg1 in
rtrm() &&= { reg2 in
pure(.Concat(reg1,reg2))
}) +++ rfac()
let parserResult = rexp().p(reg)
print(parserResult)
完整版Demo在这里：， Matcher和大家一样用的SML教材里的算法，只是用Swift实现了一下。
首先确定要实现什么样的正则表达式1. 经典正则表达式：这是我们在编译原理课或者形式语言与自动机课上学到的那种正则表达式，即正规文法，也就是Chomsky体系中的3型文法。任何正则文法都可以构造等价的有限状态自动机，也就是说我们可以构造一个有限状态自动机来实现经典正则表达式的匹配。2. 扩展的正则表达式：这个名字是我给起的，其实我更喜欢称他们为黑魔法正则，也就是我们现在在Perl、Python、Java的标准库中用到的正则表达式。相比经典正则，其表达能力更强，使用更方便，深受广大人民群众喜欢，参见Python文档（）。但此类正则表达式已经超越正则文法，特别是对backreference支持（带backreference的正则表达式匹配其实是NP完全的）。接下来，如何实现呢？为了方便论述，假设文本的长度为n，正则表达式的长度为m1. 实现经典正则表达式经典NFA：就是搜索加回溯的方式，搜索到第一个match就退出。经典NFA的空间复杂度（即状态数和转移数）是O(m)，但匹配的时间复杂度最坏情况下是指数级的，即O(2^n)。POSIX NFA: 和传统NFA差不多，不同是只有找到最长的match才会退出，所以理论上会比经典NFA更慢。Thompson NFA：上个世纪60年代，由Ken Thompson提出，空间复杂度仍然是O(m)，但匹配的时间复杂度可以降到O(nm), 算法可以参考。当然构造NFA的方法还有很多，比如Glushkov NFA，这里不一一列举了（好吧，实话是因为这样我就要去问谷歌了）DFA：NFA和DFA的表达能力有等价的，而且任何一个NFA都可以转化为一个DFA。DFA匹配的时间复杂度是线性的，即O(n), 但因为对于某些复杂的正则表达式，会导致DFA的状态爆炸，所以最坏情况下，转化需要的空间复杂度和时间复杂度是O(2^m)。可见相比NFA，DFA算是用空间来换时间了。在工程上，有时也不得不放弃DFA，投奔NFA。我建议经典正则还是值得自己实现一把的，尤其是Thompson NFA及其变种，可以自己做一些修改或精简来支持自己特殊的需求。和
大神一样，推荐系列。2. 实现扩展正则表达式实现复杂度取决于你愿意支持多少黑魔法，但因为同样基于回溯，时间复杂度和经典NFA一样，逃脱不了指数级时间复杂度的魔咒。我不建议手撸此类正则表达式，用标准库就行了。（好吧，实话是我也没干过）
先认识你要匹配的具体文本，贴到编辑器里，然后另起一行逐段的用正则替换掉，写出第一个版本，如果失败，另起一行写一个改进版本，直到满意为止 —— 这是我个人的方法。
我也来撸一个简单的Racket的版本吧，只有14行哦（（（（括号大法好））））#lang racket
; &pat& ::= &string&
| (&pat& *)
| (&pat& +)
| (&pat& ?)
| (&pat& or &pat&)
; reg-match : (listof pat) string integer -& boolean
(define (reg-match pats str pos)
(if (null? pats) (= pos (string-length str))
(match (car pats)
[(? string?) (let ([len (string-length (car pats))])
(and (&= (string-length str) (+ pos len))
(substring=? (car pats) str pos (+ pos len))
(reg-match (cdr pats) str (+ pos len))))]
[`(,p1 or ,p2) (or (reg-match `(,p1 ,@(cdr pats)) str pos)
(reg-match `(,p2 ,@(cdr pats)) str pos))]
[`(,p *) (or (reg-match (cdr pats) str pos)
(reg-match `(,p ,@pats) str pos))]
[`(,p +) (reg-match `(,p (,p *) ,@(cdr pats)) str pos)]
[`(,p ?) (reg-match `((,p or "") ,@(cdr pats)) str pos)]
[else (error "bad pattern")])))
; auxiliary function
(define (substring=? pat str start end)
(for/and ([i (in-range start end)]
[j (in-naturals)])
(char=? (string-ref pat j) (string-ref str i))))
(reg-match '("a" ("b"*) (("c"?) or ("d"+))) "abbc" 0)
已有帐号？
无法登录？
社交帐号登录