摘要：總結(jié)做語法解析器錯(cuò)誤提示功能時(shí)，再次刷新了筆者三觀，原來我們以為的必然，在編譯器里對(duì)應(yīng)著那么多可能。語法解析器為了讓報(bào)錯(cuò)符合人們的第一直覺，對(duì)錯(cuò)誤信息做了過濾，只保留剩余數(shù)最短的那條錯(cuò)誤信息。

編譯器除了生成語法樹之外，還要在輸入出現(xiàn)錯(cuò)誤時(shí)給出恰當(dāng)?shù)奶崾尽?/p>

比如當(dāng)用戶輸入 select (name，這是個(gè)未完成的 SQL 語句，我們的目標(biāo)是提示出這個(gè)語句未完成，并給出后續(xù)的建議： ) - + % / * . ( 。

分析一個(gè) SQL 語句，現(xiàn)將 query 字符串轉(zhuǎn)成 Token 數(shù)組，再構(gòu)造文法樹解析，那么可能出現(xiàn)錯(cuò)誤的情況有兩種：

語句錯(cuò)誤。

文法未完成。

給出錯(cuò)誤提示的第一步是判斷錯(cuò)誤發(fā)生。

通過這張 Token 匹配過程圖可以發(fā)現(xiàn)，當(dāng)深度優(yōu)先遍歷文法節(jié)點(diǎn)時(shí)，匹配成功后才會(huì)返回父元素繼續(xù)往下走。而當(dāng)走到父元素沒有根節(jié)點(diǎn)了才算匹配成功；當(dāng)嘗試 Chance 時(shí)沒有機(jī)會(huì)了，就是錯(cuò)誤發(fā)生的時(shí)機(jī)。

所以我們只要找到最后一個(gè)匹配成功的節(jié)點(diǎn)，再根據(jù)最后成功與否，以及搜索出下一個(gè)可能節(jié)點(diǎn)，就能知道錯(cuò)誤類型以及給出建議了。

function onMatchNode(matchNode, store) {
  const matchResult = matchNode.run(store.scanner);

  if (!matchResult.match) {
    tryChances(matchNode, store);
  } else {
    const restTokenCount = store.scanner.getRestTokenCount();
    if (matchNode.matching.type !== "loose") {
      if (!lastMatch) {
        lastMatch = {
          matchNode,
          token: matchResult.token,
          restTokenCount
        };
      }
    }

    callParentNode(matchNode, store, matchResult.token);
  }
}

所以在運(yùn)行語法分析器時(shí)，在遇到匹配節(jié)點(diǎn)（MatchNode）時(shí)，如果匹配成功，就記錄下這個(gè)節(jié)點(diǎn)，這樣我們最終會(huì)找到最后一個(gè)匹配成功的節(jié)點(diǎn)：lastMatch。

之后通過 findNextMatchNodes 函數(shù)找到下一個(gè)可能的推薦節(jié)點(diǎn)列表，作為錯(cuò)誤恢復(fù)的建議。

findNextMatchNodes 函數(shù)會(huì)根據(jù)某個(gè)節(jié)點(diǎn)，找出下一節(jié)點(diǎn)所有可能 Tokens 列表，這個(gè)函數(shù)后面文章再專門介紹，或者你也可以先閱讀 源碼.

也就是任何一個(gè) Token 匹配失敗。比如：

select * from table_name as table1 error_string;

這里 error_string 就是冗余的語句。

通過語法解析器分析，可以得到執(zhí)行失敗的結(jié)果，然后通過 findNextMatchNodes 函數(shù)，我們可以得到下面分析結(jié)果：

可以看到，程序判斷出了 error_string 這個(gè) Token 屬于錯(cuò)誤類型，同時(shí)給出建議，可以將 error_string 替換成這 14 個(gè)建議字符串中任意一個(gè)，都能使語句正確。

之所以失敗類型判斷為錯(cuò)誤類型，是因?yàn)椴檎伊诉@個(gè)正確 Token table1 后面還有一個(gè)沒有被使用的 error_string，所以錯(cuò)誤歸類是 wrong。

注意，這里給出的是下一個(gè) Token 建議，而不是全部 Token 建議，因此推薦了 where 表示 “或者后面跟一個(gè)完整的 where 語句”。

和語句錯(cuò)誤不同，這種錯(cuò)誤所有輸入的單詞都是正確的，但卻沒有寫完。比如：

select *

通過語法解析器分析，可以得到執(zhí)行失敗的結(jié)果，然后通過 findNextMatchNodes 函數(shù)，我們可以得到下面分析結(jié)果：

可以看到，程序判斷出了 * 這個(gè) Token 屬于未完成的錯(cuò)誤類型，建議在后面補(bǔ)全這 14 個(gè)建議字符串中任意一個(gè)。比較容易聯(lián)想到的是 where，但也可以是任意子文法的未完成狀態(tài)，比如后面補(bǔ)充 , 繼續(xù)填寫字段，或者直接跟一個(gè)單詞表示別名，或者先輸入 as 再跟別名。

之所以失敗類型判斷為未完成，是因?yàn)樽詈笠粋€(gè)正確 Token * 之后沒有 Token 了，但語句解析失敗，那只有一個(gè)原因，就是語句為寫完，因此錯(cuò)誤歸類是 inComplete。

在一開始有提到，我們只要找到最后一個(gè)匹配成功的節(jié)點(diǎn)，就可以順藤摸瓜找到錯(cuò)誤原因以及提示，但最后一個(gè)成功的節(jié)點(diǎn)可能和我們?nèi)祟愔庇X相違背。舉下面這個(gè)例子：

select a from b where a = "1" ~ -- 這里手滑了

正常情況，我們都認(rèn)為錯(cuò)誤點(diǎn)在 ~，而最后一個(gè)正確輸入是 "1"。但詞法解析器可不這么想，在我初版代碼里，判斷出錯(cuò)誤是這樣的：

提示是 where 錯(cuò)了，而且提示是 .，有點(diǎn)摸不著頭腦。

讀者可能已經(jīng)想到了，這個(gè)問題與文法結(jié)構(gòu)有關(guān)，我們看 fromClause 的文法描述：

const fromClause = () =>
  chain(
    "from",
    tableSources,
    optional(whereStatement),
    optional(groupByStatement),
    optional(havingStatement)
  )();

雖然實(shí)際傳入的 where 語句多了一個(gè) ~ 符號(hào)，但由于文法認(rèn)為整個(gè) whereStatement 是可選的，因此出錯(cuò)后會(huì)跳出，跳到 b 的位置繼續(xù)匹配，而 顯然 groupByStatement 與 havingStatement 都不能匹配到 where，因此編譯器認(rèn)為 “不會(huì)從 b where a = "1" ~” 開始就有問題吧？因此繼續(xù)往回追溯，從 tableName 開始匹配：

const tableName = () =>
  chain([matchWord, chain(matchWord, ".", matchWord)()])();

此時(shí)第一次走的 b where a = "1" ~ 路線對(duì)應(yīng) matchWord，因此嘗試第二條路線，所以認(rèn)為 where 應(yīng)該換成 .。

要解決這個(gè)問題，首先要 承認(rèn)這個(gè)判斷是對(duì)的，因?yàn)檫@是一種 錯(cuò)誤提前的情況，只是人類理解時(shí)往往只能看到最后幾步，所以我們默認(rèn)用戶想要的錯(cuò)誤信息，是 正確匹配鏈路最長的那條，并對(duì) onMatchNode 作出下面優(yōu)化：

將 lastMatch 對(duì)象改為 lastMatchUnderShortestRestToken:

if (
  !lastMatchUnderShortestRestToken ||
  (lastMatchUnderShortestRestToken &&
    lastMatchUnderShortestRestToken.restTokenCount > restTokenCount)
) {
  lastMatchUnderShortestRestToken = {
    matchNode,
    token: matchResult.token,
    restTokenCount
  };
}

也就是每次匹配到正確字符，都獲取剩余 Token 數(shù)量，只保留最后一匹配正確 且剩余 Token 最少的那個(gè)。

做語法解析器錯(cuò)誤提示功能時(shí)，再次刷新了筆者三觀，原來我們以為的必然，在編譯器里對(duì)應(yīng)著那么多 “可能”。

當(dāng)我們遇到一個(gè)錯(cuò)誤 SQL 時(shí)，錯(cuò)誤原因往往不止一個(gè)，你可以隨便截取一段，說是從這一步開始就錯(cuò)了。語法解析器為了讓報(bào)錯(cuò)符合人們的第一直覺，對(duì)錯(cuò)誤信息做了 過濾，只保留剩余 Token 數(shù)最短的那條錯(cuò)誤信息。

討論地址是：精讀《手寫 SQL 編譯器 - 錯(cuò)誤提示》 · Issue #101 · dt-fe/weekly

如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。