文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载本文是「手写 SQL 编译器」系列继词法分析、文法介绍之后的第三篇聚焦语法分析Parsing阶段为什么选择递归下降自顶而下而非 LR 移进规约如何用match、函数调用、分支函数tree与可选函数optional四个基本组合搭建一个可运行的 SQL 语法解析器以及为何这套朴素写法无法实现回溯需要另起炉灶用链表模拟函数执行栈。读完你就能亲手写出十几行代码级别的 SQL 解析骨架并理解通向 LL(∞) 的下一步改造方向。1. 语法分析的两大流派自顶而下与自底而上以解析顺序为角度语法分析分为两种自顶而下与自底而上。自顶而下一般采用递归下降方式处理称为 LL(k)。其中第一个L指从左到右分析扫描 Token 的方向第二个L指从左开始推导优先展开最左侧的非终结符k指超前查看Lookahead的数量。如果实现了回溯功能k 就是无限大的所以带有回溯功能的 LL(k)即 LL(∞)几乎是 LL 家族中能力最强的。LL 系列一般分为 LL(0)、LL(1)、LL(k)、LL(∞) 几个等级。自底而上一般采用移进shift规约reduce方式处理称为 LR第一个L同样是从左到右分析第二个R指从右开始推导由于规约时可能产生冲突通过超前查看一个符号解决冲突就有了 SLR之后还有能力更强的 LALR(1)、LR(1)、LR(k)。无论 LL 还是 LR都解决不了二义性文法Ambiguous Grammar。好在所有计算机语言都属于无二义性文法因此两种流派都能胜任 SQL 的解析。这里有一个关键权衡如果实现了回溯功能的 LL(k)即 LL(∞)其能力可以与 LR(k) 比肩而 LL 系列手写起来更易读。因此本系列选择 LL 方式书写本文介绍的是如何手写无回溯功能的 LL也就是基础的递归下降。除了手写也有一些根据文法自动生成 parser 的库比如兼容多语言的 ANTLR4以及对 JS 支持友好的 PEG.js 等。但自动生成方案难以深度定制本系列最终走向了自研方案详见下文与后续文章。2. 递归下降一个可以走出来的多出口迷宫递归下降可以理解为走多出口的迷宫先根据 SQL 语法构造一个迷宫进迷宫的不是探险家而是 SQL 语句这个 SQL 语句会拿上一堆令牌切分好的 Tokens详情见 精读词法分析迷宫每前进一步都会要求按顺序给出令牌交上去就没收如果走到出口时令牌刚好交完就成功走出了迷宫如果出迷宫时手上还有令牌会被迷宫工作人员带走。这个迷宫会有一些分叉在分岔路上会要求你亮出几个令牌中任意一个即可通过对应LL(1)有的迷宫允许你失败了存档只要没有走出迷宫都可以读档重来对应LL(k)理论上可以构造一个最宽容的迷宫只要还没走出迷宫可以在分叉处任意读档对应LL(∞)留到下一篇介绍。把语法分析抽象成迷宫之后剩下的工作就是回答三个问题令牌从哪来、关卡Match怎么写、岔路分支怎么选。3. 词法分析先把 SQL 切成令牌首先对 SQL 进行词法分析拿到 Tokens 列表——这些就是探险家 SQL 带上的令牌。根据上一篇词法分析的内容我们对select a from b进行词法分析可以拿到四个 Token忽略空格与注释。注意在语法解析过程中注释和空格可以被消除这样省去对空格和注释的判断可以大大简化代码量。4. Match 函数迷宫中索取令牌的关卡递归下降最重要的就是Match 函数它就是迷宫中索取令牌的关卡。每个 Match 函数只要匹配上当前 Token便将 Token index 下移一位如果没有匹配上则不消耗 Tokenfunction match(word: string) { const currentToken tokens[tokenIndex] // 拿到当前所在的 Token if (currentToken.value word) { // 如果 Token 匹配上了则下移一位同时返回 true tokenIndex return true } // 没有匹配上不消耗 Token但是返回 false return false }Match 函数本质上就是精简版的 if else。试想下面一段代码if (token[tokenIndex].value select) { tokenIndex } else { return false } if (token[tokenIndex].value a) { tokenIndex } else { return false }通过不断对比与移动 Token 进行判断等价于下面的 Match 实现match(select) match(a)这样写出来的语法分析代码可读性会更强我们能专注精神在对文法的解读上而忽略其他环境因素Token 指针移动、数组边界等。顺便一提系列后续文章会带来更精简的描述方法——chain(select, a)让函数式语法更接近文法形式见 精读《手写 SQL 编译器 - 回溯》。这种语法不但描述更精简而且拥有 LL(∞) 的查找能力拥有几乎最强大的语法分析能力。5. 语法分析主体函数十几行代码跑通第一条 SQL既然关卡Match已经有了下面开始构造主函数——也就是开始画迷宫。举个最简单的例子匹配select a from b只需要这样构造主函数let tokenIndex 0 function match() { /* .. */ } const root () match(select) match(a) match(from) match(b) tokens lexer(select a from b) if (root() tokenIndex tokens.length) { // sql 解析成功 }为了简化流程我们把 tokens、tokenIndex 作为全局变量。首先通过lexer拿到select a from b语句的 Tokens[select, , a, , from, , b]。由于语法解析阶段可以消除空格与注释最终拿到的 Tokens 是[select, a, from, b]。很显然这与我们构造的 Match 队列相吻合所以这段语句顺利走出了迷宫而且走出迷宫时 Token 正好被消费完tokenIndex tokens.length。这里有两个值得注意的判定细节root()返回 true 只代表文法匹配完成不代表语句合法——还要追加tokenIndex tokens.length判定防止 Token 有余量对应迷宫出口时手上还有令牌的情况连接天然具有短路语义一旦某个match返回 false后续 Match 不再执行整个产生式即判定失败这正好对应迷宫一条路走不通就失败的情形。这样就完成了最简单的语法分析一共十几行代码。6. 函数调用用抽象化解无限复杂的文法函数调用是 JS 最基础的知识但用在语法解析里可就不那么一样了。考虑上面最简单的语句select a from b显然无法胜任真正的 SQL 环境比如select [位置] from b这个位置可以放置任意用逗号相连的字符串。如果我们将这种 SQL 展开描述将非常复杂、难以阅读。恰好函数调用可以帮我们完美解决这个问题——我们将这个位置抽象为selectList函数主语句改造如下const root () match(select) selectList() match(from) match(b)这下能否解析select a, b, c from table就看selectList这个函数了const selectList match(a) match(,) match(b) match(,) match(c)显然这样做不具备通用性因为我们将参数名与数量固定了。考虑到上一篇精读学到的文法我们可以这样描述selectListselectList :: word (, selectList)? word :: [a-zA-Z]这里故意绕过了左递归采用右递归的写法因而避开了语法分析的核心难点。?号是可选的意思与正则的?类似。这是一个右递归文法不难看出这个文法可以如此展开selectList word (, selectList)? a (, selectList)? a, word (, selectList)? a, b, word (, selectList)? a, b, word a, b, c我们一下遇到了两个问题补充word函数如何描述可选参数。同理利用函数调用我们假定拥有了可选函数optional与函数word这样可以先把selectList函数描述出来const selectList () word() optional(match(,) selectList())这样就通过可选函数optional描述了文法符号?。我们来看word函数如何实现。需要简单改造下match使其支持正则那么word函数可以这样描述const word () match(/[a-zA-Z]*/)而optional不是普通的match函数从调用方式就能看出来我们到下一节详细介绍。注意selectList函数尾部通过右递归的方式调用自身因此可以解析任意长度以,分割的字段列表。关于左递归ANTLR4 支持左递归因此文法可以写成selectList :: selectList (, word)? | word但用在我们这个简化的代码中会导致堆栈溢出。左递归的处理方式转换为右递归在 精读《手写 SQL 编译器 - 文法介绍》 中有专门讨论左递归完全不消耗 Token而右递归可以通过消耗 Token 的方式跳出死循环。在介绍optional函数之前我们先引出分支函数因为可选函数是分支函数的一种特殊形式。7. 分支函数岔路口的选择与 Token 还原我们先看看函数word其实没有考虑到函数作为字段的情况比如select a, SUM(b) from table。所以我们需要升级下selectList的描述const selectList () field() optional(match(,) selectList()) const field () word()这时注意field作为一个字段也可能是文本或函数我们假设拥有函数处理函数functional那么用文法描述field就是field :: text | functional|表示分支我们用tree函数表示分支函数那么可以如此改写fieldconst field () tree(word(), functional())那么该如何表示tree呢按照分支函数的特性tree的职责是超前查看超前查看word是否符合当前 Token 的特征如果符合则此分支可以走通如果不符合继续尝试functional。若存在 A、B 分支由于是函数式调用若 A 分支为真则函数堆栈退出到上层若后续尝试失败则无法再回到分支 B 继续尝试因为函数栈已经退出了。这就是本文开头提到的回溯机制对应迷宫的存档、读档机制。要实现回溯机制要模拟函数执行机制、拿到函数调用的控制权这在后续文章中详细介绍见 精读《手写 SQL 编译器 - 回溯》。根据这个特性我们可以写出tree函数的第一个版本function tree(...args: any[]) { return args.some(arg arg()) }按照顺序执行tree的入参如果有一个函数执行为真则跳出函数如果所有函数都返回 false则这个分支结果为 false。考虑到每个分支都会消耗 Token所以我们需要在执行分支时先把当前 TokenIndex 保存下来如果执行成功则消耗执行失败则还原 Token 位置function tree(...args: any[]) { const startTokenIndex tokenIndex return args.some(arg { const result arg() if (!result) { tokenIndex startTokenIndex // 执行失败则还原 TokenIndex } return result }); }这个版本的tree实现了分支内部的 Token 还原每个分支都是独立尝试失败即回滚到分支入口处的 Token 位置保证不同分支的匹配起点一致。8. 可选函数ε 空产生式的妙用可选函数就是分支函数的一个特例可以描述为func? func | εε表示空也就是这个产生式解析到这里永远可以解析成功而且不消耗 Token。借助分支函数tree执行失败后还原 TokenIndex 的特性我们先尝试执行它执行失败的话下一个ε函数一定返回 true而且会重置 TokenIndex 且不消耗 Token这与可选的语义是等价的。所以可以这样描述optional函数const optional fn tree(fn, () true)看到这里可以回答上一节的疑问可选函数为什么是分支函数的特殊形式——因为func?的本质就是func | ε两个分支的并运算其中ε分支永远成功且不消耗 Token。9. 基本的运算连接四种基本文法组合上面通过对 SQL 语句的实践发现了四种基本用法match匹配单个单词、连接、tree分支、ε空字符串的产生式。这正好对应下面四个基本文法组合思想G :: ε空字符串产生式对应() true不消耗 Token总是返回true。G :: t单词匹配对应match(t)。G :: x y连接运算对应match(x) match(y)。G :: x G :: y并运算对应tree(x, y)。有了这四种基本用法几乎可以描述所有 SQL 语法。比如简单描述一下 select 语法const root () match(select) select() match(from) table() const selectList () field() optional(match(,) selectList()) const field () tree(word, functional) const word () match(/[a-zA-Z]/)把四种基本组合对照到实际代码上文法形式含义对应代码G :: ε空产生式() true不消耗 Token 恒真G :: t匹配终结符match(t)消耗一个 TokenG :: x y连接match(x) match(y)短路求值G :: x \| y分支/并tree(x, y)逐一尝试并还原 Token这套「四个基本组合」的思想在后续演进为 syntax-parser 中的四类链表节点ChainNode连接、TreeNode分支、FunctionNode函数节点、MatchNode匹配见 源码解读精读《syntax-parser 源码》。可见本篇文章打下的抽象正是整个自研语法解析引擎的雏形。10. 总结局限与下一步递归下降的 SQL 语法解析就是一个走迷宫的过程将 Token 从左到右逐个匹配最终能找到一条路线完全贴合 Token则 SQL 解析圆满结束。这个迷宫用空字符串产生式、单词匹配、连接运算、并运算四个基本文法组合就足以构成。掌握了这四大法宝基本的 SQL 解析已经难不倒你了下一步需要做这些优化回溯功能实现它才可能实现 LL(∞) 的匹配能力。从本文不难看出通过函数调用方式我们无法做到迷宫存档和读档机制——遇到岔路 A、B 时如果 A 成功了函数调用栈就会退出后面迷宫探索失败的话我们无法回到岔路 B 继续探索。回溯功能就赋予了这个探险者返回岔路 B 的能力。为了实现这个功能几乎要完全推翻这篇文章的代码组织结构用链表手动构造函数执行过程不过四个基本组合思想还会保留。这一部分在 精读《手写 SQL 编译器 - 回溯》 中有完整实现。左递归自动消除因为通过文法转换会改变文法的结合律与语义最好能实现左递归自动消除左递归在上一篇精读《手写 SQL 编译器 - 文法介绍》中有说明。生成语法树仅匹配语句的正确性是不够的还要根据语义生成语法树见 精读《手写 SQL 编译器 - 语法树》。错误检查在错误的地方给出建议甚至对某些错误做自动修复这在 SQL 智能提示时需要用到见 精读《手写 SQL 编译器 - 错误提示》。错误恢复让解析器在错误发生后尽量恢复继续解析。后续系列文章会介绍如何实现回溯让递归下降达到 LL(∞) 的效果再往后依次是语法树生成、错误提示、基于 First 集与 Match 节点缓存的性能优化以及最终落地为具备智能提示能力的 SQL 编辑器。整个系列的逻辑链条正是从本文这十几行代码和四个基本文法组合出发一步步长成完整的 JS 版语法分析引擎 syntax-parser。赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐手写 JSON Parser从语法图到递归下降解析器的完整实践前端精读周刊手写 JSON Parser从语法图到递归下降解析器的完整实践前端精读周刊 JSON.parse 是浏览器内置 API但若能亲手实现一个 JSON 解析器文档技术博客教程递归下降解析8cc编译器如何优雅解析C语言语法递归下降解析8cc编译器如何优雅解析C语言语法 还在为复杂的语法解析算法头疼8cc编译器用递归下降Recursive Descent技术将C语言解析变编译器开发工具前端精读周刊Rest 与 Spread 语法辨析 —— 一个 ... 的两种身份与三个隐蔽坑前端精读周刊Rest 与 Spread 语法辨析 —— 一个 ... 的两种身份与三个隐蔽坑 JavaScript 用同一个符号 ... 同时承载了 Rest文档技术博客教程上一篇Vite终极指南2024年Web开发构建工具的未来趋势下一篇Hexo Next主题SEO优化终极指南7个简单步骤提升博客排名创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考