この記事は言語処理系 Advent Calender７日目の記事です。
今日は、ML系の言語のプリティプリントの例ats-beautify[1]について書きます。ats-beautifyはpythonだけで実装してあり、sublime-text2のプラグインとして使ったり、コマンドライン呼び出しを使い様々なエディタから使用する事が出来ます。
モチベーション
ATS2というSMLに似た文法を持った言語があります。
ATSはプログラムコードに証明を付ける事が出来るので安全なコードを構築出来ます。しかも、C言語を出力するのでC言語のソースの一部分だけをATSが出力したコードに置き換えて証明付きの完全なプログラムに置き換えて直ぐに使う事が出来ます。
しかし、作者のホングウェイの書くプログラムコードは読みやすいものではありませんでした。
とは言え、言語の作者です。それなりのこだわりを持って書いているはずです。
奇麗に書き直してくれとお願いしてもなかなか受け入れてもらえないような気がします。
しっかりしたプリティプリンタを書いてこれを使えば奇麗になるよという話にすればよいのではないかと思った訳です。
とりあえずOCamlを参考にプリティプリンタを作ればいいじゃないかと思った訳です。
がC言語系統の言語やRubyのようにendで終わる言語と違いML系統の言語のビューティファイアは作るのがちょいと大変で、簡単に作れそうになかった。
パーサを修正する事である程度の物は作れたのですが、構文木にはない情報が必要で上手く行きません。
OCamlのプリティプリンタは独自にパーサを持っていたりと大変そうです！
ううむ。楽に奇麗に作りたい。しかし作れない。そんな状況が続いておりました。
夏頃に PEGと構文解析に関するアレコレの勉強会 Vol.1 [2]という勉強会がありました。何かネタないかなと考えてみていてふと思いつきました。
「そうだ！パーサコンビネータを作ってプリティプリンタを作ろう！」
そこで、文法にネスト情報を加える事が出来るパーサコンビネータを作成してみたのです。
これなら行ける。ある程度作れる事が分かりました。
プリティプリンタの使い方
parse(src)
パース関数にソースコードを渡すと、プリティプリントされた文字列がかえってきます。
プリティプリンタ機能付きパーサコンビネータの使い方
いきなりデカいですが、以下のように、完全ではないプリティプリントさえ出来れば良いような、ATSのパーサを書きます。
ポイントは、ネストを入れたい所に-を書くとネストが付きます。なぜ-にしたかというと、SublimeText2で-が奇麗に色がついたからです。
文法の作り方は、きっと、使い慣れれば分かります。pythonの場合演算子を多く使えないので、goのパーサコンビネータを参考に、a / b / cを or(a,b,c)と書くようにしてありますが、使い慣れないと分け分からない気もします。ま、パーサコンビネータなんてきっとそういうものです。
keywords = reg(r"^(begin|end|if|else|then|let|in|val|implement|local|typedef|sortdef|datatype|extern|lam|try|with|fnx|fn|fun|case|of|orelse|macrodef|macdef|staload|dynload|open|struct|module|and|while|do|done)\b")
semi = notp(";;") >> p(";")
exp = p(lambda i: p(exp4, rep[semi, exp4], opt(semi))(i))
exps = p(exp, opt(semi))
id = orp(
notp(keywords) >> reg(r"^[\$\\]?[_a-zA-Z0-9]+"),
str(":<cloref>"),
reg(r'^[+\-*/.<>:@=^|~?]+') ^ (lambda i: i if re.search(r'^(=|=>|=<|->|\||)$', i[1]) is None else None),
reg(r'^[!]'),
reg(r'^("(\\.|[^"])*"|\'(\\.|[^\'])\')')
)
assign = p(lambda i: p(app, "=", -exp)(i))
sexp = orp(
p("@(", -opt(exp), ")"),
p("@{", -p(assign, rep(",", assign)), "}"),
p("@[", -opt(exp), "]"),
p("'(", -opt(exp), ")"),
p(",(", -opt(exp), ")"),
p("'{", -p(assign, rep(",", assign)), "}"),
p("'[", -opt(exp), "]"),
id,
p("begin", -exp, "end"),
p("(", -opt(exp), ")"),
p("{", -p(lambda i: rep(toplevel)(i)), "}"),
p("[", -opt(exp), "]")
)
app = rep1(sexp)
exp1 = orp(
p("lam", -p[app], orp("=>", "=<cloptr1>", "=<cloref>"), -p(lambda i: exp2(i))),
p("let", -p(lambda i: rep(toplevel, opt(";;"))(i)), "in", -opt(exp), "end"),
p("if", -exps, "then", -p(lambda i: exp4(i)), opt(p("else", exp))),
p("case", -exps, "of", -p(opt("|"), app, "=>", -exp, rep("|", app, "=>", -exp))),
p("try", -exps, "with", opt("|"), -app, "=>", exp, rep["|", app, "=>", -exp]),
p("while", -exps, "do", -exps, "done"),
app
)
exp2 = p(exp1, opt(orp("=", "orelse"), p(lambda i: exp2(i))))
exp3 = p(exp2, rep(",", exp2))
exp4 = p(exp3, opt("->", exp))
prog = p(lambda i: rep(toplevel)(i))
struct = p(lambda i: orp(
p("struct", -prog, "end"),
-struct_exp
)(i))
struct_exp = rep1(orp(
id,
p("(", -opt(struct), ")")
))
datatype = p[app, "=", opt("|"), -app, opt("of", -app), rep("|", -app, opt("of", -app))]
toplevel = orp(
p(orp("fn", "fnx", "fun"), -p[app], opt("=", -exp)),
p("extern", -p[orp("fn", "fnx", "fun"), app]),
p(orp("macdef", "macrodef"), -p[app], opt("=", -exp)),
p("val", -p[app], "=", -exp),
p("implement", -p[app], "=", -exp),
p(orp("typedef", "sortdef"), -p[app], "=", -exp),
p("and", -p[app], "=", -exp),
p(orp("#include", "staload", "dynload"), -exp),
p("#define", -sexp, opt("(", -exps, ")"), -sexp),
p("local", -p[prog], "in", -p[prog], "end"),
p("datatype", -datatype, rep("and", -datatype)),
p("exception", -id, "of", -exp),
p("open", -p[id, rep(".", id)]),
p(exp, opt(semi)),
p("module", -p[app], "=", struct)
)
プリティプリンタ機能付きパーサコンビネータの実装
まずは、簡単なパーサコンビネータライブラリを作ります。
実装用の言語はsublimetext2で使いたかったのでpythonです。pythonはclassがあり、演算子はちょっとだけ変更出来ます。メソッドチェーンを使う手もありますが、goのパーサコンビネータ goparsec[3]を参考に関数を使う事にしました。
import re
import sys
sys.setrecursionlimit(1000*1000)
class Parser(object):
def __rshift__(self, that):
return p(self, that) ^ (lambda a: a[1])
def __lshift__(self, that):
return p(self, that) ^ (lambda a: a[0])
def __xor__(self, that):
return Action(self, that)
def __neg__(self):
return Action(self, lambda a: [NestP, a, NestM])
class static(type):
def __getitem__(self, i):
return self(*i) if isinstance(i, tuple) else self(i)
__metaclass__ = static
class nreg(Parser):
def __init__(self, param):
self.param = re.compile(param)
def __call__(self, i):
m = self.param.search(i)
return None if m is None else [m.group(0), i[len(m.group(0)):]]
class orp(Parser):
def __init__(self, *params):
self.params = map(lambda v: st(v) if isinstance(v, basestring) else v, params)
def __call__(self, i):
for v in self.params:
r = v(i)
if r is not None:
return r
return None
class nstr(Parser):
def __init__(self, param):
self.param = param
def __call__(self, i):
return None if not i.startswith(self.param) else [self.param, i[len(self.param):]]
class p(Parser):
def __init__(self, *params):
self.params = map(lambda v: st(v) if isinstance(v, basestring) else v, params)
def __call__(self, i):
rs = []
for v in self.params:
r = v(i)
if r is None:
return None
rs.append(r[0])
i = r[1]
return [rs, i]
class Action(Parser):
def __init__(self, thiz, action):
self.thiz = thiz
self.action = action
def __call__(self, i):
r = self.thiz(i)
if r is None:
return None
else:
r2 = self.action(r[0])
return None if r2 is None else [r2, r[1]]
class opt(Parser):
def __init__(self, *thiz):
self.thiz = p(*thiz)
def __call__(self, i):
r = self.thiz(i)
return [[], i] if r is None else r
class rep(Parser):
def __init__(self, *thiz):
self.thiz = p(*thiz)
def __call__(self, i):
rs = []
while(True):
r = self.thiz(i)
if r is None:
return [rs, i]
rs.append(r[0])
i = r[1]
def rep1(*thiz):
return rep(*thiz) ^ (lambda p: None if len(p) < 1 else p)
class notp(Parser):
def __init__(self, *thiz):
self.thiz = orp(*thiz)
def __call__(self, i):
return [[], i] if self.thiz(i) is None else None
class Any1(Parser):
def __call__(self, i):
return None if len(i) == 0 else [i[0], i[1:]]
any1 = Any1()
これをある程度カスタマイズします。
blockcomment = p(nstr("(*"), rep(orp(notp(nreg(r"^(\(\*|\*\))"), any1), (lambda i: blockcomment(i)))), nstr("*)"))
skip = rep(orp(nreg(r'^(\s|/\*.*?\*/|//[^\r\n]*)+'), blockcomment))
def st(s):
return p(skip, nstr(s))
def reg(s):
return p(skip, nreg(s))
ここで、ネスト用のオブジェクトを２つ作ります。
class Nest:
def __init__(self, name, n):
self.name = name
self.n = n
def __repr__(self):
return self.name
NestP = Nest("NestP", 1)
NestM = Nest("NestM", -1)
NestPがネストを１つ上げ、NestMが一つ下げる意味です。
これは、Parserクラスの__neg__を使って、-を付けると、パーサの前後にNestPとNestMを付ける事が出来るようにしてあります。
プリティプリント
プリティプリントの関数はflatとcnvの２つの関数で構成されます。
パース結果には、全てのトークン＋ネスト情報が含まれているので、ネスト情報をで空白を調整して出力するだけです。
def flat(a, rc):
if isinstance(a, list):
for i in a:
rc = flat(i, rc)
else:
rc.append(a)
return rc
def cnv(e):
reg2 = re.compile(r'\n')
whiteSpace = re.compile(r'^(\s|\s*\(\*)')
reg1 = re.compile(r'\n')
e = flat(e, [])
e2 = []
i = 0
while(i < len(e)):
s = [e[i]]
if isinstance(s[0], basestring) and reg2.search(s[0]) is not None and whiteSpace.search(s[0]) is not None:
s = []
while(i < len(e)):
s2 = e[i]
if s2 is NestM:
e2.append(s2)
else:
s.append(s2)
if whiteSpace.search(s2) is None:
break
i += 1
i += 1
e2.extend(s)
nest = 0
e3 = []
for s in e2:
if isinstance(s, Nest):
nest += s.n
else:
m = reg2.search(s)
if m is not None:
s = reg1.sub("\n"+(" " * nest), s)
e3.append(s)
return "".join(e3)
これらの機能は以下のようにして呼び出します。
regparse = re.compile(r"^[ \t]+", re.M)
def parse(s):
return cnv(prog(regparse.sub("", s)))
まとめ
- プリティプリンタ作成専用のパーサコンビネータを作ります。
- パーサコンビネータは自動的に構文木を作り、空白やコメントを含めたトークン情報を持ちます。
- パーサコンビネータにネスト情報を加える事が出来るようにします。
- ネスト情報を元にプリントする処理を作ります。
- 完全ではなくて良いので、プリティプリント用のパーサを作ります。
以上のようにする事で、パーサコンビネータを使ってプリティプリントを作る事が出来ます。
ATSのプリティプリンタはまだ完全ではありませんが、このパーサを拡張して行けばより良い物になるでしょう。また、この仕組みを使えば他のML系のプリティプリンタも奇麗に書く事が出来るはずです。
リンク
-
[1] ats/beautify
https://github.com/hsk/docs/tree/master/ats/beautify -
[2] PEGと構文解析に関するアレコレの勉強会 Vol.1
http://connpass.com/event/16630/ -
[3] goparsec
https://github.com/prataprc/goparsec