<< 2024/04 >> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
|
論理式の構文解析機(パーサー)
08/05/18 03:52 / DScript
カテゴリまで作ってみたりして。
言語で条件分岐をする場合は、論理式による評価を行わなければなりません。 条件分岐では一番の基本となるのは 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文でまわしているだけで再帰すら使っていないので微妙なのですが、スタックオーバーフローの心配は無いのである意味イイカモシレマセン。 [更新日付:2008/05/18 04:40:54]
トラックバックを見る(0) Log Link [https://akisoftware.com/cgi-bin/blom.exe?akisoft+sl+4e8c65f9cabe312eafdcc132a493e3f24118789c] TB Link [https://akisoftware.com/cgi-bin/blom.exe?akisoft+tb+4e8c65f9cabe312eafdcc132a493e3f24118789c] 記事へのコメント コメントはありません |
@AKISoftOfficialをフォロー
掲示板 サポートBBS PMailServer BBS アクセスの多い記事
最新記事(カテゴリ別)
PMailServer2 Version 2.53 をリリースしました。
04/08 00:50 フリー版からの製品版移行時の MTA 並列数について 02/17 23:52 メールサーバーの開発を始めて20年 02/07 21:46 PMailServer2 Version 2.52a をリリースしました。 12/26 14:02 PMailServer2 Version 2.52 をリリースしました。 10/01 10:48 PMailServer2 Version 2.51b をリリースしました。 09/19 01:43 PMailServer2 Version 2.51b(仮) Memo 09/12 00:33 PMailServer2 Version 2.51a をリリース、及び脆弱性についてのお知らせ 09/05 01:15 PMailServer2 Version 2.51a Memo 08/21 00:48 アドレスV125(K5)のスターターリレーの交換 08/04 10:10 最新コメント
コメントはありません
UUアクセス数
今日は 369回
昨日は 330回 トータル 305225回 3ヶ月記事別ランキング
プロフィール
Z80から68系、8086系を経由して
Pascalに移行。現在は Delphiをメインに C/C#も囓ってみたり。 「無い物は作れ」の精神で年がら年中なにかを作っています。 すぐ自前で作りたがるので無駄に工数が上がったりして自爆してみたりもします。 好きな物は麺類とお煎餅 Blom内検索
BLOM Version 1.39 ©2007-15 A.K.I Software all rights reserved. |