株式会社GA technologies
🤖

簡易な正規表現エンジンを実装する

YuheiNakasaka
に公開
Ruby
アルゴリズム
正規表現
計算理論
オートマトン
tech

GA technologiesでソフトウェアエンジニアをしている中坂です。

先日社内で正規表現エンジンの実装の話題で盛り上がりました。ソフトウェアエンジニアであれば普段の開発の中では当たり前のように正規表現を使っていると思いますので、記法や挙動に関する知識はある程度持っているはずです。しかしながら、具体的に我々の書いた正規表現がいかにしてテキストにマッチするのか、その内部の仕組みまで理解している人は多くないと思います。

今回は「正規表現エンジン」の実装を実際に示しながら、普段当たり前のように書いている正規表現がどのように処理されているのかを深掘っていきます。

全体の流れ

この記事は少々長いので、まず最初に正規表現エンジンを実装するまでの流れをザッと書いておきます。

はじめは正規表現エンジンを理解するために必要な基礎知識として有限オートマトンの概念を説明します。有限オートマトンには主に決定性有限オートマトン(DFA)と非決定性有限オートマトン(NFA)の2種類がありますが、今回はNFAを使って実装を進めます。

次に正規表現とNFAの関係について説明します。正規表現はNFAに変換できることが知られています。この変換手法としてThompsonの構成法を用います。この手法を理解することでNFAと正規表現の関係がより深く理解できるはずです。

一通り必要な解説を行った後、正規表現エンジンの実装を以下の5つのステップで進めていきます。

  1. NFAの実装
    • 状態と状態遷移を表現するクラスを作成
  2. 字句解析器(レキサー)の実装
    • 正規表現文字列をトークン列に分解
  3. 構文解析器(パーサー)の実装
    • トークン列を抽象構文木(AST)に変換
  4. ASTからNFAへの変換
    • Thompsonの構成法を使ってASTをNFAに変換
  5. マッチング処理の実装
    • NFAを使ってテキストが正規表現にマッチするか判定

実装はRubyで行います。入力文字は ASCII文字のアルファベットと記号(\以外) を受け入れ、機能としては和集合・連接・連接閉包(正規表現記号としては|・*・(・)のみ)の完全一致のパターンに絞り、正規表現エンジンの理解しやすさに焦点を当てます。

有限オートマトンとは

有限オートマトンは、記号列を1文字ずつ読み込みながら状態を遷移させ、最終的にその記号列を受理するか拒否するかを判定する計算モデルです。

有限オートマトンは以下の要素で構成されます。

  1. 状態の有限集合
    • オートマトンが取りうる全ての状態
  2. 入力となる有限のアルファベット
    • 処理対象となる文字の集合
  3. 状態遷移関数
    • 現在の状態と入力文字から次の状態を決定するルール
  4. 初期状態
    • オートマトンの開始状態
  5. 受理状態の集合
    • 文字列が受理される状態

厳密な定義を理解出来ずとも、直感的には下記のような状態遷移図で表されるものとして理解しておけば良いです。

例えばこの遷移図はq0やq1などの丸が状態を表し、左の矢印から始まります。aなどの文字が書いてある矢印はその入力文字によってどの状態に遷移するかを表し、二重丸は受理状態の状態を表しています。最後に辿り着いた場所が二重丸であれば受理されます。

なのでこの遷移図の場合、aやabやabbやabbbbbbbbbbを受理しますがbやbaは拒否されます。

ネタバレになってしまうのですが、これはつまり正規表現としてはab*と書けます。「aから始まりbを0個以上含む文字列の集合」を表現しているわけですね。

DFAとNFA

有限オートマトンには主に2つの種類があります。

DFA(Deterministic Finite Automaton: 決定性有限オートマトン) は、ある状態である文字を読んだとき、次の状態が必ず一意に決まります。つまり、どの時点でも次に進む道が1つしかありません。

一方、NFA(Non-deterministic Finite Automaton: 非決定性有限オートマトン) は、同じ状態で同じ文字を読んでも複数の遷移先を持つことができます。下記の図ではq0の時にaがq0とq1の2パターンの遷移の可能性があります。


さらに、NFAにはε遷移(イプシロン遷移)と呼ばれる、入力を消費せずに状態を遷移できる特殊な遷移があります。例えば下記の遷移図ではεの部分は入力文字に関わらず自由に遷移して良いので一気にq2まで遷移できます。なのでacやbcやabcが受理されるのはもちろんcだけでも受理されます。

NFAは各状態で一意に遷移先が決まらないので一見すると複雑に見えますが、結局は有限なので実装上は「取りうる全ての状態」を同時に追跡することで処理できます。

厳密な証明は省きますが、なんとDFAとNFAは表現能力が等価です。つまりどんなNFAもDFAに変換でき、逆もまた真です(詳しくは計算理論とオートマトン言語理論[第2版]などの教科書を読んでください)。

NFAをゴニョゴニョ書き換えるとDFAになるし、DFAをゴニョゴニョするとNFAにもできるというのはなんとも驚きですね...。

正規表現とNFA

ここで今まで当たり前のように使ってきた正規表現をもう少し具体的に表現すると、正規表現とは入力アルファベットの記号に3種類の演算を次々と施してできる式であり、3種類の演算とは和集合・連接・連接閉包です。

お馴染みの正規表現として書き下した方がわかりやすいと思うのでそれぞれ例を挙げてみると下記です。

  • 和集合
    • a|b(aという文字もしくはbという文字というor的な処理)
  • 連接
    • ab(aという文字とbという文字を繋げる処理)
  • 連接閉包(クリーネ閉包と言ったりもする)
    • a*(aという文字の0以上の連続を表す処理)

この正規表現で表現される式が実は有限オートマトンと等価であることが知られています(詳しくは計算理論とオートマトン言語理論[第2版]などの教科書を読んでください)。

ですので今回正規表現エンジンを実装する際は、任意の正規表現を取り、それをNFAに変換することができれば、あとは入力文字列をNFAに流し込めば受理or拒否が判定でき、いわゆる正規表現によるマッチングの判定ができるという算段になります。

Thompsonの構成法

正規表現をNFAに変換する代表的な手法がThompsonの構成法です。この方法により作成されるNFAは全て開始状態と受理状態を持ち、正規表現の構造に対応する形でそれらNFAを再帰的に組み合わせて全体のNFAを構築します。

正規表現の基本要素に対応する各種NFAの構築ルールは以下の通りです。各種正規表現と状態遷移図も併記しました。図の作り方が下手すぎて見づらいと思いますが、実装を読むと実際に左側の正規表現を右側の状態遷移図へと変換していることが理解できるはずです。

1. 単一の文字

開始状態から文字で遷移して受理状態に到達する2状態を持つNFAです。rといった単一の文字を表せます。

1文字ですが開始状態と受理状態を持つNFAであるという点が重要なポイントです。

文字は直感的には状態が1つしか無いように思えてしまうのですが、このように実装することで以下の2~4における演算時に受理状態を別の状態の開始状態に接続してまた別のNFAを構築する、といったレゴブロックのようなことができるパーツとして取り回しやすくなります。

自分は実装時にここの理解が甘くて少し苦労しました。

2. 連接

r1のNFAの受理状態からr2のNFAの開始状態へ接続します。r1r2といった2文字以上の文字を表現できます。

3. 和集合

新しい開始状態からr1とr2のNFAへε遷移で分岐し、両者の受理状態を新しい受理状態へε遷移で統合します。

4. 連接閉包

新しい開始状態からrのNFAへε遷移、rのNFA受理状態から自身の開始状態へε遷移(1回以上の繰り返し)、さらに新しい開始状態から直接受理状態へのε遷移(0回の繰り返し)です。

この構築ルールに従うことで、複雑な正規表現も段階的にNFAに変換できます。

とはいえ実際のコードを見てみないとイメージがつかないと思うので、以降ではいよいよ実装へと進みます。

実装の流れ

正規表現エンジンの実装は、以下の5つのステップに分けられます。

  1. 字句解析器の実装
    正規表現の文字列を意味のあるトークンに分解します。例えば(はLEFT_PAREN、*はREPEATといった具合です。
  2. 構文解析器の実装
    トークン列を解析して抽象構文木(AST)を構築します。演算子の優先順位は* > 連接 > |で処理します。
  3. NFAの実装
    NFAのデータ構造(State、遷移関数など)を実装します。
  4. ASTからNFAへの変換
    Thompsonの構成法を使って、ASTの各ノードに対応するNFAを再帰的に構築します。
  5. マッチング処理の実装
    構築したNFAを使って、入力テキストがパターンにマッチするかを判定します。NFAの特性上、取りうる全ての状態を同時に追跡します。

以降では、実際のRubyコードを示しながら各ステップの詳細を解説していきます。

ちなみに1と2は言語処理系の実装の知識を前提としています。正規表現とは直接関係ないので解説は最小限にとどめています。もし正規表現に限った実装だけに興味がある人は3以降に進んでください。

字句解析の実装

字句解析器(レキサー)は正規表現の文字列を読み込んで、意味のある単位(トークン)に分解する役割を担います。

トークンの定義

まず、トークンを表現するクラスを定義します。

class Token
  attr_accessor :type, :value

  def initialize(type, value)
    @type = type
    @value = value
  end

  def to_s
    "#{@type}: #{@value}"
  end
end

トークンはtype(トークンの種類)とvalue(値)を持ちます。例えば、文字aはtypeが:charで value:が'a'というトークンになります。

レキサーの実装

次に、レキサーを実装します。

class Lexer
  SPECIAL_CHARS = {
    '|' => :or,
    '*' => :repeat,
    '(' => :left_paren,
    ')' => :right_paren,
  }

  def initialize(pattern)
    @pattern = pattern
    @pos = 0
  end

  def tokenize
    tokens = []
    while @pos < @pattern.length
      char = @pattern[@pos]

      if SPECIAL_CHARS.key?(char)
        tokens << Token.new(SPECIAL_CHARS[char], nil)
      else
        tokens << Token.new(:char, char)
      end

      @pos += 1
    end

    tokens << Token.new(:eof, nil)
    tokens
  end
end

レキサーは正規表現文字列を1文字ずつ読み込み、特殊文字(|, *, (, ))を対応するトークンタイプに変換します。それ以外の文字は:charタイプのトークンとして扱います。最後に:eofトークンを追加して、パーサーが文字列の終わりを認識できるようにしています。

ここで定義したトークンのタイプ名などに決まったルールはないので自前で勝手に決めて定義して問題ないです。

このレキサーがうまく動くと、例えば正規表現(a|b)*cを字句解析すると、以下のような感じでトークン列が生成されます。

lexer = Lexer.new("(a|b)*c")
tokens = lexer.tokenize
tokens.each { |token| puts token }
# left_paren:
# char: a
# or:
# char: b
# right_paren:
# repeat:
# char: c
# eof:

このトークン列が、次のステップであるパーサーへの入力となります。

構文解析器の実装

構文解析器(パーサー)は、レキサーが生成したトークン列を解析して、抽象構文木(AST: Abstract Syntax Tree)を構築します。ここで出力されるASTは正規表現の構造を木構造で表現したものです。

再帰下降構文解析

今回のパーサーでは再帰下降構文解析(Recursive Descent Parsing)という手法を使います。これは文法規則を再帰的な関数呼び出しで表現する、シンプルで理解しやすい構文解析手法です。

これもRui Ueyamaさんの低レイヤを知りたい人のためのCコンパイラ作成入門の文法の記述方法と再帰下降構文解析が参考になります。

ASTノードの定義

まず、ASTのノードを表現するクラスを定義します。

class ASTNode
  attr_accessor :type, :value, :left, :right

  def initialize(type, value, left = nil, right = nil)
    @type = type
    @value = value
    @left = left
    @right = right
  end

  def to_s
    case @type
    when :char
      value
    when :concat
      "#{@left}#{@right}"
    when :or
      "(#{@left}|#{@right})"
    when :repeat
      "#{@left}*"
    end
  end
end

パーサーの実装

次に、パーサー本体を実装します。

class Parser
  def initialize(tokens)
    @tokens = tokens
    @pos = 0
  end

  def parse
    result = parse_or
    if current_token.type != :eof
      raise "Failed to parse"
    end
    result
  end

  private

  def current_token
    @tokens[@pos] || Token.new(:eof, nil)
  end

  def consume(expected_type = nil)
    token = current_token
    if expected_type && token.type != expected_type
      raise "Expected #{expected_type} but got #{token.type}"
    end
    @pos += 1
    token
  end

  # 和集合(|)の解析: 最も優先順位が低い
  def parse_or
    left = parse_concat

    while current_token.type == :or
      consume(:or)
      right = parse_concat
      left = ASTNode.new(:or, nil, left, right)
    end

    left
  end

  # 連接の解析
  def parse_concat
    nodes = []

    # 文字か左括弧が続く限り、ノードを収集
    while [:char, :left_paren].include?(current_token.type)
      nodes << parse_repeat
    end

    return nil if nodes.empty?

    # 収集したノードを左結合で連結
    nodes.reduce do |left, right|
      ASTNode.new(:concat, nil, left, right)
    end
  end

  # 連接閉包(*)の解析
  def parse_repeat
    node = parse_atom

    while current_token.type == :repeat
      consume(:repeat)
      node = ASTNode.new(:repeat, nil, node, nil)
    end

    node
  end

  # 基本要素(文字または括弧)の解析: 最も優先順位が高い
  def parse_atom
    case current_token.type
    when :char
      char = consume(:char)
      ASTNode.new(:char, char.value, nil, nil)
    when :left_paren
      consume(:left_paren)
      node = parse_or
      consume(:right_paren)
      node
    else
      raise "Unexpected token: #{current_token.type}"
    end
  end
end

この実装では例えば(a|b)*cというトークン列を解析すると、雑ですが以下のようなASTが構築されます。

      concat
      /    \
   repeat   c
     |
     or
    /  \
   a    b

この木構造は、「aまたはbの0回以上の繰り返しの後にcが続く」という正規表現の意味を正確に表現しています。

パーサーがparse関数を呼び出すと、まずparse_orが呼ばれ、それがparse_concatを呼び、さらにparse_repeat、parse_atom, parse_or...と再帰的に呼び出されていきます。この再帰呼び出しの連鎖により、演算子の優先順位が自然に処理されます。

NFAの実装

正規表現の式がASTへと変換できたので次はNFAを実装していきます。

状態とNFAの基本クラス

まず、NFAの状態を表現するStateクラスを定義します。状態遷移図でいうと丸いやつとその丸から伸びる矢印と文字です。

class State
  attr_accessor :transitions, :is_final

  def initialize
    @transitions = Hash.new { |hash, key| hash[key] = [] }
    @is_final = false
  end

  def add_transition(char, state)
    @transitions[char] << state
  end

  def get_transitions(char)
    @transitions[char]
  end
end

Stateクラスは、遷移先の状態を文字ごとにHashで管理します。nilをキーとする遷移はε遷移を表します(このアイデアはアンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまでという本を参考にしています。多謝🙏)。is_finalフラグは、この状態が受理状態かどうかを示します。

次に、NFAそのものを表現するNFAクラスを定義します。

class NFA
  attr_accessor :start, :accept

  def initialize(start_state, accept_state)
    @start = start_state
    @accept = accept_state
  end
end

NFAは開始状態と受理状態を持つだけのシンプルな構造です。先に解説した通り、Thompsonの構成法では各NFAが必ず1つの開始状態と1つの受理状態を持つという性質を利用します。

各種NFAの文字と演算の実装

単一文字のNFA

class Char < NFA
  attr_accessor :char

  def initialize(char)
    @char = char
    start = State.new
    accept = State.new
    accept.is_final = true
    start.add_transition(@char, accept)
    super(start, accept)
  end

  def to_s
    "#{@char}"
  end
end

単一文字のNFAは、開始状態から単一文字で遷移して受理状態に到達する、最もシンプルな2状態のNFAです。

連接のNFA

class Concat < NFA
  attr_accessor :left, :right

  def initialize(left, right)
    @left = left
    @right = right
    @left.accept.is_final = false
    @left.accept.add_transition(nil, @right.start)
    super(@left.start, @right.accept)
  end

  def to_s
    "#{@left}#{@right}"
  end
end

連結abのNFAは、aのNFAの受理状態からbのNFAの開始状態へε遷移で接続します。これにより、「aを読んでからbを読む」という動作が実現されます。

和集合のNFA

class Or < NFA
  attr_accessor :nfa1, :nfa2

  def initialize(nfa1, nfa2)
    @nfa1 = nfa1
    @nfa2 = nfa2
    start = State.new
    accept = State.new
    accept.is_final = true

    @nfa1.accept.is_final = false
    @nfa1.accept.add_transition(nil, accept)
    @nfa2.accept.is_final = false
    @nfa2.accept.add_transition(nil, accept)

    start.add_transition(nil, @nfa1.start)
    start.add_transition(nil, @nfa2.start)
    super(start, accept)
  end

  def to_s
    "(#{@nfa1}|#{@nfa2})"
  end
end

選択a|bのNFAは、新しい開始状態からaとbのNFAへε遷移で分岐します。どちらかのパスが成功すれば全体が成功します。

連接閉包のNFA

class Repeat < NFA
  attr_accessor :nfa

  def initialize(nfa)
    @nfa = nfa
    start = State.new
    accept = State.new

    start.add_transition(nil, accept)
    start.add_transition(nil, @nfa.start)
    @nfa.accept.is_final = false
    @nfa.accept.add_transition(nil, @nfa.start)
    @nfa.accept.add_transition(nil, accept)
    accept.is_final = true
    super(start, accept)
  end

  def to_s
    "#{@nfa}*"
  end
end

これらのクラスを組み合わせることで、任意の正規表現をNFAに変換できます。

例えば(a|b)*cというパターンは、Repeat(Or(Char('a'), Char('b')))とChar('c')をConcatで結合して表現されます。

ASTからNFAへの変換

パーサーが構築したASTをThompsonの構成法を使ってNFAに変換します。この変換は、ASTを深さ優先探索で走査しながら、各ノードに対応するNFAを再帰的に構築することで実現できます。

ASTToNFAクラスの実装

class ASTToNFA
  def build(ast)
    return nil if ast.nil?

    case ast.type
    when :char
      build_char(ast)
    when :concat
      build_concat(ast.left, ast.right)
    when :or
      build_or(ast.left, ast.right)
    when :repeat
      build_repeat(ast.left)
    else
      raise "Unexpected type: #{ast.type}"
    end
  end

  private

  def build_char(ast)
    Char.new(ast.value)
  end

  def build_concat(left, right)
    left_nfa = build(left)
    right_nfa = build(right)
    Concat.new(left_nfa, right_nfa)
  end

  def build_or(left, right)
    left_nfa = build(left)
    right_nfa = build(right)
    Or.new(left_nfa, right_nfa)
  end

  def build_repeat(left)
    left_nfa = build(left)
    Repeat.new(left_nfa)
  end
end

このクラスは非常にシンプルです。ASTの各ノードタイプに対応するbuild_*メソッドを呼び出し、それぞれが対応するNFAクラス(Char、Concat、Or、Repeat)のインスタンスを返します。

例えば、(a|b)*cのAST(Concat(Repeat(Or(Char('a'), Char('b'))), Char('c')))は以下のように変換されます。

  1. ルートのconcatノードを処理
  2. 左側の子ノードrepeatを処理
    • その子ノードorを処理
      • aのChar NFAを構築
      • bのChar NFAを構築
      • これらをOr NFAで結合
    • Or NFAをRepeat NFAで包む
  3. 右側の子ノードcを処理
    • cのChar NFAを構築
  4. Repeat NFAとChar NFAをConcat NFAで結合

この再帰的な処理により、複雑な正規表現が段階的にNFAに変換されていきます。

レキサー、パーサー、ASTからNFAへの変換を組み合わせると、下記のような実装で正規表現文字列からNFAを構築できます。

tokens = Lexer.new("(a|b)*c").tokenize
ast = Parser.new(tokens).parse
nfa = ASTToNFA.new.build(ast)

これで正規表現(a|b)*cが完全なNFAに変換されます。あとはこのNFAを使ってテキストのマッチング処理を実装すれば、正規表現エンジンが完成します。

マッチング処理の実装

いよいよ最後のステップです。構築したNFAを使って入力テキストが正規表現にマッチするかを判定します。

NFAの非決定性とε閉包

NFAは非決定性を持つため、ある時点で複数の状態を同時に取りうることを思い出してください。さらにε遷移により入力を消費せずに複数の状態に到達できます。

そのためマッチング処理では以下を実装します。

  1. ε閉包の計算
    • ある状態集合からε遷移だけで到達可能な全ての状態を計算
  2. 状態集合の管理
    • 各文字を読むたびに現在取りうる全ての状態を追跡
  3. 受理判定
    • 最終的な状態集合に受理状態が含まれていれば文字列を受理

Evaluatorクラスの実装

class Evaluator
  attr_accessor :nfa

  def initialize(nfa)
    @nfa = nfa
  end

  def match?(text)
    return false if @nfa.nil?

    current_states = epsilon_closure([@nfa.start])

    text.each_char do |char|
      next_states = Set.new

      current_states.each do |state|
        state.get_transitions(char).each do |next_state|
          next_states.add(next_state)
        end
      end

      current_states = epsilon_closure(next_states)

      return false if current_states.empty?
    end

    current_states.any?(&:is_final)
  end

  private

  def epsilon_closure(states)
    closure = Set.new(states)
    stack = states.to_a

    while !stack.empty?
      state = stack.pop

      state.get_transitions(nil).each do |next_state|
        unless closure.include?(next_state)
          closure.add(next_state)
          stack.push(next_state)
        end
      end
    end

    closure
  end
end

epsilon_closureメソッドは、スタックを使った探索でε遷移で遷移可能な全ての状態を見つけ出します。これにより、入力を消費せずに到達可能な全ての状態を効率的に列挙できます。

例えば、a*のNFAでは、開始状態からε遷移で複数の状態に同時に存在できるため、ε閉包の計算が不可欠です。

完成した正規表現エンジン

これまでの全てのコンポーネントを統合すると、完全な正規表現エンジンが完成します。

class RegexEngine
  def initialize(pattern)
    @pattern = pattern
    compile
  end

  def match?(text)
    Evaluator.new(@nfa).match?(text)
  end

  private

  def compile
    tokens = Lexer.new(@pattern).tokenize
    ast = Parser.new(tokens).parse
    @nfa = ASTToNFA.new.build(ast)
  end
end

使用例

engine1 = RegexEngine.new("(a|b)*c")
puts engine1.match?("c")     # => true
puts engine1.match?("ac")    # => true
puts engine1.match?("bc")    # => true
puts engine1.match?("abc")   # => true
puts engine1.match?("aabbc") # => true
puts engine1.match?("ab")    # => false
puts engine1.match?("d")     # => false

engine2 = RegexEngine.new("a|b|c")
puts engine2.new("a|b|c").match?("a")   # => true
puts engine2.new("a|b|c").match?("b")   # => true
puts engine2.new("a|b|c").match?("c")   # => true
puts engine2.new("a|b|c").match?("ab")  # => false
puts engine2.new("a|b|c").match?("ac")  # => false
puts engine2.new("a|b|c").match?("bc")  # => false
puts engine2.new("a|b|c").match?("abc") # => false

engine3 = RegexEngine.new("a(b|c)")
puts engine3.match?("ab")  # => true
puts engine3.match?("ac")  # => true
puts engine3.match?("bc")  # => false
puts engine3.match?("abc") # => false
puts engine3.match?("a")   # => false
puts engine3.match?("b")   # => false
puts engine3.match?("c")   # => false

正規表現が概ね正しく動作していることが確認できました!!!!!

今回実装した完全なソースコードは以下になります。
https://github.com/YuheiNakasaka/tiny-regexp-rb

最後に

この記事では簡単な正規表現エンジンを一から実装することでオートマトンと正規表現の関係や正規表現を文字列にマッチさせる仕組みを実践的に理解しました。

今回は*や|といった基本的な記号しか実装しなかったですが+や?もこの実装の延長線上にあるので追加して自作することもできます。

とはいえここまでで学んだ知識だけで実用的な正規表現エンジンが実装できるかというとそうではないです。例えば現代的なプログラミング言語に搭載されている正規表現エンジンではざっとリストアップするだけでも下記のような高度な機能があります。

  • 文字クラス([a-z]、\dなど)
  • 量化子(+、?、{n,m}など)
  • キャプチャグループ
  • 後方参照
  • 行頭/行末のアンカー(^、$)
  • 最長一致と最短一致

これらの機能の中には今回実装したNFA型の正規表現エンジンでは実現できないものもあります(例えば後方参照。NFAでは過去のマッチ結果を再度参照することが理論上できません。NFAはチョムスキー階層でいうところの正規言語しか表現できないですが、後方参照は文脈自由文法の範囲。詳しくはリンクの教科書を読んでください。)。

ではどのように実装するのかというと、一種のVMを実装し、そのVMのバイトコードに正規表現をコンパイルしてからVM内でマッチングを行うというVM型の正規表現エンジンを使います。このマッチングではパターンにマッチするまでバックトラッキングという手法を使いながらマッチするまで全探索させます。(詳しくはRegular Expression Matching: the Virtual Machine Approachを読んでください)。この仕組みがいわゆるReDoSに繋がったりします。

今回はシンプルな正規表現エンジンの実装に絞りましたが、このように正規表現エンジンから派生してまだまだ解説できていない技術や分野がたくさん広がっています。詳しくは計算理論や形式言語理論の教科書などを読んでみてください。

個人的にはまずアンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまでをお勧めします。今回実装したようなオートマトンからチューリングマシンや停止問題などの理論的な話がRubyによる実装を以て解説されており非常に理解しやすいです(特にラムダ計算だけでFizzBuzzコードを書いている章は圧倒されます...)。

GA technologiesではこのように普段当たり前のように利用している技術を自作して深くまで学ぶことができる心意気のあるソフトウェアエンジニアを求めています。もし興味があれば下記のリンク、もしくは私のXのアカウントまでご連絡ください。

https://ga-technologies-engineering.notion.site/GA-technologies-9794c78bc56c4011a03f7f3dcf91a18f

参考リンク

株式会社GA technologies
株式会社GA technologies

株式会社GA technologiesの公式アカウントです。 「テクノロジー×イノベーションで驚きと感動を生み、世界を前進させる。」を理念に掲げ、不動産をはじめ、さまざまな産業のビジネス変革に取り組んでいます。

Discussion