寻找项目建议。解析逻辑表达式 [英] Looking for advice on project. Parsing logical expression

问题描述

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

I'm looking for some advice on my school project. I am supposed to create a program that takes a logical expression and outputs a truth table for it. The actually creating of the truth table for me is not difficult at all and I've already wrote the methods in Java for it. I would like to know if there are any classes in java that I could use to parse the expression for me and put it into a stack. If not I'm looking for help on parsing the expression. It's the parentheses that get me whenever I try and think it through. Also if this would be easier in any other language I would be open to doing it in that. Perl is probably my next best language.

一些例子
（P&& Q） - > R

Some examples (P && Q) -> R

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

(P || Q || R) && ((P -> R) -> Q)

推荐答案

如果你被允许使用像ANTLR这样的解析器生成器工具，这是你如何开始。简单逻辑语言的语法可能如下所示：

If you're allowed to use a parser generator tool like ANTLR, here's how you could get started. The grammar for a simple logic-language could look like this:

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）使用从上面的语法生成的解析器，解析树将包含括号（解析表达式后您不感兴趣的东西）和运算符不会是每个子树的根，如果你对评估表达式感兴趣，这不会让你的生活变得更容易。

However, if you'd parse input like (P || Q || R) && ((P -> R) -> Q) with a parser generated from the grammar above, the parse tree would contain the parenthesis (something you're not interested in after parsing the expression) and the operators would not be the root of each sub-trees, which doesn't make your life any easier if you're interested in evaluating the expression.

你会需要告诉ANTLR省略AST中的某些令牌（这可以通过在令牌/规则之后放置！ 来完成）并制作某些令牌/规则它们（子）树的根（这可以通过在它之后放置 ^ 来完成）。最后，您需要在语法的选项部分中指出您希望创建正确的AST而不是简单的解析树。

You'll need to tell ANTLR to omit certain tokens from the AST (this can be done by placing a ! after the token/rule) and make certain tokens/rules the root of their (sub) tree (this can be done by placing a ^ after it). Finally, you need to indicate in the options section of your grammar that you want a proper AST to be created instead of a simple parse tree.

所以，上面的语法看起来像这样：

So, the grammar above would look like this:

// 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;};

您可以使用以下类测试解析器：

You can test the parser with the following class:

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 class，do：

Now to run the Main class, do:

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

Windows

Windows

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的href =http://www.graphviz.org/content/dot-language =nofollow noreferrer> DOT来源：

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

(image produced with graphviz-dev.appspot.com)

现在所有你需要做的就是评估这个AST！ ：）

Now all you need to do is evaluate this AST! :)

这篇关于寻找项目建议。解析逻辑表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！