blog.monophile.net

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、情報科学芸術大学院大学[IAMAS]においてメディア表現を専攻し修了。 現在は digitiminimi Inc. において、インフラエンジニアとして生計をたててている。 また、計算を主題に制作を行い、現代音楽作品や公共インスタレーション作品など技術提供を行う。 三輪眞弘に師事する。

List

SKIコンビネータをPythonで構文解析する

いきさつ

研究でコンビネータ論理を扱っていて、Pythonでツールを構築しています。 SKIコンビネータをpyparsingを使って構文解析しました。 python3.4を使っています。

構文解析

pyparsingモジュールをインストールします。 MacPortsを使います。

install

$ sudo port install py-parsing

EBNF記法

今回はunlambda記法ではなく括弧を使った記法のSKIコンビネータを解析します。 例えば“(S(S(KS)K)I)”と記述されるもので、そのEBNF記法は以下のようになります。

(* EBNF of SKI-Combinator *)
C = C, {C} | "(", C, ")" | "S" | "K" | "I"

parse.py

上記のSKIコンビネータを構文解析するソースparse.pyは以下になります。

import pyparsing as pp

def parse(string):
    s, k, i = map(pp.Literal, ["S","K","I"])
    lp, rp  = map(pp.Suppress, ["(", ")"])
    c       = pp.Forward()
    c       << pp.OneOrMore( pp.Group(lp + c + rp) | s | k | i )
    return c.parseString(string).asList()

if __name__ == "__main__":
    ZERO = "(S K)"
    ONE = "I"
    TWO = "(S (S (K S) K) I)"
    for expr in (ZERO, ONE, TWO):
        print("%s -> %s" % (expr, parse(expr)))

上記を実行すると以下のように出力されます。 無事に構文解析されています。

(S K) -> [['S', 'K']]
I -> ['I']
(S (S (K S) K) I) -> [['S', ['S', ['K', 'S'], 'K'], 'I']]

unlambda記法での構文解析(追記:2015/07/14)

unlambda記法でも試してみました。

EBNF記法

(* EBNF of SKI-Combinator *)
C = "`", C, C | "s" | "k" | "i"

parse.py

上記のSKIコンビネータを構文解析するソースparse_unlmabda.pyは以下になります。

import pyparsing as pp

def parse(string):
    s, k, i = map(pp.Literal, ["s","k","i"])
    bq = pp.Suppress("`")
    c  = pp.Forward()
    c  << ( pp.Group(bq + c + c) | s | k | i )
    cs = pp.OneOrMore(c)
    return cs.parseString(string).asList()

def tostr(c):
    return c if isinstance(c, str) else "`%s%s" % (tostr(c[0]), tostr(c[1]))

if __name__ == "__main__":
    ZERO = "`sk"
    ONE = "i"
    TWO = "``s``s`kski"
    src = ZERO + ONE + TWO
    print("%s -> %s" % (src, parse(src)))
    for i, c in enumerate(parse(src)):
        print("[%02d] " % i, tostr(c))

上記を実行すると以下のように出力されます。

`ski``s``s`kski -> [['s', 'k'], 'i', [['s', [['s', ['k', 's']], 'k']], 'i']]
[00]  `sk
[01]  i
[02]  ``s``s`kski