Question

我们已经看到非确定性和自由移动增强了有限自动机的表达能力，而且不会干扰我们对有限自动机的模拟。在这一节，我们将会看到这些特性一个重要的实际应用：正则表达式匹配。

正则表达式提供了书写模式的语言，字符串可以按照这个模式进行匹配。下面是一些正则表达式的例子。

· hello，只能匹配字符串 'hello'。

· hello|goodbye，能匹配字符串'hello' 和 'goodbye'。

· (hello)*，匹配字符串 'hello'、'hellohello'、'hellohellohello' 等，也与空字符串匹配。

在这一章里，我们把正则表达式看成是与整个字符串进行匹配。真实世界中的正则表达式实现通常与部分字符串匹配，如果要求与整个字符串匹配的话，则应该使用额外的语法。

例如， 我们的正则表达式hello|goodbye 在Ruby 中应该写成/\A(hello|goodbye)\z/，这确保任何匹配都固定在字符串的开始（\A）和结尾（\z）之间。

给定一个正则表达式和一个字符串，我们如何写程序决定这个字符串是否与那个表达式匹配呢？大多数的编程语言，包括Ruby 在内，已经内建了对正则表达式的支持，但是这样的支持是如何工作的呢？如果语言没有支持正则表达式，我们如何使用Ruby 实现它们呢？

有限自动机完全适合这个工作。就像我们即将看到的，把任何正则表达式转成一个等价的NFA 是可能的——每一个与正则表达式匹配的字符串都能被这台NFA 接受，反过来也一样——把字符串输入给一台模拟的NFA 看它是否能被接受，从而判断字符串是否与正则表达式匹配。用第2 章的话说，我们可以把这个看成是为正则表达式提供了一种指称语义：我们不一定知道如何直接执行一个正则表达式，但是可以展示如何把它表示成一台NFA，并且因为有了NFA 的操作语义（“通过读取字符然后执行规则改变状态”），所以可以执行这个指称（denotation）实现同样的结果。

3.3.1　语法

让我们明确一下“正则表达式”是什么意思。下面是两种极其简单的正则表达式，它们已经没法更简单了。

· 一个空的正则表达式。与空字符匹配，没有别的可匹配的了。

· 一个只含有一个字符的正则表达式。例如，a 和 b 是分别只能匹配 'a' 和 'b' 的正则表达式。

有了这几种简单的模式之后，我们有三种方式可以把它们结合起来构造更复杂的表达式。

· 连接两个模式。我们可以把正则表达式 a 和 b 连接起来得到正则表达式 ab，它只与字符串'ab' 匹配。

· 在两个模式之间选择，使用运算符 | 把它们联结起来。我们可以把正则表达式 a 或 b 联结在一起得到a|b，它与字符串'a' 和'b' 匹配。

· 重复一个模式零次或者多次，写法是加上运算符*作为后缀。我们可以给正则表达式a加上后缀得到a*，它与字串'a'、'aa'、'aaa' 等匹配，当然也与空字符串'' 匹配（也就是说重复零次）。

现实中的正则表达式引擎（比如构建到Ruby 当中的），支持更多的特性。为了简单起见，我们不会尝试实现这些额外的特性，它们中有很多从学术上讲多余，只是为了方便才提供的。

例如，省略运算符? 和+ 没有什么太大区别，因为它们的作用（分别为“重复一或者零次”和“重复一或者多次”）很容易使用已有的特性实现：正则表达式ab? 可以重写成ab|a，而模式ab+ 与abb* 匹配同样的字符串。其他计数重复（如a{2,5}）和字符组（如[abc]）等方便的特性也是这样。

捕获组（capture group）、反向引用（backreference） 以及先行/ 后行断言（lookahead/lookbehind assertion）这样的高级特性已经超出了本章的讲述范围。

为了使用Ruby 实现这个语法，我们可以为每类正则表达式定义一个类，并使用这些类的实例表示任何正则表达式的抽象语法树，就像在第2 章里处理Simple 表达式一样：

module Pattern
   def bracket(outer_precedence)
    if precedence < outer_precedence
     '(' + to_s + ')'
     else
      to_s
  end
end

   def inspect
    "/#{self}/"
   end
end

class Empty
   include Pattern

   def to_s
    ''
   end

   def precedence
    3
   end
end

class Literal < Struct.new(:character)
   include Pattern

   def to_s
    character
   end

   def precedence
    3
   end
end

class Concatenate < Struct.new(:first, :second)
   include Pattern

   def to_s
    [first, second].map { |pattern| pattern.bracket(precedence) }.join
   end

   def precedence
    1
   end
end

class Choose < Struct.new(:first, :second)
   include Pattern

   def to_s
    [first, second].map { |pattern| pattern.bracket(precedence) }.join('|')
   end

   def precedence
    0
   end
end

class Repeat < Struct.new(:pattern)
   include Pattern

   def to_s
    pattern.bracket(precedence) + '*'
   end

   def precedence
    2
   end
end

在算术表达式中乘法对它参数的绑定比加法要更紧（1+2×3 等于7，而不是9），同样，这个约定也适用于正则表达式的语法，它的*运算符也比串联运算符绑定得更紧，而串联运算符又比| 运算符绑定得紧。例如，在正则表达式abc*中，* 只会应用到c 上（'abc'、'abcc'、'abccc'……），而为了让它能应用到整个abc 上（'abc'、'abcabc'），需要加上括号写成(abc)*。

语法类的实现#to_s 和Pattern#bracket 方法一起，会在必要的时候自动插入括号，这样在查看一棵抽象语法树的简单字符串表示时，我们也能知道它的结构信息。

有了这些类，我们就可以手工构建表示正则表达式的树：

>> pattern =
    Repeat.new(
    Choose.new(
    Concatenate.new(Literal.new('a'), Literal.new('b')),
    Literal.new('a')
  )
)
=> /(ab|a)*/

当然，在实际的实现中，我们不会手工构建这些树，而会使用语法解析器构建它们；可以参考3.3.3 节。

3.3.2　语义

既然我们可以把正则表达式语法表示成Ruby 对象组成的树，那么如何把这个语法转换成NFA 呢？

我们需要知道每个语法类的实例应该如何转换成NFA。转换起来最简单的类是Empty，应该总是把它转换成一个状态的NFA，这个NFA 只接受空字符串：

类似地，我们应该把任何单字符的模式转换成只接受包含那个字符的、单字符串的NFA。下面是模式a 的NFA：

为Empty 和Literal 实现#to_nfa_design 方法来生成这些NFA 相当容易：

class Empty
   def to_nfa_design
    start_state = Object.new
    accept_states = [start_state]
    rulebook = NFARulebook.new([])

    NFADesign.new(start_state, accept_states, rulebook)
   end
end

class Literal
   def to_nfa_design
     start_state = Object.new
     accept_state = Object.new
     rule = FARule.new(start_state, character, accept_state)
     rulebook = NFARulebook.new([rule])
     NFADesign.new(start_state, [accept_state], rulebook)
   end
end

3.1.4 节提到过，用Ruby 对象实现自动机时，状态对象彼此之间一定要能区分。这里没有使用数字（如Fixnum实例）作为状态，而是使用了新创建的Object 实例。

这是为了每一个NFA 都能有它自己独一无二的状态，以便把小的机器组合成大的机器，而不会意外把它们的状态也进行归并。例如，如果两个不同的NFA 都使用Ruby 的Fixnum 对象1 作为状态，在保持它们两个状态独立的情况下，它们不能合到一起。但是我们将来会需要能进行这样的合并，以便能实现更复杂的正则表达式。

类似地，我们不会继续在图上为状态打标记，这样以后把图连到一起时也不用重新对其进行标记。

可以检查由Empty 和Literal 正则表达式生成的NFA 能否接受我们想要它接受的字符串：

>> nfa_design = Empty.new.to_nfa_design
=> #<struct NFADesign ...>
>> nfa_design.accepts?('')
=> true
>> nfa_design.accepts?('a')
=> false
>> nfa_design = Literal.new('a').to_nfa_design
=> #<struct NFADesign ...>
>> nfa_design.accepts?('')
=> false
>> nfa_design.accepts?('a')
=> true
>> nfa_design.accepts?('b')
=> false

这里有机会可以把#to_nfa_design 封装进#matches? 方法，让模式有一个更友好的接口：

module Pattern
  def matches?(string)
    to_nfa_design.accepts?(string)
  end
end

这样我们就可以直接用模式匹配字符串：

>> Empty.new.matches?('a')
=> false
>> Literal.new('a').matches?('a')
=> true

既然我们知道如何把简单的Empty 和Literal 正则表达式转成NFA 了，那对Concatenate（串联）、Choose（选择）和Repeat（重复）也需要类似的进行转换。

从Concatenate 开始：如果有两个已经知道如何转换成NFA 的正则表达式，那么如何构造一个NFA 表示这些正则表达式的串联呢？举个例子，假如能把单个字符的正则表达式a和b 转换成NFA，那怎么把ab 转成一个NFA 呢？

对于ab，我们可以把两个NFA 按顺序连接到一起，用自由移动把它们联结在一起，并且保留第二个NFA 的接受状态：

这个技术在其他情况下也行得通。任意两个NFA 的连接，都可以先把第一个NFA 的每一个接受状态转成非接受状态，再通过自由有移动把它与第二个NFA 的开始状态连接。如果一串输入能让原来第一台NFA 进入接受状态，串联起来的机器读入这串输入之后就能自发的进入到原来第二个NFA 的起始状态，然后通过读取一串原来第二个NFA 能接受的输入，它将到达自己的接受状态。

因此，组合机器的原材料是：

· 第一个 NFA的起始状态；

· 第二个 NFA的接受状态；

· 两台 NFA的所有规则；

· 一些额外的自由移动，可以把第一台NFA 旧的接受状态与第二个 NFA 旧的起始状态连接起来。

可以把这个想法转换成Concatenate#to_nfa_design 的实现：

class Concatenate
   def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design

    start_state = first_nfa_design.start_state
    accept_states = second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = first_nfa_design.accept_states.map { |state|
     FARule.new(state, nil, second_nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)

    NFADesign.new(start_state, accept_states, rulebook)
   end
end

这段代码首先把第一和第二个正则表达式转换成NFADesign，然后把它们的状态和规则用合适的方式组合到一起构成新的NFADesign。ab 这种简单的情况是没有问题的：

>> pattern = Concatenate.new(Literal.new('a'), Literal.new('b'))
=> /ab/
>> pattern.matches?('a')
=> false
>> pattern.matches?('ab')
=> true
>> pattern.matches?('abc')
=> false

这个转换过程是递归的（Concatenate#to_nfa_design 对其他对象调用#to_nfa_design），因此对于像abc 这样的更深嵌套的正则表达式也能正常工作，这种情况下将包含两次串联（a 与b 串联然后与c 串联）：

>> pattern =
    Concatenate.new(
     Literal.new('a'),
     Concatenate.new(Literal.new('b'), Literal.new('c'))
   )
=> /abc/
>> pattern.matches?('a')
=> false
>> pattern.matches?('ab')
=> false
>> pattern.matches?('abc')
=> true

这又是一个组合型指称语义的例子：复合正则表达式的NFA 指称由它每一部分NFA 的指称组成。

我们可以使用同样的策略把Choose 表达式转成一台NFA。在最简单的情况下，正则表达式a 和b 的NFA 能结合起来构造成正则表达式a|b 的NFA，方法是增加一个新的起始状态并使用自由移动把它与两台原始机器之前的起始状态连接起来：

在a|b NFA 读取任何输入之前，它可以自由移动进入任何一个原始机器的起始状态，再从这个状态开始读取'a' 或者'b' 从而到达一个接受状态。通过增加一个新的起始状态和两个自由移动，把任意两台机器连到一起很简单：

在这种情况下，组合机器的原材料是：

· 一个新的起始状态；

· 两台 NFA 的所有接受状态；

· 两台 NFA 的所有规则；

· 两个额外的自由移动，可以把新的起始状态与 NFA旧的起始状态连接起来。

实现Choose#to_nfa_design 仍然不难：

class Choose
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design

    start_state = Object.new
    accept_states = first_nfa_design.accept_states + second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
      extra_rules = [first_nfa_design, second_nfa_design].map { |nfa_design|
      FARule.new(start_state, nil, nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)

    NFADesign.new(start_state, accept_states, rulebook)
  end
end

这个实现很好：

>> pattern = Choose.new(Literal.new('a'), Literal.new('b'))
=> /a|b/
>> pattern.matches?('a')
=> true
>> pattern.matches?('b')
=> true
>> pattern.matches?('c')
=> false

最后，我们开始讨论Repeat：如何把与一个字符串匹配的NFA，转换成能匹配同一个字符串重复零次或者更多次的NFA 呢？我们为a* 构造一个NFA，其开头是一个a 对应的NFA，然后做两个补充：

· 从它的接受状态到开始状态增加一个自由移动，这样它就可以与多于一个'a' 匹配了；

· 增加一个可自由移动到旧的开始状态的新状态，并且使其作为接受状态，这样它就可以匹配空字符串了。

图示如下：

从旧的接受状态得到旧的起始状态的自由移动，能让机器进行多次匹配而不是只匹配一次（'aa'、'aaa' 等），并且新的起始状态允许它匹配空字符串而不会影响它能接受的其他字符串5。对任何的NFA 我们都可以一样处理，只要通过自由移动把每一个旧的接受状态和旧的起始状态连接起来即可：

5在这种简单的情况下，我们可以只把原始的起始状态转成一个接受状态，而不增加新状态。但是在更复杂的情况下（例如(a*b)*），这种技术可能会产生一台接受除了空字符串外其他一些不想要字符串的机器。

这次我们需要：

· 一个新的起始状态，它也是一个接受状态；

· 旧的 NFA中所有的接受状态；

· 旧的 NFA中所有的规则；

· 一些额外的自由移动，把旧 NFA 的每一个接受状态与旧的起始状态连接起来；

· 另一些自由移动，把新的起始状态与旧的起始状态连接起来。

让我们把这些转换成代码：

class Repeat
  def to_nfa_design
    pattern_nfa_design = pattern.to_nfa_design

    start_state = Object.new
      accept_states = pattern_nfa_design.accept_states + [start_state]
      rules = pattern_nfa_design.rulebook.rules
      extra_rules =
        pattern_nfa_design.accept_states.map { |accept_state|
          FARule.new(accept_state, nil, pattern_nfa_design.start_state)
        } +
        [FARule.new(start_state, nil, pattern_nfa_design.start_state)]
      rulebook = NFARulebook.new(rules + extra_rules)

      NFADesign.new(start_state, accept_states, rulebook)
  end
end

然后检查结果：

>> pattern = Repeat.new(Literal.new('a'))
=> /a*/
>> pattern.matches?('')
=> true
>> pattern.matches?('a')
=> true
>> pattern.matches?('aaaa')
=> true
>> pattern.matches?('b')
=> false

既然每个正则表达式语法类都已经有了#to_nfa_design 实现，下面就可以构建复杂的模式并用它们匹配字符串了：

>> pattern =
    Repeat.new(
      Concatenate.new(
        Literal.new('a'),
        Choose.new(Empty.new, Literal.new('b'))
      )
    )
=> /(a(|b))*/
>> pattern.matches?('')
=> true
>> pattern.matches?('a')
=> true
>> pattern.matches?('ab')
=> true
>> pattern.matches?('aba')
=> true
>> pattern.matches?('abab')
=> true
>> pattern.matches?('abaab')
=> true
>> pattern.matches?('abba')
=> false

这个结果很好。我们从模式的语法开始，然后展示如何把任意模式转换成一台NFA，而NFA 是我们已经知道如何执行的抽象机器，这样就拥有了这种语法的语义。再配上一个语法解析器，我们就有了一种实用的方法，可以读取正则表达式并决定它是否与某个特定的字符串匹配。对这种方法自由移动非常有用，因为它们能把小一些的机器组合成更大的机器，并且不会影响其中任何组成部分的行为。

现实中多数正则表达式实现（如Ruby 使用的Onigmo 库）的工作方式都不是照字面把模式编译到有限自动机然后模拟它们执行。尽管这种方法在对字符串进行正则表达式匹配时快而且高效，但是在支持更高级的特性，如捕获组（capture groups）和先行/ 后行断言（lookahead/lookbehind assertions）时，会困难得多。因此，大多数的库都使用某种回溯算法（backtracking algorithm）更直接地处理正则表达式，而不是把它们转换成有限自动机。

Russ Cox 的RE2 库（http://code.google.com/p/re2/）是一个产品质量级别的C++ 正则表达式实现，它不把模式编译成自动机6，而Pat Shaughnessy 已经写了一篇很详细的博客（http://patshaughnessy.net/2012/4/3/exploring-rubysregular-expression-algorithm），来探索Ruby 正则表达式如何工作。

6RE2 的口号是“一个高效的、条理化的正则表达式库”，这很难反驳。

3.3.3　解析

我们几乎构建了一个完整的（虽然很基本）正则表达式实现。唯一缺失的是一个模式语法的语法解析器：如果我们只需要写(a(|b))*而不是通过Repeat.new(Concatenate.new(Literal.new('a'), Choose.new(Empty.new, Literal.new('b')))) 手工地构建出抽象语法树就方便多了。我们在2.6 节中看到使用Treetop 生成一个语法解析器并不困难，它能把原始语法自动转换成一个AST（抽象语法树），因此下面也这样做来完成我们的实现。

下面是一个简单正则表达式的Treetop 语法：

grammar Pattern
  rule choose
    first:concatenate_or_empty '|' rest:choose {
      def to_ast
        Choose.new(first.to_ast, rest.to_ast)
      end
    }
    /
    concatenate_or_empty
  end

  rule concatenate_or_empty
    concatenate / empty
  end
  rule concatenate
    first:repeat rest:concatenate {
      def to_ast
        Concatenate.new(first.to_ast, rest.to_ast)
      end
    }
    /
    repeat
  end

  rule empty
    '' {
    def to_ast
      Empty.new
    end
  }
  end

  rule repeat
    brackets '*' {
      def to_ast
        Repeat.new(brackets.to_ast)
      end
    }
    /
    brackets
  end

  rule brackets
    '(' choose ')' {
      def to_ast
        choose.to_ast
      end
    }
    /
    literal
  end

  rule literal
    [a-z] {
      def to_ast
        Literal.new(text_value)
    end
  }
  end
end

规则的顺序又一次反映了每一个运算符的优先级：运算符的优先级从上到下越来越高，| 运算符的绑定最宽松，因此choose 规则在最前面。

现在我们分析一个正则表达式，把它转换成一个抽象语法树，并使用它匹配字符串所需要的条件已经全部俱备：

>> require 'treetop'
=> true
>> Treetop.load('pattern')
=> PatternParser
>> parse_tree = PatternParser.new.parse('(a(|b))*')
=> SyntaxNode+Repeat1+Repeat0 offset=0, "(a(|b))*" (to_ast,brackets):
  SyntaxNode+Brackets1+Brackets0 offset=0, "(a(|b))" (to_ast,choose):
    SyntaxNode offset=0, "("
    SyntaxNode+Concatenate1+Concatenate0 offset=1, "a(|b)" (to_ast,first,rest):
      SyntaxNode+Literal0 offset=1, "a" (to_ast)
      SyntaxNode+Brackets1+Brackets0 offset=2, "(|b)" (to_ast,choose):
      SyntaxNode offset=2, "("
      SyntaxNode+Choose1+Choose0 offset=3, "|b" (to_ast,first,rest):
        SyntaxNode+Empty0 offset=3, "" (to_ast)
        SyntaxNode offset=3, "|"
        SyntaxNode+Literal0 offset=4, "b" (to_ast)
      SyntaxNode offset=5, ")"
    SyntaxNode offset=6, ")"
    SyntaxNode offset=7, "*"
>> pattern = parse_tree.to_ast
=> /(a(|b))*/
>> pattern.matches?('abaab')
=> true
>> pattern.matches?('abba')
=> false