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

Question

我正在寻找关于我学校项目的一些建议.我应该创建一个程序,它采用逻辑表达式并为其输出真值表.实际上为我创建真值表并不困难,我已经用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中的某些令牌(这可以通过在令牌/规则! 之后放置一个)并使某些令牌/规则成为其(子)树的根(这可以通过放置一个^之后).最后,您需要在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!:)