西尾泰和のブログ

言語内DSLの主張：

新しい文法を覚える必要はないよ！だって言語○○で書けるもんね！

その実態：

でも(他のライブラリを使うとき同様)クラスとか関数とかどの演算子でつなぐのかとかは覚えてね！ あとこの言語のパーサに理解させるために頑張ったところはちょっと直感的じゃないけど、 言語○○で書くためなんだ、あきらめてね！ 他の言語で同じことをするライブラリと微妙に記法が違うけど、しかたないよね、 言語○○だもんね！

そこまで言語○○が好きですか？

もちろん「言語○○でシームレスに拡張できる」とかなら大歓迎。

---

= Packrat Parser勉強中。 BNFと違う表記をしていたのをPackratParserなのかなと思っていたけども、それは 解析表現文法 - Wikipedia だった。 で、この文法で表現できる言語の範囲はBNFで記述できる言語の範囲より広い。 正規表現で表現できる文法よりももちろん広い。 ただ、無制限に先読みができるので、文法によっては指数時間がかかる。 そこでメモ化を使って計算時間を減らしたのがPackrat Parser、なのかな？

で、そのWikipediaの 「PEGにおける繰り返しは常に貪欲であり、マッチし続ける限り入力を消費し、バックトラックしない。」 ってほんとかなぁ。 でも、その方が楽なのでそれで実装してみた。

---

= 自分に言いたい。 「長さ0のマッチはFailではないっ！」

---

= 荒削りだけど大体やりたかったことができるようになった。 Packratパーサではない。 解析表現文法ですらないかもしれない。定義がよくわからないし。 やりたいことが実現できるのが一番重要。

IDENT = RE(r"[\w_][\w\d_]*")
SPACE_GE0 = RE(r"\s*")
SPACE_GE1 = RE(r"\s+")
DOT = RE(r"\.")
COMMA_W_S = SPACE_GE0 + RE(",") + SPACE_GE0

AS_PHRASE = (
    SPACE_GE1 + RE("as") + SPACE_GE1 + IDENT
)

IMPORT = (
    RE("import") + SPACE_GE1 + 
    LOOP1(
        (
            GROUP(
                LOOP1(IDENT, DOT), "modname"
            ) + OPTION(AS_PHRASE)
        ), COMMA_W_S
    )
)

IMPORT.match("import xxx.yyy.zzz as bar, os.path")
print GROUP.result
# [('modname', 'xxx.yyy.zzz'), ('modname', 'os.path')]

もろもろのクラス定義は現時点で公開しても荒削りすぎるので全部は載せない。 例えば解析表現文法の「Sequence」にあたる表現の順接は こんな感じの実装。

class Add(RE):
    def __init__(self, r1, r2):
        self.r1 = r1
        self.r2 = r2

    def match(self, s):
        try:
            m1, s = match(self.r1, s)
            m2, s = match(self.r2, s)
            return Result((m1, m2))

        except Fail, f:
            return None

で、実は正規表現で可能な場合は正規表現に落とすような実装になっているので、 さっきのimport文の構文からGROUPを取り除くと生の正規表現が見られる。

IMPORT = (
    RE("import") + SPACE_GE1 + 
    LOOP1(
        (
            LOOP1(IDENT, DOT)
            + OPTION(AS_PHRASE)
        ), COMMA_W_S
    )
)
print IMPORT.pat
#import\s+[\w_][\w\d_]*(?:\.[\w_][\w\d_]*)*(?:\s+as\s+[\w_][\w\d_]*)?
#(?:\s*,\s*[\w_][\w\d_]*(?:\.[\w_][\w\d_]*)*(?:\s+as\s+[\w_][\w\d_]*)?)*

正規表現で可能であったとしても、 その正規表現を人間が直接書くかどうかは別というわけ。 機械語を直接書かずにコンパイルして生成するのと同じ。

全部機械語に直してしまわずに 機械がやっているようなことを ソフトウェア的に実装して、 速度を代償に柔軟性を得るのだ。 これも、全部正規表現のオートマトンに落としてしまわずに、 部分的にオートマトンがやるようなことをPythonで実装することで、 正規表現ライブラリが持っていないような機能を追加していると言えるだろう。

逆に 正規表現に落とさずに全部自分でオートマトンを作るのが スクリプト言語的なアプローチだとすれば、 部分的に正規表現に落とすのは 「部分的に機械語に変換して高速化」 ってのと同じかも。

まぁ、パフォーマンスがどの程度出るのかにはあまり興味がない。 実用上十分であればそれでいい。

---

= もう3時か…。

---

= 次の日の日記。

最初に言語内DSLを批判しておきながらできあがったものが結局言語内DSLである件について。

だから言語内DSLってのはなにも高尚なことじゃなくて、 単にパーサをかくのが面倒だから手抜きをしたってだけじゃないかと。

ごくまれに、言語○○のパーサが、作ろうとしてたDSLに完璧にマッチしていて、 すばらしいできの言語内DSLになる可能性もないとは言えないけども、 基本的には違うでしょう。

解析表現文法 - Wikipediaの例にあった a^nb^nc^nを実装してみた。

元の記法：

    S ← &(A !b) a+ B !c
    A ← a A? b
    B ← b B? c 

Pythonのコード：

    # non-context-free language
    A = RE("a") + OPTION(REF("A")) + RE("b")
    B = RE("b") + OPTION(REF("B")) + RE("c")
    S = ANDP(A + NOTP(RE("b"))) + LOOP1(RE("a")) + B + NOTP(RE("c"))
    print S.match("aaabbbcccc").group() #=> aaabbbccc

REFって。定義する前に参照できないというプログラミング言語上の制約のせいで、 文字列として受け取って評価を遅延させるREFが挟まっている。 Sの定義が一番下に来ているのもAとBの定義の後にしたいから。

本質的にはAの参照は全てREF("A")にすればすむのだけども、 それを簡潔に書く手段がないのは言語内DSLだからに他ならない。