状態遷移による文字列パースのテクニック【Python】

588, 2022-11-20

状態遷移による文字列パース

状態遷移を使った文字列のパースは複雑な構文を持つフォーマットのテキストを解析するときなどに使われる。
これはパースの状態を複数に分割し、問題を小さくして処理を書いて解決するという手法である。

特定のフォーマットを持つ文字列と言うのは非常に複雑な構造になっている。
たとえばマークダウン、HTML、CSVなどがあげられる。
こういった構造の文字列をパースするにはこのような状態遷移を使うのが一般的である。

この記事では状態遷移パースのテクニックを取り上げる。
またサンプルコードはPythonで記述する。

普通の状態遷移を使ったパース

普通の状態遷移を使ったコードはたとえば↓のようになる。

def parse_digit(content: str):
    clen = len(content)
    i = 0
    buf = ''
    m = 0  # 状態変数

    while i < clen:
        c = content[i]

        if m == 0:
            if c.isdigit():
                m = 10
                buf += c
            else:
                break
        elif m == 10:
            if c.isdigit():
                buf += c
            else:
                break

        i += 1

    if len(buf):
        return int(buf)
    return None

これは文字列の先頭にある数字を読み取り整数として返すだけの簡単なパースの例である。
mというのが状態変数だ。
この状態変数がパースでずいじ切り替わっていく。

mの状態は0と10がありそれぞれの状態でパース内容が変わる。
上の例では状態0の時に数字を見つけたら状態10に切り替わるようになっている。
状態10では数字を読み取り、数字以外が来たらパースを終了して読み取った数字を整数にして返す。

これが状態遷移パースの基本的な形である。

複数の文字を先読みするパターン

基本の形を変形して、パースのさいに複数の文字を先読みしてパースする例を挙げる。

def parse_h3(content: str):
    clen = len(content)
    i = 0
    buf = ''
    m = 0  # 状態変数

    while i < clen:
        c1 = c2 = c3 = ''

        c1 = content[i]
        if i < clen - 1:
            c2 = content[i + 1]
        if i < clen - 2:
            c3 = content[i + 2]

        block3 = c1 + c2 + c3

        if m == 0:
            if block3 == '###':
                m = 10
                i += 2
            else:
                break
        elif m == 10:
            if c1 == '\n':
                break
            else:
                buf += c1

        i += 1

    if len(buf):
        return buf.strip()
    return None

この型はパース中の文字を複数の文字列として読み取りたい場合に適した型である。
パース中のインデックスから1つ、2つ先の文字を先読みしてそれをブロックな文字列にしている。
こうすることで文字単位ではなく文字列単位、つまり2以上の長さを持ったキーワードをパースの条件に使える。

多少、ループの先頭が頭でっかちにはなるが、それを差し引いても便利なパースを行うことが可能である。

パース対象のキーワードかどうかを判定する関数

パース中のインデックスから先読みしていくというテクニックを応用するとこのような関数も作れる。
たとえばパース中のインデックスに複数の数字（マークダウンのリストの項目）が並んでいるかどうかチェックしたい場合がある。
これをif文だけで判定すると非常にわい雑なコードになる。

こういったキーワードには↓のようなis_digit_dot関数を作る。

def is_digit_dot(content: str, i: int):
    clen = len(content)
    m = 0

    while i < clen:
        c = content[i]
        if m == 0:
            if c.isdigit():
                m = 10
            else:
                return False
        elif m == 10:
            if c.isdigit():
                pass
            elif c == '.':
                return True
            else:
                return False
        i += 1

    return False

このis_digit_dot()を使うと状態遷移のパースは↓のように書ける。

def parse_digit_dot(content: str):
    clen = len(content)
    i = 0
    m = 0  # 状態変数

    while i < clen:
        c = content[i]

        if m == 0:
            if is_digit_dot(content, i):
                m = 10
                i -= 1
            else:
                break
        elif m == 10:
            # ここにdigit dotのパース処理
            print('parse digit dot')
            pass

        i += 1

このような文字列のマッチングは正規表現を使った方がコードは短くなる。
しかし複雑なフォーマットになると正規表現によるマッチングはかなり難しくなる。
上のdigit dotの判定ぐらいなら正規表現の方が楽である。

正規表現を使った方法と↑のようなwhile文を書く方法、どちらが速いか？　というのはテストしていないのでわからない。
おそらく正規表現の方が速いだろう。
Pythonのwhile文はカウント変数をインクリメントするのにかなり時間がかかるらしい。
だがテストしてみないと何とも言えない。

おわりに

今回は状態遷移のテクニックをいくつか扱った。
状態遷移による文字列のパースは非常に汎用性がありマスターすれば一生の財産になるだろう。
なにか参考になれば幸いです。