正規表現のパーサー

正規表現のパターンは前の章で説明した構文を持った文字列です。そのため、マッチングを行うためにはまず、構文解析 (パース) をして、どのようなパターンなのかコンピュータが理解できるようにしなければなりません。この構文解析を行う部分をパーサーと呼びます。この章ではパターンのパーサーの実装をします。

NOTE

この章は「正規表現の動作を理解する」という目標からは少し離れた内容になっています。そのため、場合によっては次の「抽象構文木 (AST)」の部分に目を通したのち、パーサーの実装をコピーして、次の章に進んでも構いません。

抽象構文木 (AST)

パターンを構文解析した結果を表すデータ構造を、抽象構文木 (AST) と呼びます。そして、文字列からこの抽象構文木へと変換することが構文解析 (パース) になります。

抽象構文木はDataを使って表すことにします。

class KantanRegex
  # 文字リテラル・エスケープ文字に対応する抽象構文木のデータ型。
  Literal = Data.define(:value)

  # 繰り返しに対応する抽象構文木のデータ型。
  Repetition = Data.define(:child, :quantifier)

  # 選択に対応する抽象構文木のデータ型。
  Choice = Data.define(:children)

  # 連接に対応する抽象構文木のデータ型。
  Concat = Data.define(:children)
end

それぞれどのような型か説明します。

Literalは文字リテラルやエスケープ文字を表す型です。 valueにはその文字を表す長さ1の文字列が入ります。例えば1文字のパターンaはLiteral['a']として表します。
Repetitionは繰り返しを表す型です。 childは繰り返し対象の抽象構文木です。 quantifierがどの繰り返しの種類かを表すパラメータで:starか:plusか:questionのいずれかになります。例えばパターンa*はRepetition[Literal['a'], :star]として表します。
Choiceは選択を表す型で、childrenは抽象構文木の配列です。例えばパターンa|bはChoice[[Literal['a'], Literal['b']]]として表します。
Concatは連接を表す型で、childrenは抽象構文木の配列です。例えばパターンabはConcat[[Literal['a'], Literal['b']]]として表します。

グループ化はパターンのマッチ結果に影響しない構文のため、型としては定義していません。例えばa*と(a)*はマッチする文字列は同じで、どちらもRepetition[Literal['a'], :star]で表します。

パーサーの実装

パーサーの実装方法は、パーサージェネレーターを使う方法や、手書きでパーサーを実装する方法など、いくつか存在します。今回はその中でも手書きで実装する再帰下降パーサーという方法を使うことにします。再帰下降パーサーは文字列を複数の再帰関数 (メソッド) を用いて走査することで構文解析を行う方法です。

実装はKantanRegex::Parserクラスで行います。このクラスは構文解析の度に生成されて、再帰下降パーサーの状態を管理します。

class KantanRegex::Parser
  def initialize(pattern)
    @pattern = pattern
    @offset = 0
  end
  
  def current_char =@pattern[@offset]
  def end? = @pattern.size <= @offset

  def next_char
    @offset += 1
  end
end

インスタンス変数@patternは構文解析対象の文字列で、@offsetは現在の構文解析中の文字列上の位置です。
current_charは現在の構文解析中の文字を返すメソッドで、end?は末尾に到達しているかを判定するメソッドです。
next_charは構文解析中の文字を次に進めるメソッドです。

これらのメソッドを使って構文解析を行います。基本的には各構文の優先順位に従ってメソッドを呼び出していきます。

class KantanRegex::Parser
  # 構文解析の開始地点。
  def parse
    tree = parse_choice

    # 最後までちゃんと構文解析したかをチェックする。
    raise 'End-of-string is expected' unless end?
    tree
  end

  # 選択 (`a|b`) を構文解析するメソッド。
  def parse_choice
    children = []
    children << parse_concat

    while current_char == '|'
      next_char
      children << parse_concat
    end

    # `children`が1つしか無い場合は`Choice`を生成しない。
    return children.first if children.size == 1
    KantanRegex::Choice[children]
  end

  # 連接 (`ab`) を構文解析するメソッド。
  def parse_concat
    children = []

    until concat_stop?
      children << parse_repetition
    end

    # `children`が1つしか無い場合は`Concat`を生成しない。
    return children.first if children.size == 1
    KantanRegex::Concat[children]
  end

  # 現在の文字が連接を続けるべきか判定するメソッド。
  def concat_stop? =
    end? || current_char == ')' || current_char == '|'

  # 繰り返し (`a*`, `a+`, `a?`) を構文解析するメソッド。
  def parse_repetition
    child = parse_group

    quantifier =
      case current_char
      when '*' then :star
      when '+' then :plus
      when '?' then :question
      else nil
      end
    return child unless quantifier
    next_char

    KantanRegex::Repetition[child, quantifier]
  end

  # グループ化 (`(a)`) を構文解析するメソッド。
  def parse_group
    return parse_literal if current_char != '('
    next_char

    child = parse_choice

    raise '")" is expected' if current_char != ')'
    next_char

    child
  end

  # 文字リテラルやエスケープ文字を構文解析するメソッド。
  def parse_literal
    if current_char == '\\'
      next_char
      raise 'Missing escaped character' if end?

      value = current_char
      case value
      when '(', ')', '*', '+', '?', '|', '\\'
        next_char
      else
        raise 'Unsupported escaped character'
      end

      return KantanRegex::Literal[value]
    end

    value = current_char
    case value
    when '(', ')', '*', '+', '?', '|', '\\'
      raise 'Invalid literal character'
    else
      next_char
    end

    KantanRegex::Literal[value]
  end
end

KantanRegex::Parserクラスの作成とparseメソッドの呼び出しを一度に行うKantanRegex.parseメソッドを追加しておきます。

class KantanRegex::Parser
  def self.parse(pattern) =
    KantanRegex::Parser.new(pattern).parse
end

最後にirbからこれを使ってみます。

irb(main):001> load './kantan-regex/parser.rb'
=> true
irb(main):002> KantanRegex::Parser.parse('a*')
=>
#<data KantanRegex::Repetition
 child=#<data KantanRegex::Literal value="a">,
 quantifier=:star>
irb(main):003> KantanRegex::Parser.parse('(a|b)*c')
=>
#<data KantanRegex::Concat
 children=
  [#<data KantanRegex::Repetition
    child=
     #<data KantanRegex::Choice
      children=
       [#<data KantanRegex::Literal value="a">,
        #<data KantanRegex::Literal value="b">]>,
    quantifier=:star>,
   #<data KantanRegex::Literal value="c">]>

正しく動作してそうです。

作って学ぶ正規表現エンジン

正規表現のパーサー

抽象構文木 (AST)

パーサーの実装