我正在为我的学校项目寻求一些建议。我应该创建一个程序，该程序采用逻辑表达式并为其输出真值表。对我来说，实际创建真值表一点也不难，而且我已经用 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)使用从上述语法生成的解析器一样解析输入，则解析树将包含括号（解析表达式后您不感兴趣的东西）并且运算符不会是每个子的根 -树，如果您对评估表达式感兴趣，这不会让您的生活变得更轻松。
您需要告诉 ANTLR 从 AST 中省略某些标记（这可以通过在标记/规则! 之后放置一个来完成）并使某些标记/规则成为它们（子）树的根（这可以通过放置一个^之后）。最后，您需要在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
查看 JavaCC 或 ANTLR。正则表达式不起作用。
您也可以使用 StreamTokenizer 运行自己的解析器。
构建表达式解析器很容易。在解析时附加操作以计算值也很容易。
我假设您可以为您的表达语言编写 BNF。
如果您有 BNF，此答案将向您展示如何轻松构建解析器。
如果您想编写自己的解析器，请使用Shunting-yard 算法通过将表达式从中缀转换为后缀表示法或直接转换为树来去除括号。
Java 的另一个解析器生成器是CUP。