Diary?

(01:30)

Caty プロジェクト全体の進捗については檜山さんのブログにあるとおりなので、今日はちょっと細かい成果物の公開でも。というかこれは Caty プロジェクトで開発したものではなく、俺が気分転換に書いたソフトウェアなのだが、何か使えそうなので Caty にバンドルする事にした（実際、既に Caty 内部では使われて始めてる）。

• topdown-0.1.0

これは何かと言うとだな、 Python 用の文字列解析ライブラリだ。元ネタになったのは Haskell の Parsec なのだが、俺の作った奴はパーサコンビネータというわけでは全然ない。ただ、 Parsec みたいに宣言的にパーサを記述できるととても嬉しいので、ある程度は宣言的に書けるようにしたつもりだ。例えばサンプル代わりに同梱されている電卓のパーサはこう。

from topdown import *
from operator import *

def num(seq):
    e = seq.parse(Regex('-?[0-9]+'))
    return int(e)

def op1(seq):
    e = seq.parse(list('+-'))
    if e == '+':
        o = add
    else:
        o = sub
    return lambda a, b: (o, a, b)

def op2(seq):
    e = seq.parse(list('*/'))
    if e == '*':
        o = mul
    else:
        o = div
    return lambda a, b: (o, a, b)

def factor(seq):
    def _factor(s):
        p1 = s.parse('(')
        e = expr(s)
        p2 = s.parse(')')
        return e
    return seq.parse([num, _factor])

term = chainl(factor, op2)
expr = chainl(term, op1)

ちなみに括弧による演算順序の指定まで含めた四則演算の構文は、 BNF っぽく書くとこう。

EXPR ::= EXPR '+'|'-' TERM | TERM
TERM ::= TERM '*'|'/' FACTOR | FACTOR
FACTOR ::= '(' EXPR ')' | NUMBER
NUMBER ::= '-' DIGIT | DIGIT
DIGIT ::= '0'|'1'|...

ただし、これは定義が左再帰になっているので、トップダウン構文解析では無限再帰に陥る事がある。というか、このライブラリだと陥る。なので、左再帰を除去する。ここでのεは空を表すものとする。また、 FACTOR 以下は先のものと同じ。

EXPR ::= TERM _EXPR
_EXPR ::= '+'|'-' TERM _EXPR | ε
TERM ::= FACTOR _TERM
_TERM ::= '*'|'/' FACTOR _TERM | ε

ただしこのまま素直に展開すると演算子が右結合になってしまって具合が悪いんで、もうちょっと考える必要がある。

ちなみにこの四則演算というのはつまり、

1. EXPR は TERM と加減算の演算子が交互に現れるリストを結合したもの
2. TERM は FACTOR と乗除算の演算子が交互に現れるリストを結合したもの

といっていい。先のサンプルコードで言うと、

term = chainl(factor, op2)
expr = chainl(term, op1)

の部分がほぼそれだ。また、他の関数も大体定義どおりに実装できている。

実際これはちょっと都合の良すぎる例で、例えば同梱してる creole 文法のパーサはパフォーマンスチューニングのためにかなり汚い書き方になっている。一方で同じく同梱してる超簡易テンプレートエンジンはかなりファイル冒頭の嘘BNFに近い形でパーサが書けているので、まずは直観的にパーサを書き下してみて、パフォーマンス上の問題が出てきたら適宜力技でパーサを書き換えていくというのが良さそうである。

ちなみにドキュメントは何一つとして書いていないので、俺以外の人間が扱える代物かどうかは不明。先に書いたとおり Parsec とは最終的に全然別物になったので、そっちの知識があってもそこまで役に立つとは思えないし。