摘要：引言重回手写编辑器系列。现在节点不匹配时性能已经最优，那下一步就是如何优化匹配时的性能，这时就用到节点缓存。更多讨论讨论地址是精读手写编译器性能优化之缓存如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。
1 引言
重回 “手写 SQL 编辑器” 系列。这次介绍如何利用缓存优化编译器执行性能。
可以利用 Frist 集 与 Match 节点缓存 这两种方式优化。
本文会用到一些图做解释，下面介绍图形规则：
First 集优化，是指在初始化时，将整体文法的 First 集找到，因此在节点匹配时，如果 Token 不存在于 First 集中，可以快速跳过这个文法，在文法调用链很长，或者 “或” 的情况比较多时，可以少走一些弯路：
如图所示，只要构建好了 First 集，不论这个节点的路径有多长，都可以以最快速度判断节点是否不匹配。如果节点匹配，则继续深度遍历方式访问节点。
现在节点不匹配时性能已经最优，那下一步就是如何优化匹配时的性能，这时就用到 Match 节点缓存。
Match 节点缓存，指在运行时，缓存节点到其第一个终结符的过程。与 First 集相反，First 集可以快速跳过，而 Match 节点缓存可以快速找到终结符进行匹配，在非终结符很多时，效果比较好：
如图所示，当匹配到节点时，如果已经构建好了缓存，可以直接调到真正匹配 Token 的 Match 节点，从而节省了大量节点遍历时间。
这里需要注意的是，由于 Tree 节点存在分支可能性，因此缓存也包含将 “沿途” Chances 推入 Chances 池的职责。
2 精读那么如何构建 First 集与 Match 节点缓存呢？通过两张图解释。
构建 First 集如图所示，构建 First 集是个自下而上的过程，当访问到 MatchNode 节点时，就可以收集作为父节点的 First 集了！父集判断 First 集收集完毕的话，就会触发它的父节点 First 集收集判断，如此递归，最后完成 First 集收集的是最顶级节点。
构建 Match 节点缓存如图所示，访问节点时，如果没有缓存，则会将这个节点添加到 Match 缓存查找队列，同时路途遇到 TreeNode，也会将下一个 Chance 添加到缓存查找队列。直到遇到了第一个 MatchNode 节点，则这个节点是 “Match 缓存查找队列” 所有节点的 Match 节点缓存，此时这些节点的缓存就可以生效了，指向这个 MatchNode，同时清空缓存查找队列，等待下一次查找。
3 总结拿 select a, b, c, d from e 这个语句做测试：
| node 节点访问次数 | Frist 集优化 | First 集 + Match 节点缓存优化 |
|---|---|---|
| 784 | 669 | 652 |
从这个简单 Demo 来看，提效了 16% 左右。不过考虑到文法结构会影响到提效，对于层级更深的文法、能激活深层级文法的输入可以达到更好的效率提升。
4 更多讨论讨论地址是：精读《手写 SQL 编译器 - 性能优化之缓存》 · Issue #110 · dt-fe/weekly
如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/99009.html
摘要：经过连续几期的介绍，手写编译器系列进入了智能提示模块，前几期从词法到文法语法，再到构造语法树，错误提示等等，都是为智能提示做准备。 1 引言 词法、语法、语义分析概念都属于编译原理的前端领域，而这次的目的是做 具备完善语法提示的 SQL 编辑器，只需用到编译原理的前端部分。 经过连续几期的介绍，《手写 SQL 编译器》系列进入了 智能提示 模块，前几期从 词法到文法、语法，再到构造语法...
摘要：引言是一个版语法解析器生成器，具有分词语法树解析的能力。实现函数用链表设计函数是最佳的选择，我们要模拟调用栈了。但光标所在的位置是期望输入点，这个输入点也应该参与语法树的生成，而错误提示不包含光标，所以我们要执行两次。 1. 引言 syntax-parser 是一个 JS 版语法解析器生成器，具有分词、语法树解析的能力。 通过两个例子介绍它的功能。 第一个例子是创建一个词法解析器 my...
摘要：返回的语法树作为结果被传递到文法中，其结果可能是。每个元素的子节点全部执行完毕，才会生成当前节点的语法树。更多讨论讨论地址是精读手写编译器语法树如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。 1 引言 重回 手写 SQL 编辑器 系列。之前几期介绍了 词法、文法、语法的解析，以及回溯功能的实现，这次介绍如何生成语法树。 基于 《回溯》 一文介绍的思路，我们利用 JS ...
阅读 2208·2021-11-22 15:35
阅读 3592·2021-11-04 16:14
阅读 2442·2021-10-20 13:47
阅读 2329·2021-10-13 09:49
阅读 1936·2019-08-30 14:09
阅读 2060·2019-08-26 13:49
阅读 732·2019-08-26 10:45
阅读 2651·2019-08-23 17:54
