Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

正規表現の実現

学生時代、オートマトンとかNFAとかDFAとか習った記憶がありますが、全く身についていないので取り組んでみました。参考にしたのは、学生時代に買った『Cプログラマのためのアルゴリズムとデータ構造〈Part2〉 (SOFTBANK BOOKS)』です。本棚から引っ張り出してきました。

正規表現を実現するには、

  1. 正規表現をパースして構文木を作る
  2. 構文木からNFAを作成する
  3. NFAからDFAを作成する

という作業が必要になってくるそうです。読んだら理解できるのですが、これをプログラムで具現化しようと思うと大変です。

理解を深めるために、作ってみました。ただし、「正規表現をパースして構文木を作る」までです。

regexp.rb

require 'pp'

class Scanner
  def initialize(reg)
    @reg = reg
    @list = []
  end
  def createTokenList
    @reg.split(//).each do |char|
      case char
      when "|"
        @list << Token.new(Token::Union)
      when "("
        @list << Token.new(Token::Lpar)
      when ")"
        @list << Token.new(Token::Rpar)
      when "*"
        @list << Token.new(Token::Star)
      when "+"
        @list << Token.new(Token::Plus)
      else
        @list << Token.new(Token::Char, char)
      end
    end
    @list << Token.new(Token::End)
    return @list
  end
end

class Parser
  # <regexp> ::= <term> | <term> '|' <regexp>
  # <term>   ::= EMPTY  | <factor> <term>
  # <factor> ::= <primary> | <primary>'*' | <primary>'+'
  # <primary>::= CHARACTER | '(' <regexp> ')'
  def initialize(tokenList)
    @tokenList = tokenList
    @current = nil
  end
  def parseRegexp
    nextToken
    t = regexp
    if @current.type != "End"
      raise SyntaxError
    end
    return t
  end
  def regexp
    x = term
    while @current.type == "Union"
      nextToken
      x = Node.new("op_union", x, term, nil)
    end
    return x
  end
  def term
    if @current.type == "Union" || 
        @current.type == "Rpar" || 
        @current.type == "End"
      x = Node.new("op_empty", nil, nil, nil)
    else
      x = factor
      while @current.type != "Union" && 
          @current.type != "Rpar" && 
          @current.type != "End"
        x = Node.new("op_concat", x, factor, nil)
      end
    end
    return x
  end
  def factor
    x = primary
    if @current.type == "Star"
      x = Node.new("op_closure", x, nil, nil)
      nextToken
    elsif @current.type == "Plus"
      x = Node.new("op_concat", x, 
                   Node.new("op_closure", x, nil, nil),
                   nil)
      nextToken
    end
    return x
  end
  def primary
    if @current.type == "Char"
      x = Node.new("op_char", nil, nil, @current.char)
      nextToken
    elsif @current.type == "Lpar"
      nextToken
      x = regexp
      if @current.type != "Rpar"
        raise SyntaxError
      end
      nextToken
    else
      raise SyntaxError
    end
    return x
  end
  def nextToken
    @current = @tokenList.shift
  end
  class SyntaxError < StandardError; end
end

class Node
  attr_reader :op, :left, :right, :char
  def initialize(op, left, right, char)
    @op = op
    @left = left
    @right = right
    @char = char
  end
end

class Token
  Char = "Char"
  Union = "Union"
  Lpar = "Lpar"
  Rpar = "Rpar"
  Star = "Star"
  Plus = "Plus"
  End = "End"
  attr_reader :type, :char
  def initialize(type, char = nil)
    @type = type
    @char = char
  end
end

if __FILE__ == $0
  reg = "a(a|b)*a"
  scanner = Scanner.new(reg)
  tokenList = scanner.createTokenList
  parser = Parser.new(tokenList)
  tree = parser.parseRegexp
  pp tree
end

"a(a|b)*a"を構文解析した結果が以下です。ちょっと見にくいですが、構文木ができています。

実行結果

mmasa@debian:~/work/ruby/regexpression$ ruby regexp.rb
#<Node:0xb7c9f600
 @char=nil,
 @left=
  #<Node:0xb7c9f8a8
   @char=nil,
   @left=#<Node:0xb7c9f90c @char="a", @left=nil, @op="op_char", @right=nil>,
   @op="op_concat",
   @right=
    #<Node:0xb7c9f664
     @char=nil,
     @left=
      #<Node:0xb7c9f768
       @char=nil,
       @left=
        #<Node:0xb7c9f7a4 @char="a", @left=nil, @op="op_char", @right=nil>,
       @op="op_union",
       @right=
        #<Node:0xb7c9f6c8 @char="b", @left=nil, @op="op_char", @right=nil>>,
     @op="op_closure",
     @right=nil>>,
 @op="op_concat",
 @right=#<Node:0xb7c9f5b0 @char="a", @left=nil, @op="op_char", @right=nil>>