使用PEG生成Parser
@ wgjak47 | 星期四,十二月 2 日,2021 年 | 5 分钟阅读 | 更新于 星期四,十二月 2 日,2021 年

使用PEG生成Parser

背景

前端时间收到一个需求,就是把我们server cmdb的高级查询功能移植到CLI工具上,所谓高级查询是类似这个样子的:

ip in ["10.0.0.1", "10.0.0.2"] && tag = "serivce:k8s" && (cpu = "EPYC 7763" || memory = "1024G")

前端大概会解析这种高级表达式,转换成json请求,格式如下:

{
    "filters": {
        "conjunction": "and",
        "values": [
            {
                "field": "ip",
                "cmp_method": "in",
                "value": ["10.0.0.1", "10.0.0.2"]
            },
            {
                "field": "tag",
                "cmp_method": "=",
                "value": "service:k8s"
            },
            {
                "conjunction": "or",
                "values": [
                    {
                        "field": "cpu",
                        "cmp_method": "=",
                        "value": "EPYC 7763"
                    },
                    {
                        "field": "memory",
                        "cmp_method": "=",
                        "value": "1024G"
                    }
                ]
            },
        ]
    },
    "params": {
    }
}

我本人没有写过js,但是了解一点,所以打算参照一下,用Go移植到CLI工具上,但是看到实现,我就蒙了,它的实现大概是这样:

import peg from 'pegjs';

const grammar = `
OrExpr
  = first:AndExpr rest:(_ ("||" / "|") _ AndExpr)* _ {
      return rest.length === 0
        ? first
        : {
            "conjunction": "OR",
            "values": [first].concat(rest.map(element => element[3]))
        };
    }
  / _ {
    // Filter that just returns true
      return { 'type': 'binary_operator', 'cmp_method': 'AND', 'values': [] }
  }

AndExpr
  = first:AtomOrParens rest:(_ ("&&" / "&") _ AtomOrParens)* {
      return rest.length === 0
        ? first
        : {
            "conjunction": "AND",
            "values": [first].concat(rest.map(element => element[3]))
        };
    }

AtomOrParens
  = _ "(" _ expr:OrExpr _ ")" { return expr; }
  / _ "!" expr:OrExpr { return { "type": "unary_operator", "cmp_method": "NOT", "value": expr } }
  / lhs:Field _ neg:MaybeNotSign "=" _ rhs:Value {
      var result = { "field": lhs, "method": "equals", "value": rhs }
      if (neg) {
            result = { "cmp_method": "NOT", "value": result }
      }
      return result
  }
  / lhs:Field _ neg:MaybeNotSign "contains"i _ rhs:Value {
      var result = { "field": lhs, "method": "contains", "value": rhs }
      if (neg) {
          result = { "cmp_method": "NOT", "value": result }
      }
      return result
  }
  / lhs:Field _ neg:MaybeNotSign "in"i _ rhs:ArrayOfValues {
      var result = { "field": lhs, "method": "in", "value": rhs }
      if (neg) {
          result = { "cmp_method": "NOT", "value": result }
      }
      return result
  }

Field
  = _ field:([A-Za-z0-9-_]+) { return key.join('') }

ArrayOfValues
  = _ "[" _ first:(_ Value) rest:(_ "," Value)* _ ("," _)? "]" { return [head[1]].concat(tail.map(element => element[2])) }

Value
  = _ "\\"" value:([A-Za-z0-9-:._ @]*) "\\"" { return value.join('') }

MaybeNotSign
  = not_sign:"!"? { return not_sign ? true : false; }

_ "whitespace"
  = [ \\t\\n\\r]*
`;

const parser = peg.generate(grammar, { cache: true });

这堆鬼画符是个啥啊,然后去问我们前端,前端表示不知道,git blame了一下,实现这个的印尼老哥离职很久了…看来只能硬着头皮自己上了。

PEG是啥

https://en.wikipedia.org/wiki/Parsing_expression_grammar, Parsing Expression Grammar,是一种分析型形式文法,什么是形式文法呢,简单的来说就是一套字符串的产生式规则,也就是语言生成器(或者反过来,作为识别器,例如本文中的PEG就是经常被作为识别器)。例如:

1. S -> aSb
2. S -> ba

这里从S开始,会随机选择一个规则,如果选择1,则得到字符串aSb,其中有S可以继续选择规则进行扩这,如果继续选择1,则可以得到aaSbb,反正如果选择2,则会得到abab,因为已经没有S表达式,生成结束。

回到PEG自身的语法: 形式上,一个解析表达文法由以下部分组成:

  • 一个有限的非终结符的集合 N

  • 一个有限的终结符的集合 Σ,和 N 没有交集

  • 一个有限的解析规则的集合 P

  • 一个被称作开始表达式的解析表达式 eS

P 中的每一个解析规则以 A ← e 的形式出现,这里 A 是一个非终结符,e 是一个解析表达式。解析表达式是类似正则表达式的层次表达式:

  1. 原子解析表达式由以下组成:

    • 任何的终结符,

    • 任何的非终结符,

    • 空字符串 ε.

  2. 给定已经存在的解析表达式 e, e1 和 e2, 一个新的解析表达式可以通过以下操作构成:

    • 序列: e1 e2

    • 有序选择: e1 / e2

    • 零个或更多: e*

    • 一个或更多: e+

    • 可选: e?

    • 肯定断言: &e

    • 否定断言: !e

PEG有一个关键的地方,就是PEG的选择操作符是有序的,即会优先匹配先出现的表达式,忽略剩下可能匹配的表达式 我们以最简单的一个例子,利用PEG.js实现的四则运算:

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "+") { return result + element[3]; }
        if (element[1] === "-") { return result - element[3]; }
      }, head);
    }

Term
  = head:Factor tail:(_ ("*" / "/") _ Factor)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "*") { return result * element[3]; }
        if (element[1] === "/") { return result / element[3]; }
      }, head);
    }

Factor
  = "(" _ expr:Expression _ ")" { return expr; }
  / Integer

Integer "integer"
  = _ [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
  = [ \t\n\r]*

我们以 1 * (2 + 3) / 4 为例, 首先会匹配到Expression的表达式, 其中tail后的*表示的是0或者多个, 这样就匹配到了head, 也就是Term,然后进入Term表达式进行匹配, 我们可以看到在Term表达式中, 1匹配到了head, * (2 + 3) / 4 匹配到了tail的部分,准确的说这里匹配到了两个Factor, 即 * (2 + 3)和 / 4,然后进入Factor部分,Factor表达式是一个有序选择表达式, 这里1明显匹配Integer部分, 进入Integer匹配, integer就是一个整数啦,就返回了,然后回溯到Term的tail部分, 继续匹配2个Factor部分, (2 + 3) 的部分匹配到了"(" _ expr:Expression _ ")" , 而这里2 + 3又匹配到了Expression部分,接着递归匹配,不再赘述,而 4 则匹配到Integer的部分。 整个解析流程大致如此, 这里为了叙述简洁,我省略了whitespace的部分,这个表示匹配空格,指标符回车等等, 也就是_部分。

总的来看,PEG.js的表达式包含了两部分,第一部分是PEG表达式,第二部分是用户自定义的函数,用于对匹配到的文本进行进一步处理,这里的head和tail是变量声明,会作为参数出现在函数中,类型取决于后续表达式的运算结果。而PEG的匹配方式是递归进行的,有兴趣的可以去 在线测试, 添加一些console.log来观察peg.js的匹配过程。

golang版本的替代

然而搞懂了PEG的工作原理并不能解决我当前的问题,我们的后端是Golang而不是NodeJS,这就需要一个golang版的peg.js,万能的github上正好有一个: pigeon。 golang不是动态语言,因此相关参数和返回值都是interface{},需要花一些额外的代码进行类型转换。其次,golang的元编程能力没有那么强,这个库使用的是go generate生成相关代码,但是生成出来的代码不是很好阅读,需要一定的编译原理知识,代码中有很大一部分是语法树,如果你设计的 规则比较复杂,可能会生成近万行代码。其次就是一些细微的语法差异,例如peg.js中的=就被换成了<-。

PEG
保存为图片