3

我正在尝试为以下表达式创建一个逻辑表达式解析器： ((VariableA -> VariableB) AND NOT VariableC) 对于给定的变量值，无论结果是真还是假，解析器都应该能够返回。

基本上，表达式将只包含变量、逻辑运算符（或、和、蕴涵、等价、否定和括号）。

我想问一下实现这种解析器的最佳方法是什么（使用 AST 树或反向波兰表示法）？或者也许已经存在一些可以完成这项工作的开源解析器？

4

6 回答 6

2

你的目标是什么语言？

如果您想创建一个解析器，也许ANTLR会为您解决问题。它最初是基于 java 的，但它具有多种语言的生成器（例如，我用它来生成 C# 解析器）并且不难上手。它有一个很好的编辑器（ANTLRWorks），可以测试语法，这是一个很好的加分项。

于 2009-05-05T20:27:05.807 回答
1

如果我是你，我会使用 RPN。这应该可以在解析它时为您省去一些麻烦，并且算法应该像在运算符进入时推送和弹出一堆值一样简单。您也不必用括号来愚弄，这应该会让生活更轻松。唯一真正的缺点是大多数人不熟悉后缀（AKA RPN）表示法。

堆栈可能也比树更容易使用。

只是我的 2 美分 :)

于 2009-05-05T20:23:05.833 回答
0

如果您使用 Python，请尝试使用pyparsing编写的表达式 parser/evaluator作为起点。

于 2010-08-27T09:22:19.983 回答
0

我确信已经有工具可以做到这一点（逻辑评估），但我找不到任何工具。如果您使用诸如Bison（YACC，用于 C）或ANTLR（生成多种语言，但使用 Java）之类的工具，则不必担心解析。Coco/R是另一个可以生成许多不同语言的解析器生成器。如果你想自己做，我会使用 RPN 或前缀表示法（我认为它比 RPN 更简单）。这将使解析变得更加简单，但会惹恼您的用户。

于 2009-05-05T20:30:52.850 回答
0

这听起来像一个家庭作业:-)

首先，您必须递归地定义您的语言。

变量是良构形式 (WFF)

如果 X 是 WFF 则不是 X 是 WFF

如果 X 和 Y 是 WFF，则 (X -> Y) 是 WFF

如果 X 和 Y 是 WFF，那么（X AND Y 是）一个 WFF

定义语法后，使用 LEX 或 Flex 或 Java 的等效语言或您喜欢的语言来编写简单的扫描器。

使用 YACC 或 Bison 或等效物来编写后代递归解析器。

稍后将属性添加到语法中，以便以后代递归方式获得要评估的表达式的评估。

于 2009-05-05T20:35:22.747 回答
0

你看过http://ncalc.codeplex.com吗？

它是可扩展的、快速的（例如有自己的缓存），使您能够通过处理 EvaluateFunction/EvaluateParameter 事件在运行时提供自定义函数和变量。它可以解析的示例表达式：

表达式 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()); 它还原生处理 unicode 和许多数据类型。如果您想更改语法，它会附带一个 antler 文件。还有一个 fork 支持 MEF 加载新功能。

于 2010-12-09T09:40:31.467 回答