CSAのインタプリタ的なものを作ってみた
所要時間は３時間ほど。コードを書いては没書いては没という作業を繰り返して今に至ります。没コードを合わせると1週間くらいはゆうに費やしているような気がします。
本当はパーサジェネレータでも書いた方がいいのかもしれませんが、あいにくそういうことはやっておりません。長いことツリー構造＋Visitorパターンをベースに云々やってましたが、なんか意図しない所でメソッドがクロージャっぽい挙動になってて正しくないツリーが構築されちゃったり、仕組みが必要以上に大掛かりで無駄に複雑な感じになってしまったりとあまり良いことがありませんでした。で、今回はできるだけシンプルになるよう努力してみました。
基本的にボトムアップになるような感じで書いています。概要としては以下のような感じです。
- 基本単位として、「1行をパースして結果を返す関数」を書く(マルチステートメントがありえるため、その部分には再帰を適用。よって返す結果はリスト形式)。この関数は「1行」の記述が文法的に正しいことを保証するが、前後の行との兼ね合い(順序関係とか競合とか)や意味的な部分のチェックなどには一切責任を持たない。
- パース関数は引数として「パース機能を持つクラス(DefaultParser)」をとり、実際のパース処理はそっちに委譲する。同じインタフェースを持つクラスを新たに実装することで、実際にパースするアルゴリズムは変更できるようになるため、仕様の変更等に伴うコード修正はある程度防ぐことができる。やってることはStrategyパターンに近いと思う。
- パース関数のラッパー(parseline2)を書く。ラッパーでは引数に「継続オブジェクト(≒コールバック, contクラスのインスタンス)」を導入し、結果を受け取った後行う処理をパース関数から独立に変更可能となるようにする。
継続というのは関数型言語でメジャーな考え方です。parse()の結果を呼び出し側で受け取る代わりに、結果を引数にとるような関数(、もしくはそのようなメソッドを備えたオブジェクト)をあらかじめ渡してやることで、パースの結果をどのように処理するか？という部分がソフトウェアの部品単位として交換できるようになります。開発の初期であれば結果を単にprintするようにしておけば良いし、順序関係のチェックなんかの上位の処理に渡したいときはそのようにすればいい。パース関数が返す「結果」の仕様さえ(後々変更がないよう)しっかり考えておけば、棋譜解析関連のすべての開発はこの関数をベースに出発できるわけです。
まぁ、それ故に戻り値の仕様決めはかなり難しいのですが、今回はあまり深いことは考えずにやってみます。本当はCSAでもKIFでも関係なく処理できるような仕様...というか、実世界の「棋譜」で表現されていること全部をカバーできるような仕様を考えるべきだと思ってます。適切な仕様であれば、任意のフォーマットに対応可能なはずです。
以下にコードを掲載します。main部分は解釈した結果をそのままprintするだけです。Windowsでの動作確認はやってませんが、LinuxでPython2.7なら多分動くと思います。
#!/usr/bin/env python # -*- coding: utf-8 -*- import os,sys,glob import string,re import csaioutil import signal,time,cProfile class DefaultLineParser: """ CSA ver.1.0 [player name] N+, N- [starting condition] PI, P1,P2,...P9, P+, P- +,- [move] [+-](00|[1-9]{2}[1-9]{2}(piece)(<sep>T[1-9][0-9]*)? [special command] %(TORYO|MATTA|CHUDAN|SENNICHITE|JISHOGI|TSUMI|FUZUMI|ERROR|KACHI|HIKIWAKE) """ mpnm= re.compile("^N[+-]") mpi = re.compile("^PI((00|[1-9]{2})(FU|KY|KE|GI|KI|KA|HI|OU)){0,9}") mpn = re.compile("^P[1-9](([^+-].{2}|[+-](FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU)))*") mpx = re.compile("^P[+-](00AL|((00(FU|KY|KE|GI|KI|KA|HI))|[1-9]{2}(FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU))*)") mtrn= re.compile("^[+-]$") mmov= re.compile("^[+-]((00[1-9]{2})(FU|KY|KE|GI|KI|KA|HI)|[1-9]{4}(FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU))") mtim= re.compile("T(0|[1-9][0-9]*)") msp = re.compile("^%(TORYO|MATTA|CHUDAN|SENNICHITE|JISHOGI|TSUMI|FUZUMI|ERROR|KACHI|HIKIWAKE)") mcom= re.compile("^'") memp= re.compile("^$") mksp= re.compile("^/") matches = [mpnm, mpi, mpn, mpx, mtrn, mmov, mtim, msp, mcom, memp, mksp] #groups = { # "playername": [mpnm], # "position": [mpi, mpn, mpx], # "turn": [mtrn], # "move": [mmov,mtim], # "sp" : [msp], # "comment": [mcom], # "empty": [memp], # "kifusep": [mksp] #} @classmethod def parse(cls,line): """ main()部分で動いているのはこれを継承したV2LineParserの方なので、 ここの実装はとりあえずダミー。 デフォルト実装としてCSA Ver.1.0を想定しているので、本来はそれをパースできるように書いとく所。 """ for i,m in enumerate(cls.matches): if(m.match(line)): return line raise Exception, "CSA SYNTAX ERROR: "+line def nsplit(l,n): """ 文字列をn文字ずつに分割する関数 """ return [l[i:i+n] for i in range(0,len(l),n)] def generateTerm(cate,tag,values=[]): """ パース結果の形式を生成する関数 """ return [{u"categoly": cate, u"tag": tag, u"values": values}] class V2LineParser(DefaultLineParser): #mpnm= re.compile("^N[+-]") #mpi = re.compile("^PI((00|[1-9]{2})(FU|KY|KE|GI|KI|KA|HI|OU)){0,9}") #mpn = re.compile("^P[1-9](([^+-].{2}|[+-](FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU)))*") #mpx = re.compile("^P[+-](00AL|((00(FU|KY|KE|GI|KI|KA|HI))|[1-9]{2}(FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU))*)") #mtrn= re.compile("^[+-]$") #mmov= re.compile("^[+-]((00[1-9]{2})(FU|KY|KE|GI|KI|KA|HI)|[1-9]{4}(FU|KY|KE|GI|KI|KA|HI|TO|NY|NK|NG|UM|RY|OU))") #mtim= re.compile("T(0|[1-9][0-9]*)") #msp = re.compile("^%(TORYO|MATTA|CHUDAN|SENNICHITE|JISHOGI|TSUMI|FUZUMI|ERROR|KACHI|HIKIWAKE)") #mcom= re.compile("^'") #memp= re.compile("^$") #mksp= re.compile("^/") minf= re.compile("^\$.*:.*") mver= re.compile("^V2(.[0-3])?") @classmethod def parse(cls,line): c="" if(len(line)==0): return generateTerm(u"other", u"empty", []) c=line[0] if((not (c=="$" or c=="'")) and len(line.split(","))>1): # multi statement return reduce(lambda a,b: a+b, map(lambda l: cls.parse(l), line.split(","))) if(c=="V"): if(cls.mver.match(line)): return generateTerm(u"version", u"version",[line[1:]]) elif(c=="N"): if(cls.mpnm.match(line)): if(line[1]=="+"): return generateTerm(u"info", u"name+", [line[2:]]) elif(line[1]=="-"): return generateTerm(u"info", u"name-", [line[2:]]) elif(c=="$"): if(cls.minf.match(line)): return generateTerm(u"info", line.split(":")[0], [line.split(":")[1:]]) elif(c=="P"): if(cls.mpi.match(line)): #mytag return generateTerm(u"ini", u"pi", map(lambda l: [int(l[0]), int(l[1]), l[2:4]], nsplit(line[2:],4))) elif(cls.mpn.match(line)): return generateTerm(u"ini", u"pl", [int(line[1]), map(lambda l: [l[0], l[1:3]] if(l[0]=="+" or l[0]=="-") else [u"*",u"*"], nsplit(line[2:],3))]) elif(cls.mpx.match(line)): return generateTerm(u"ini", u"px", [line[1], map(lambda l: [int(l[0]), int(l[1]), l[2:4]], nsplit(line[2:],4))]) elif(c=="+" or c=="-"): if(len(line)==1): return generateTerm(u"ini", u"turn",[c]) else: if(cls.mmov.match(line)): return generateTerm(u"move", c, [int(line[1]), int(line[2]), int(line[3]), int(line[4]), line[5:7]]) elif(c=="T"): if(cls.mtim.match(line)): return generateTerm(u"move", u"time", [int(line[1:])]) elif(c=="%"): if(cls.msp.match(line)): return generateTerm(u"move", u"special", [line[1:]]) elif(c=="'"): if(cls.mcom.match(line)): return generateTerm(u"comment", u"", [line[1:]]) elif(c=="/"): if(cls.mksp.match(line)): return generateTerm(u"kifuseparator", u"", []) raise Exception,line return None def parseline(line,parser=DefaultLineParser): """ parseline(line, parser=DefaultParser) Argument 'line' is must Unicode string 'parser' is a class object that line parser, parser class must have an interface classmethod 'parse(cls, line)' """ return parser.parse(line) class cont: # parse()に対するコールバック用のクラス。関数型言語で言う所の「継続」。 def accept(self,res): print res[u"categoly"]+" : "+res[u"tag"]+" : "+str(res[u"values"]) def parseline2(line, continuous, parser=DefaultLineParser): """ variation of parseline(), using continuous object """ for res in parseline(line, parser): continuous.accept(res) def test(): lines = [ "'csa version 1.0", "N+you", "N-com", "PI-82HI", "-", "-3334FU", "T1", "%TORYO"] lines = map(lambda l: unicode(l), lines) for line in lines: parseline2(line, cont(), DefaultLineParser) def test2(): lines = csaioutil.readlines_wrap(file("sample.csa")) # readlines() + unicode文字列への変換を行うラッパー関数 for line in lines: parseline2(line, cont(),V2LineParser) if __name__=="__main__": cProfile.run("test2()")
