Jexl源码解析之二有限状态机如何一步步构建表达式AST语法树【免费下载链接】JexlJavascript Expression Language: Powerful context-based expression parser and evaluator项目地址: https://gitcode.com/gh_mirrors/je/JexlJexl 是一款 JavaScript 表达式语言Javascript Expression Language库核心能力是解析并求值上下文相关的表达式字符串。本文深入剖析 Jexl 源码带你完整看懂有限状态机FSM如何一步步把表达式字符串构建成 AST 语法树帮助新手理解字符串 → 词法单元 → 语法树的全链路。 一、Jexl 表达式解析流水线从字符串到AST语法树Jexl 的编译流程非常简洁入口在 Expression.compilecompile() { const lexer new Lexer(this._grammar) const parser new Parser(this._grammar) const tokens lexer.tokenize(this._exprStr) parser.addTokens(tokens) this._ast parser.complete() return this }整个过程只有三步对应三个核心组件步骤组件职责源码位置1️⃣ 词法分析Lexer把字符串切成带类型的 token 流lib/Lexer.js2️⃣ 状态机解析Parser驱动状态机逐 token 构建 ASTlib/parser/Parser.js3️⃣ 语法定义grammar声明运算符、优先级、函数lib/grammar.js其中有限状态机正是 Parser 的灵魂——用一张状态表来驱动整个解析过程这也是本文的重点。 二、词法分析Lexer 如何把字符串切成 Token在状态机启动之前Lexer.tokenize 先把表达式字符串切碎。它根据 grammar.js 中的元素表动态拼出一条分割正则把user.name | upper这样的字符串切成一个个 token 对象{ type: identifier, // 词法类型 value: user, // 解析后的值 raw: user // 原文含尾部空格 }type 只有两大类内容词literal字面量数字、字符串、布尔值、identifier标识符、binaryOp二元运算符、unaryOp一元运算符控制符.、[、(、{、?等符号type 就是语法表中定义的名字如dot、openParen值得一提的是 Lexer._isNegative 的一个巧妙处理当-出现在表达式开头或运算符之后它会被并入下一个 token 作为负号-5是一个 token而不是当作减号5-3中的-独立成 token。这种词法层面预判让后续状态机不用处理任何歧义。 三、有限状态机的16个状态完整一览Jexl 的全部状态定义在 lib/parser/states.js 中。每个状态只描述一件事在这个状态下遇到某类 token该做什么、然后跳到哪个状态。状态分两种处理模式源码注释解释得非常清楚tokenTypes 表驱动一张token 类型 → { handler, toState }的映射表遇到未登记的 token 直接报错subHandler 子表达式表示当前状态要吞下一整段子表达式子表达式结束符由endStates声明// lib/parser/states.js 中的真实定义 expectOperand: { tokenTypes: { literal: { toState: expectBinOp }, identifier: { toState: identifier }, unaryOp: {}, openParen: { toState: subExpression }, openCurl: { toState: expectObjKey, handler: h.objStart }, dot: { toState: traverse }, openBracket:{ toState: arrayVal, handler: h.arrayStart } } }Jexl 共定义了16 个状态看这张表就懂整台状态机了状态通俗含义可结束(completable)expectOperand等着吃一个操作数起始状态expectBinOp操作数吃完了等运算符或结束✅identifier刚读完一个标识符✅traverse刚读完.等下一个属性名expectTransform刚读完管道符\|等变换名postTransform变换名读完了等参数/运算符✅postArgs括号参数读完等运算符✅expectObjKey在{}中等对象键expectKeyValSep键读完了等冒号:objVal子状态读对象值subHandlerargVal子状态读函数调用参数subHandlersubExpression子状态读括号内子表达式subHandlerarrayVal子状态读数组元素subHandlerfilter子状态读[...]过滤器subHandlerternaryMid子状态读三元表达式中间段ternaryEnd子状态读三元表达式尾段✅其中 6 个子状态使用 subHandler 模式这是 Jexl 处理嵌套结构的递归复用技巧下面细讲。⚙️ 四、状态转移引擎addToken 的逐步执行Parser.addToken 是整台状态机的引擎每吃一个 token 就走一次这个流程查表取当前状态定义states[this._state]子表达式分支若当前状态有subHandler则首次进入时通过 _startSubExpressionnew 出一个子 Parser把当前状态声明的endStates作为它的stopMap传入然后递归调用子 Parser 的addToken。子 Parser 命中 stopMap 时把子表达式编译成 AST 交还给subHandler父 Parser 再切到endStates指定的状态tokenTypes 分支若 token 类型在当前状态表中先执行handler构建 AST 节点再按toState跳转兜底报错Token () unexpected in expression: 1 这样带原文的错误提示这个设计的妙处在于主状态机和子状态机共用同一套 16 个状态。解析(23)*4时遇到(跳入subExpression子 Parser 从expectOperand重新起步遇到)命中 endStates 返回。嵌套再深也只是不断 new Parser天然支持无限嵌套——没有一行专门的递归下降代码。所有 handler 实现集中在 lib/parser/handlers.js它们只干一件事往 AST 上挂节点。例如 literal 处理器 就三行创建{type: Literal, value}并放到光标处。 五、运算符优先级23*4如何构建树新手最容易困惑的问题状态机是线性的优先级靠什么实现答案是 binaryOp 处理器 里的父链回溯exports.binaryOp function (token) { const precedence this._grammar.elements[token.value].precedence || 0 let parent this._cursor._parent while (parent parent.operator this._grammar.elements[parent.operator].precedence precedence) { this._cursor parent parent parent._parent } // 新建 BinaryExpression 节点left 指向回溯到的位置 }每个运算符在 语法表 里都带优先级数值/-为 30*//为 40%/^为 50/为 20/||最低为 10。当新运算符到来时沿_parent链向上回溯只要父节点优先级 ≥ 当前运算符就继续上爬爬到父优先级 当前优先级时停下新运算符节点挂到该处的right上所以23*4中*40到来时父节点30优先级不够高回溯停止3*4成为的右子树而2*34中30到来时父节点*40优先级更高整个2*3子树被包裹为的左子树。优先级规则完全由数据语法表驱动Parser.test.js 里两个用例正好验证了这两种情况。 六、完整走查12的状态轨迹用一个最小例子把前面串起来。解析12Parser 的状态变化轨迹如下步骤Token当前状态动作转移后状态0—初始化_startSubExpression 前状态置为起始态expectOperand11expectOperandliteral处理器挂节点{Literal: 1}expectBinOp2expectBinOpbinaryOp处理器建节点{, left: 1}expectOperand32expectOperandliteral处理器挂节点{Literal: 2}到光标 rightexpectBinOp4结束expectBinOpcomplete 校验completable后返回整棵树complete最终产出与测试用例断言完全一致{ type: BinaryExpression, operator: , left: { type: Literal, value: 1 }, right: { type: Literal, value: 2 } }注意第 4 步的刹车complete()会检查当前状态是否标记了completable。如果表达式写了一半比如停在expectOperand就调用 complete会抛出Unexpected end of expression——状态表的completable标记就是合法结束位置的白名单。 七、总结AST 语法树构建的3个设计要点回顾整条链路Jexl 用约 700 行代码实现了一个完整的表达式解析器有 3 个点值得新手借鉴表驱动状态机状态转移规则全部写在 states.js 这张数据表里引擎 Parser.js 只做通用的查表、执行、跳转新增语法只需加状态、加 handler子 Parser 递归复用括号、数组、对象、过滤器等嵌套结构靠 stopMap endStates 让同一台状态机自我递归天然支持任意嵌套深度语法即数据运算符、优先级、函数都注册在 grammar.js用户可通过 Jexl.addBinaryOp、addTransform 在不碰状态机的前提下扩展语言想亲手验证本文的每一步建议跑一遍tests/lib/parser/Parser.test.js 和tests/lib/Lexer.test.js用npm test命令即可查看每个状态转移对应的断言。下一篇我们将走进 Evaluator看这棵 AST 语法树是如何在任意上下文中求值出结果的。【免费下载链接】JexlJavascript Expression Language: Powerful context-based expression parser and evaluator项目地址: https://gitcode.com/gh_mirrors/je/Jexl创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考