逻辑表达式解析器

Question

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

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

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

- Adam

---

实现一个递归下降解析器。逻辑表达式非常简单，并且可以轻松地通过这种方式进行解析。解析操作可以评估变量，从栈中推入/弹出中间值。这应该是大约50行C代码。 - Ira Baxter

Answer 1

你的目标语言是什么？

如果你想创建一个解析器，也许ANTLR适合你。它最初是基于Java的，但它有多种语言的生成器（例如我用它来生成C#解析器），并且不太难掌握。 它有一个很好的编辑器（ANTLRWorks），可以测试语法，这是一个不错的优点。

- Denis Troller

Answer 2

如果我是你的话，我会使用逆波兰表示法(RPN)。这样可以避免在解析时出现一些困难，算法就像在运算符进入时推入和弹出值堆栈那么简单。您也不必再担心括号了，这应该会让生活更容易。唯一真正的缺点是大多数人不熟悉后缀(又称RPN)表示法。

与树相比，堆栈可能更易于处理。

只是我的个人建议 :)

- DigitalPioneer

Answer 3

你看过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.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文件。还有一个支持MEF加载新功能的分支。

- GreyCloud

Answer 4

如果你正在使用 Python 进行编程，可以试试利用 pyparsing 编写的 表达式解析器/求值器 作为一个起点。

- PaulMcG

Answer 5

我相信已经有做这个（逻辑评估）的工具了，但我找不到。如果您使用像Bison（用于C的YACC）或ANTLR（生成多种语言，但使用Java）这样的工具，您就不必太担心解析了。Coco/R是另一个可以生成许多不同语言的解析器生成器。不过，如果您想自己动手，我建议使用RPN或前缀表示法（我认为比RPN更简单）。这将使解析变得简单得多，但会让用户感到烦恼。

- Zifre

Answer 6

听起来像是一道作业 :-)

首先，您需要递归地定义您的语言。

如果X是一个良好形式（WFF），那么变量就是良好形式（WFF）

如果X和Y是WFF，则（X -> Y）是WFF

如果X和Y是WFF，则（X AND Y）是WFF

一旦定义了语法，请使用LEX或Flex或Java等等价物编写简单扫描器。

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

稍后，为了以后以递归方式评估表达式，添加属性到语法中。

- Luixv

---

Yacc和Bison不会创建递归下降解析器，而是创建基于表格驱动的移进-规约（即自底向上）解析器。 - ackb

真的！很厉害。我有一段时间没有使用lex和yacc了。 - Luixv