資訊專欄INFORMATION COLUMN
摘要：引言重回手寫編輯器系列?，F(xiàn)在節(jié)點(diǎn)不匹配時(shí)性能已經(jīng)最優(yōu)，那下一步就是如何優(yōu)化匹配時(shí)的性能，這時(shí)就用到節(jié)點(diǎn)緩存。更多討論討論地址是精讀手寫編譯器性能優(yōu)化之緩存如果你想?yún)⑴c討論，請點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。
1 引言
重回 “手寫 SQL 編輯器” 系列。這次介紹如何利用緩存優(yōu)化編譯器執(zhí)行性能。
可以利用 Frist 集 與 Match 節(jié)點(diǎn)緩存 這兩種方式優(yōu)化。
本文會用到一些圖做解釋，下面介紹圖形規(guī)則：
First 集優(yōu)化，是指在初始化時(shí)，將整體文法的 First 集找到，因此在節(jié)點(diǎn)匹配時(shí)，如果 Token 不存在于 First 集中，可以快速跳過這個(gè)文法，在文法調(diào)用鏈很長，或者 “或” 的情況比較多時(shí)，可以少走一些彎路：
如圖所示，只要構(gòu)建好了 First 集，不論這個(gè)節(jié)點(diǎn)的路徑有多長，都可以以最快速度判斷節(jié)點(diǎn)是否不匹配。如果節(jié)點(diǎn)匹配，則繼續(xù)深度遍歷方式訪問節(jié)點(diǎn)。
現(xiàn)在節(jié)點(diǎn)不匹配時(shí)性能已經(jīng)最優(yōu)，那下一步就是如何優(yōu)化匹配時(shí)的性能，這時(shí)就用到 Match 節(jié)點(diǎn)緩存。
Match 節(jié)點(diǎn)緩存，指在運(yùn)行時(shí)，緩存節(jié)點(diǎn)到其第一個(gè)終結(jié)符的過程。與 First 集相反，F(xiàn)irst 集可以快速跳過，而 Match 節(jié)點(diǎn)緩存可以快速找到終結(jié)符進(jìn)行匹配，在非終結(jié)符很多時(shí)，效果比較好：
如圖所示，當(dāng)匹配到節(jié)點(diǎn)時(shí)，如果已經(jīng)構(gòu)建好了緩存，可以直接調(diào)到真正匹配 Token 的 Match 節(jié)點(diǎn)，從而節(jié)省了大量節(jié)點(diǎn)遍歷時(shí)間。
這里需要注意的是，由于 Tree 節(jié)點(diǎn)存在分支可能性，因此緩存也包含將 “沿途” Chances 推入 Chances 池的職責(zé)。
2 精讀那么如何構(gòu)建 First 集與 Match 節(jié)點(diǎn)緩存呢？通過兩張圖解釋。
構(gòu)建 First 集如圖所示，構(gòu)建 First 集是個(gè)自下而上的過程，當(dāng)訪問到 MatchNode 節(jié)點(diǎn)時(shí)，就可以收集作為父節(jié)點(diǎn)的 First 集了！父集判斷 First 集收集完畢的話，就會觸發(fā)它的父節(jié)點(diǎn) First 集收集判斷，如此遞歸，最后完成 First 集收集的是最頂級節(jié)點(diǎn)。
構(gòu)建 Match 節(jié)點(diǎn)緩存如圖所示，訪問節(jié)點(diǎn)時(shí)，如果沒有緩存，則會將這個(gè)節(jié)點(diǎn)添加到 Match 緩存查找隊(duì)列，同時(shí)路途遇到 TreeNode，也會將下一個(gè) Chance 添加到緩存查找隊(duì)列。直到遇到了第一個(gè) MatchNode 節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)是 “Match 緩存查找隊(duì)列” 所有節(jié)點(diǎn)的 Match 節(jié)點(diǎn)緩存，此時(shí)這些節(jié)點(diǎn)的緩存就可以生效了，指向這個(gè) MatchNode，同時(shí)清空緩存查找隊(duì)列，等待下一次查找。
3 總結(jié)拿 select a, b, c, d from e 這個(gè)語句做測試：
| node 節(jié)點(diǎn)訪問次數(shù) | Frist 集優(yōu)化 | First 集 + Match 節(jié)點(diǎn)緩存優(yōu)化 |
|---|---|---|
| 784 | 669 | 652 |
從這個(gè)簡單 Demo 來看，提效了 16% 左右。不過考慮到文法結(jié)構(gòu)會影響到提效，對于層級更深的文法、能激活深層級文法的輸入可以達(dá)到更好的效率提升。
4 更多討論討論地址是：精讀《手寫 SQL 編譯器 - 性能優(yōu)化之緩存》 · Issue #110 · dt-fe/weekly
如果你想?yún)⑴c討論，請點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。前端精讀 - 幫你篩選靠譜的內(nèi)容。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/99009.html
摘要：經(jīng)過連續(xù)幾期的介紹，手寫編譯器系列進(jìn)入了智能提示模塊，前幾期從詞法到文法語法，再到構(gòu)造語法樹，錯(cuò)誤提示等等，都是為智能提示做準(zhǔn)備。 1 引言 詞法、語法、語義分析概念都屬于編譯原理的前端領(lǐng)域，而這次的目的是做 具備完善語法提示的 SQL 編輯器，只需用到編譯原理的前端部分。 經(jīng)過連續(xù)幾期的介紹，《手寫 SQL 編譯器》系列進(jìn)入了 智能提示 模塊，前幾期從 詞法到文法、語法，再到構(gòu)造語法...
摘要：引言是一個(gè)版語法解析器生成器，具有分詞語法樹解析的能力。實(shí)現(xiàn)函數(shù)用鏈表設(shè)計(jì)函數(shù)是最佳的選擇，我們要模擬調(diào)用棧了。但光標(biāo)所在的位置是期望輸入點(diǎn)，這個(gè)輸入點(diǎn)也應(yīng)該參與語法樹的生成，而錯(cuò)誤提示不包含光標(biāo)，所以我們要執(zhí)行兩次。 1. 引言 syntax-parser 是一個(gè) JS 版語法解析器生成器，具有分詞、語法樹解析的能力。 通過兩個(gè)例子介紹它的功能。 第一個(gè)例子是創(chuàng)建一個(gè)詞法解析器 my...
摘要：返回的語法樹作為結(jié)果被傳遞到文法中，其結(jié)果可能是。每個(gè)元素的子節(jié)點(diǎn)全部執(zhí)行完畢，才會生成當(dāng)前節(jié)點(diǎn)的語法樹。更多討論討論地址是精讀手寫編譯器語法樹如果你想?yún)⑴c討論，請點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。 1 引言 重回 手寫 SQL 編輯器 系列。之前幾期介紹了 詞法、文法、語法的解析，以及回溯功能的實(shí)現(xiàn)，這次介紹如何生成語法樹。 基于 《回溯》 一文介紹的思路，我們利用 JS ...
閱讀 2478·2021-11-22 15:35
閱讀 3767·2021-11-04 16:14
閱讀 2696·2021-10-20 13:47
閱讀 2507·2021-10-13 09:49
閱讀 2078·2019-08-30 14:09
閱讀 2377·2019-08-26 13:49
閱讀 887·2019-08-26 10:45
閱讀 2778·2019-08-23 17:54
