c# - 解析表达式(带有自定义函数和操作)

Question

我有一个字符串，其中包含一个自定义表达式，我必须对其进行解析和求值:

例如:

(FUNCTION_A(5,4,5) UNION FUNCTION_B(3,3)) 
INTERSECT (FUNCTION_C(5,4,5) UNION FUNCTION_D(3,3))

FUNCTION_X代表函数，用C#实现，返回ILists。 UNION 或 INTERSECT 是自定义函数，应应用于从这些函数返回的列表。

并集和交集是通过Enumerable.Intersect/Enumerable.Union实现的。

如何以优雅和可扩展的方式实现解析和评估？

Answer 1

这取决于表达式的复杂程度、可用的不同运算符数量以及不同变量的数量。无论采用哪种方式，您都可能需要先确定一个 grammar为你的迷你语言。

对于简单的语法，您可以编写自定义解析器。对于许多计算器和类似应用程序，一个 recursive descent解析器具有足够的表现力来处理语法并且编写起来很直观。链接的维基百科页面提供了示例语法和 C 解析器的实现。埃里克怀特也有一个 blog post关于在 C# 中构建递归下降解析器。

对于更复杂的语法，您可能希望跳过自己创建的工作并使用 lex/yacc -type 词法分析器和解析器工具集。通常，您将 EBNF 中的语法作为输入或类似的语法，它们将生成解析输入所需的代码。解析器通常会返回 syntax tree。您可以遍历它，允许您为输入流中的每个标记(树中的每个节点)应用逻辑。对于 C#，我使用过 GPLex和 GPPG , 但其他如 ANTLR也可用。

基本解析概念

通常，您希望能够将输入中的每个项目拆分为一个有意义的标记，并基于这些标记构建一棵树。构建树后，您可以遍历树并在每个节点执行必要的操作。 FUNCTION_A(5,4,5) UNION FUNCTION_B(3,3) 的语法树可能看起来像这样，其中节点类型是大写字母，它们的值在括号中:

                        PROGRAM
                           |
                           |
                         UNION
                           |
            ------------------------------
           |                              |
  FUNCTION (FUNCTION_A)          FUNCTION(FUNCTION_B)
        |                                 |
  -------------                       ----------
 |      |      |                     |          |
INT(5) INT(4) INT(5)                INT(3)     INT(3)

解析器需要足够聪明，知道当找到 UNION 时，需要为它提供两个要联合的项，等等。给定这棵树，您将从根开始 ( PROGRAM) 并进行深度优先遍历。在 UNION 节点，操作是首先访问所有子节点，然后将结果合并在一起。在 FUNCTION 节点，操作将是首先访问所有子节点，找到它们的值，并将这些值用作函数的参数，然后根据这些输入评估函数并返回值(value)。

这将继续适用于所有标记，适用于您可以想出的任何表达式。通过这种方式，如果您花时间让解析器生成正确的树并且每个节点都知道如何执行它需要的任何操作，那么您的设计是非常可扩展的并且可以处理与其设计的语法相匹配的任何输入。