江苏龙网

  1. 主页 > 生活百科 > >

从 0 到 1 搭建技术中台之报警平台实践：匹配器演进( 二 )

匹配器演进

  • 生成中间表述 (IR Generation)：转化成合理的内存数据结构
    • 以下就是匹配表达式的 IR：
    ?复制代码
    type PrimitiveMatcher struct { Labelstring Textstring IsRegexp bool re*regexp.Regexp} type Matcher struct { PrimitiveMatcher *PrimitiveMatcher IsCompoundbool OperatorMatcherOperator Operands[]*Matcher}其中 Matcher 既可以是原始匹配器 (表达式) 也可以是复合匹配器 (表达式) 。
    下面分别介绍报警平台匹配器编译器的两个版本实现，Matcher Compiler V1 (MCV1) 和 Matcher Compiler V2 (MCV2) 。
    Matcher Compiler V1在实现 MCV1 时我们并未从编译的角度看待这个模块，而只是单纯地想实现从表达式到 IR 的转化 。凭借工程师的本能，MCV1 将编译的前端处理过程分成 3 步：
    ?复制代码
    err = m.parseToken()if err != nil {return} err = m.toElements()if err != nil {return} return m.buildMatcher()parseTokenparseToken 将原始表达式转化成一个词语数组，是词法分析的雏形，其整体过程如下：
    ?复制代码
    for i, c := m.expr {hasLeftDoubleQuote := falseswitch c {case '('://...case ')'://...case '='://...case '~'//...default://...}}parseToken 需要许多状态，如：
    • 是否在括号内
    • 是否在引号内
    • 遇到 ~ 要考虑是否会和上一个字符共同组成 =~
    • …
    由于状态较多，要同时考虑各种状态及其之间的转化过程，使得 parseToken 足够健壮，过程烧脑且容易出错 。
    toElementstoElements 遍历词语数组，构建其中的原始表达式，可以看作理解成是语法分析和语义分析的一部分，其整体过程如下：
    ?复制代码
    for i, word := range m.words {switch strings.ToLower(word) {case "=":leftWord, rightWord, _ := m.tryFetchBothSideWord(i)m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord, false))case "=~":leftWord, rightWord, _ := m.tryFetchBothSideWord(i)m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord, true))// deal with more casesdefault:// ...}这部分逻辑比较简单，遇到 = 或者 =~ 时看一下前后的词语，看是否能构成原始表达式 。
    buildMatcherbuildMatcher 遍历 elements 数组，构建最终的树状复合表达式，其实就是中缀表达式的计算过程，是栈的典型应用场景，利用操作符栈和操作数栈即可实现，其整体过程如下：
    ?复制代码
    var (valueStack Stack opStack Stack) for i, element := range m.elements {switch e := element; {case e == "(":opStack.Push("(")case e == ")":for op := opStack.Pop(); op != "(" {rhs, lhs := valueStack.Pop(), valueStack.Pop()// Apply}// operatorscase isOp(e):currOp = efor prevOp := opStack.Peek(); precedence[currOp] <= precedence[prevOp] {opStack.Pop()rhs, lhs := valueStack.Pop(), valueStack.Pop()// apply prevOp}opStack.Push(currOp)default:valueStack.Push(e)}} // deal with the rest valueStack and opStackMCV1 小结MCV1 是凭借工程师本能构建的一个模块，优势就在于可以迅速地搭建原型，验证想法 。从代码健壮性角度看， parseToken 的状态管理比较脆弱；从可读性角度看，无法从逻辑中直接看出其所支持的语法，为后期维护造成障碍；从可扩展性角度看，buildMatcher 目前只支持中缀表达式，如果有语法变化将整体逻辑产生较大影响；从效率角度看，编译一次表达式需要 3 次遍历，如果将 toElements 与 buildMatcher 逻辑合并可以优化到 2 次 。
    Matcher Compiler V2为了解决上述问题，我们想到了 Lex 和 Yacc 。Lex 是 lexical analyzer generator，能够帮助我们生成词法分析器 (lexical analyzer)；Yacc 是 parser generator，能够帮助我们生成解析器 (parser)，完成语法分析 。Lex 和 Yacc 是 Unix 系统的原生工具，linux 与 macOS 平台也都自带这两个工具 。既然已经有前人为我们栽树，我们为什么不趁机乘凉？
    Lex & YaccLex 和 Yacc 的协作过程如下图所示：
    从 0 到 1 搭建技术中台之报警平台实践：匹配器演进

    文章插图
     
    开发者将构词规则和一些定制化逻辑 (C Code) 定义到 lex.l 文件中，利用 lex 命令生成词法分析器；将语法规则和一些定制化逻辑定义到 parser.y 文件中，利用 yacc 命令生成解析器 。词法分析器的 yylex 方法将输入文本转化成 token，投喂给 yyparse，后者根据语法和定制化逻辑将 token 流转化成最终的目标数据结构，即 IR 。
    Example：Calculator以一个支持加减运算的计算机为例，先定义语法规则：
    ?复制代码
    // parser.y%token NUMBER%% // 括号中的 $$ 表示语法左手边 (LHS) 的值// 括号中的 $1、$2、$3 表示语法右手边 (RHS) 的值statement: expression{ printf("= %dn", $1); }; expression: NUMBER '+' NUMBER{ $$ = $1 + $3; }|NUMBER '-' NUMBER{ $$ = $1 - $3; }|NUMBER{ $$ = $1; };


    推荐阅读


    上一篇：天龙八部属性减抗怎么算？

    下一篇：女生最在意的4个称呼是什么？