16

個人的なプロジェクトとして真理値表ジェネレーターを書きたいと思っています。

こことここに Web ベースのオンラインのものがいくつかあります。

代替テキスト
(Example screenshot of an existing Truth Table Generator)

次の質問があります。

  • ((P => Q) & (Q => R)) => (P => R)のような式を解析するにはどうすればよいですか?
  • ANTLr や YACC などのパーサー ジェネレーターを使用する必要がありますか、それとも正規表現をそのまま使用する必要がありますか?
  • 式を解析したら、真理値表を生成するにはどうすればよいですか? 式の各セクションを最小のコンポーネントに分割し、テーブルの左側から右側に再構築する必要があります。そのようなものをどのように評価しますか？

これらの任意の式の解析と最終的に解析された式の評価に関するヒントを教えてもらえますか?

4

5 に答える 5

24

これは素晴らしい個人的なプロジェクトのように聞こえます。コンパイラの基本的な部分がどのように機能するかについて多くを学びます。パーサジェネレータを使用することはスキップします。これがあなた自身の啓蒙のためであるならば、あなたはそれをすべてゼロから行うことによってより多くを学ぶでしょう。

そのようなシステムが機能する方法は、私たちが自然言語を理解する方法の形式化です。「犬、ローバー、彼の食べ物を食べました。」という文をあなたに与えると、あなたが最初にすることはそれを言葉と句読点に分割することです。「The」、「SPACE」、「dog」、「COMMA」、「SPACE」、「Rover」、...それは「トークン化」または「字句解析」です。

次に行うことは、トークンストリームを分析して、文が文法的であるかどうかを確認することです。英語の文法は非常に複雑ですが、この文はかなり単純です。SUBJECT-APPOSITIVE-VERB-OBJECT。これが「構文解析」です。

文が文法的であることがわかったら、文を分析して実際に意味を引き出すことができます。たとえば、この文には、主語、同格、およびオブジェクト内の「彼」の3つの部分があり、すべて同じエンティティ、つまり犬を参照していることがわかります。犬が食べているものであり、食べ物が食べられているものであることがわかります。これはセマンティック分析フェーズです。

コンパイラーには、人間にはない第4フェーズがあります。つまり、コンパイラーは、言語で記述されたアクションを表すコードを生成します。

だから、それをすべて行います。言語のトークンを定義することから始め、基本クラスTokenとそれぞれの派生クラスの束を定義します。（IdentifierToken、OrToken、AndToken、ImpliesToken、RightParenToken ...）。次に、文字列を受け取り、IEnumerable'を返すメソッドを記述します。それがあなたのレクサーです。

次に、言語の文法が何であるかを理解し、IEnumerableを言語の文法エンティティを表す抽象構文ツリーに分割する再帰下降パーサーを記述します。

次に、そのツリーを調べて、「いくつの異なる自由変数がありますか？」のように計算するアナライザーを作成します。

次に、真理値表を評価するために必要なコードを吐き出すコードジェネレーターを記述します。ILを吐くのはやり過ぎのように思えますが、本当にバフになりたいのであれば、そうすることができます。式ツリーライブラリにそれを行わせる方が簡単かもしれません。解析ツリーを式ツリーに変換してから、式ツリーをデリゲートに変換して、デリゲートを評価できます。

幸運を！

于 2009-07-05T22:34:17.117 に答える
2

パーサージェネレーターはやり過ぎだと思います。この問題を解決するには、式を後置式に変換して後置式を評価する(または中置式から式ツリーを直接構築し、それを使用して真理値表を生成する) というアイデアを使用できます。

于 2009-07-05T21:44:49.603 に答える
1

Mehrdad が言及しているように、レクサー/パーサーの構文を学習するのと同じ時間で、解析をハンドロールできるはずです。必要な最終結果は、与えられた式の抽象構文ツリー (AST) です。

次に、式で定義されたシンボルの入力の組み合わせを作成する入力ジェネレーターを構築する必要があります。

次に、最初のステップで解析したルール (AST) に基づいて、入力セット全体を反復し、各入力コンボの結果を生成します。

どのように私はそれを行うだろう:

ツリーを解析するときにラムダ関数を使用して AST/ルールを表現し、解析しながらシンボル テーブルを構築し、入力セットを構築して、シンボル テーブルをラムダ式ツリーに解析し、結果を計算することを想像できます。

于 2009-07-05T22:39:39.853 に答える
1

あなたの目標がブール式を処理することである場合、パーサージェネレーターとそれに付随するすべての機械は、それらがどのように機能するかを学びたくない限り、時間の無駄です (その場合はどれでも問題ありません)。

しかし、式を「評価」した結果を計算して返すブール式用の再帰降下パーサーを手動で構築するのは簡単です。このようなパーサーは、最初のパスで一意の変数の数を決定するために使用できます。ここで、「評価」は「新しい変数名ごとに 1 を数えること」を意味します。N 個の変数に対して考えられるすべての真理値を生成するジェネレータを作成するのは簡単です。値のセットごとに、単純にパーサーを再度呼び出し、それを使用して式を評価します。ここで、評価は「演算子に従って部分式の値を結合する」ことを意味します。

文法が必要です:

formula = disjunction ;
disjunction = conjunction 
              | disjunction "or" conjunction ;
conjunction = term 
              | conjunction "and" term ;
term = variable 
       | "not" term 
       |  "(" formula ")" ;

あなたのものはもっと複雑になる可能性がありますが、ブール式の場合はそれほど複雑になることはありません。

文法規則ごとに、解析対象の文字列にグローバルな「スキャン」インデックスを使用する 1 つのサブルーチンを記述します。

  int disjunction()
 // returns "-1"==> "not a disjunction"
 // in mode 1:
 // returns "0" if disjunction is false
 // return  "1" if disjunction is true
 { skipblanks(); // advance scan past blanks (duh)
   temp1=conjunction();
   if (temp1==-1) return -1; // syntax error
   while (true)
     { skipblanks();
       if (matchinput("or")==false) return temp1;
       temp2= conjunction();
       if (temp2==-1) return temp1;
       temp1=temp1 or temp2;
     }
  end

  int term()
  { skipblanks();
    if (inputmatchesvariablename())
       { variablename = getvariablenamefrominput();
         if unique(variablename) then += numberofvariables;
         return lookupvariablename(variablename); // get truthtable value for name
       }
     ...
  }

各解析ルーチンは、これほど複雑になります。真剣に。

于 2009-08-22T11:57:55.027 に答える
0

pyttgen プログラムのソース コードはhttp://code.google.com/p/pyttgen/source/browse/#hg/srcで入手できます。論理式の真理値表を生成します。コードは ply ライブラリに基づいているため、非常にシンプルです :)

于 2010-05-14T20:19:25.447 に答える