続・Logo基礎文法最速実装
前回は、とりあえず字句解析、構文解析、実行の一通りができるようになりました。こんなかんじ。
なかなからしくなっては来ましたが、けれど、多くの組み込みコマンド/組み込みオペレーションはまだ未実装ですし、厄介な二項演算子、to〜end での関数定義、くわえて Logo の看板であるタートルグラフィックスが未実装です。むむむ、まだ先は遠いです。
二項演算子
で、その二項演算子なのですが、これがちょっと厄介で。
式 ::= {式 '+' 式 | 値}みたいなものですが、これを再帰下降解析すると、「式 + 式」であることを確定するために、一つ先読みすればいい・・とやろうとしても、演算子の左側が再帰してしまって、無限ループになってしまいます。「左再帰」と言って、再帰降下解析の苦手なパターンの一つなのですがこれは、
式 ::= 項 |
項 { {'+'|'-'|'*'|'/'} 項}*
項 ::= 値みたいにして回避します。
イメージ的には こういう探索
((((値 '+' 値) '+' 値) '+' 値) '+' 値)
を、こんな風に変形
値 ('+' 値)('+' 値)('+' 値)('+' 値)するカンジ？
さて、実装開始。プログラムパーザが主役なのですが、まずは下準備。トークンの型と、
class LGTokenType(object): Word = "Word" # 語 QWrd = "QuoWord" # quote (") + 語 ・ ・ BOpe = "BinaryOperator"# 二項演算子 #<=追加 def __init__(self): ・ ・ self.bopeptn = re.compile( r"[+\-\/\*\<\>\=]" ) #<=追加 def typeOf(self, token): if self.nwrdptn.match( token ): return LGTokenType.NWrd if self.qwrdptn.match( token ): return LGTokenType.QWrd if self.dwrdptn.match( token ): return LGTokenType.DWrd if self.bopeptn.match( token ): return LGTokenType.BOpe #<=追加 ・ ・
データパーザ用の構文要素、
class LGBinOpeWord( object ): def __init__(self, value): self.value = value def __str__(self): return self.value def evaluate(self, context): raise LGRuntimeError( 'not-evalutable-exception' )
データパーザ、
class LGDataParser(object): def list_(self, currentlist): while True: self.scanner.advance() toktype = self.scanner.getTokenType() tokval = self.scanner.getTokenValue() if toktype == LGTokenType.Word: currentlist.append( LGWord(tokval) ) ・ ・ if toktype == LGTokenType.BOpe: #<=追加 currentlist.append( LGBinOpeWord(tokval) ) #<=追加 ・ ・ def group(self, currentgroup): while True: self.scanner.advance() toktype = self.scanner.getTokenType() tokval = self.scanner.getTokenValue() if toktype == LGTokenType.Word: currentgroup.append( LGWord(tokval) ) ・ ・ if toktype == LGTokenType.BOpe: #<=追加 currentgroup.append( LGBinOpeWord(tokval) )#<=追加 ・ ・
と、プログラムパーザまで二項演算子の情報のパスを通します。
プログラムパーザーは、基本的に、 expression メソッドの差し替えです。今までの expression メソッドを normalExpression にリネームし、expression メソッド自体は 「式 ::= 通常式 | {通常式 二項オペレーション}*」という内容にします。
class LGProgramParser(object): def expression(self): '''式 ::= 通常式 | {通常式 二項オペレーション}*''' fstret = self.normalExpression() while True: try: elm = self.scanner.nextElement() except IndexError: return fstret if type(elm) == LGBinOpeWord: fstret = self.binOperation(fstret) else: return fstret def normalExpression(self): '''通常式 ::= "語 | 数値語 | :語 | リスト | オペレーション | グループ ''' try: elm = self.scanner.nextElement() except IndexError: raise StopIteration if (type(elm) == LGQuoWord or type(elm) == LGNumWord or type(elm) == LGDotWord or type(elm) == LGList): self.scanner.advance() return self.scanner.getElement() if type(elm) == LGWord: return self.operation() if type(elm) == LGGroup: self.scanner.advance() return self.parseGroup( self.scanner.getElement() ) raise LGRuntimeError('parse error (expression) %s' % type(elm) ) def binOperation(self, rval): '''二項オペレーション ::= 二項演算子 通常式''' # 手続き名 self.scanner.advance() elm = self.scanner.getElement() if type(elm) != LGBinOpeWord: raise LGRuntimeError("parse error (binary operation)") ope = LGOperation( elm.value ) ope.appendArgument( rval ) try: ope.appendArgument( self.normalExpression() ) except StopIteration: raise LGRuntimeError( 'parse error (binary operatoin)' ) return ope
グループの中も同じように。
def group(self, argc): '''グループ ::= グループオペレーション | 二項演算グルーピング | "語 | 数値語 | :語 | リスト''' elm = self.scanner.nextElement() if type(elm) == LGWord: return self.groupOperation(argc) if argc != 0: return self.groupingBinOperation() if (type(elm) == LGQuoWord or type(elm) == LGNumWord or type(elm) == LGDotWord or type(elm) == LGList): if argc != 0: raise LGRuntimeError("too much inside ()'s") self.scanner.advance() return self.scanner.getElement() raise LGRuntimeError('parse error (group) %s' % type(elm) ) def groupingBinOperation(self): '''二項演算グルーピング ::= オペレーションを除く通常式 二項オペレーション {通常式 二項オペレーション}+ ''' fstret = self.normalExpression() if type(fstret) == LGOperation: raise LGRuntimeError("parse error (grouping bin operator)") while True: try: elm = self.scanner.nextElement() except IndexError: return fstret if type(elm) == LGBinOpeWord: fstret = self.binOperation(fstret) else: return fstret
以上で、二項演算子に対応できたハズ。試してみます。
え？ 演算子の優先順位に対応できていない？・・・・こまけぇこたぁいいんだよっ！、です（ここまで面倒くさくなるんだったら、パーザジェネレータ使えば良かった ...orz）
タートルグラフィクス
ここまでで文法的には十分・・ですが、やっぱり Logo といったらタートルグラフィックス！・・・とはいえ、Logo のプログラミング記事というよりは、Tkinter のプログラミング記事になってしまうので、コードはかるーく。
タートルとそのコマンドはこんな感じで。
class Turtle( Subject ): def __init__(self, x=0.0, y=0.0): Subject.__init__(self) self.direction = 0 # タートルの向き self.isPenDown = True self.pos = Coordinate(x,y) self.oldpos = self.pos def oldX(self): return self.oldpos.x def oldY(self): return self.oldpos.y def x(self): return self.pos.x def y(self): return self.pos.y def forward(self, distance): self.oldpos = self.pos.clone() self.pos.moveVector(self.direction, distance) self.notifyObservers('forward') def back(self, distance); ・ ・ class ForwardFunc(object): def requieredArgCount(self): return 1 def evaluate(self, context, args): turtle = context.findVariable('turtle') turtle.forward( _asNum(args[0]) ) class BackFunc(object): ・ ・
あ、Coordinate は座標計算用自作クラスです。捜せば出来合いのモノがありそうですが切羽詰まってたのでゴリゴリっと力業。うう。
スクリーンはこんな感じ。
class TurtleScreen( Canvas ): def __init__(self, turtle, master=None, **args): Canvas.__init__(self, master, args) self.turtle = turtle self.turtle.addObserver(self) self.orgX = int(self['width']) / 2 self.orgY = int(self['height']) / 2 self.writeTurtle() def update(self, aspect): self.writeTurtle() if (aspect == 'forward' or aspect == 'back' or aspect == 'home'): if self.turtle.isPenDown: self.writeTrac() def writeTrac(self): if self.turtle.isPenDown == True: self.create_line( self.turtle.oldX() +self.orgX, self.turtle.oldY() +self.orgY, self.turtle.x() +self.orgX, self.turtle.y() +self.orgY, tag='trac' ) def deleteTrac(self): self.delete('trac') def writeTurtle(self): ・ ・
コードが汚いのは、見なかったことに..。おねがい。
さてさて、そうして出来た Logo with TurtleGraphics で、このコードを実行します。
lt 120 + 30 fd 100 lt 120 fd 100 lt 120 fd 100 fd 100 rt 90 repeat 360 [ rt 1 fd 2 * 100 * pi / 360 ] rt 90 + 30 fd 2 * 50 * sqrt 3 lt 90 pu fd 100 pd lt 90 fd 2 * 50 * sqrt 3 lt 60 pu repeat 360 / 12 [ lt 1 fd 2 * 100 * pi / 360 ] pd lt 90 fd 2 * 100
よかった、できて...
* * *
最速実装、続・最速実装と、ここまで実装するのに週末丸2日かかってしまいました。
Logo は 文法が簡単なので実装するのは楽ちん！だからほんの 5,6時間くらいで終わらすつもりでしたのに、気付けばもう日曜深夜26時ですよ。ほえほえ。「週末ゆったりコーディング」・・・のつもりが「週末ギッチリコーディング」になってしまいました..orz ちょっと企画にムリがありましたか...。ホント終わって良かったデス。
「最速実装」というにはなんだかグダグダすぎで、全然参考にならず申し訳なのですが、最近はコンパイラ・インタプリタ本も流行ってる見たいですし、プログラミング言語は意外に作ってみると簡単ですので、プラモデル感覚でちょちょいと作ってみると愉しいかもですよ？
