精读 syntax-parser 源码：用链表模拟 JS 执行引擎实现带回溯与智能提示的语法分析器

文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载本文是前端精读周刊 源码解读 栏目对 JS 版语法解析器生成器syntax-parser的深度源码剖析同时也是《手写 SQL 编译器》系列的源码级总结。文章将带你从词法分析的分词器出发逐步拆解语法分析器是如何通过链表 模拟执行引擎解决回溯问题、实现 LL(∞) 匹配能力并最终支撑错误提示、输入推荐与 First 集优化等高级功能。读完本文你将理解一个通用语法分析器生成器的完整实现思路并能基于它构建自己的 DSL 解析与编辑器智能提示能力。1. 引言syntax-parser 是什么syntax-parser 是一个 JS 版语法解析器生成器具备**分词词法解析与语法树解析语法解析**两大能力。它与传统根据文法文本生成解析器的工具如 antlr4、pegjs不同走的是用 JS 代码直接表达文法结构的路线——正如《手写 SQL 编译器》系列中反复强调的与其把文法文本解析成代码不如直接用代码表达文法代码自身执行后的结果就是编译后的代码。在 精读《手写 SQL 编译器 - 智能提示》 中已经说明正是为了给 SQL 编辑器做深度定制的智能提示需要在语句不完整甚至错误时仍能给出光标位置的所有可能输入作者没有采用 antlr4 等现成生成器而是创造了 syntax-parser 这个业务无关的语法解析引擎生成器并只开源最底层这一层其上的sql-parser、monaco-editor-plugin则由各业务自行封装。第一个例子创建词法解析器 myLexerimport { createLexer } from syntax-parser; const myLexer createLexer([ { type: whitespace, regexes: [/^(\s)/], ignore: true }, { type: word, regexes: [/^([a-zA-Z0-9])/] }, { type: operator, regexes: [/^(\)/] } ]);如上通过正则分别匹配了空格、字母或数字、加号并将匹配到的空格忽略不输出到结果中。分词匹配是从左到右的优先匹配数组的第一项依此类推。接下来使用myLexerconst tokens myLexer(a b); // tokens: // [ // { type: word, value: a, position: [0, 1] }, // { type: operator, value: , position: [2, 3] }, // { type: word, value: b, position: [4, 5] }, // ]a b会按照上面定义的三种类型被分割为数组数组的每一项都包含了原始值value以及其位置position。第二个例子创建语法解析器 myParserimport { createParser, chain, matchTokenType, many } from syntax-parser; const root () chain(addExpr)(ast ast[0]); const addExpr () chain(matchTokenType(word), many(addPlus))(ast ({ left: ast[0].value, operator: ast[1] ast[1][0].operator, right: ast[1] ast[1][0].term })); const addPlus () chain(), root)(ast ({ operator: ast[0].value, term: ast[1] })); const myParser createParser( root, // Root grammar. myLexer // Created in lexer example. );利用chain函数书写文法表达式通过字面量的匹配比如号以及matchTokenType来模糊匹配上面词法解析出的三种类型就形成了完整的文法表达式。syntax-parser还提供了其他几个有用的函数比如many、optional分别表示匹配多次和匹配零或一次。接下来使用myParserconst ast myParser(a b); // ast: // [{ // left: a, // operator: , // right: { // left: b, // operator: null, // right: null // } // }]2. 源码精读从词法解析到语法解析按照下面的思路大纲进行源码解读词法解析词汇与概念分词器语法解析词汇与概念重新做一套JS 执行引擎实现 Chain 函数引擎执行何时算执行完或逻辑的实现many, optional, plus 的实现错误提示 输入推荐First 集优化3. 词法解析词法解析有点像 NLP 中的分词但比分词简单词法解析的分词逻辑是明确的一般用正则片段表达。正如 精读《手写 SQL 编译器 - 词法分析》 所描述的那样词法分析就像刀削面的过程拿着一段字符串面条的一端不断下刀当面条被切完也就完成了词法分析所以词法分析是字符串 - 一堆字符段的过程。难点在于下刀的分寸也就是如何为每一类 Token 写好头匹配正则。3.1 词汇与概念Lexer词法解析器。Token分词后的词素包括value: 值、position: 位置、type: 类型。在 精读《手写 SQL 编译器 - 词法分析》 中Token 被归纳为注释、关键字、操作符、开闭合标志、占位符、空格、引号包裹的文本/数字/字段、方言语法等分类。值得强调的是词法分析阶段不需要关心某个词是不是关键词关键词的辨认留到语法分析阶段处理同理词法分析也不需要考虑 Token 摆放是否合理只负责切分即可。3.2 分词器分词器createLexer函数接收的是一个正则数组因此思路是遍历数组一段一段匹配字符串。核心需要这几个函数class Tokenizer { public tokenize(input: string) { // 调用 getNextToken 对输入字符串 input 进行正则匹配匹配完后 substring 裁剪掉刚才匹配的部分再重新匹配直到字符串裁剪完 } private getNextToken(input: string) { // 调用 getTokenOnFirstMatch 对输入字符串 input 进行遍历正则匹配一旦有匹配到的结果立即返回 } private getTokenOnFirstMatch({ input, type, regex }: { input: string; type: string; regex: RegExp; }) { // 对输入字符串 input 进行正则 regex 的匹配并返回 Token 对象的基本结构 } }tokenize是入口函数循环调用getNextToken匹配 Token 并裁剪字符串直到字符串被裁完getNextToken遍历正则数组一旦命中立即返回这正是优先匹配数组第一项语义的实现getTokenOnFirstMatch负责单个正则的匹配并组装出{ type, value, position }的 Token 基本结构。主流程与 精读《手写 SQL 编译器 - 词法分析》 中给出的不断匹配、切割字符串、再匹配主函数完全一致while (sqlStr) { token getTokenWhitespace(sqlStr, token) || getTokenBlockComment(sqlStr, token); sqlStr sqlStr.substring(token.value.length); tokens.push(token); }每取一次 Token都将取到的 Token 长度丢掉继续匹配剩下的字符串直到字符串被切分完为止个别特殊场景需要拿到上一次的 Token才能判断下一个 Token 该如何切割所以每个 Match 函数也接收上一个 Token 作为上下文。4. 语法解析语法解析是基于词法解析的输入是 Tokens根据文法规则依次匹配 Token当 Token 匹配完且完全符合文法规范后语法树就出来了。语法解析器生成器就是生成语法解析器的工具只要输入规定的文法描述内部引擎会自动做掉其余的事。这个生成器的难点在于匹配或逻辑失败时调用栈需要恢复到失败前的位置而 JS 引擎中调用栈不受代码控制因此代码需要在模拟引擎中执行。4.1 词汇与概念Parser语法解析器。ChainNode连续匹配执行链四节点之一。TreeNode匹配其一执行链四节点之一。FunctionNode函数节点执行链四节点之一。MatchNode匹配字面量或某一类型的 Token执行链四节点之一。每一次正确的 Match 匹配都会消耗一个 Token。从 精读《手写 SQL 编译器 - 智能提示》 的归纳可以更直观地理解这四种节点能消耗 Token 的只有 MatchNodeChainNode 描述先后关系如expr - name idTreeNode 描述并列关系如factor - num | idFunctionNode 是尚未展开的函数节点如果把文法匹配比作迷宫探险那这是无限迷宫无法穷尽展开只能执行到用时再展开。4.2 为什么要重新做一套JS 执行引擎看下面的代码const main () chain(functionA(), tree(functionB1(), functionB2()), functionC()); const functionA () chain(a); const functionB1 () chain(b, x); const functionB2 () chain(b, y); const functionC () chain(c);假设chain(a)可以匹配 Tokena而chain(functionC)可以匹配到 Tokenc。当输入为a b y c时我们该怎么写tree函数呢期望的行为是匹配functionB1时失败再尝试functionB2直到有一个成功为止。那么tree函数可能是这样的function tree(...funs) { // ... 存储当前 tokens for (const fun of funs) { // ... 复位当前 tokens const result fun(); if (result true) { return result; } } }不断尝试tree中内容直到能正确匹配结果后返回。由于正确的匹配会消耗 Token因此需要在执行前后存储当前 Tokens 内容在执行失败时恢复 Token 并尝试新的执行链路。这样看去很容易不是吗然而下面这个例子会打破这个美好的假设稍稍换几个值const main () chain(functionA(), tree(functionB1(), functionB2()), functionC()); const functionA () chain(a); const functionB1 () chain(b, y); const functionB2 () chain(b); const functionC () chain(y, c);输入仍然是a b y c看看会发生什么线路functionA - functionB1是a b y匹配会通过但连上functionC后结果就是a b y y c显然不符合输入。此时正确的线路应该是functionA - functionB2 - functionC结果才是a b y c再看functionA - functionB1 - functionC这条链路当执行到functionC时才发现匹配错了此时想要回到functionB2门也没有因为tree(functionB1(), functionB2())的执行堆栈已退出再也找不回来了。这正是 精读《手写 SQL 编译器 - 语法分析》 中描述的迷宫存档/读档困境如果 A 分支成功函数调用栈就会退出而后面迷宫探索失败的话无法回到岔路 B 继续探索。而 精读《手写 SQL 编译器 - 回溯》 给出了解法方向通过链表手动构造函数执行过程这样不仅可以实现任意位置回溯还可以解决左递归问题——因为函数并不是立即执行的在执行前可以加一些 Magic 动作比如调换执行顺序。所以需要模拟一个执行引擎在遇到分叉路口时将functionB2保存下来随时可以回到这个节点重新执行。4.3 实现 Chain 函数用链表设计Chain函数是最佳选择我们要模拟 JS 调用栈了。const main () chain(functionA, [functionB1, functionB2], functionC)(); const functionA () chain(a)(); const functionB1 () chain(b, y)(); const functionB2 () chain(b)(); const functionC () chain(y, c)();上面的例子只改动了一小点函数不会立即执行。chain将函数转化为FunctionNode将字面量a或b转化为MatchNode将[]转化为TreeNode将自己转化为ChainNode。我们就得到了如下的链表ChainNode(main) └── FunctionNode(functionA) ─ TreeNode ─ FunctionNode(functionC) │── FunctionNode(functionB1) └── FunctionNode(functionB2)至于为什么FunctionNode不直接展开成MatchNode请思考这样的描述const list () chain(,, list)。直接展开则陷入递归死循环实际上 Tokens 数量总有限用到再展开总能匹配尽 Token而不会无限展开下去。需要一个函数将chain函数接收的不同参数转化为对应 Node 节点const createNodeByElement ( element: IElement, parentNode: ParentNode, parentIndex: number, parser: Parser ): Node { if (element instanceof Array) { // ... return TreeNode } else if (typeof element string) { // ... return MatchNode } else if (typeof element boolean) { // ... true 表示一定匹配成功false 表示一定匹配失败均不消耗 Token } else if (typeof element function) { // ... return FunctionNode } };注意boolean分支true表示一定匹配成功、false表示一定匹配失败且二者都不消耗 Token——这正是后面实现optional、many的基石。链表结构与 精读《手写 SQL 编译器 - 回溯》 中给出的双向链表定义一致每个节点拥有prev与next指向上一个与下一个节点childs是该链表下挂载的子元素matchToken 函数、链表节点或函数。对每一个节点如果存在多个子元素则表示这是一个tree节点存在分支情况无论是直线还是分支都可以看作是分支路线直线无分支可以看作只有一条分叉的分支。4.4 引擎执行引擎执行其实就是访问链表通过visit函数是最佳手段。const visit tailCallOptimize( ({ node, store, visiterOption, childIndex }: { node: Node; store: VisiterStore; visiterOption: VisiterOption; childIndex: number; }) { if (node instanceof ChainNode) { // 调用 visitChildNode 访问子节点 } else if (node instanceof TreeNode) { // 调用 visitChildNode 访问子节点 visitChildNode({ node, store, visiterOption, childIndex }); } else if (node instanceof MatchNode) { // 与当前 Token 进行匹配匹配成功则调用 visitNextNodeFromParent 访问父级 Node 的下一个节点匹配失败则调用 tryChances这会在 或 逻辑里说明。 } else if (node instanceof FunctionNode) { // 执行函数节点并替换掉当前节点重新 visit 一遍 } } );由于visit函数执行次数至多可能几百万次因此使用tailCallOptimize进行尾递归优化防止内存或堆栈溢出。visit函数只负责访问节点本身而visitChildNode函数负责访问节点的子节点如果有而visitNextNodeFromParent函数负责在没有子节点时找到父级节点的下一个子节点访问。function visitChildNode({ node, store, visiterOption, childIndex }: { node: ParentNode; store: VisiterStore; visiterOption: VisiterOption; childIndex: number; }) { if (node instanceof ChainNode) { const child node.childs[childIndex]; if (child) { // 调用 visit 函数访问子节点 child } else { // 如果没有子节点就调用 visitNextNodeFromParent 往上找了 } } else { // 对于 TreeNode如果不是访问到了最后一个节点则添加一次 存档 // 调用 addChances // 同时如果有子元素visit 这个子元素 } } const visitNextNodeFromParent tailCallOptimize( ( node: Node, store: VisiterStore, visiterOption: VisiterOption, astValue: any ) { if (!node.parentNode) { // 找父节点的函数没有父级时下面再介绍记住这个位置叫 END 位。 } if (node.parentNode instanceof ChainNode) { // A B - next node C // └── node - current node // 正如图所示找到 nextNode 节点调用 visit } else if (node.parentNode instanceof TreeNode) { // TreeNode 节点直接利用 visitNextNodeFromParent 跳过。因为同一时间 TreeNode 节点只有一个分支生效所以它没有子元素了 } } );可以看到visitChildNode与visitNextNodeFromParent函数都只处理好自己的事情而将其他工作交给别的函数完成这样函数间职责分明代码也更易懂。有了visit、visitChildNode与visitNextNodeFromParent就完成了节点的访问、子节点的访问、以及当没有子节点时追溯到上层节点的访问。4.5 何时算执行完当visitNextNodeFromParent函数访问到END 位时是时候做一个了结了当 Tokens正好消耗完完美匹配成功Tokens 没消耗完匹配失败还有一种失败情况是Chance用光时结合下面的或逻辑一起说。4.6 或逻辑的实现或逻辑是重构 JS 引擎的原因现在这个问题被很好解决掉了。const main () chain(functionA, [functionB1, functionB2], functionC)();比如上面的代码当遇到[]数组结构时被认为是或逻辑子元素存储在TreeNode节点中。在visitChildNode函数中与ChainNode不同之处在于访问TreeNode子节点时还会调用addChances方法为下一个子元素存储执行状态以便未来恢复到这个节点继续执行。addChances维护了一个池子调用是先进后出function addChances(/* ... */) { const chance { node, tokenIndex, childIndex }; store.restChances.push(chance); }与addChance相对的就是tryChance。下面两种情况会调用tryChancesMatchNode匹配失败。节点匹配失败是最常见的失败情况但如果chances池还有存档就可以恢复过去继续尝试没有下一个节点了但 Tokens 还没消耗完也说明匹配失败了此时调用tryChances继续尝试。看看神奇的存档恢复函数tryChances是如何做的function tryChances( node: Node, store: VisiterStore, visiterOption: VisiterOption ) { if (store.restChances.length 0) { // 直接失败 } const nextChance store.restChances.pop(); // reset scanner index store.scanner.setIndex(nextChance.tokenIndex); visit({ node: nextChance.node, store, visiterOption, childIndex: nextChance.childIndex }); }tryChances其实很简单除了没有chances就失败外找到最近的一个chance节点恢复 Token 指针位置并visit这个节点就等价于读档。这正是 精读《手写 SQL 编译器 - 回溯》 中treeChances机制在 syntax-parser 中的正式形态每次节点成功时进行位置存档防止后续链路执行失败整个 visit 执行完后若结果失败而 chances 池还有存货就 pop 出最近的存档、setIndex还原 token 位置、重新 visit。机会用尽则匹配失败只要有任意一次机会或者能一命通关则匹配成功。4.7 many, optional, plus 的实现这三个方法实现得也很精妙。先看可选函数optionalexport const optional (...elements: IElements) { return chain([chain(...elements)(/**/)), true])(/**/); };可以看到可选参数实际上就是一个TreeNode也就是chain(optional(a))(); // 等价于 chain([a, true])();为什么呢因为当a匹配失败后true是一个不消耗 Token 一定成功的匹配整体来看就是可选的意思。进一步解释下如果a没有匹配上则true一定能匹配上匹配true等于什么都没匹配就等同于这个表达式不存在。这与 精读《手写 SQL 编译器 - 语法分析》 中用tree(fn, () true)表达func? func | εε 表示空产生式永远解析成功且不消耗 Token的思路完全一致——可选函数就是分支函数的一个特例。再看匹配一或多个的函数plusexport const plus (...elements: IElements) { const plusFunction () chain(chain(...elements)(/**/), optional(plusFunction))(/**/); return plusFunction; };能看出来吗plus函数等价于一个新递归函数。也就是const aPlus () chain(plus(a))(); // 等价于 const aPlus () chain(plusFunc)(); const plusFunc () chain(a, optional(plusFunc))();通过不断递归自身的方式匹配到尽可能多的元素而每一层的optional保证了任意一层匹配失败后可以及时跳到下一个文法不会失败。这里正是利用了FunctionNode 用到再展开的特性文法存在无限递归但 Tokens 数量总有限匹配尽 Token 后自然结束不会无限展开。最后看匹配多个的函数manyexport const many (...elements: IElements) { return optional(plus(...elements)); };many就是optional的plus不是吗三个神奇的函数都利用了已有功能实现建议每个函数留一分钟左右时间思考为什么。4.8 错误提示 输入推荐错误提示与输入推荐类似都是给出错误位置或光标位置后期待的输入。输入推荐就是给定字符串与光标位置给出光标后期待内容的功能。首先通过光标位置找到光标的上一个Token再通过findNextMatchNodes找到这个Token后所有可能匹配到的MatchNode这就是推荐结果。那么如何实现findNextMatchNodes呢看下面function findNextMatchNodes(node: Node, parser: Parser): MatchNode[] { const nextMatchNodes: MatchNode[] []; let passCurrentNode false; const visiterOption: VisiterOption { onMatchNode: (matchNode, store, currentVisiterOption) { if (matchNode node passCurrentNode false) { passCurrentNode true; // 调用 visitNextNodeFromParent忽略自身 } else { // 遍历到的 MatchNode nextMatchNodes.push(matchNode); } // 这个是画龙点睛的一笔所有推荐都当作匹配失败通过 tryChances 可以找到所有可能的 MatchNode tryChances(matchNode, store, currentVisiterOption); } }; newVisit({ node, scanner: new Scanner([]), visiterOption, parser }); return nextMatchNodes; }所谓找到后续节点就是通过Visit找到所有的MatchNode而MatchNode只要匹配一次即可因为我们只要找到第一层级的MatchNode。通过每次匹配后执行tryChances就可以找到所有MatchNode节点了再看错误提示我们要记录最后出错的位置再采用输入推荐即可。但光标所在的位置是期望输入点这个输入点也应该参与语法树的生成而错误提示不包含光标所以我们要执行两次visit。举个例子select | from b;|是光标位置此时语句内容是select from b;显然是错误的但光标位置应该给出提示给出提示就需要正确解析语法树所以对于提示功能我们需要将光标位置考虑进去一起解析。因此一共有两次解析。这与 精读《手写 SQL 编译器 - 智能提示》 的架构决策一脉相承语法检查与智能提示分为两个模块独立处理——语法角度它是错的不完整语句提示角度它是正确的输入过程所以需要分两条线程处理。syntax-parser 在解析引擎层将光标作为一个特殊 Token参与解析因此即使语句有语法错误也总能返回{ ast, cursorPath }两个信息供上层sql-reader追溯光标在语法树中的位置。4.9 First 集优化构建 First 集是个自下而上的过程当访问到MatchNode节点时其值就是其父节点的一个 First 值当父节点的 First 集收集完毕后就会触发它的父节点 First 集收集判断如此递归最后完成 First 集收集的是最顶级节点。从 精读《手写 SQL 编译器 - 性能优化之缓存》 可以补充 First 集优化的意义在初始化时将整体文法的 First 集找到因此在节点匹配时如果 Token 不存在于 First 集中可以快速跳过这个文法在文法调用链很长、或或的情况比较多时可以少走很多弯路不论节点路径有多长都可以以最快速度判断节点是否不匹配。与之配合的还有Match 节点缓存运行时缓存节点到其第一个终结符的过程让匹配时可以直达真正匹配 Token 的 Match 节点两者叠加可以显著减少节点访问次数。5. 总结这篇文章是对《手写 SQL 编译器》系列的总结从源码角度出发词法分析用正则 从左到右循环裁剪实现分词语法分析用ChainNode / TreeNode / FunctionNode / MatchNode 四类节点构成的链表重写了函数执行机制通过addChances/tryChances的存档-读档机制实现了任意位置的回溯从而让递归下降达到LL(∞)的匹配能力optional/plus/many这三个高频文法组合子全部由既有能力递归组合而成在此基础上findNextMatchNodes与两次 visit支撑起了错误提示与输入推荐最终让 syntax-parser 有能力承载一个带智能提示的 SQL 编辑器。该系列的每篇文章都以图文方式介绍了各技术细节可以作为补充阅读精读《手写 SQL 编译器 - 词法分析》精读《手写 SQL 编译器 - 文法介绍》精读《手写 SQL 编译器 - 语法分析》精读《手写 SQL 编译器 - 回溯》精读《手写 SQL 编译器 - 语法树》精读《手写 SQL 编译器 - 错误提示》精读《手写 SQL 编译器 - 性能优化之缓存》精读《手写 SQL 编译器 - 智能提示》赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐Hermes 正则引擎深度解析从源码看回溯栈字节码的编译与执行Hermes 正则引擎深度解析从源码看回溯栈字节码的编译与执行 导读 本文以 doc/RegExp.md https://link.gitcode.com/i语言运行时编译器移动开发ImHex模式语言语法解析与执行引擎ImHex模式语言语法解析与执行引擎 引言二进制世界的编程语言 还在为解析复杂的二进制文件格式而头疼吗面对PE文件、ELF可执行文件、图片格式、音频文件等桌面应用开发工具逆向工程Actual-Server解释器模式语法解析与执行引擎Actual Server解释器模式语法解析与执行引擎 痛点分布式同步的复杂性挑战 在现代个人财务管理工具中多设备数据同步是一个核心但极其复杂的挑战。传统后端金融科技数据同步上一篇Repomix Explorer 技能Agent Skills让 AI 助手用自然语言分析任意代码仓库下一篇Grafana Loki 发布说明模板tools/release-note.md深度解析从模板变量到 Docker 与二进制安装实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考