この記事は パーサジェネレーターLIME入門 の続きです。
正規表現相当の「あいまい検索」から一歩飛躍した「構文解析」の領分に突入するのが今回の要点です。
簡単な除算に一致させる
話を簡単にする為に使う数値を１桁の整数に限定します。
// 整数値
Matcher Number = '0'.To('9');
// 除算
Matcher DivExp = Number + '/' + Number;
この定義で3/3のような単純な数式にマッチしますが
3/3/3/3/3/3/3/3/3のようないくつも連結された数式には対応できません。
無限に循環する定義なら、無限の項数でも対応できる
式がいくつ連結されても大丈夫なように定義を書き換えます。
// 整数値
Matcher Number = '0'.To('9');
// 「除算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher DivExp = new RecursionMatcher();
// 「除算」の中身を設定する。
DivExp.Inner = ((Number | DivExp) + '/' + Number);
二項演算だろうが三項演算だろうが百項演算だろうが一致するマッチャーができました。
なぜMatcher型ではなくRecursionMatcher型なのか？
本音としては
Matcher DivExp = ((Number | DivExp) + '/' + Number);
と書きたいところですが「初期化していないDivExpは使えません。」とコンパイラに怒られます。
そこで必要になるのがRecursionMatcher型です。
RecursionMatcher型としてDivExpを初期化し、DivExp.Innerプロパティとして後から中身を設定しています。
では、数式の文字列を与えた時にどう一致判定が行われるかを見てみましょう。
数式 1/2 はDivExpと一致するのか？
1 は(Number | DivExp)に一致するがDivExpとNumberのどちらに一致するか？ もちろんNumberです。
/ は/と一致します。
2 はNumberと一致します。
これで数式 1/2 はDivExpに一致すると示されました。
数式 1/2/3 はDivExpと一致するのか？
ここで注意すべきなのは 1/2/3 をどう分割すれば((Number | DivExp) + '/' + Number)のそれぞれと一致するかです。
可能性は以下の２通りです。
1 / 2/3
1/2 / 3
では前者の 1 / 2/3 から試してみましょう。
1 はDivExpとNumberのどちらに一致するか？ もちろんNumberです。
/ は/と一致します。
2/3 はNumberと一致…しません。
どうやら 1 / 2/3 と分ける方向では無理のようです。
正解は後者の 1/2 / 3 です。
1/2/3 はDivExpの中で 1/2 / 3 に分割されます。
1/2 はDivExpの中で 1 / 2 に分割されます。
1 はNumberと一致します。
/ は/と一致します。
2 はNumberと一致します。
3 はNumberと一致します。
項数が二項から三項に増えても１回余計にDivExpに潜れば対処できます。
これで数式 1/2/3 はDivExpに一致すると示されました。
数式 1/2/3/4 はDivExpと一致するのか？
２回余計にDivExpに潜ればＯＫです。
1/2/3/4 はDivExpの中で 1/2/3 / 4 に分割されます。
1/2/3 はDivExpの中で 1/2 / 3 に分割されます。
1/2 はDivExpの中で 1 / 2 に分割されます。
1 はNumberと一致します。
/ は/と一致します。
2 はNumberと一致します。
3 はNumberと一致します。
/ は/と一致します。
4 はNumberと一致します。
これで数式 1/2/3/4 はDivExpに一致すると示されました。
数式 1/2/3/4/5 はDivExpと一致するのか？
３回余計にDivExpに潜ればＯＫです。
1/2/3/4/5 はDivExpの中で 1/2/3/4 / 5 に分割されます。
1/2/3/4/ はDivExpの中で 1/2/3 / 4 に分割されます。
1/2/3 はDivExpの中で 1/2 / 3 に分割されます。
1/2 はDivExpの中で 1 / 2 に分割されます。
1 はNumberと一致します。
/ は/と一致します。
2 はNumberと一致します。
3 はNumberと一致します。
/ は/と一致します。
4 はNumberと一致します。
/ は/と一致します。
5 はNumberと一致します。
これで数式 1/2/3/4/5 はDivExpに一致すると示されました。
以下、項数が無限まで増えても同様に対応できると納得頂けたでしょう。
実は演算の優先順位にも対応していた
実は先の例の((Number | DivExp) + '/' + Number)という定義は演算の優先順位にも対応する定義でした。
1/2/3/4/5 という数式を (((1/2)/3)/4)/5 と左から順に解釈する検索パターンです。
(Number + '/' + (Number | DivExp))という風に定義を替えても式全体にマッチしますが、
1/2/3/4/5 という数式を 1/(2/(3/(4/5))) と右から順に解釈してしまいます。
次は減算にも対応してみる
先に「演算の優先順位(左から順に解釈する)」を解説しましたが、
今から扱うのは「演算子の優先順位」です。
要するに加減算より乗除算の方が優先する事を実装します。
// 整数値
Matcher Number = '0'.To('9');
// 「除算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher DivExp = new RecursionMatcher();
// 「除算」の中身を設定する。
DivExp.Inner = ((Number | DivExp) + '/' + Number);
// 「減算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher SubExp = new RecursionMatcher();
// 「減算」の中身を設定する。
SubExp.Inner = ((Number | DivExp | SubExp) + '-' + (Number | DivExp));
整数値と除算の定義に関しては前回までと同じです。
減算の定義を追加しただけになります。
減算の定義の要点は
「整数値だけでなく、減算より優先度の高い除算を受け入れる」です。
より優先度の低い演算子にも対応してみる
左シフト演算にも対応させてみます。
// 整数値
Matcher Number = '0'.To('9');
// 「除算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher DivExp = new RecursionMatcher();
// 「除算」の中身を設定する。
DivExp.Inner = ((Number | DivExp) + '/' + Number);
// 「減算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher SubExp = new RecursionMatcher();
// 「減算」の中身を設定する。
SubExp.Inner = ((Number | DivExp | SubExp) + '-' + (Number | DivExp));
// 「左シフト演算」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher LShiftExp = new RecursionMatcher();
// 「左シフト演算」の中身を設定する。
LShiftExp.Inner = ((Number | DivExp | SubExp | LShiftExp) + "<<" + (Number | DivExp | SubExp));
整数値と除算と減算の定義に関しては前回までと同じです。
左シフト演算の定義を追加しただけになります。
左シフト演算の定義の要点は
「整数値だけでなく、左シフト演算より優先度の高い除算と減算を受け入れる」です。
二項演算式に一致する定義を一般化する
左から順に演算する★演算式の定義を一般化すると
★演算式 = (★を超える優先度の式 | ★演算式) + "★" + ★を超える優先度の式です。
★の左辺に「★演算式」を加える事で定義を無限に循環させ、無限の項数に対応します。
今回触れませんでしたが、
右から順に演算する▲演算式の定義を一般化すると
▲演算式 = ▲を超える優先度の式 + "▲" + (▲を超える優先度の式 | ▲演算式)です。
もしC言語のパーサを実装するならば、代入演算子のパースはこちらの定義で実装します。
次回の予定
次回はデクリメントやマイナス符号のような単項演算子に一致させる実装を解説します。
5------5 という式があった場合、どう解釈すべきでしょうか？