逻辑表达式解析器
我正在尝试为以下表达式创建一个逻辑表达式解析器： （（变量A -> 变量B）而不是变量C） 对于给定的变量值，解析器应该能够返回结果是 true 还是 false。
基本上，表达式仅包含变量、逻辑运算符（或、与、蕴涵、等价、否定和括号）。
我想问实现这种解析器的最佳方法是什么（使用 AST 树，或逆波兰表示法）？ 或者也许已经存在一些可以完成这项工作的开源解析器？
I'm trying to create a logic expression parser for expressions like:
((VariableA -> VariableB) AND NOT VariableC)
The parser should be able to return, whether the result is true or false for given values of variables.
Basically, the expressions will only contain variables, logical operators (or, and, implication, equivalence, negation and parentheses).
I would like to ask what is the best way to implement this kind of parser (using AST tree, or Reverse Polish Notation)? Or maybe there already exist some open source parsers that can do the job?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您的目标语言是什么？
如果您想创建一个解析器，也许 ANTLR 会为您解决问题。 它最初是基于 java 的，但它具有多种语言的生成器（例如，我用它来生成 C# 解析器），并且上手并不难。
它有一个很好的编辑器（ANTLRWorks），可以测试语法，这是一个很好的优点。
What language are you targeting?
If you want to create a parser, maybe ANTLR will do the trick for you. It is originally java-based but it has generators for a variety of languages (I use it for generating a C# parser for example) and is no too difficult to pick-up.
It has a nice editor (ANTLRWorks) that allows testing the grammar, which is a nice plus.
如果我是你，我会使用 RPN。 这应该会在解析它时为您节省一些麻烦，并且该算法应该像在运算符进入时推送和弹出一堆值一样简单。您也不必欺骗括号，这应该会让生活变得更轻松。 唯一真正的缺点是大多数人不熟悉后缀（AKA RPN）表示法。
堆栈可能也比树更容易使用。
只是我的 2 美分:)
I would use RPN if I were you. That should save you some grief when parsing it, and the algorithm should be as simple as pushing and popping a stack of values as the operators come in. You won't have to fool with parentheses either, which should make life easier. The only real downside is that most people aren't familiar with postfix (AKA RPN) notation.
A stack will probably be easier to work with than a tree as well.
Just my 2¢ :)
我确信已经有工具可以做到这一点（逻辑评估），但我找不到任何工具。 如果您使用诸如 Bison（YACC，用于 C）或 ANTLR（生成多种语言，但使用 Java）您不必太担心解析。 Coco/R 是另一个解析器生成器，可以生成许多不同的语言。 如果你想自己做，我会使用 RPN 或前缀表示法（我认为这比 RPN 更简单）。 这将使解析变得更简单，但会惹恼您的用户。
I'm sure there are already tools that do this (logic evaluation), but I couldn't find any. If you use a tool such as Bison (YACC, for C) or ANTLR (generates a number of languages, but uses Java) you won't have to worry much about parsing. Coco/R is another parser generator that can generate many different languages. If you want to do it yourself though, I would use RPN or prefix notation (which I think is simpler than RPN). This will make it much simpler to parse, but will annoy your users.
这听起来像是一项家庭作业:-)
首先你必须递归地定义你的语言。
变量的格式良好 (WFF)
如果 X 是 WFF，则 X 不是 WFF
如果 X 和 Y 是 WFF，则 (X -> Y) 是 WFF
如果 X 和 Y 是 WFF，则 (X AND Y 是) a WFF
定义语法后，使用 LEX 或 Flex 或 Java 的等效项
或者您编写简单扫描仪的首选语言。
使用 YACC 或 Bison 或等效工具来编写后代递归解析器。
稍后将属性添加到语法中，以便以下降递归方式获得要计算的表达式的计算结果。
It sounds like a homework :-)
First you have to define your language recursively.
A variable is well formed form (WFF)
if X is a WFF then not X is a WFF
if X and Y are WFF then (X -> Y) is a WFF
if X and Y are WFF then (X AND Y is) a WFF
Once the grammar is defined use LEX or Flex or the equivalent for Java
or your prefered language for writing a trivial scanner.
Use YACC or Bison or the equivalent for writing the descendent recursive parser.
Later add attributes to the grammar in order to get the evaluation of the expression you want to evaluate in a descendent recursive way.
如果您使用 Python，请尝试 此表达式解析器/评估器，使用以下代码编写pyparsing，作为起点。
If you are working in Python, try this expression parser/evaluator, written using pyparsing, as a starting point.
您看过 http://ncalc.codeplex.com 吗？
它是可扩展的、快速的（例如有自己的缓存），使您能够在运行时通过处理 EvaluateFunction/EvaluateParameter 事件来提供自定义函数和变量。 它可以解析的示例表达式：
Expression e = new Expression("Round(Pow(Pi, 2) + Pow([Pi2], 2) + X, 2)");
e.Parameters["Pi2"] = new Expression("Pi * Pi");
e.参数["X"] = 10;
e.EvaluateParameter += delegate(字符串名称, ParameterArgs args)
{
如果（名称==“Pi”）
args.Result = 3.14;
};
调试.Assert(117.07 == e.Evaluate());
它还处理 unicode 和 许多本地数据类型。 如果您想更改语法，它会附带一个鹿角文件。 还有一个支持 MEF 加载新功能的 fork。
Have you seen http://ncalc.codeplex.com ?
It's extensible, fast (e.g. has its own cache) enables you to provide custom functions and varaibles at run time by handling EvaluateFunction/EvaluateParameter events. Example expressions it can parse:
Expression e = new Expression("Round(Pow(Pi, 2) + Pow([Pi2], 2) + X, 2)");
e.Parameters["Pi2"] = new Expression("Pi * Pi");
e.Parameters["X"] = 10;
e.EvaluateParameter += delegate(string name, ParameterArgs args)
{
if (name == "Pi")
args.Result = 3.14;
};
Debug.Assert(117.07 == e.Evaluate());
It also handles unicode & many data type natively. It comes with an antler file if you want to change the grammer. There is also a fork which supports MEF to load new functions.