0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Yudon66(yudon66)

Pythonで小さなパーサーを書く

0
Posted at

Pythonで小さなパーサーを書く

パーサーという言葉にはインタプリタとかコンパイラのイメージがあるが、個人的にちょっとした文字列処理にパーサーをシュッと書けるとカッコいいという憧れがある。
なので少し調べたのでまとめる。

はじめに

なんとなくの思いつきで考えた入力例であり、こういうのをパッとパースできるとカッコいいと思う。
次のようなスケジュール文字列を解析する。

9/3 19:00 友人と夕食 @新宿 #私用

これはなんとなくの思いつきで考えた入力例である。
結果は次のようなデータにする。JSON なら取り回しが良いからだ。

{
    "month": 9,
    "day": 3,
    "hour": 19,
    "minute": 0,
    "title": "友人と夕食",
    "location": "新宿",
    "tags": ["私用"],
}

文法を決める

あらかじめ、入力例が決められているのでそれに合わせて文法を決める。
文法はEBNF風の記法とする。EBNF は BNF (バッカス・ナウア記法)を拡張したもの。

entry    := date WS time WS title (WS field)*
date     := number "/" number
time     := number ":" number
title    := field が始まるまでの文字列
field    := location | tag
location := "@" value
tag      := "#" value
value    := 空白以外の文字+
number   := digit+

原則として入力例を仕様の基準とし、文法化によって気づいた改善点などは実装に反映しない。

注意事項は次の通り

  • WS は 1 文字以上の空白文字
  • 文法は location を複数取れるように見えるが、場所は1つまでとする
date := number "/" number

は、数字、/、数字の順に読むという意味になる。

現在位置を持つ

パーサーは入力文字列と現在位置を持つ。

def __init__(self, text):
    self.text = text
    self.pos = 0

pos を進めながら左から順に読む。

基本操作を作る

現在の文字を見る peek、1文字読む consume、特定の文字を要求する expect を用意する。

def peek(self):
    if self.eof():
        return None
    return self.text[self.pos]

def consume(self):
    if self.eof():
        self.error("予期せず入力が終わりました")

    c = self.text[self.pos]
    self.pos += 1
    return c

def expect(self, expected):
    if self.peek() != expected:
        self.error(f"{expected!r} を期待しました")

    self.pos += 1

文法ごとに関数を作る

文法の各要素を関数に対応させる。

number := digit+

なら、数字が続く間だけ読む。

def parse_number(self):
    start = self.pos

    while not self.eof() and self.peek().isdigit():
        self.pos += 1

    if start == self.pos:
        self.error("数字を期待しました")

    return int(self.text[start:self.pos])

日付は、

date := number "/" number

なので、そのまま実装できる。

def parse_date(self):
    month = self.parse_number()
    self.expect("/")
    day = self.parse_number()

    if not 1 <= month <= 12:
        self.error("月は1〜12で指定してください")

    if not 1 <= day <= 31:
        self.error("日は1〜31で指定してください")

    return month, day

時刻も同じように number ":" number として読む。

ここでは構文を解析すると同時に、月、日、時、分の範囲も簡単に検証する。

予定名を読む

予定名には空白を含めたい。

友人と夕食

そのため、単純に空白まで読むことはできない。

今回は、空白の後ろに @ または # が現れたらフィールドの開始とする。

def parse_title(self):
    start = self.pos

    while not self.eof():
        if self.at_field_start():
            break

        self.pos += 1

    return self.text[start:self.pos].rstrip()

at_field_start は現在位置から先を見て、次のフィールドが始まるかを調べる。

def at_field_start(self):
    if not self.peek().isspace():
        return False

    p = self.pos

    while p < len(self.text) and self.text[p].isspace():
        p += 1

    return p < len(self.text) and self.text[p] in "@#"

ここでは self.pos ではなく p を進めるため、入力自体はまだ消費しない。

フィールドを読む

@ は場所、# はタグとする。

def parse_field(self):
    marker = self.consume()

    if marker == "@":
        return "location", self.parse_value()

    if marker == "#":
        return "tag", self.parse_value()

    self.error("'@' または '#' を期待しました")

値は空白まで読む。

def parse_value(self):
    start = self.pos

    while not self.eof() and not self.peek().isspace():
        self.pos += 1

    if start == self.pos:
        self.error("値がありません")

    return self.text[start:self.pos]

たとえば、

@新宿

なら ("location", "新宿")、

#私用

なら ("tag", "私用") になる。

全体を読む

最後に、

entry := date WS time WS title (WS field)*

を順番に実装する。

month, day = self.parse_date()
self.require_ws()

hour, minute = self.parse_time()
self.require_ws()

title = self.parse_title()

その後、入力が終わるまで @ や # のフィールドを読む。

このように、文法の規則ごとに関数を作り、上位の規則から下位の規則へ降りながら解析するのが再帰下降パーサーの基本的な作り方である。
今回は再帰的な規則がないため、実際の再帰呼び出しはない。

サンプルコード

以上をまとめたコードが次になる。

"""
entry    := date WS time WS title (WS field)*
date     := number "/" number
time     := number ":" number
title    := field が始まるまでの文字列
field    := location | tag
location := "@" value
tag      := "#" value
value    := 空白以外の文字+
number   := digit+
"""
import json


class ParseError(ValueError):
    pass


class ScheduleParser:
    def __init__(self, text):
        self.text = text
        self.pos = 0

    def parse(self):
        result = self.parse_entry()

        self.skip_ws()

        if not self.eof():
            self.error("余分な文字があります")

        return result

    def parse_entry(self):
        month, day = self.parse_date()

        self.require_ws()

        hour, minute = self.parse_time()

        self.require_ws()

        title = self.parse_title()

        if not title:
            self.error("予定名がありません")

        result = {
            "month": month,
            "day": day,
            "hour": hour,
            "minute": minute,
            "title": title,
            "location": None,
            "tags": [],
        }

        while True:
            self.skip_ws()

            if self.eof():
                break

            kind, value = self.parse_field()

            if kind == "location":
                if result["location"] is not None:
                    self.error("場所 @ は1つだけ指定できます")

                result["location"] = value

            elif kind == "tag":
                result["tags"].append(value)

        return result

    def parse_date(self):
        month = self.parse_number()

        self.expect("/")

        day = self.parse_number()

        if not 1 <= month <= 12:
            self.error("月は1〜12で指定してください")

        if not 1 <= day <= 31:
            self.error("日は1〜31で指定してください")

        return month, day

    def parse_time(self):
        hour = self.parse_number()

        self.expect(":")

        minute = self.parse_number()

        if not 0 <= hour <= 23:
            self.error("時は0〜23で指定してください")

        if not 0 <= minute <= 59:
            self.error("分は0〜59で指定してください")

        return hour, minute

    def parse_title(self):
        start = self.pos

        while not self.eof():
            if self.at_field_start():
                break

            self.pos += 1

        return self.text[start:self.pos].rstrip()

    def parse_field(self):
        marker = self.consume()

        if marker == "@":
            return "location", self.parse_value()

        if marker == "#":
            return "tag", self.parse_value()

        self.error("'@' または '#' を期待しました")

    def parse_value(self):
        start = self.pos

        while not self.eof() and not self.peek().isspace():
            self.pos += 1

        if start == self.pos:
            self.error("値がありません")

        return self.text[start:self.pos]

    def parse_number(self):
        start = self.pos

        while not self.eof() and self.peek().isdigit():
            self.pos += 1

        if start == self.pos:
            self.error("数字を期待しました")

        return int(self.text[start:self.pos])

    # ---------- パーサー共通の基本操作 ----------

    def at_field_start(self):
        if not self.peek().isspace():
            return False

        p = self.pos

        while p < len(self.text) and self.text[p].isspace():
            p += 1

        return p < len(self.text) and self.text[p] in "@#"

    def require_ws(self):
        if self.eof() or not self.peek().isspace():
            self.error("空白を期待しました")

        self.skip_ws()

    def skip_ws(self):
        while not self.eof() and self.peek().isspace():
            self.pos += 1

    def peek(self):
        if self.eof():
            return None

        return self.text[self.pos]

    def consume(self):
        if self.eof():
            self.error("予期せず入力が終わりました")

        c = self.text[self.pos]
        self.pos += 1

        return c

    def expect(self, expected):
        if self.peek() != expected:
            self.error(f"{expected!r} を期待しました")

        self.pos += 1

    def eof(self):
        return self.pos >= len(self.text)

    def error(self, message):
        raise ParseError(
            f"{message} (位置 {self.pos})\n"
            f"{self.text}\n"
            f"{' ' * self.pos}^"
        )


def parse_schedule(text):
    return ScheduleParser(text).parse()


if __name__ == "__main__":
    text = "9/3 19:00 友人と夕食 @新宿 #私用"

    print(json.dumps(
        parse_schedule(text),
        ensure_ascii=False,
        indent=2,
    ))

実行結果は次のようになる。

{
  "month": 9,
  "day": 3,
  "hour": 19,
  "minute": 0,
  "title": "友人と夕食",
  "location": "新宿",
  "tags": [
    "私用"
  ]
}

まとめ

文法の規則ごとに関数を作ると、入力形式とコードを対応させながらパーサーを書ける。
今回のような小さな文法なら、現在位置を持って一文字ずつ読むだけでも実装できる。
今後は気軽に思いついては作り、捨てるくらいの身近なものにしていきたい。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?