5

我有一个字符串，其中包含一个自定义表达式，我必须解析和评估：

例如：

(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 是应该应用于列表的自定义函数，这些函数是从这些函数返回的。

Union 和 intersect 是通过 实现的Enumerable.Intersect/Enumerable.Union。

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

4

1 回答 1

5

这取决于您的表达式将变得多么复杂，将有多少不同的运算符可用，以及大量不同的变量。无论您采用哪种方式，您都可能需要首先确定您的迷你语言的语法。

对于简单的语法，您可以编写一个自定义解析器。在许多计算器和类似应用程序的情况下，递归下降解析器的表达能力足以处理语法并且编写起来很直观。链接的 Wikipedia 页面提供了示例语法和 C 解析器的实现。Eric White 还有一篇关于在 C# 中构建递归下降解析器的博文。

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

基本解析概念

通常，您希望能够将输入中的每个项目拆分为一个有意义的标记，并基于这些标记构建一个树。构建树后，您可以遍历树并在每个节点处执行必要的操作。for 的语法树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找到 a 时，需要为其提供两个联合项目，等等。给定这棵树，您将从根 ( PROGRAM) 开始并进行深度优先遍历。在UNION节点处，动作将是首先访问所有子节点，然后将结果合并在一起。在一个FUNCTION节点上，操作将首先访问所有子节点，找到它们的值，并将这些值用作函数的参数，然后根据这些输入评估函数并返回值。

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

于 2012-10-18T15:44:36.720 回答