ダイス式を計算するプログラムを作ってみる(1)

photo by Tomi Tapio (CC BY-SA 2.1)

あるアイデアをふと思い立った時に、それを最後まで実行するために役立つ手段の一つが、「やる」と宣言してしまうこと、だそうですね。

そんなわけで思いついたことを実行してみます。

やりたいこと

"2d6" とか "D12+5" みたいな、ゲーマーにはおなじみのダイス式を入力すると、内部でダイスを振って結果を出してくれるプログラムを書く。これを通して構文解析の初歩の初歩とか練習してみる。

実現のための順序

仕様を決める
それを BNF で書き下す
構文解析に向いた形式に BNF を置き換える
それを python のコードに落とす
ウマー

仕様を決める

じゃあまず仕様を決めます。これはだいたいこんな感じで。

カッコつきの四則演算を許す
整数のみ表記可能（結果は整数でないこともある）
ダイスの記号は D または d として（どっちも同じ意味）、表現形式は "mDn" とする。「n面ダイスをm回振って出た目の合計を返す」の意。
- ただしmとnは数または数式。解析を楽にする都合上、mとnは省略できないものとする（たとえば "1D6"はいいけど "2D" とか "D6" とかは不可とする）。
- m と n には数式が許されるので (3+2)d(4*2)みたいなのもオーケー。あんまり意味ないけど、こっちの方が解析が楽。
- ダイス記号の結合度は最高とする。たとえば 2+3D6*4 とあったら、2+(3D6)*4と解釈する。
すべてのダイスは最小の出目が1、最大がmとする。

BNF で書く

仕様も決まったので、それを BNF で書き下してみます。あっちこっちで見かけた「電卓プログラム」の BNF をちょっと参考にしつつ、こんな感じで。*1

数についてはあまり難しくないですよね…

<数字>          ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
<非ゼロ数字>    ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
<数字列>        ::= <数字>+
<数>            ::= <非ゼロ数字><数字列> | <数>

あと、演算子もまぁ、自明というか。

<加減演算子>    ::= "+" | "-"
<乗除演算子>    ::= "*" | "/"
<ダイス演算子>  ::= "d" | "D"

で、ここからが少しややこしいんですが、こういう感じです。

<式>            ::= <式><加減演算子><因子> | <因子>
<因子>          ::= <因子><乗除演算子><ダイス項> | <ダイス項>
<ダイス項>      ::= <ダイス項><ダイス演算子><項> | <項>
<項>            ::= "(" <式> ")" | <数>

結局、最初の<式>の所で、右辺の最初が<式>になってて、ループしてるのがわかると思います(他のところも一緒ですね)。このままでは、堂々めぐりになっちゃって解決しないんですが、それをこれから何とかします。

構文解析に向いた形にBNFを書き換える

上に書いた<式>の構文ですが、同じ構文の最初に<式>って書いてあるので、このままだと解決できません。こういうのを「左再規性」って言って、これがあるとうまくいかないんですね。そんなわけでこれをどうにかします。

BNF から左再帰性を取り除くには簡単な方法があります。これは

<A> ::= <A><B> | <C>

という構文がある時には、こういう風に置き換えることができるというルールです。

<A1> ::= <C><A2>
<A2> ::= <B><A2>

これを使って最初の構文を置き換えると、こういう感じになります。ちなみにεは「何もない」を明示的に示す記号です。あんまり気にしなくて（というか無視しちゃって）構いません。

<式1>           ::= <因子1><式2>
<式2>           ::= <加減演算子><式2> | ε
<因子1>         ::= <ダイス項1><因子2>
<因子2>         ::= <乗除演算子><因子2> | ε
<ダイス項1>     ::= <項><ダイス項2>
<ダイス項2>     ::= <ダイス演算子><ダイス項2> | ε
<項>            ::= "(" <式1> ")" | <数>

で、このうち<なんとか2>ってなっている式は全部自分と同じ名前で終わっています。これを「末尾回帰」というのですが、これは全部「０回以上の繰り返し」で置き換えることができます。これは「閉包」というそうなのですが、要は正規表現でいうところの「*(アスタリスク)」です。それを使って書き換えると、<なんとか2>は全部消えて、こんな具合になります。*2

<式1>           ::= <因子1> (<加減演算子><因子1>)*
<因子1>         ::= <ダイス項1> (<乗除演算子><ダイス項1>)*
<ダイス項1>     ::= <項> (<ダイス演算子><項>)*
<項>            ::= "(" <式1> ")" | <数>

あ、表記上、ただの「(」と「"("」は違うものなので注意してください。前者は解釈を束ねる記号ですが、後者は文字列上に現れる左括弧記号そのものを表しています。

あと、<なんとか1>ってのも紛らわしいので全部取っちゃいます。

<式>            ::= <因子> (<加減演算子><因子>)*
<因子>          ::= <ダイス項> (<乗除演算子><ダイス項>)*
<ダイス項>      ::= <項> (<ダイス演算子><項>)*
<項>            ::= "(" <式> ")" | <数>

すっきりしました。

<式> は１つ以上の<因子>を<加減演算子>で連結したもの
<因子> は１つ以上の<ダイス項>を<乗除演算子>で連結したもの
<ダイス項>は１つ以上の<項>を<ダイス演算子>で連結したもの
<項>は "(" と ")" に括られた<式>か、<数>のどちらか

です。

さて、ここまで来るとどういうやり方で文字列を解釈していけばいいのかが分かります。

大事なのはこれが、ある注目点から１つ先注目点を見るだけで、それが何であるかを決定づけらえるかどうかです。それを次の１個だけ読めばいいのなら、それはかなり楽に処理をこなすことができます。これを「LL(1)」というそうです。

今回のケースでは：

<式> : <因子>からの分岐は <加減演算子>があるかどうかで決まりますが、これは "+" か "-" があるかどうかだけで決められるので1文字あれば十分です。
<因子>：上と同じく<ダイス項>以降の分岐は <乗除演算子> の有無で決まりますが、"*" と "/" の有無で判別可能です。やはり１文字で OK。
<ダイス項>：同じく<ダイス演算子>の "D" または "d" で分岐を判別できます。１文字でOK。
<項>： | の前と後ろは、"(" で始まっているかどうかで区別できます。1文字でOK。

以上から、この構文はすべて次の１文字を読むだけで分岐が可能であることが分かります。すなわち LL(1) の構文です。LL(1) ということは、先読み１文字だけで構文を判別することができ、コーディングがかなり楽になります。そう安心できたところで、次に進みます。

…そろそろ疲れたので、以下次回。図らずも連載に…w