簡(jiǎn)介一份面向編譯原理課程設(shè)計(jì)的實(shí)現(xiàn)報(bào)告適合計(jì)算機(jī)專(zhuān)業(yè)本科生或需要在課設(shè)中完成編譯器前端模塊的讀者參考。內(nèi)容圍繞簡(jiǎn)單文法編譯器前端展開(kāi)涵蓋詞法分析、遞歸下降語(yǔ)法分析、語(yǔ)義分析、四元式中間代碼生成并擴(kuò)展了常量、數(shù)組、if-else 與 while 語(yǔ)句等文法同時(shí)簡(jiǎn)述后端目標(biāo)代碼生成流程可幫助理解從源碼到中間代碼的完整構(gòu)造思路。文中包含設(shè)計(jì)任務(wù)、總體流程、數(shù)據(jù)結(jié)構(gòu)與算法、程序流程圖、實(shí)驗(yàn)結(jié)果及結(jié)論等模塊并給出遞歸子程序調(diào)用?？煺张c四元式生成實(shí)例能直觀看到編譯過(guò)程的關(guān)鍵處理。資源為 1 個(gè) docx 文檔壓縮包約 381KB便于直接查閱或?qū)φ照n程設(shè)計(jì)要求修改復(fù)用該報(bào)告已有 693 人學(xué)習(xí)適合作為課程設(shè)計(jì)選題、報(bào)告結(jié)構(gòu)或代碼實(shí)現(xiàn)方面的參考樣例。1. 一個(gè)“簡(jiǎn)單”文法編譯器前端難點(diǎn)到底在哪很早之前A同學(xué)給我看他自己寫(xiě)的編譯器前端詞法分析器用正則硬掃語(yǔ)法分析器選了經(jīng)典的遞歸下降。代碼寫(xiě)得很規(guī)矩一跑卻出了怪事解析“12*3”這種三行表達(dá)式結(jié)果永遠(yuǎn)是把加法放在根節(jié)點(diǎn)乘法縮在右子樹(shù)里優(yōu)先級(jí)整個(gè)是反的。再試?yán)ㄌ?hào)程序直接棧溢出評(píng)論區(qū)一句“這是傳統(tǒng)的左遞歸問(wèn)題”把他晾在原地。這類(lèi)問(wèn)題在所謂“簡(jiǎn)單”的文法編譯器前端里特別常見(jiàn)。它看起來(lái)只有詞法、語(yǔ)法、抽象語(yǔ)法樹(shù)三段真動(dòng)手時(shí)坑全在“文法”與代碼的縫里左遞歸、公共前綴、優(yōu)先級(jí)分層、回溯、錯(cuò)誤定位哪一件不處理都跑不順。這篇筆記就按我實(shí)際搭一個(gè)最小前端時(shí)的順序來(lái)寫(xiě)先講模塊怎么切、文法怎么設(shè)計(jì)再給一個(gè)能運(yùn)行的遞歸下降實(shí)現(xiàn)最后盤(pán)點(diǎn)那些不看會(huì)翻車(chē)的邊角問(wèn)題。它不打算做完整語(yǔ)言的編譯器目標(biāo)是把“簡(jiǎn)單文法”的前端從能跑變成扛得住用適合正在學(xué)編譯原理的同學(xué)也適合要給自己的小語(yǔ)言快速搭前端的從業(yè)者。2. 先把前端流水線畫(huà)清楚詞法、語(yǔ)法與AST的職責(zé)與選型很多人一上來(lái)就寫(xiě)代碼結(jié)果詞法和語(yǔ)法的邊界反復(fù)改今天覺(jué)得數(shù)字識(shí)別該歸語(yǔ)法管明天又覺(jué)得括號(hào)匹配該在詞法里做。其實(shí)前端順序很固定源碼先進(jìn)詞法分析器產(chǎn)出 token 流token 流進(jìn)語(yǔ)法分析器按文法產(chǎn)生抽象語(yǔ)法樹(shù)AST。中間不需要第二個(gè)接口AST 就是前端交付給后端的唯一產(chǎn)品。把這條線畫(huà)清后面的大部分選擇都是順理成章的。2.1 詞法分析器手寫(xiě)掃描、正則庫(kù)還是自動(dòng)生成器詞法分析器的任務(wù)不是“看懂代碼”而是把字符串切成有類(lèi)型的 token。它一般只做四件事跳過(guò)空白和注釋、識(shí)別一個(gè)字面量數(shù)字、標(biāo)識(shí)符、識(shí)別一個(gè)符號(hào)、-、*、/、括號(hào)、分號(hào)以及記錄這個(gè) token 在源碼中的行號(hào)和列號(hào)。對(duì)于一個(gè) token 類(lèi)型保持在 20 個(gè)以?xún)?nèi)、不帶復(fù)雜字符串轉(zhuǎn)義的文法我通常直接手寫(xiě)一個(gè)掃描循環(huán)。理由有三第一線性掃描一個(gè)字符一個(gè)字符地推進(jìn)邏輯透明出錯(cuò)時(shí)用 debugger 跟一遍就能看出問(wèn)題第二報(bào)錯(cuò)信息可以精確到“第幾行第幾列的某個(gè)字符無(wú)法識(shí)別”這對(duì)后面的語(yǔ)法報(bào)錯(cuò)非常關(guān)鍵第三不需要維護(hù)任何生成配置改一個(gè) token 就是改幾行代碼的事。反過(guò)來(lái)如果哪天要支持多行字符串、嵌套注釋、模板字符串這類(lèi)狀態(tài)敏感的語(yǔ)法手寫(xiě)掃描會(huì)迅速變成狀態(tài)機(jī)地獄那時(shí)候用 flex 這類(lèi)自動(dòng)生成器或者成熟的詞法庫(kù)更劃算它們?cè)陂L(zhǎng)輸入和復(fù)雜狀態(tài)切換上已經(jīng)被大量驗(yàn)證過(guò)。也有一種中間做法在 Python、JS 這類(lèi)語(yǔ)言里用正則庫(kù)一條一條地匹配。它適合快速驗(yàn)證但有個(gè)硬傷——大部分正則庫(kù)默認(rèn)從當(dāng)前位置開(kāi)始匹配并返回第一個(gè)成功項(xiàng)順序?qū)懙蒙杂衅頸f和ifx就會(huì)被切錯(cuò)而且正則引擎的內(nèi)部回溯在遇到超長(zhǎng)輸入時(shí)很難控制。所以我自己的規(guī)則很簡(jiǎn)單演示可以工程上不推薦。2.2 語(yǔ)法分析器遞歸下降、LL(1) 表驅(qū)動(dòng)還是 LR 生成器語(yǔ)法分析器的選擇比詞法更影響開(kāi)發(fā)節(jié)奏。常見(jiàn)路線四條手寫(xiě)遞歸下降、LL(1) 表驅(qū)動(dòng)、LR(1)/LALR 生成器yacc/bison 這類(lèi)、以及 ANTLR 這種基于自適應(yīng) LL(*) 的生成器。我手頭這個(gè)“簡(jiǎn)單文法”項(xiàng)目默認(rèn)選手寫(xiě)遞歸下降因?yàn)樗臀姆ńY(jié)構(gòu)是一一對(duì)應(yīng)的文法里的一條產(chǎn)生式在代碼里就是一個(gè)函數(shù)產(chǎn)生式右側(cè)的每個(gè)符號(hào)就是函數(shù)里的一個(gè)調(diào)用或匹配動(dòng)作。這種對(duì)應(yīng)關(guān)系讓排查非常舒服——文法第 3 行有問(wèn)題直接去第 3 個(gè)函數(shù)里找狀態(tài)。表驅(qū)動(dòng)雖然也適合 LL(1)但那張預(yù)測(cè)分析表是二維的每次想加一條產(chǎn)生式得先重新算 FIRST 和 FOLLOW再翻表格心智負(fù)擔(dān)比遞歸下降大得多。LR 生成器能處理更大的文法集合可一旦出現(xiàn)沖突報(bào)錯(cuò)信息像天書(shū)對(duì)“簡(jiǎn)單”項(xiàng)目來(lái)說(shuō)屬于殺雞用牛刀還磨刀。那什么時(shí)候該換工具我的判斷標(biāo)準(zhǔn)是文法迭代速度。如果一周要改十幾次文法手寫(xiě)函數(shù)跟著改十幾次太累這時(shí)用 ANTLR 這類(lèi)生成器改完文法重新生成代碼反而效率最高。簡(jiǎn)單項(xiàng)目里更常見(jiàn)的情形是文法基本穩(wěn)定只需要在函數(shù)里不斷調(diào)整構(gòu)建 AST 的動(dòng)作遞歸下降依然是最舒服的姿勢(shì)。2.3 token 與 AST 的數(shù)據(jù)契約先定死再動(dòng)手前后端之間必須有一份穩(wěn)定的數(shù)據(jù)契約否則今天給 parser 一個(gè)字符串?dāng)?shù)組明天改成帶位置的字典接口每動(dòng)一次兩側(cè)的代碼全要跟著改。我一般把契約固定成兩個(gè)結(jié)構(gòu)。token 最小結(jié)構(gòu)是四元組kindtoken 類(lèi)型如NUM/PLUS/IDENT、value字面量原文或解析后的值、line、col。其中col我習(xí)慣記“該 token 起始字符的列號(hào)”而不是結(jié)束位置因?yàn)閳?bào)錯(cuò)要指出的是“從哪里開(kāi)始出錯(cuò)”。AST 節(jié)點(diǎn)最小結(jié)構(gòu)是三元組type節(jié)點(diǎn)類(lèi)型如binop/number/name、value可選保存運(yùn)算符或字面量值、children有序子節(jié)點(diǎn)列表。注意區(qū)分語(yǔ)法樹(shù)和 AST語(yǔ)法樹(shù)會(huì)保留每一個(gè)產(chǎn)生式的展開(kāi)痕跡包括很多冗余節(jié)點(diǎn)AST 則把括號(hào)、分隔符這類(lèi)純語(yǔ)法信息丟到結(jié)構(gòu)里比如(12)*3的括號(hào)在 AST 中根本沒(méi)有節(jié)點(diǎn)它的層級(jí)關(guān)系直接把“括號(hào)內(nèi)先算”表達(dá)掉了。后端的語(yǔ)義分析和代碼生成拿到的應(yīng)當(dāng)只是 AST而不是 token 流或語(yǔ)法樹(shù)這個(gè)約定越早定下來(lái)越好。3. 文法設(shè)計(jì)先行分層、消左遞歸與提左因子決定天花板我寫(xiě)前端的順序和大部分人相反先寫(xiě)文法再寫(xiě)代碼。文法不是寫(xiě)代碼之前的文檔它是前端的地基分層分不好后面代碼怎么寫(xiě)都別扭。上機(jī)驗(yàn)證過(guò)太多次文法設(shè)計(jì)階段省下的半小時(shí)會(huì)在調(diào)試階段用兩小時(shí)還回去。3.1 按運(yùn)算優(yōu)先級(jí)把文法分成三層以最常用的四則運(yùn)算表達(dá)式為例最簡(jiǎn)單的做法是把優(yōu)先級(jí)直接分層嵌入文法。標(biāo)準(zhǔn) EBNF 寫(xiě)法如下expr :: term (( | -) term)* ; term :: factor ((* | /) factor)* ; factor :: NUMBER | IDENT | ( expr ) ;這里的關(guān)鍵是“層”的順序優(yōu)先級(jí)最低的運(yùn)算符放在最外層優(yōu)先級(jí)最高的放在最底層解析factor作為原子單元要么是數(shù)字、變量要么是用括號(hào)包裹的整個(gè)表達(dá)式。expr處理加減時(shí)它的運(yùn)算對(duì)象是term而term已經(jīng)先把乘除算完了所以12*3解析出來(lái)一定是1 (2*3)的結(jié)構(gòu)。這個(gè)分層還被另一個(gè)事實(shí)反推著文法中每多一層遞歸下降代碼里就多一個(gè)函數(shù)。所以“簡(jiǎn)單”不是指層數(shù)少而是指每層只解決一件事。等你要往語(yǔ)言里加比較運(yùn)算、邏輯運(yùn)算時(shí)照這個(gè)模式繼續(xù)往上疊層or_expr包and_exprand_expr包equality_expr一層一個(gè)職責(zé)優(yōu)先級(jí)天然成立。3.2 左遞歸和公共前綴文法的兩處必改點(diǎn)教科書(shū)上寫(xiě)表達(dá)式文法常寫(xiě)成expr :: expr term這叫做直接左遞歸因?yàn)楫a(chǎn)生式左側(cè)的非終結(jié)符一開(kāi)頭又出現(xiàn)了自己。遞歸下降函數(shù)一旦照這個(gè)文法寫(xiě)解析第一個(gè) token 就會(huì)無(wú)限調(diào)用自身直到棧溢出。所以實(shí)現(xiàn)前必須把它改成右遞歸或 EBNF 循環(huán)式expr :: term expr_tail ; expr_tail :: ( term) expr_tail | ε ;這個(gè)改法保持了“加減是左結(jié)合”的語(yǔ)義同時(shí)讓遞歸下降在每一層只消耗一個(gè)運(yùn)算符再遞歸下降到尾部不會(huì)死循環(huán)。實(shí)際寫(xiě)代碼時(shí)expr_tail很少單獨(dú)做成函數(shù)而是直接用 while 循環(huán)代替這點(diǎn)下一章會(huì)看到。另一個(gè)必改點(diǎn)是公共前綴。比如文法里同時(shí)有if ( expr ) stmt和if ( expr ) stmt else stmt兩條產(chǎn)生式它們都以if ( expr ) stmt開(kāi)頭。如果照抄遞歸下降解析到if之后必須做出選擇但當(dāng)下根本沒(méi)有足夠信息判斷后面有沒(méi)有else只能往兩條路都試——這是回溯的根源。解決辦法是提取左因子stmt :: if ( expr ) stmt else_part ; else_part :: else stmt | ε ;把公共前綴提出來(lái)把“有沒(méi)有 else”這個(gè)決策推遲到else_part處處理。這樣解析器始終是單路徑的不用試錯(cuò)也不會(huì)有指數(shù)級(jí)回溯的隱患。3.3 優(yōu)先級(jí)靠文法分層結(jié)合性靠遞歸方向兩者別混這是新手最容易混的地方。優(yōu)先級(jí)解決的是“先算誰(shuí)”結(jié)合性解決的是“同優(yōu)先級(jí)時(shí)從左還是從右算”。expr :: term ((|-) term)*寫(xiě)成循環(huán)默認(rèn)是左結(jié)合因?yàn)槊孔x到一個(gè)運(yùn)算符就把左邊的結(jié)果和右邊的term合成新節(jié)點(diǎn)天然形成左深樹(shù)。如果需要一個(gè)右結(jié)合運(yùn)算符比如賦值或乘方^做法不是在這個(gè)循環(huán)里做特殊判斷而是單寫(xiě)一層右遞歸文法assign :: IDENT assign | expr ;這里assign右側(cè)又出現(xiàn)assign遞歸下降解析時(shí)會(huì)一直向右展開(kāi)形成右深樹(shù)。把“結(jié)合性”放到文法層代碼層就只管照著遞歸方向建節(jié)點(diǎn)兩者一一對(duì)應(yīng)調(diào)試時(shí)不至于為了一個(gè)運(yùn)算符寫(xiě)一堆 if 特例。我見(jiàn)過(guò)有人為了省錢(qián)在平鋪文法上用代碼手動(dòng)調(diào)整左右子樹(shù)結(jié)果打印 AST 一看有的節(jié)點(diǎn)前序?qū)τ械暮笮驅(qū)Ω?jié)點(diǎn)位置還隨輸入長(zhǎng)度變化最后整層返工。4. 手寫(xiě)遞歸下降落地可跑通的最小前端與關(guān)鍵參數(shù)到這一步文法已經(jīng)定了表達(dá)式語(yǔ)言支持?jǐn)?shù)字、變量、四則運(yùn)算、括號(hào)。下面給一個(gè)能直接運(yùn)行的最小實(shí)現(xiàn)按照上一章的文法分層來(lái)寫(xiě)。語(yǔ)言用 Python原因是結(jié)構(gòu)表達(dá)清晰、跑起來(lái)零依賴(lài)核心邏輯可以照搬到任何語(yǔ)言。4.1 詞法部分Token 定義與線性掃描器先定義 token 結(jié)構(gòu)和詞法分析器把行號(hào)、列號(hào)在掃描時(shí)記準(zhǔn)。class Token: def __init__(self, kind, value, line, col): self.kind kind # token 類(lèi)型NUM / IDENT / PLUS / MINUS / STAR / SLASH / LPAREN / RPAREN / EOF self.value value # 字面量原文例如 123、 self.line line # 起始行號(hào)從 1 開(kāi)始 self.col col # 起始列號(hào)從 1 開(kāi)始 class Lexer: def __init__(self, text): self.text text self.pos 0 # 當(dāng)前掃描位置指向下一個(gè)待處理字符 self.line 1 self.col 1 def _advance(self): ch self.text[self.pos] self.pos 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def peek(self, offset0): idx self.pos offset if idx len(self.text): return return self.text[idx] def next_token(self): while self.peek() and self.peek().isspace(): self._advance() if self.pos len(self.text): return Token(EOF, , self.line, self.col) line, col self.line, self.col ch self.peek() if ch.isdigit(): raw while self.peek().isdigit(): raw self._advance() return Token(NUM, raw, line, col) if ch.isalpha() or ch _: raw while self.peek().isalnum() or self.peek() _: raw self._advance() return Token(IDENT, raw, line, col) if ch in -*/(): op self._advance() kind_map {: PLUS, -: MINUS, *: STAR, /: SLASH, (: LPAREN, ): RPAREN} return Token(kind_map[op], op, line, col) raise SyntaxError(f第 {line} 行第 {col} 列出現(xiàn)無(wú)法識(shí)別的字符 {ch!r})這個(gè)掃描器的核心參數(shù)有兩個(gè)pos標(biāo)記字符消費(fèi)進(jìn)度line/col隨_advance維護(hù)。關(guān)鍵技巧是next_token里先把line, col存到局部變量再開(kāi)始消費(fèi)字符——因?yàn)開(kāi)advance會(huì)改掉這兩個(gè)值不提前保存所有 token 的位置都會(huì)變成結(jié)束位置。數(shù)字和標(biāo)識(shí)符都采用“讀到不再屬于本類(lèi)的字符為止”這就是最長(zhǎng)匹配的樸素實(shí)現(xiàn)。注意peek只做預(yù)讀不消費(fèi)所以數(shù)字掃描時(shí)不會(huì)把下一個(gè)字符吞掉。4.2 語(yǔ)法部分遞歸下降與 match 模式parser 層只維護(hù)一個(gè)前瞻 tokencurrent指向當(dāng)前正在處理的 tokenadvance消費(fèi)它并更新。match是統(tǒng)一入口類(lèi)型對(duì)得上就推進(jìn)對(duì)不上就拋出帶位置的語(yǔ)法錯(cuò)誤。class Parser: def __init__(self, lexer): self.lexer lexer self.current None self.advance() def advance(self): self.current self.lexer.next_token() return self.current def match(self, kind): if self.current.kind ! kind: raise SyntaxError( f第 {self.current.line} 行第 {self.current.col} 列 f期望 {kind}實(shí)際 {self.current.kind} ) return self.advance() def parse_expr(self): node self.parse_term() while self.current.kind in (PLUS, MINUS): op self.advance() right self.parse_term() node Node(binop, op.value, [node, right]) return node def parse_term(self): node self.parse_factor() while self.current.kind in (STAR, SLASH): op self.advance() right self.parse_factor() node Node(binop, op.value, [node, right]) return node def parse_factor(self): if self.current.kind NUM: tok self.advance() return Node(number, tok.value, []) if self.current.kind IDENT: tok self.advance() return Node(name, tok.value, []) if self.current.kind LPAREN: self.advance() node self.parse_expr() self.match(RPAREN) return node raise SyntaxError( f第 {self.current.line} 行第 {self.current.col} 列 f意外的 token {self.current.kind} )注意parse_expr里 while 循環(huán)是如何實(shí)現(xiàn)舊文法expr_tail的每遇到一個(gè)加減號(hào)就把已經(jīng)解析出的左節(jié)點(diǎn)和新的右節(jié)點(diǎn)合成binop。因?yàn)樾鹿?jié)點(diǎn)總把舊節(jié)點(diǎn)放在children[0]所以左結(jié)合語(yǔ)義被完整保留。parse_term同理只是把優(yōu)先級(jí)更低的運(yùn)算對(duì)象換成factor。這樣12*3解析時(shí)parse_expr第一次調(diào)parse_term后者先吃掉整個(gè)2*3加法節(jié)點(diǎn)自然掛在更外層。4.3 AST 節(jié)點(diǎn)與驗(yàn)證入口AST 節(jié)點(diǎn)僅需要type/value/children三個(gè)字段再加一個(gè)遞歸打印方法就夠了。驗(yàn)證入口建議直接打印樹(shù)形結(jié)構(gòu)而不是只輸出一個(gè)對(duì)象地址。class Node: def __init__(self, type, valueNone, childrenNone): self.type type self.value value self.children children if children is not None else [] def dump(self, indent0): line * indent f{self.type} if self.value is not None: line f {self.value} print(line) for child in self.children: child.dump(indent 1) def parse_source(text): lexer Lexer(text) parser Parser(lexer) ast parser.parse_expr() if parser.current.kind ! EOF: raise SyntaxError(f第 {parser.current.line} 行第 {parser.current.col} 列存在未消費(fèi)的 token) return ast代碼里最后一步檢查EOF經(jīng)常會(huì)被人漏掉。它的作用是保證整個(gè)輸入都被消費(fèi)完否則12 3這類(lèi)多個(gè)表達(dá)式連寫(xiě)的輸入會(huì)被靜默接受只解析出前半段。parse_source是外部唯一入口下游拿到的只應(yīng)是一個(gè)完整 AST。這套最小前端缺了語(yǔ)句層但如果要擴(kuò)展只需仿照expr加一個(gè)parse_stmt函數(shù)文法改三行代碼加三五行。5. 文法編譯器前端排查五個(gè)翻車(chē)場(chǎng)景與補(bǔ)救辦法前端跑不動(dòng)、結(jié)果不對(duì)絕大多數(shù)不是代碼寫(xiě)錯(cuò)而是文法與代碼的隱式約定被破壞。下面五條都是我在各種“簡(jiǎn)單”文法項(xiàng)目里真實(shí)踩過(guò)的坑每條按現(xiàn)象、原因、解決的順序拆開(kāi)方便對(duì)照排查。5.1 遞歸深入后棧溢出或卡死現(xiàn)象解析12時(shí)直接RecursionError或者程序看起來(lái)卡住不動(dòng)用調(diào)試器一看棧里全是同一個(gè)函數(shù)名。這個(gè)現(xiàn)象幾乎可以斷定是直接左遞歸漏網(wǎng)進(jìn)了代碼。原因文法寫(xiě)成expr :: expr term | term但遞歸下降的函數(shù)parse_expr第一行就調(diào)用了parse_exprtoken 還沒(méi)有被消費(fèi)每次調(diào)用都在原位置重進(jìn)。解決改文法把左遞歸改成循環(huán)式expr :: term ((|-) term)*代碼里用while而不是首行遞歸調(diào)用?？焖倥挪榉椒z查每個(gè) parse 函數(shù)的函數(shù)體確認(rèn)第一個(gè)遞歸調(diào)用之前至少消費(fèi)了一個(gè) token如果一個(gè)函數(shù)在沒(méi)有任何 token 消費(fèi)的情況下調(diào)用自己基本就是左遞歸的代碼化身。5.2 優(yōu)先級(jí)錯(cuò)亂AST 結(jié)構(gòu)不對(duì)現(xiàn)象解析12*3打印 AST 根節(jié)點(diǎn)是binop 沒(méi)錯(cuò)但右子樹(shù)居然也是binop 或者只有2乘號(hào)被掛在更下層解析(12)*3括號(hào)居然不起作用。原因絕大多數(shù)情況是文法分層沒(méi)做term和expr共用同一個(gè)層級(jí)或者 parse 函數(shù)里把、*放在同一個(gè) while 循環(huán)內(nèi)處理。解決回到第 3.1 節(jié)的文法逐層確認(rèn)expr - term、term - factor的調(diào)用鏈。AST 驗(yàn)證我用一個(gè)土辦法把1*23、12*3、(12)*3三組輸入并排打印肉眼檢查根節(jié)點(diǎn)和左右子樹(shù)的運(yùn)算符任何一組的根節(jié)點(diǎn)運(yùn)算符與預(yù)期優(yōu)先級(jí)不符就沿著調(diào)用的層數(shù)往上查。5.3 語(yǔ)法報(bào)錯(cuò)的位置永遠(yuǎn)指向行首或文件末尾現(xiàn)象錯(cuò)誤信息寫(xiě)“第 1 行第 1 列”或者明明在表達(dá)式中間出錯(cuò)位置卻指向整個(gè)輸入的末尾。原因Token 不帶位置信息或者詞法分析器在消費(fèi)完字符后才記錄line/col導(dǎo)致每個(gè) token 的位置都是結(jié)束位置又或者 parser 報(bào)錯(cuò)時(shí)拿的是advance之后的current。解決詞法層在next_token開(kāi)頭先把當(dāng)前l(fā)ine/col存下來(lái)帶著它構(gòu)造 Tokenparser 層在做假設(shè)時(shí)用當(dāng)前 token 的位置。注意一個(gè)隱蔽細(xì)節(jié)如果報(bào)錯(cuò)邏輯里先advance再取錯(cuò)誤位置位置會(huì)順移到下一個(gè) token所以匹配失敗要先取current.line/col再?zèng)Q定是否推進(jìn)。5.4 輸入稍長(zhǎng)就慢得不像線性現(xiàn)象解析一個(gè)幾百行的程序還能忍受到幾千行時(shí)肉眼可見(jiàn)地越跑越慢甚至出現(xiàn)指數(shù)級(jí)膨脹。原因解析器不是單路徑的它在某些決策點(diǎn)走了一條錯(cuò)路發(fā)現(xiàn)失敗再回頭如果公共前綴沒(méi)有提干凈比如if語(yǔ)句的兩個(gè)變體共用了大量前綴每次遇到if都要把整棵子樹(shù)嘗試兩遍復(fù)雜度直接炸開(kāi)。解決先做第 3.2 節(jié)的提取左因子把所有“先試 A 再試 B”的分支改成“讀完公共前綴再?zèng)Q策”。還有一個(gè)常見(jiàn)誤用在factor里先試著按數(shù)字解析失敗再按變量解析這種局部回溯其實(shí)無(wú)害因?yàn)橄牡氖遣煌?token 序列真正危險(xiǎn)的是兩個(gè)分支共享同一段 token 消耗那才是指數(shù)級(jí)的來(lái)源。排查時(shí)看 parse 函數(shù)里有沒(méi)有“嘗試性調(diào)用”有的話重點(diǎn)檢查兩個(gè)分支是否在同一 token 位置開(kāi)始。5.5 標(biāo)識(shí)符與關(guān)鍵字互相吞噬數(shù)字邊界切錯(cuò)現(xiàn)象把ifx識(shí)別成關(guān)鍵字或者123abc沒(méi)有報(bào)錯(cuò)而是拆成123和abc兩個(gè) token1.2.3這種非法數(shù)字也可能被部分接受。原因詞法分析器按順序匹配規(guī)則如果關(guān)鍵字正則排在標(biāo)識(shí)符前面任何以關(guān)鍵字開(kāi)頭的變量都會(huì)被吞數(shù)字掃描循環(huán)沒(méi)有判斷終止字符是否為字母或小數(shù)點(diǎn)。解決一類(lèi)修復(fù)路徑是“先識(shí)別完整標(biāo)識(shí)符再查關(guān)鍵字表”因?yàn)閕fx是完整標(biāo)識(shí)符不在表里自然不會(huì)被誤傷數(shù)字掃描則要求循環(huán)只在連續(xù)數(shù)字內(nèi)推進(jìn)遇到字母或第二個(gè)小數(shù)點(diǎn)立即結(jié)束并報(bào)錯(cuò)。邊界處理還有個(gè)參數(shù)可調(diào)是否允許數(shù)字后緊跟字母報(bào)錯(cuò)。我的習(xí)慣是報(bào)錯(cuò)因?yàn)?23abc幾乎一定是用戶(hù)漏寫(xiě)了運(yùn)算符靜默拆成兩個(gè) token 會(huì)把錯(cuò)誤埋到語(yǔ)法層導(dǎo)致報(bào)錯(cuò)信息看不懂。6. 讓前端更扛錯(cuò)錯(cuò)誤恢復(fù)、同步 token 與 AST 驗(yàn)證前端的價(jià)值不只體現(xiàn)在能解析合法代碼還體現(xiàn)在遇到非法代碼時(shí)能繼續(xù)報(bào)出更多錯(cuò)誤。一個(gè)錯(cuò)誤就停的解析器在長(zhǎng)文件上體驗(yàn)極差用戶(hù)修完第一個(gè)錯(cuò)還要再次編譯才知道第二個(gè)錯(cuò)在哪。所以我會(huì)在 parser 里加上最小限度的錯(cuò)誤恢復(fù)做法是經(jīng)典的 panic mode。所謂 panic mode就是在語(yǔ)法錯(cuò)誤發(fā)生后不停留在原地糾結(jié)而是跳過(guò)一批 token直到遇到一個(gè)“同步 token”再繼續(xù)解析。同步 token 的選擇要配合文法邊界語(yǔ)句結(jié)束的分號(hào)、右括號(hào)、EOF都適合。下面這段是expect的恢復(fù)版本可以替換基礎(chǔ)版match在語(yǔ)句層使用。SYNC_KINDS {SEMI, RPAREN, EOF} def expect(self, kind): if self.current.kind kind: return self.advance() self.errors.append( f第 {self.current.line} 行第 {self.current.col} 列 f期望 {kind}實(shí)際 {self.current.kind} ) while self.current.kind not in SYNC_KINDS: self.advance() return None注意這個(gè)版本只適合語(yǔ)句層的匹配不能用在表達(dá)式內(nèi)部。表達(dá)式里誤吃一個(gè)右括號(hào)后面整段結(jié)構(gòu)都會(huì)亂而語(yǔ)句層用分號(hào)同步能保證錯(cuò)誤后至少能繼續(xù)識(shí)別下一條語(yǔ)句。錯(cuò)誤恢復(fù)后的 AST 是不完整的下游做語(yǔ)義分析前必須檢查errors列表非空就只報(bào)錯(cuò)不繼續(xù)。我把錯(cuò)誤收集和 AST 構(gòu)建解耦就是為了避免“AST 缺了一截還拿去分析”的情況。驗(yàn)證方面除了第 4 章的 AST 打印我還會(huì)維護(hù)一組“用例對(duì)照表”每個(gè)用例保存預(yù)期根節(jié)點(diǎn)類(lèi)型和錯(cuò)誤數(shù)。正常用例檢查優(yōu)先級(jí)和結(jié)合性異常用例檢查報(bào)錯(cuò)位置是否精確。比如12*3期待根節(jié)點(diǎn)binop 12 3期待錯(cuò)誤且錯(cuò)誤位置指向3這類(lèi)表跑一遍勝過(guò)手動(dòng)點(diǎn)十次。最值得留意的驗(yàn)證是“改動(dòng)文法后回歸全表”因?yàn)榍岸烁囊惶幬姆ㄍ鶢窟B parser 函數(shù)和錯(cuò)誤位置不回歸很難發(fā)現(xiàn)某個(gè)角落里優(yōu)先級(jí)悄悄變了。這段路我走得不算順。最早做前端時(shí)我也是先寫(xiě)代碼再補(bǔ)文法結(jié)果一半時(shí)間花在追優(yōu)先級(jí)錯(cuò)亂和棧溢出的玄學(xué)問(wèn)題上后來(lái)改成“文法先行、代碼對(duì)照文法”同樣的功能只用一半時(shí)間落地報(bào)錯(cuò)還更準(zhǔn)。每當(dāng)有人拿著調(diào)試到崩潰的前端來(lái)找我我第一句問(wèn)的永遠(yuǎn)是“你的文法文件在哪”。先讓文法立住代碼才有資格談踩坑。希望這些場(chǎng)景能幫你在自己的前端里少繞幾個(gè)彎路。本文還有配套的精品資源點(diǎn)擊獲取