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