blog.monophile.net

コンピュータのこととかのメモ。

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS] においてメディア表現を専攻し修了。 現在は digitiminimi Inc. において、インフラエンジニアとして生計をたててている。

work

各種システム構築と管理を承ります。

Cloud PlatformOpenstack, GCP, AWS, Azure, ...
Openstackkeystone, glance, cinder, swift, neutron, nova, ...
VirtualizationQEMU+KVM, LXD/LXC, Docker, ...
OSDebian GNU/Linux, Ubuntu, CentOS, ...
NetworksIPSec, L2TP, VXLAN, WirelessAP, ...
WebAppsWordPress, GitLab, Redmine, ...
Configuration ManagementAnsible, Terraform, ...
MonitoringNagios, Munin, ...

posts

いきさつ

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

pyparsingのインストール

pyparsingモジュールをインストールする。 MacPortsを使う。

$ 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