カテゴリまで作ってみたりして。
言語で条件分岐をする場合は、論理式による評価を行わなければなりません。
条件分岐では一番の基本となるのは if文ですが、多くの言語では
if (式) { 命令 }
となります。Pascal であれば
if (式) then begin 命令 end
です。
式は不等号で表され、= や < > が基本です。
大抵の場合は変数とセットで表され
if (i = 1) { i=1なら実行 }
if (i < 1) { i<1なら実行 }
if (i > 1) { i>1なら実行 }
のようになります。式のパーサーは別処理となりますので、ここではおいといて、if文に戻りますと、条件分岐では複数の式で分岐をしたいケースが多々あります。
例えば i の値が 10 以上かつ w の値が 20以上の場合と言った具合です。
なにも考えずに書きますと
if (i < 10) {
if (w < 20) {
命令
}
}
となります。冗長です。ステップ数増えまくりです。
そんな時は大抵
if (i < 10) and (w < 20) {
命令
}
と書くわけです。
組み合わせるとこんな状態になったりします。
if (式1) and (式2) and ((式3) or (式4)) { 命令 }
AND は論理積で OR は論理和です。
論理積は AND で結ばれた式が両方とも真である場合に真になります。
論理和は OR で結ばれた式のどちらかが真である場合に真になります。
次に論理式には四則演算と同じように括弧と式に優先順位があります。これは(おそらく殆どが)統一されており
() → and → or の順番になります。
(他にも NOT や XOR や NAND などがあります)
ここで論理式パーサーの出番です。
単純に左から評価していくだけで良ければ簡単ですが、優先順位がある為、そうはいきません。
式の構文を解析し優先順位が上位の物から順番に式を評価していく必要があります。
前置きが非常に長いのですが・・・
3日かけて作りました。論理式パーサーを。
(多分、言語の基礎的な機能ですので探せば論文やアルゴリズムなどがあると思うのですが、なにせ大抵英語だったり、C言語だったりするので参考にする方が大変です。というか参考にするくらいなら、それを使います。でもそれはイヤです)
あれこれ考えつつ150ステップほどでパーサーが出来上がりましたが今度は別の問題が。
「はたして、このパーサーは正しいのか?」
好きに考えたパーサーですので、その処理内容が正しいかどうか?を判定できるのは私自身しかいません。
本来ならばアルゴリズムを検証し、正しいかどうかを確認するのですが、困ったことにアルゴリズムなぞ深く考えずに直接コーディングをしていますので、検証ができません。
少し考えた上で、ランダムな論理式を作成する関数を作成しそれをパーサーに入力して結果を出力し、同一の論理式を Perlでパーサーの結果と同じように出力するようにして、同一性を確認しよう。と言うことになりました。
非常に力業ですが、実行と確認を繰り返す意味では科学的かもしれません(違うような気もしますが。
そして結果は正しいようです。(もちろん30,000パターンぽっちでは無く、現在バックグラウンドで 300,000パターンで検証中です。パーサーがおかしいのに順番を含めて完全一致したら奇跡です)
パーサーの中身は for文でまわしているだけで再帰すら使っていないので微妙なのですが、スタックオーバーフローの心配は無いのである意味イイカモシレマセン。