使用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 是一个解析表达式。解析表达式是类似正则表达式的层次表达式：

原子解析表达式由以下组成:
- 任何的终结符，
- 任何的非终结符，
- 空字符串 ε.
给定已经存在的解析表达式 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生成Parser
@ wgjak47 | 星期四，十二月 2 日，2021 年 | 5 分钟阅读 | 更新于星期四，十二月 2 日，2021 年