最近公司规范出来后，关于字符串不提倡用 “ + ”  进行拼接，于是自己写了个function，利用正则表达式来进行匹配。对于正则表达式，之前不了解原理，每次要用的时候查一下，很浪费时间。

内容

基础知识；

正则表达式引擎；

贪婪与非贪婪模式；

DFA与NFA引擎；

回溯机制及常见的回溯形式

基础知识

1. 占有字符：正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中

2. 零宽度：只匹配一个位置，或者是匹配的内容并不保存到匹配结果中

一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配

3.控制权：正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个

4. 元字符 

5. 反义元字符

6. 转义字符：\  使元字符失去它的意义，仅代表其输入中字符的意义

需要转义的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重复限定符：匹配优先量词，忽略优先量词，即：贪婪与非贪婪

{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*'

8. 字符类：[ ]，区分大小写

9. 分支条件： |

10. 分组 ：（）指定子表达式，可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用，例：(\d{1,3}){3}\d{3}

断言；(?

11. 括号及反向引用：（子表达式一）（子表达式二）\1      此时括号作用为分组，它具有记忆的功能，即在正则表达式内部仍然能回忆上次匹配到的是什么；\1、\2、\n 是用在正则表达式的匹配环节。在正则表达式的替换环节，则要使用像 $1、$2、$n 这样的语法

12. 平衡组 参考

正则表达式引擎

有两个主要特点：

1. 默认贪婪匹配；（ 贪婪匹配与非贪婪匹配 ）

2. 返回最先匹配到的结果

针对简单的正则匹配进行分析，例：

        当把cat应用到“He captured a catfish for his cat”，引擎先比较c和“H”，结果失败了。于是引擎再比较c和“e”，也失败了。直到第四个字符，c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”，也失败了。引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始，cat匹配上了“catfish”中的“cat”，正则表达式引擎急切的返回第一个匹配的结果，而不会再继续查找是否有其他更好的匹配

Rubular: 基于 Web 的 Ruby 正则表达式编辑器

贪婪与非贪婪（又称惰性、懒惰等）模式

两者影响的是被量词修饰的子表达式的行为。

贪婪模式在整个表达式匹配成功的前提下，尽可能多的匹配；而非贪婪模式（只被部分NFA引擎支持）在整个表达式匹配成功的前提下，尽可能少的匹配。

匹配优先量词（属于贪婪模式的量词）：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略优先量词（匹配优先量词后加上“?”：非贪婪模式的量词）：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

例：

源字符串：aa

正则表达式一：

正则表达式二：

DFA与NFA引擎（JS的正则引擎是NFA：非确定型有限自动机）

参考： 正则表达式引擎及其分类

DFA引擎：在线性时状态下执行，不要求回溯（因此永远不测试相同的字符两次）；确保匹配最长的可能的字符串；因为只包含有限的状态（？），所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式

传统的NFA引擎：运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但传统 NFA的 回溯使它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现

POSIX NFA 引擎：与传统 NFA 引擎类似，不同点：在可以确保已找到了可能的最长的匹配之前，它们将继续回溯（更慢）；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索

例：

字符串： this is yansen’s dog

正则表达式： /ya(msen|nsen|nsem)/

NFA工作方式：先在字符串中查找 y， 然后匹配其后是否为 a；  如果是 a 则继续查找其后是否为 m； 如果不是则匹配其后是否为 n (此时淘汰 msen 支分支)； 然后继续看其后是否依次为 s,e； 接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！

DFA：从 this 中 t 开始依次查找 y ，定位到 y ，已知其后为 a ，则查看表达式是否有 a ，此处正好有 a； 然后字符串 a 后为 n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。 nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到 sen 中的 n 时只有 nsen 分支符合，则匹配成功！

由此两种引擎是完全不同的工作方式：NFA以表达式为主导，更容易操纵；DFA以文本为主导（搜索更快）

回溯机制

引擎是如何来处理那些模糊的条件匹配？

从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

--来自百度百科

本质上就是深度优先搜索算法：尝试匹配失败时的下一步通常就是回溯

JS中正则表达式会产生回溯的地方都有哪些呢？

常见的回溯形式

1.贪婪量词

例：正则：/ab{1,3}c/

可视化形式

1. 没有回溯的匹配：当目标字符串是"abbbc"时

匹配过程

2. 有回溯的匹配：当目标字符串是“abbc”时

匹配过程

上图第5步有红颜色（仅表示匹配不成功）：此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了；上图的第6步，就是“回溯”

即：尝试可能的顺序是“从多往少”的方向去尝试：首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了

另一个清晰的回溯：

正则：/".*"/

目标字符串："acd"ef

省略了尝试匹配双引号失败的匹配过程

其实“.*”最简单但也是非常影响效率的

2.惰性量词

虽然惰性量词不贪，但也会有回溯的现象（为了整体匹配成）

正则表达式

目标字符串："12345"

匹配过程

3.分支结构

分支也是惰性的，比如/Java|JavaScript/，去匹配字符串"JavaScript"，得到的结果是"Java"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯：

正则表达式

匹配过程

虽然第五步没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能

总结：有回溯的过程，那么匹配效率肯定比DFA相对低一些；别看匹配慢，但是编译快而且还挺有趣

参考： 正则表达式的回溯机制

安装和设置Git

下载Git for

Windows，采用默认安装，安装完成后就可以在本地使用Git了。

但要将内容放到Github上，必须先在Github网站上注册个账户，然后在本机使用Git创建SSH Key。操作如下：

在Git Bash上输入命令:

ssh-keygen -C "[email protected]" -t rsa

Note: “[email protected]”需要更换成你在Github上注册的Email地址或者是Username

这样会在用户目录(C:\Users\用户名)下产生一个.ssh文件夹，里面为对应的SSH

Keys，其中id_rsa.pub是Github需要的SSH公钥文件。

到c:\Users\用户名\.ssh\目录找到id_rsa.pub（可能位置不一定对，但是确认是以.pub结尾的文件），并用记事本打开复制全部内容。

Note：建议私钥公钥的名称最好写成"id_rsa"，这样连接Github的时候会找这个文件，如果文件名已定，之后改名也行。

在github网站选择“Account Settings”>>“SSH Public Keys”>>“Add another

public key”，将刚才复制的内容粘贴到key文本框内。

这样就可以直接使用Git和GitHub了。

Note：建议在Git Bash中输入“ssh -v [email protected]”测试能够正常连接github

安装Ruby环境

下载RubyInstaller和DevKit。

因为Octopress需要的Ruby版本为1.9.2，所以选rubyinstaller-1.9.2-p290.exe，DevKit-tdm-32-4.5.2-20111229-1559-sfx.exe。

先安装RubyInstaller，然后解压缩DevKit(路径中不能有中文)。

在“Start Command Prompt with Ruby”命令行中进入DevKit解压缩的目录，然后运行以下命令:

ruby dk.rb init

ruby dk.rb install

gem install rdiscount --platform=ruby

如果安装成功，就可以使用一些Ruby的工具了，也为后面搭建博客提供了基础环境。

安装Octopress

先通过Git从Github上克隆一份Octopress（在Git Bash上输入命令）

git clone git://github.com/imathis/octopress.git octopress

然后安装一些依赖的工具（后面都是在Start Command Prompt with Ruby中输入）

cd octopress

ruby --version # Should report Ruby 1.9.2

gem install bundler

bundle install

安装Octopress默认的Theme

rake install

配置Octopress

将octopress的文件夹下的_config.yml的编码改成UTF-8：

保存（或另存为）时选择编码格式为UTF-8

修改_config.yml，批改url、title、subtitle、author等等。

到Ruby的安装目次\lib\ruby\gems\1.9.1\gems\jekyll-0.11.2\lib\jekyll\找到convertible.rb这个文件，批改self.content

= File.read（File.join（base， name））为self.content = File.read（File.join（base，

name）， :encoding =>"utf-8"）。

写博文

最简单的方式：复制octopress\source\_posts下某个文件，例如2012-07-30-the-first-post.markdown，修改文件名和文件中的内容

或者，命令行中输入rake

new_post["title"]，会创建一个新的Post，新文件在source/_post下，文件名如下面的格式:2012-07-31-title.markdown。该文件可以直接打开修改。

写文章时，可以使用Markdown和Octopress

Plugins等工具对内容进行格式排版。

预览效果

在修改设置或者写完文章后，想看看具体效果，可以通过如下命令来完成:

rake generate

rake preview

将博客部署到Github上

在预览的效果符合自己的预期后，就可以通过如下命令将内容部署到Github上了。

如果是第一次部署，需要在Github上创建一个username.github.com的repository

在github网站选择“Create a New Repo”,如图

填写对应的内容即可

note：Repository

name填写username.github.com，username一定要和github的username一致，建好的博客代表的是你这个github账户的主页即page

配置octopress与github的连接：

进入Octopress目录：

rake setup_github_pages

按照提示填入你的github项目网址，比如：

[email protected]:Username/yourname.github.com.git

note：可以按照上面的修改，也可以在github的项目页中找地址

分发到github上：

rake deploy

第一次运行时，会询问是否建立对github的授权，输入：yes。然后将站点更新的内容推送到github上。

补充一点：

最后的但并不是最重要的，我们需要将修改的日志同步到github上，因此下面的3个命令也是必须的。

git status

git add .

git commit -m 'your message'

git push origin source

大功告成！

f=File.new(File.join("C:","Test.txt"), "w+")

f.puts("I am Jack")

f.puts("Hello World")

文件模式

"r" ：Read-only. Starts at beginning of file (default mode).

"r+" ：Read-write. Starts at beginning of file.

"w" ：Write-only. Truncates existing file to zero length or creates a new file for writing.

"w+" ：Read-write. Truncates existing file to zero length or creates a new file for reading and writing.

"a" ：Write-only. Starts at end of file if file existsotherwise, creates a new file for writing.

"a+" ：Read-write. Starts at end of file if file existsotherwise, creates a new file for reading and writing.

"b" ：(DOS/Windows only.) Binary file mode. May appear with any of the key letters listed above

二、读取文件

file=File.open(File.join("C:","Test.txt"),"r")

file.each { |line| print "#{file.lineno}.", line }

file.close

三、新建、删除、重命名文件

File.new( "books.txt", "w" )

File.rename( "books.txt", "chaps.txt" )

File.delete( "chaps.txt" )

四、目录操作

1     创建目录

Dir.mkdir("c:/testdir")

04     #删除目录

05     Dir.rmdir("c:/testdir")

07     #查询目录里的文件

08     p Dir.entries(File.join("C:","Ruby")).join(' ')

10     #遍历目录

11     Dir.entries(File.join("C:","Ruby")).each {

|e| puts e

}

1、ARGV and ARGF

ARGV

ARGV <<"cnblogslink.txt"

#The gets method is a Kernel method that gets lines from ARGV

print while gets

p ARGV.class

ARGF

while line = ARGF.gets

print line

end

2、文件信息查询

#文件是否存在

p File::exists?( "cnblogslink.txt" ) # =>true

#是否是文件

p File.file?( "cnblogslink.txt" ) # =>true

#是否是目录

p File::directory?( "c:/ruby" ) # =>true

p File::directory?( "cnblogslink.txt" ) # =>false

#文件权限

p File.readable?( "cnblogslink.txt" ) # =>true

p File.writable?( "cnblogslink.txt" ) # =>true

p File.executable?( "cnblogslink.txt" ) # =>false

#是否是零长度

p File.zero?( "cnblogslink.txt" ) # =>false

#文件大小 bytes

p File.size?( "cnblogslink.txt" ) # =>74

p File.size( "cnblogslink.txt" ) # =>74

#文件或文件夹

p File::ftype( "cnblogslink.txt" ) # =>"file"

#文件创建、修改、最后一次存取时间

p File::ctime( "cnblogslink.txt" ) # =>Sat Sep 19 08:05:07 +0800 2009

p File::mtime( "cnblogslink.txt" ) # =>Sat Sep 19 08:06:34 +0800 2009

p File::atime( "cnblogslink.txt" ) # =>Sat Sep 19 08:05:07 +0800 2009

3、查找文件

puts "查找目录下所有文件及文件夹"

Dir["c:/ruby/*"].each {|x|

puts x

}

puts "条件查询"

Dir.foreach('c:/ruby') {

|x| puts x if x != "." &&x != ".."

}

puts "查找某一类型文件"

Dir["*.rb"].each {|x|

puts x

}

puts "Open 查询"

Dir.open('c:/ruby') { |d| d.grep /l/ }.each{|x| puts x}

puts "---------------------------"

puts "正则表达式查询"

Dir["c:/ruby/ruby/[rs]*"].each{|x| puts x}

puts "------------------------"

Dir["c:/ruby/[^s]*"].each{|x| puts x}

puts "------------------------"

Dir["c:/ruby/{ruby,li}*"].each{|x| puts x}

puts "------------------------"

Dir["c:/ruby/?b*"].each{|x| puts x}

puts "查找目录及子目录的文件"

require 'find'

Find.find('./') { |path| puts path }

3、查询目录及子目录文件

require "find"

Find.find("/etc/passwd", "/var/spool/lp1", ".") do |f|

Find.prune if f == "."

puts f

end

原型：ref.find( [ aName ]* ) {| aFileName | block }

prune：Skips the current file or directory, restarting the loop with the next entry. If the current file is a directory, that directory will not be recursively entered. Meaningful only within the block associated with Find::find.

4、文件比较 复制等

require 'ftools'

File.copy 'testfile', 'testfile1'  » true

File.compare 'testfile', 'testfile1'  » true