创建 DSL 表达式解析器/规则引擎

Creating a DSL expressions parser / rules engine

我正在构建一个应用程序,该应用程序具有将 expressions/rules 嵌入配置 yaml 文件的功能。因此,例如用户可以引用在 yaml 文件中定义的变量,如 ${variables.name == 'John'}${is_equal(variables.name, 'John')}。我可能可以使用简单的表达式,但我想支持复杂的 rules/expressions 这样的 ${variables.name == 'John'} and (${variables.age > 18} OR ${variables.adult == true})

我正在寻找可以支持这些类型的表达式并对其进行规范化的 parsing/dsl/rules-engine 库。如果有人知道该语言的库,我将使用 ruby、javascript、java 或 python 打开。

我想到的一个选择是只支持 javascript 作为 conditons/rules 并基本上通过 eval 传递它,并设置正确的上下文设置以访问变量和其他可引用的变量。

不知道你会不会用Golang,如果你会用,推荐这个https://github.com/antonmedv/expr

我用它来解析机器人策略(股票期权机器人)。这是来自我的测试单元:

func TestPattern(t *testing.T) {
    a := "pattern('asdas asd 12dasd') && lastdigit(23asd) < sma(50) && sma(14) > sma(12) && ( macd(5,20) > macd_signal(12,26,9) || macd(5,20) <= macd_histogram(12,26,9) )"

    r, _ := regexp.Compile(`(\w+)(\s+)?[(]['\d.,\s\w]+[)]`)
    indicator := r.FindAllString(a, -1)
    t.Logf("%v\n", indicator)
    t.Logf("%v\n", len(indicator))

    for _, i := range indicator {
        t.Logf("%v\n", i)
        if strings.HasPrefix(i, "pattern") {
            r, _ = regexp.Compile(`pattern(\s+)?\('(.+)'\)`)
            check1 := r.ReplaceAllString(i, "")
            t.Logf("%v\n", check1)
            r, _ = regexp.Compile(`[^du]`)
            check2 := r.FindAllString(check1, -1)
            t.Logf("%v\n", len(check2))
        } else if strings.HasPrefix(i, "lastdigit") {
            r, _ = regexp.Compile(`lastdigit(\s+)?\((.+)\)`)
            args := r.ReplaceAllString(i, "")
            r, _ = regexp.Compile(`[^\d]`)
            parameter := r.FindAllString(args, -1)
            t.Logf("%v\n", parameter)
        } else {

        }
    }
}

将它与正则表达式结合起来,你就有了很好的(如果不是很好,字符串翻译器)。

而对于 Java,我个人使用 https://github.com/ridencww/expression-evaluator 但不用于生产。它与上述 link.

具有相似的特征

它支持很多条件,您不必担心圆括号和方括号。

Assignment  =
Operators   + - * / DIV MOD % ^ 
Logical     < <= == != >= > AND OR NOT
Ternary     ? :  
Shift       << >>
Property    ${<id>}
DataSource  @<id>
Constants   NULL PI
Functions   CLEARGLOBAL, CLEARGLOBALS, DIM, GETGLOBAL, SETGLOBAL
            NOW PRECISION

希望对您有所帮助。

One option I thought of was to just support javascript as conditons/rules and basically pass it through eval with the right context setup with access to variables and other reference-able vars.

我个人会倾向于这样的事情。如果您遇到诸如逻辑比较之类的复杂问题,DSL 可能会成为野兽,因为此时您基本上几乎是在编写编译器和语言。您可能只想没有配置,而是让可配置文件只是 JavaScript(或任何语言),然后可以对其进行评估和加载。那么这个“配置”文件的目标受众是谁,可以根据需要补充逻辑表达式。

我不会这样做的唯一原因是如果此配置文件暴露给 public 或其他东西,但在那种情况下解析器的安全性也将非常困难。

您可能会惊奇地发现使用一个语法分析器和 50 行代码就能走多远!

Check this out。右侧的抽象语法树 (AST) 以漂亮的数据结构表示左侧的代码。您可以使用这些数据结构编写自己的简单解释器。

我写了一个小例子: https://codesandbox.io/s/nostalgic-tree-rpxlb?file=/src/index.js

打开控制台(底部的按钮),您将看到表达式的结果!

此示例只能处理 (||) 和 (>),但查看代码(第 24 行),您可以了解如何使其支持任何其他 JS 运算符。只需在分支中添加一个案例,评估边,然后在 JS 上进行计算。

括号和运算符优先级都由解析器为您处理。

我不确定这是否适合您,但肯定会很有趣 ;)

I'm building an app which has a feature for embedding expressions/rules in a config yaml file.

I'm looking for a parsing/dsl/rules-engine library that can support these type of expressions and normalize it. I'm open using ruby, javascript, java, or python if anyone knows of a library for that languages.

一种可能是 嵌入 规则解释器,例如 ClipsRules inside your application. You could then code your application in C++ (perhaps inspired by my clips-rules-gcc project) and link to it some C++ YAML library such as yaml-cpp.

另一种方法可能是 embed some Python interpreter inside a rule interpreter (perhaps the same ClipsRules) 和一些 YAML 库。

第三种方法可能是使用 Guile (or SBCL or Javascript v8) 并使用一些“专家系统 shell”对其进行扩展。

在开始编码之前,一定要阅读几本书,例如 Dragon Book, the Garbage Collection handbook, Lisp In Small Pieces, Programming Language Pragmatics. Be aware of various parser generators such as ANTLR or GNU bison, and of JIT compilation libraries like libgccjit or asmjit

您可能需要就各种 open source 许可的法律兼容性问题联系律师。

一些困难和你应该考虑的事情。

1。统一表达语言 (EL),

另一个选项是 EL,指定为 JSP 2.1 标准的一部分(JSR-245). Official documentation

他们有一些不错的 examples 可以让您很好地了解语法。例如:

   El Expression: `${100.0 == 100}` Result=  `true`   
   El Expression: `${4 > 3}`        Result=  `true` 

您可以使用它来评估类似脚本的小表达式。还有一些实现:Juel 是 EL 语言的一种开源实现。

2。观众和安全

所有答案都推荐使用不同的解释器、解析器生成器。所有这些都是添加功能以处理复杂数据的有效方法。但我想在这里添加一个重要说明。

每个解释器都有一个解析器,注入攻击以这些解析器为目标,诱使它们将数据解释为命令。 你应该清楚地了解解释器的解析器是如何工作的,因为这是降低成功注入攻击机会的关键现实世界的解析器有许多可能与眼镜。并有明确的措施来缓解可能存在的缺陷。

并且即使您的应用程序未面向 public。您可以有可以滥用此功能的外部或内部参与者。

我曾经做过类似的事情,你可能会拿起它并根据你的需要进行调整。

TL;DR:感谢 Python 的 eval,你做这件事是一件轻而易举的事。

问题是以文本形式解析日期和持续时间。我所做的是创建一个将正则表达式模式映射到结果的 yaml 文件。映射本身是一个 python 表达式,它将使用匹配对象进行评估,并且可以访问文件中其他地方定义的其他函数和变量。

例如,以下自包含代码段可以识别诸如“l'11 agosto del 1993”(意大利语“1993 年 8 月 11 日”)之类的时间。

__meta_vars__:
  month: (gennaio|febbraio|marzo|aprile|maggio|giugno|luglio|agosto|settembre|ottobre|novembre|dicembre)
  prep_art: (il\s|l\s?'\s?|nel\s|nell\s?'\s?|del\s|dell\s?'\s?)
  schema:
    date: http://www.w3.org/2001/XMLSchema#date

__meta_func__:
  - >
    def month_to_num(month):
        """ gennaio -> 1, febbraio -> 2, ..., dicembre -> 12 """
        try:
            return index_in_or(meta_vars['month'], month) + 1
        except ValueError:
            return month

Tempo:
  - \b{prep_art}(?P<day>\d{{1,2}}) (?P<month>{month}) {prep_art}?\s*(?P<year>\d{{4}}): >
      '"{}-{:02d}-{:02d}"^^<{schema}>'.format(match.group('year'),
                                              month_to_num(match.group('month')),
                                              int(match.group('day')),
                                              schema=schema['date'])

__meta_func____meta_vars(我知道这不是最好的名字)定义了匹配转换规则可以访问的函数和变量。为了使规则更易于编写,使用元变量对模式进行格式化,以便 {month} 替换为匹配所有月份的模式。转换规则调用元函数 month_to_num 将月份转换为 1 到 12 之间的数字,并从 schema 元变量中读取。在上面的示例中,匹配结果为字符串 "1993-08-11"^^<http://www.w3.org/2001/XMLSchema#date>,但其他一些规则会生成字典。

在 Python 中这样做非常容易,因为您可以使用 exec 将字符串计算为 Python 代码(关于安全隐患的强制性警告)。元函数和元变量被评估并存储在字典中,然后传递给匹配转换规则。

代码是on github,如果您需要说明,请随时提出任何问题。相关部分,略作编辑:

class DateNormalizer:
    def _meta_init(self, specs):
        """ Reads the meta variables and the meta functions from the specification
        :param dict specs: The specifications loaded from the file
        :return: None
        """
        self.meta_vars = specs.pop('__meta_vars__')

        # compile meta functions in a dictionary
        self.meta_funcs = {}
        for f in specs.pop('__meta_funcs__'):
            exec f in self.meta_funcs

        # make meta variables available to the meta functions just defined
        self.meta_funcs['__builtins__']['meta_vars'] = self.meta_vars

        self.globals = self.meta_funcs
        self.globals.update(self.meta_vars)

    def normalize(self, expression):
        """ Find the first matching part in the given expression
        :param str expression: The expression in which to search the match
        :return: Tuple with (start, end), category, result
        :rtype: tuple
        """
        expression = expression.lower()
        for category, regexes in self.regexes.iteritems():
            for regex, transform in regexes:
                match = regex.search(expression)
                if match:
                    result = eval(transform, self.globals, {'match': match})
                    start, end = match.span()
                    return (first_position + start, first_position + end) , category, result

这里有一些分类的 Ruby 选项和资源:

不安全

  1. 用您选择的语言将表达式传递给 eval

必须指出的是,eval 在技术上是一种选择,但其输入必须存在非凡的信任,完全避免它更安全。

重量级

  1. 为你的表达式编写一个解析器和一个解释器来评估它们

成本密集型解决方案是实施您自己的表达式语言。也就是说,为您的表达式语言设计一个词典,为它实现一个解析器,以及一个解释器来执行解析后的代码。

一些解析选项(ruby)

中等体重

  1. 选择一种现有语言来编写表达式并解析/解释这些表达式。

此路线假定您可以选择一种已知的语言来编写表达式。好处是该语言可能已经存在解析器,可以将其转换为抽象语法树(可以遍历以进行解释的数据结构) .

一个 ruby 示例 Parser gem

require 'parser'

class MyInterpreter
  # https://whitequark.github.io/ast/AST/Processor/Mixin.html
  include ::Parser::AST::Processor::Mixin

  def on_str(node)
    node.children.first
  end

  def on_int(node)
    node.children.first.to_i
  end

  def on_if(node)
    expression, truthy, falsey = *node.children
    if process(expression)
      process(truthy)
    else
      process(falsey)
    end
  end

  def on_true(_node)
    true
  end

  def on_false(_node)
    false
  end

  def on_lvar(node)
    # lookup a variable by name=node.children.first
  end

  def on_send(node, &block)
    # allow things like ==, string methods? whatever
  end

  # ... etc
end

ast = Parser::ConcurrentRuby.parse(<<~RUBY)
  name == 'John' && adult
RUBY
MyParser.new.process(ast)
# => true

这里的好处是解析器和语法是预先确定的,您可以只解释您需要的内容(并防止控制器执行 on_sendon_const 允许的恶意代码)。

模板化

这更面向标记,可能不适用,但您可以在模板库中找到一些用途,它会为您解析表达式并求值。根据您为此使用的库,可以控制和向表达式提供变量。可以检查表达式的输出是否真实。