Help us understand the problem. What is going on with this article?

Polishtalk

More than 3 years have passed since last update.

はじめに

Lukas Renggli さんが書いた PetitParser はとても便利です。
東京のSmalltalk勉強会でも取り上げられたようですが、その回は休んでしまったし、小ネタとして加減算とシフト演算のポーランド記法のパーサを書いてみます。

ポーランド記法の整数加減シフト演算

どんなパーサを書きたいかというと、EBNFでいうと以下のような感じです。

expr = num | add | sub | lshift | rshift;
num = non zero digit , {digit} ;
add = '+' expr expr ;
sub = '-' expr expr ;
lshift = '<<' expr expr ;
rshift = '>>' expr expr ;
non zero digit = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
digit = '0' | non zero digit ;

PolishGrammarクラス

まずはポーランド記法の構文定義を実装します。まとまった構文定義をする場合、PetitParserには PPCompositeParser という便利なクラスがあります。これを使ってみましょう。
PPCompositeParserのサブクラスとしてPolishGrammarクラスを定義します。

PPCompositeParser subclass: #PolishGrammar
    instanceVariableNames: ''
    classVariableNames: ''
    category: 'SmalltalkAdvent2015'

これにポーランド記法の構文を定義していきます。

まずはPPCompositeParserのお約束として、startメソッドを定義しなければなりません。
後でちゃんとした定義をすることにして、まずは空のメソッドで誤魔化しておきます。

PolishGrammar
start

non zero digit と digit を定義する

まずは non zero digit を定義しましょう。non zero digit を受け付けるパーサを持つインスタンス変数を定義します。

PPCompositeParser subclass: #PolishGrammar
    instanceVariableNames: 'nonZeroDigit'
    classVariableNames: ''
    category: 'SmalltalkAdvent2015'

次に、nonZeroDigit パーサを生成するメソッドを定義します。

PolishGrammar
nonZeroDigit
    ^ '1' asParser / '2' asParser / '3' asParser / '4' asParser / '5' asParser / '6' asParser / '7' asParser / '8' asParser / '9' asParser

EBNFでの non zero digit の定義にそっくりですね。PetitParserでは文字列オブジェクトに asParser メッセージを投げることで、その文字列を受け付けるパーサを生成することができます。これを逐次的選択をあらわす / で結合していくと、まずは / の左側のパーサで受け付けられるか試して、成功したらOK、失敗したら右側のパーサを試します。

では、nonZeroDigitを試してみましょう。

PolishGrammar new nonZeroDigit parse: '123'

結果は'1'となります。

PolishGrammar new nonZeroDigit parse: '0123'

こちらはパースに失敗して「'1' expected at 0」というエラーメッセージをもつPPFailureオブジェクトを返します。

続いて、digit を定義します。

PolishGrammar
digit
    ^ '0' asParser | nonZeroDigit

ここでポイントは、nonZeroDigitというインスタンス変数にはnonZeroDigitメソッドで定義したパーサが代入されているということです。PPCompositeParserはサブクラスがインスタンス変数を定義していたら、同名のメソッドを探して自動的に初期化してくれます。いちいち「nonZeroDigit := self nonZeroDigit」みたいなことをするボイラープレートを書かなくてもよいです。Smalltalkらしいメタな仕組みですね。
digitの動作を自分でテストしてみてください。

num, add, sub, lshift, rshiftを定義する

同様に、以下のように定義していきます。

PPCompositeParser subclass: #PolishGrammar
    instanceVariableNames: 'nonZeroDigit digit expr num add sub lshift rshift'
    classVariableNames: ''
    category: 'SmalltalkAdvent2015'
PolishGrammar
num
    ^ (nonZeroDigit , digit star) flatten trim

digit starは、digitを0回以上連続して受け付けるパーサです。
flattenはパーサが受け付けた元の文字列を返すパーサ、trimは前後の空白文字を空読みするパーサを生成するメッセージです。

PolishGrammar
add
    ^ '+' asParser trim , expr , expr```
PolishGrammar
sub
    ^ '-' asParser trim , expr , expr
PolishGrammar
lshift
    ^ '<<' asParser  trim , expr , expr
PolishGrammar
rshift
    ^ '>>' asParser  trim , expr , expr
PolishGrammar
expr
    ^ num / add / sub / lshift / rshift

構文定義が一通り終わったので、ここでstartメソッドをちゃんと定義します。

PolishGrammar
start
    ^ expr

これで、PolishGrammarクラスのオブジェクトはデフォルトでexprをパースするようになります。
さて、実験してみましょう。

PolishGrammar new parse: '+ 1 << 2 3'

結果は、

#('+' '1' #('<<' '2' '3'))

となります。たぶん、あってます。

PolishInterpreterクラス

次に、PolishGrammarを実行する処理系を実装してみましょう。とても簡単です。

PolishGrammar subclass: #PolishInterpreter
    instanceVariableNames: ''
    classVariableNames: ''
    category: 'SmalltalkAdvent2015'

上記のようにPolishGrammarクラスのサブクラスとして定義するのが便利です。
あとは、継承したメソッドを使って、評価実行した結果を返すようなパーサを書けばインタプリタが出来上がります。

PolishInterpreter
num
    ^ super num ==> [ :str | str asInteger ]

上記を少し説明します。
super num は、自然数を表す文字列を読み込むパーサです。より詳しく言うと、自然数を表す文字列を読んで、受け付けた文字列を出力するパーサです。 ==> [:str | str asInteger]で、そのパーサから出力された文字列にasIntegerメッセージを投げた結果を出力するようなパーサを生成します。結果、文字列を読み込んで、受け付けたら整数を出力するようなパーサが得られます。
この==>を使った仕組みを使って、+, -, <<, >>の評価実行を実装します。

PolishInterpreter
add
    ^ super add ==> [ :triple | triple second + triple third ]
PolishInterpreter
sub
    ^ super sub ==> [ :triple | triple second - triple third ]
PolishInterpreter
lshift
    ^ super add ==> [ :triple | triple second << triple third ]
PolishInterpreter
rshift
    ^ super add ==> [ :triple | triple second >> triple third ]

インタプリタの完成です。試してみましょう。

PolishInterpreter new parse: '+ 1 << 2 3'

結果は 17 です。

PolishTranslator クラス

さらに、ポーランド記法からSmalltalkへのトランスレータを実装してみましょう。
インタプリタと同じく、PolishGrammarのサブクラスとして定義します。

PolishGrammar subclass: #PolishTranslator
    instanceVariableNames: ''
    classVariableNames: ''
    category: 'SmalltalkAdvent2015'

各メソッドを定義していきます。

PolishTranslator
add
    ^ super add ==> [ :triple | '(', triple second, ' + ', triple third, ')' ]
PolishTranslator
sub
    ^ super sub ==> [ :triple | '(', triple second, ' - ', triple third, ')' ]
PolishTranslator
lshift
    ^ super lshift ==> [ :triple | '(', triple second, ' << ', triple third, ')' ]
PolishTranslator
rshift
    ^ super rshift ==> [ :triple | '(', triple second, ' >> ', triple third, ')' ]

試してみましょう。

PolishTranslator new parse: '+ 1 << 2 3'

結果は、'(1 + (2 << 3))'となりました。んー、よくわかりませんね、じゃあ、こうしてみましょう。

Compiler evaluate: (PolishTranslator new parse: '+ 1 << 2 3')

よかった、結果はPolishInterpreterと同じく 17 です。

パーサオブジェクトの可視化

PetitParserで作ったパーサオブジェクトをインスペクタで開くと、以下のような可視化ができます。
PolishTranslator.png

いやー、moldable inspector って、いいですね!
インスペクタで開く対象はEBNFでもクラスでもなく、パーサオブジェクトです。念のため。

まとめ

こんな風に、PPCompositeParser のサブクラスとして構文定義をして、構文解析した結果を利用してインタプリタやトランスレータを構文定義クラスのサブクラスとして定義すると、構文定義と意味定義をうまく分離した実装にできて、なおかつ、文法拡張した時などの対応関係がわかりやすいので便利です。
他にも、PetitParser には PPExpressionParser など、便利な道具が沢山揃っています。
ほーら、オレオレDSLを書きたくなったでしょ?
よい開発ツールはコードを書きたい気分にさせるものなのです。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away