学校のプロジェクトについてアドバイスを求めています。論理式を取り、その真理値表を出力するプログラムを作成することになっています。私にとって真理値表を実際に作成することはまったく難しくなく、そのためのメソッドを Java で既に作成しています。式を解析してスタックに入れるために使用できるクラスがJavaにあるかどうかを知りたいです。そうでない場合は、式の解析に関するヘルプを探しています。私がそれを考えてみると、いつでも私を得るのは括弧です. また、これが他の言語でより簡単になる場合は、その言語で行うことにオープンです。Perl はおそらく次善の言語です。
いくつかの例 (P && Q) -> R
(P || Q || R) && ((P -> R) -> Q)
ANTLR などのパーサー ジェネレーター ツールの使用が許可されている場合は、次の方法で開始できます。単純な論理言語の文法は次のようになります。
grammar Logic;
parse
: expression EOF
;
expression
: implication
;
implication
: or ('->' or)*
;
or
: and ('||' and)*
;
and
: not ('&&' not)*
;
not
: '~' atom
| atom
;
atom
: ID
| '(' expression ')'
;
ID : ('a'..'z' | 'A'..'Z')+;
Space : (' ' | '\t' | '\r' | '\n')+ {$channel=HIDDEN;};
ただし、(P || Q || R) && ((P -> R) -> Q)上記の文法から生成されたパーサーを使用して入力を解析する場合、解析ツリーには括弧 (式の解析後には関心のないもの) が含まれ、演算子は各サブのルートにはなりません。式を評価することに興味がある場合、これはあなたの人生を楽にするものではありません。
AST から特定のトークンを省略し (トークン/ルールの! 後に a を配置することで実行できます)、特定のトークン/ルールを (サブ) ツリーのルートにするように ANTLR に指示する必要があります (これは、^その後）。options最後に、文法のセクションで、単純な解析ツリーの代わりに適切な AST を作成することを示す必要があります。
したがって、上記の文法は次のようになります。
// save it in a file called Logic.g
grammar Logic;
options {
output=AST;
}
// parser/production rules start with a lower case letter
parse
: expression EOF! // omit the EOF token
;
expression
: implication
;
implication
: or ('->'^ or)* // make `->` the root
;
or
: and ('||'^ and)* // make `||` the root
;
and
: not ('&&'^ not)* // make `&&` the root
;
not
: '~'^ atom // make `~` the root
| atom
;
atom
: ID
| '('! expression ')'! // omit both `(` and `)`
;
// lexer/terminal rules start with an upper case letter
ID : ('a'..'z' | 'A'..'Z')+;
Space : (' ' | '\t' | '\r' | '\n')+ {$channel=HIDDEN;};
次のクラスでパーサーをテストできます。
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;
public class Main {
public static void main(String[] args) throws Exception {
// the expression
String src = "(P || Q || R) && ((P -> R) -> Q)";
// create a lexer & parser
LogicLexer lexer = new LogicLexer(new ANTLRStringStream(src));
LogicParser parser = new LogicParser(new CommonTokenStream(lexer));
// invoke the entry point of the parser (the parse() method) and get the AST
CommonTree tree = (CommonTree)parser.parse().getTree();
// print the DOT representation of the AST
DOTTreeGenerator gen = new DOTTreeGenerator();
StringTemplate st = gen.toDOT(tree);
System.out.println(st);
}
}
Mainクラスを実行するには、次のようにします。
java -cp antlr-3.3.jar org.antlr.Tool Logic.g javac -cp antlr-3.3.jar *.java java -cp .:antlr-3.3.jar メイン
java -cp antlr-3.3.jar org.antlr.Tool Logic.g javac -cp antlr-3.3.jar *.java java -cp .;antlr-3.3.jar メイン
次の AST のDOTソースを出力します。
( graphviz-dev.appspot.comで作成された画像)
あとは、この AST を評価するだけです。:)
Perl ではRegexp::Grammars、解析を行うために使用できます。「アリを殺す手榴弾」側に少しあるかもしれませんが、うまくいくはずです。
編集：これは（非常に簡単な）例です。
#!/usr/bin/env perl
use strict;
use warnings;
use Regexp::Grammars;
use Data::Dumper;
my $parser = qr/
<nocontext:>
<Logic>
<rule: Logic> <[Element]>*
<rule: Element> <Group> | <Operator> | <Item>
<rule: Group> \( <[Element]>* \)
<rule: Operator> (?:&&) | (?:\|\|) | (?:\-\>)
<rule: Item> \w+
/xms; #/ #Fix Syntax Highlight
my $text = '(P && Q) -> R';
print Dumper \%/ if $text =~ $parser; #/ #Fix Syntax Highlight
独自のパーサーを作成する場合は、Shunting-yardアルゴリズムを使用して、式を中置から後置表記に、または直接ツリーに変換することにより、括弧を取り除きます。
式パーサーの構築は簡単です。値を解析するときに値を計算するためのアクションを添付することも簡単です。
式言語の BNF を記述できると仮定します。
この回答は、BNF がある場合にパーサーを簡単に構築する方法を示しています。
JavaCC または ANTLR を調べてください。正規表現は機能しません。
StreamTokenizer を使用して独自のパーサーを実行することもできます。
Java 用の別のパーサー ジェネレーターはCUPです。