解析表达式(使用自定义函数和操作)

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#中实现并返回IList的函数.UNION或INTERSECT是自定义函数,应该应用于从这些函数返回的列表.

联盟和交叉是通过实现的Enumerable.Intersect/Enumerable.Union.

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

Answer 1

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

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

对于更复杂的语法,您可能希望自己跳过创建它的工作并使用lex/yacc- type lexer和parser工具集.通常,您可以在EBNF或类似语法中为这些语法提供输入,并且它们将生成为您解析输入所需的代码.解析器通常会返回一个可以遍历的语法树,允许您为输入流中的每个标记应用逻辑(树中的每个节点).对于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找到a时,需要为union提供两个项目等.给定这个树,你将从root(PROGRAM)开始并进行深度优先遍历.在UNION节点处,操作是首先访问所有子节点,然后将结果合并在一起.在FUNCTION节点上,操作是首先访问所有子节点,找到它们的值,并将这些值用作函数的参数,然后评估这些输入上的函数并返回值.

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