Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2017年02月18日

[]行指向 HTML5 タグ用の正規表現エンジン

これは HTML5 タグを行指向でタグの前のインデント空白列と、 タグの後の行末空白と改行コードも含めて行全体にマッチングさせたい用途向けに組んだ、 特定パターン専用の正規表現エンジンです。 タグ名と要素の文字位置をリストアップすることができます。

素朴なバックトラック仮想マシンにカスタム化した文字クラス判定命令と、 文字位置をリストアップするための限定されたキャプチャ機能をもっています。 汎用のキャプチャ機能を組み込むと大げさになりすぎるので、 必要最小限にして単純化してあります。

仮想マシンの文字照合命令は N. Wirth の表駆動 LL(1) 解析器から、 バックトラック制御命令は PEG 用仮想マシン Ierusalimschy VM から取り入れて、 その上に簡易キャプチャ機能を追加しました。 なお、 前者は 「アルゴリズム+データ構造=プログラム 第一版」(1976)、 もしくは後に章を切り分けて独立させた「翻訳系構成法序論」(1984) に記載されています。 この書籍の英文原文の電子版が Wirth 教授のウェブページで公開されていますが、 現在の版では紹介文程度で説明が乏しいため古い版を当たった方が良いでしょう。

enum {
    EPSILON = 0, PCHAR = 1, NCHAR = 2, NSTART = 3, SPACE = 4, BLANK = 5,
    LF = 10, CR = 13, BOL = 16, SPLIT = 17, JOIN = 18, MATCH = 19,
    MARK0 = 20, MARK1 = 21, SAVE = 22
};

struct instruction_type {
    char sym;
    unsigned char succ;
    unsigned char fail;
};

static inline int
ord (std::string const& str, std::size_t s, std::size_t eos)
{
    return s < eos ? static_cast<unsigned char> (str[s]) : 0;
}

static inline int
code (int const c)
{
    return c > 128 ? 7 : CODE_TABLE[c];
}

static bool
scanloop_html5tag (std::string const& str, std::size_t& pos, std::vector<std::size_t>& capture)
{
    struct trail_type {
        unsigned int ctl;
        std::size_t pos;
        std::size_t mark0;
        std::size_t mark1;
        std::size_t cap;
    };
    std::vector<trail_type> trail;
    std::size_t mark0, mark1;
    std::size_t const eos = str.size ();
    unsigned int ctl = 0;
    do {
        bool succ = true;
        int sym = PATTERN[ctl].sym;
        switch (sym) {
        case EPSILON:
            break;
        case BOL:
            succ = (pos == 0 || '\n' == ord (str, pos - 1, eos));
            break;
        case SPLIT:
            trail.push_back ({PATTERN[ctl].fail, pos, mark0, mark1, capture.size ()});
            break;
        case JOIN:
            trail.pop_back ();
            break;
        case MATCH:
            return true;
        case MARK0:
            mark0 = pos;
            break;
        case MARK1:
            mark1 = pos;
            break;
        case SAVE:
            capture.push_back (mark0);
            capture.push_back (mark1);
            break;
        default:
            if (sym <= BLANK)
                succ = (code (ord (str, pos, eos)) & (1U << (sym - 1U))) != 0;
            else
                succ = (ord (str, pos, eos) == sym);
            if (succ)
                ++pos;
            break;
        }
        ctl = succ ? PATTERN[ctl].succ : PATTERN[ctl].fail;
        if (ctl == 0 && ! trail.empty ()) {
            ctl = trail.back ().ctl;
            pos = trail.back ().pos;
            mark0 = trail.back ().mark0;
            mark1 = trail.back ().mark1;
            capture.resize (trail.back ().cap);
            trail.pop_back ();
        }
    } while (ctl > 0);
    capture.clear ();
    return false;
}

動かすには、 パターン・マッチングのための命令列と文字クラス集合の判定表が必要です。 命令列は正規表現を直訳したような代物です。 文字クラス集合の要素は一つ一つがビットベクトルになっていて、 文字が属する文字集合に対応するビットを立ててあります。

命令は第一欄が文字・文字集合・制御命令コード、 第二欄が成功時に次に実行する命令の番地、 第二欄は失敗時に次に実行する命令の番地が入ります。 飛び先の番地は絶対アドレスです。 ただし、 ゼロ番地は失敗を表しておりジャンプ先番地ではありません。 例えば、 2番地は現在の文字位置の文字が BLANK 文字集合の要素だったら 2 番地を繰り返し、 要素でないときは次の 3 番地へ移す命令になっています。 このように成功時と失敗時の飛び先番地を文字照合命令から得るのが Wirth の LL(1) マシンのやりかたです。 Wirth のマシンにはバックトラックに対応していないので、 そこは Ierusalimschy VM の SPLIT 命令と JOIN 命令を使っています。 SPLIT 命令は第二欄から失敗時の再試行命令の入る番地をとりだして他の状況変数と一緒に記録します。 JOIN 命令は失敗時用の記録を一つ廃棄します。 キャプチャは 2 つのマーク変数へ一時的に記録し、 確定した段階で SAVE 命令でキャプチャリストへ追加します。 SPLIT 時点でキャプチャリストの長さを記録しており、 バックトラックのときにキャプチャリストを切り詰めます。

static const instruction_type PATTERN[] = {
    /*  0*/ {SPLIT,   1U,  4U},
    /*  1*/ {BOL,     2U,  0U},
    /*  2*/ {BLANK,   2U,  3U},
    /*  3*/ {JOIN,    4U,  0U},
    /*  4*/ {'<',     5U,  0U},
    /*  5*/ {MARK0,   6U,  0U},
    /*  6*/ {NSTART,  7U, 36U},
    /*  7*/ {NCHAR,   7U,  8U},
    /*  8*/ {MARK1,   9U,  0U},
    /*  9*/ {SAVE,   10U,  0U},
    /* 10*/ {SPACE,  11U, 34U},
    /* 11*/ {SPACE,  11U, 12U},
    /* 12*/ {MARK0,  13U,  0U},
    /* 13*/ {NSTART, 14U, 34U},
    /* 14*/ {NCHAR,  14U, 15U},
    /* 15*/ {MARK1,  16U,  0U},
    /* 16*/ {SPLIT,  17U, 33U},
    /* 17*/ {SPACE,  17U, 18U},
    /* 18*/ {'=',    19U,  0U},
    /* 19*/ {JOIN,   20U,  0U},
    /* 20*/ {SPACE,  20U, 21U},
    /* 21*/ {'"',    22U, 24U},
    /* 22*/ {'"',    32U, 23U},
    /* 23*/ {PCHAR,  22U,  0U},
    /* 24*/ {'\'',   25U, 27U},
    /* 25*/ {'\'',   32U, 26U},
    /* 26*/ {PCHAR,  25U,  0U},
    /* 27*/ {'`',    28U, 30U},
    /* 28*/ {'`',    32U, 29U},
    /* 29*/ {PCHAR,  28U,  0U},
    /* 30*/ {NSTART, 31U,  0U},
    /* 31*/ {NCHAR,  31U, 32U},
    /* 32*/ {MARK1,  33U,  0U},
    /* 33*/ {SAVE,   10U,  0U},
    /* 34*/ {'/',    35U, 35U},
    /* 35*/ {'>',    44U,  0U},
    /* 36*/ {'/',    37U,  0U},
    /* 37*/ {MARK0,  38U,  0U},
    /* 38*/ {NSTART, 39U,  0U},
    /* 39*/ {NCHAR,  39U, 40U},
    /* 40*/ {MARK1,  41U,  0U},
    /* 41*/ {SAVE,   42U,  0U},
    /* 42*/ {SPACE,  42U, 43U},
    /* 43*/ {'>',    44U,  0U},
    /* 44*/ {SPLIT,  45U, 50U},
    /* 45*/ {BLANK,  45U, 46U},
    /* 46*/ {LF,     49U, 47U},
    /* 47*/ {CR,     48U,  0U},
    /* 48*/ {LF,     49U, 49U},
    /* 49*/ {JOIN,   50U,  0U},
    /* 50*/ {MATCH,   0U,  0U},
};

static const unsigned char CODE_TABLE[128] = {
    0,  0,  0,  0,  0,  0,  0,  0,  0,25U, 9U,  0,  0, 9U,  0,  0,
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  25U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 3U, 3U, 1U,
   3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 7U, 1U,  0, 1U,  0, 1U,
   1U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,
   7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 1U, 1U, 1U, 1U, 7U,
   1U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,
   7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 1U, 1U, 1U, 1U,  0
};

2017年02月15日

[]丸括弧解釈あり演算子優先度構文解析

LR 遷移表を作らず、 二項演算子へ左右の結合度と演算子優先度を指定し、 演算子の結合優先度の比較から数式の構文解析をおこなう Floyd の手法のコード例の多くは、 丸括弧で囲んだ数式を解析手続きの再帰呼び出しで処理しています。 これに対して、 丸括弧の部分もすべてまとめて上向き構文解析する方法を今朝の寝起きにふと思いついたので試してみたところ、 期待通りに動作しました。

例えば、 次の単純化した構文を考えてみます。

    %left '+'
    %left '*'
    E: E '+' E
    E: E '*'E
    E: '(' E' )'
    E: number

これの LR 状態遷移表を作ると非終端記号 E が一つだけのシンプルなものになります。 表内の数値はシフトと GOTO 先の状態番号を表し、 還元には生成項の右辺を書いています。 この表から、 終了記号は還元と受理、 二項演算子はシフトと還元の両方、 左丸括弧と数値リテラルはシフトだけをすることがわかります。 右丸括弧はシフトと還元の両方があるかのように見えますが、 シフトした直後の状態で必ず還元するため、 実質還元だけになっています。

        状態
        0   1   2   3   4   5   6   7   8   9
    --------------------------------------------------------
記  $     受理      n              E+E E*E (E)  還元と受理
号  )               n           9  E+E E*E (E)  実質還元だけ
    +       4       n           4  E+E E*E (E)  シフトと還元
    *       5       n           5   5  E*E (E)  シフトと還元
    (   2       2       2   2                   シフトだけ
    n   3       3       3   3                   シフトだけ
    --------------------------------------------------------
    E   1       6       7   8

Floyd の上向き解析器は、 二項演算子の左右のオペランドが必ずシフトしかしないことと、 シフトと還元は二項演算子同士の結合方向と優先度により決定することを利用しています。 Floyd の解析器は、 LR オートマトンの記号スタックのトップが右辺のオペランドになっている状況だけで駆動して、 右辺のオペランドはスタックの外の積算変数を束縛し、 スタック・トップの記号が二項演算子にしています。この状況で、 入力記号列の先頭は必ず二項演算子が顔をだしているので、 スタック・トップの二項演算子と入力記号列先頭のそれの結合方向と優先度を比較して、 還元するかどうかを決定します。 このため、 Floyd の手法は丸括弧式を直接解析できず、 そこに再帰下降を使わざるをえないわけです。

さて、 上の例の遷移表を使って、 Floyd の手法に関係している解析状況を抜き出してみると、 記号スタックの底と左丸括弧が同じ働きをすることがわかります。

      記号スタック     入力記号列
        $           (1+2+3)*4+5$ ( をシフト
        $(           1+2+3)*4+5$ 1 をシフト
        $(E           +2+3)*4+5$ + をシフト
        $(E+           2+3)*4+5$ 2 をシフト
        $(E+E           +3)*4+5$ E:E+E の還元
        $(E             +3)*4+5$ + をシフト
        $(E+             3)*4+5$ 3 をシフト
        $(E+E             )*4+5$ E:E+E の還元
        $(E               )*4+5$ ) のシフトと E:(E) の還元
        $E                 *4+5$ * のシフト
        $E*                 4+5$ 4 のシフト
        $E*E                 +5$ E:E*E の還元
        $E                   +5$ + のシフト
        $E+                   5$ 5 のシフト
        $E+E                   $ E:E+E の還元
        $E                     $ 受理

        $           2*(3+4+5)+6$ 2 をシフト
        $E           *(3+4+5)+6$ * をシフト
        $E*           (3+4+5)+6$ ( をシフト
        $E*(           3+4+5)+6$ 3 をシフト
        $E*(E           +4+5)+6$ + をシフト (* との比較なし)
        $E*(E+           4+5)+6$ 4 をシフト
        $E*(E+E           +5)+6$ E:E+E の還元
        $E*(E             +5)+6$ + をシフト
        $E*(E+             5)+6$ 5 をシフト
        $E*(E+E             )+6$ E:E+E の還元
        $E*(E               )+6$ ) のシフトと E:(E) の還元
        $E*E                 +6$ E:E*E の還元 (* との比較あり)
        $E                   +6$ + をシフト
        $E+                   6$ 6 をシフト
        $E+E                   $ E:E+E を還元
        $E                     $ 受理

このことから、 演算子優先度解析器のスタックへ左丸括弧もシフトしておけば、 再帰下降なしで丸括弧あり数式を解析可能だろうことが予想できます。 Floyd の手法を一般化した Pratt のトップダウン演算子優先度解析器を参考にしつつ、 上の解析状況に近くなるように処理を書き下してみると次のようになりました。 右辺のオペランドもスタックへ積むように変更し、 先読みトークンの arity が Binary と Centinel の場合に限り、 記号スタックのトップに二項演算子式があるかどうか調べ、 あるときは優先度をチェックして還元をおこないます。 右丸括弧は記号スタックに積まずに、 左丸括弧の対応関係が正しいときは、 ただちに還元して次のトークンへ進めます。

require 'strscan'

Token = Struct.new(:sym, :value)
SymDesc = Struct.new(:sym, :prec, :arity, :reduce)

STATE = [
  {:LParen => 0, :Literal => 1},
  {:Dollar => 2, :RParen => 1, :Binary => 0},
  {:Dollar => 2},
]
SYM = {
  '$' => SymDesc['$', 0, :Dollar,   nil],
  ')' => SymDesc[')', 0, :RParen,   nil],
  'L' => SymDesc['L', 2, :Literal,  nil],  # 数値リテラル
  '(' => SymDesc['(', 2, :LParen,   nil],
  '+' => SymDesc['+', 3, :Binary,   proc{|a,b,c| a + c }],
  '-' => SymDesc['-', 3, :Binary,   proc{|a,b,c| a - c }],
  '*' => SymDesc['*', 4, :Binary,   proc{|a,b,c| a * c }],
  '/' => SymDesc['/', 4, :Binary,   proc{|a,b,c| a / c }],
}

def next_token(scanner)
  scanner.skip(/[ ]+/)
  if scanner.empty?
    Token[SYM['$'], '$']
  elsif scanner.scan(/[()+\-*\/]/)
    Token[SYM[scanner.matched], scanner.matched]
  elsif scanner.scan(/[0-9]+/)
    Token[SYM['L'], scanner.matched.to_i]
  else
    raise SyntaxError, "WHAT?"
  end
end

def trace_stack(stack)
  puts 'stack=>$' + stack.map{|tk| tk.value.to_s }.join(' ')
end

def parse(scanner)
  token = next_token(scanner)
  state = STATE[0][token.sym.arity] or raise SyntaxError, "WHAT?"
  stack = []
  while true
    if token.sym.arity == :Binary || token.sym.prec == 0
      while stack.size >= 3 and stack[-2].sym.arity == :Binary
        break if stack[-2].sym.prec < token.sym.prec
        lhs, op, rhs = stack.pop(3)
        puts "reduce E:E#{op.sym.name}E"
        value = op.sym.reduce.call(lhs.value, op.value, rhs.value)
        stack.push Token[SYM['L'], value]
        trace_stack(stack)
      end
    end
    break if token.sym.name == '$'
    if token.sym.name == ')'
      if stack.size >= 2 and stack[-2].sym.name == '('
        lparen, value = stack.pop(2)
        stack.push value
        puts "reduce E:(E)"
      else
        raise SyntaxError, "unbalance ( and )"
      end
      #Note: NEVER push ')', '$'
      token = next_token(scanner)
    else
      puts "shift #{token.sym.name}:#{token.value}"
      stack.push token
      token = next_token(scanner)
    end
    state = STATE[state][token.sym.arity] or raise SyntaxError, "WHAT?"
    trace_stack(stack)
  end
  stack.size == 1 or raise SyntaxError, "unbalance ( and )"
  stack.last.sym.name == 'L' or raise SyntaxError, "WHAT?"
  stack.last.value
end

puts parse(StringScanner.new('2*(3+4+5)+6')) #=> 30

2017年02月07日

[]TAoCP 流その場書き換え B+ 木をノードあふれなしに

左側のポインタとキーをまとめるのか、 それとも右側のポインタとまとめるのか。 違いは些細なことですが、 実際にコードを記述してみると、 それぞれの書きやすいやりかたに差があるようです。 B+ 木の葉以外のノードが一致するキーを含んでいるとき、 左に隣接したポインタを辿って子ノードへ降ります。 そのことから、 B+ 木では左側のポインタとキーをまとめるのが自然に思えていたのですが、 この場合の挿入時に新しいノードを左側へ挿入し、 削除時に左側のノードを取り除く方がコードが素直になります。 一方、 右側のポインタとキーをまとめると、 新しいノードを右側へ挿入し、 右側のノードを取り除く方が素直になります。 左右のどちらにノードを追加・削除するかは、 コピー・モディファイ・ライトの場合は変更を加えるノードをすべて新しく割り当てるので違いは少なそうですけど、 その場書き換えでは事情が異なってきます。 B+ 木の場合、 葉同士のリンクを辿っていくシーケンシャルな走査を頻繁に加える用途に応用することが多いわけで、 その場合、 左へ挿入するモデルの場合、 ファイルの終わりから先頭へ向けてシークをしてノードを読み出す頻度が高くなります。 一方、 右へ挿入するモデルの場合、 ファイルの先頭から末尾へ向けてシークしてノードを読み出す頻度が高くなります。 後者の方がファイルシステムのバッファ・キャッシュに馴染みやすいだろうことは予想できるわけで、 その場書き換え B+ 木では、 キーと右側のポインタをまとめて、 ノードの挿入・削除を右側へおこなう方が有利だろうと考えられます。

昨日の B+ 木では、 ノードに格納可能なセル数よりも、 挿入・削除の途中で、 1 個分あふれてしまうことがありました。 今度は、 途中でもセルの個数があふれないように Bplus クラスを書き直します。

class Bplus
  ORDER = 5

  attr_accessor :root

  def initialize
    @root = alloc_node
  end

  def alloc_node() Node.new end
  def free_node(node) end

#@<store メソッドを定義します@>
#@<insert_cell メソッドを定義します@>
#@<overflow メソッドを定義します@>

  def erase(k)
    # ノードあふれ版と同じなので省略
  end

#@<underflow メソッドを定義します@>

  def trase(k)
    # ノードあふれ版と同じなので省略
  end
end

挿入では、 満杯でないときに単純にノードにセルを追加します。 満杯のときは、 ノードを分割してから、 分割された左右のノードのいずれか適切な方へセルを挿入します。 この分割とそれに続く挿入処理は、 overflow メソッドにおしつけます。

#@<store メソッドを定義します@>=
  def store(key, value)
    path, _, left, pos = trace(key)
    if pos > 0
      left[pos].ptr = value
      return self
    end
    pos = left.abs(pos)
    cell = Cell.new(key, value)
    left.keys_size >= ORDER - 1 or return insert_cell(left, pos, cell)
    cell = overflow(left, alloc_node(), pos, cell)
    while not path.empty?
      parent, dot = path.pop(2)
      parent.keys_size >= ORDER - 1 or return insert_cell(parent, dot, cell)
      cell = overflow(parent, alloc_node(), dot, cell)
    end
    left = @root
    @root = alloc_node()
    @root[0].ptr = left
    @root.insert(1, cell)
    self
  end

insert_cell メソッドで、 満杯でないときのセルの挿入をおこないます。 これは、 Node クラスの insert メソッドのデリゲータにすぎません。

#@<insert_cell メソッドを定義します@>=
  def insert_cell(node, pos, cell)
    node.insert(pos, cell)
    self
  end

overflow メソッドでは、 満杯のノードを left として、 それの右側に挿入する空のノード right とします。 left から right へセルを移し替えて、 空きを作ります。 まず、 葉として分割をおこない、 左右のいずれか適切な方へセルを挿入します。 その後に、 葉でないときのつじつま合わせをおこなうやりかたにします。 最後に、 親ノードへ挿入するセルを作って呼び出し元へ返します。

#@<overflow メソッドを定義します@>=
  def overflow(left, right, pos, cell)
    # とりあえず葉として分割します。
    cutpos = (ORDER + 1) / 2
    if pos < cutpos + 1
      right.rotate(left, cutpos ... ORDER, 1)
      left.insert(pos, cell)
    else
      right.rotate(left, cutpos + 1 ... ORDER, 1)
      right.insert(pos - cutpos, cell)
    end
    key = left[cutpos].key
    # 分割して挿入をした後に、 left のキーは (ORDER + 1) / 2 個、 right は ORDER / 2 個になります。
    if left.node?
      # 葉でないとき、 つじつま合わせをします。
      right[0].ptr = left[cutpos].ptr
      left.erase(cutpos)
    end
    Cell.new(key, right)
  end

underflow メソッドでノードのあふれが生じるのは、 left ノードが満杯のときでも、 間のキーのセルを left へ挿入していた部分でした。 そこを書き直し、 満杯でない方へ挿入するようにします。 この修正の影響が受け、 バランスをとるため左右のどちらへ向けてセルを移動するかを判定する条件が若干変化します。 変更箇所はそれだけで、 それ以外はあふれ許容版と同じです。

#@<underflow メソッドを定義します@>=
  def underflow(parent, pos)
    pos = parent.keys_size if pos > parent.keys_size
    left = parent[pos - 1].ptr
    right = parent[pos].ptr
    orig_left_count = left.keys_size
    left_count = (left.keys_size + right.keys_size + 1) / 2
    right_count = (left.keys_size + right.keys_size) / 2
    if left.node?
      if right_count < ORDER / 2 || left.keys_size < left_count
        left.insert(left.keys_size + 1, Cell.new(parent[pos].key, right[0].ptr))
      else
        right.insert(1, Cell.new(parent[pos].key, right[0].ptr))
      end
    end
    if right_count < ORDER / 2
      left.rotate(right, 1 ... right.keys_size + 1, left.keys_size + 1)
      parent.erase(pos)
      free_node(right)
    else
      d = (left.leaf?) ? 1 : 2
      if left.keys_size + 1 - d >= left_count
        right.rotate(left, left_count + d ... left.keys_size + 1, 1)
      else
        left.rotate(right, 1 ... left_count - left.keys_size + d, left.keys_size + 1)
      end
      parent[pos].key = left[left.keys_size].key
      if left.node?
        right[0].ptr = left[left.keys_size].ptr
        left.erase(left.keys_size)
      end
    end
    nil
  end