学生時代、オートマトンとかNFAとかDFAとか習った記憶がありますが、全く身についていないので取り組んでみました。参考にしたのは、学生時代に買った『Cプログラマのためのアルゴリズムとデータ構造〈Part2〉 (SOFTBANK BOOKS)』です。本棚から引っ張り出してきました。
正規表現を実現するには、
という作業が必要になってくるそうです。読んだら理解できるのですが、これをプログラムで具現化しようと思うと大変です。
理解を深めるために、作ってみました。ただし、「正規表現をパースして構文木を作る」までです。
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>>