題幹與適用場景
請設計一個解析算術表達式和變數宣告的小型解析器。輸入可能包含多個語法錯誤，但解析器仍需回報位置、繼續解析後續語句，並為 IDE 提供部分 AST。
題目考察詞法、語法、錯誤恢復和資料結構邊界。Bison 文件建議在同步點丟棄輸入並繼續解析；IDE 場景還要求錯誤節點、穩定範圍和不因首個錯誤終止整份輸入。
面試官考察點
候選人應先定義 token 和語法，再說明遞迴下降或 LR 方案；能否區分語法錯誤與詞法錯誤；能否選擇安全同步點、抑制級聯錯誤、保留部分 AST，並測試巢狀括號、缺少分隔符和未閉字串。
30 秒回答框架
「我把輸入分成 lexer、parser 和診斷層。Parser 維護 token 游標和來源範圍，遇到錯誤先記錄期望與實際 token，再跳到分號、右括號或檔案尾等同步點，插入 ErrorNode 後繼續。恢復期間抑制重複診斷，成功消費若干 token 後恢復回報。AST 節點保留缺失範圍，呼叫方可選擇嚴格或容錯模式。」
分步驟深入解答
第一步：定義 token 和語法
詞法器輸出種類、文字、起止偏移和行列號；識別識別字、數字、運算符、括號、分號和非法字元。語法明確優先級與結合性，避免把錯誤恢復散落到每個表達式函式。
第二步：選擇解析器結構
遞迴下降易讀，適合小語法；用 precedence climbing 處理表達式優先級。語法複雜時可用產生器和明確 error strategy。無論方式，都要讓 parser 查詢 lookahead、有限回退 token，並攜帶來源範圍。
第三步：分離詞法錯誤與語法錯誤
非法字元或未閉字串屬於詞法錯誤，lexer 應產生錯誤 token 並繼續掃描；缺少操作數、右括號或分號屬於語法錯誤，由 parser 按上下文回報。不要把所有問題都包成「Unexpected token」。
第四步：選擇同步點
語句級同步點通常是分號、右大括號或檔案尾；表達式內可同步到逗號、右括號或運算符邊界。跳過 token 時必須保證游標前進，否則同一錯誤會無限循環。
第五步：構造部分 AST
錯誤位置保留在節點範圍內；缺失子節點用 MissingNode，無法恢復的片段用 ErrorNode 包住原 token。下游格式化、語法高亮和補全應能處理這些節點，不能假設樹永遠完整。
第六步：抑制級聯診斷
一次恢復可能引發多個表面錯誤。記錄最近同步點和成功消費計數，在恢復後至少消費若干 token 再輸出下一條診斷；同時限制單一檔案錯誤數量，避免日誌和 UI 被淹沒。
第七步：支援增量解析
編輯器輸入變化時，只重解析受影響 token 區間和相鄰語法上下文，複用未變子樹。節點範圍和 token ID 要穩定，快取失效必須以父節點邊界和語法狀態為準，不能只按字元位置猜測。
第八步：測試與效能
測試正確輸入、單個錯誤、多個錯誤、巢狀錯誤、長字串和極大表達式。斷言錯誤位置、數量、AST 錯誤節點和終止條件；對長輸入測量線性掃描、遞迴深度、記憶體和最壞恢復成本。
設計取捨與邊界
嚴格失敗還是繼續解析
編譯器批次可在診斷後繼續以提升回饋；設定校驗可能在首個錯誤後立即拒絕。用模式開關控制，共享 lexer、token 和診斷結構，避免兩套實作漂移。
同步點多還是少
同步點多能縮短錯誤影響範圍，卻可能跳過可恢復 token；同步點少能保留上下文，卻容易產生級聯錯誤。依語句和分隔符設計，並用語料測試。
遞迴下降還是產生器
遞迴下降便於解釋和定制錯誤資訊；產生器適合大型穩定語法。錯誤恢復策略應是明確介面，不能依賴產生器預設行為而缺少測試。
失敗演練與演進計畫
缺少右括號
輸入下一條語句，確認 parser 在分號或檔案尾同步，輸出一條缺失括號錯誤並保留後續語句。
非法字元和未閉字串
確認 lexer 產生錯誤 token 後繼續到行尾或字串結束，parser 不因單一字元卡住。
連續錯誤風暴
構造每個 token 都非法的輸入，確認游標始終前進、錯誤數量受限且 CPU 不呈平方增長。
常見誤區與追問
誤區一：遇到第一個錯誤就返回 null
追問：IDE 如何繼續高亮和補全？應返回帶範圍的 ErrorNode 或 MissingNode。
誤區二：恢復時不推進游標
追問：如何證明不會在同一 token 無限循環？
誤區三：所有錯誤都在 parser 回報
追問：未閉字串和非法字元的診斷責任屬於 lexer 還是 parser？
誤區四：忽略級聯錯誤抑制
追問：一個缺分號為什麼不能印十條重複錯誤？
誤區五：增量解析只按字元偏移快取
追問：插入一個括號後，哪些父節點和語法狀態必須失效？
延伸追問與參考答案
為什麼要保留錯誤節點？
格式化、補全和高亮仍需要結構與範圍；錯誤節點讓下游顯式處理不完整輸入，而不是崩潰。
如何保證恢復終止？
每次恢復必須消費 token 或到達 EOF，並設定最大錯誤數和最大遞迴深度。
如何驗證錯誤品質？
用包含多個獨立錯誤的語料斷言位置、數量、後續 AST 和執行時間，不只測試第一個錯誤。