寻找项目建议。 解析逻辑表达式

我正在为我的学校项目寻找一些建议。 我应该创建一个程序，它采用逻辑表达式并为其输出真值表。 实际上为我创建真值表并不困难，我已经用Java编写了这些方法。 我想知道java中是否有任何类可以用来解析表达式并将其放入堆栈中。 如果不是，我正在寻找解析表达式的帮助。 每当我尝试思考它时，它就是括号。 此外，如果这在任何其他语言中都比较容易，我会愿意这样做。 Perl可能是我的下一个最好的语言。

一些例子（P && Q） – > R.

（P || Q || R）&&（（P – > R） – > Q）

Answer 1

如果您被允许使用像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中的某些令牌（这可以通过在令牌/规则之后放置一个!来完成）并使某些令牌/规则成为他们（子）树的根（这可以通过放置来完成） a ^之后）。 最后，您需要在语法的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类，执行：

* nix中/ MacOS的

  java -cp antlr-3.3.jar org.antlr.Tool Logic.g 
 javac -cp antlr-3.3.jar * .java
 java -cp。：antlr-3.3.jar 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 Main 

这将打印以下AST的DOT源 ：

（使用graphviz-dev.appspot.com制作的图像）

现在您需要做的就是评估此AST！ 🙂

Answer 2

在Perl中，您可以使用Regexp::Grammars进行解析。 这可能是“杀死ant”手镯的一点点，但它应该有效。

编辑：这是一个（非常快）的例子，可能会让你去。

 #!/usr/bin/env perl use strict; use warnings; use Regexp::Grammars; use Data::Dumper; my $parser = qr/    <[Element]>*   |  |   \( <[Element]>* \)  (?:&&) | (?:\|\|) | (?:\-\>)  \w+ /xms; #/ #Fix Syntax Highlight my $text = '(P && Q) -> R'; print Dumper \%/ if $text =~ $parser; #/ #Fix Syntax Highlight 

Answer 3

查看JavaCC或ANTLR。 正则表达式不起作用。

您也可以使用StreamTokenizer运行自己的解析器。

Answer 4

构建表达式解析器很容易。 在解析它时附加动作以计算值也很容易。

我假设您可以为您的表达语言编写BNF。

如果您有BNF，此答案将向您展示如何轻松构建解析器。

是否有可用于8位嵌入式系统的flex / bison的替代方案？

Answer 5

如果您想编写自己的解析器，请使用Shunting-yard算法通过将表达式从中缀转换为后缀表示法或直接转换为树来删除括号。

Answer 6

另一个Java解析器生成器是CUP 。