簡介這是山東大學(xué)編譯原理課程PL/0編譯器實驗的完整實現(xiàn)面向計算機(jī)專業(yè)學(xué)生及編譯原理學(xué)習(xí)者覆蓋詞法分析、語法分析、語義分析與符號表建立等編譯器前端核心環(huán)節(jié)。壓縮包共94個文件、約513KB以C/C源碼、CMake構(gòu)建腳本、可執(zhí)行程序、實驗報告及多組測試輸入與運(yùn)行截圖為主要內(nèi)容便于對照工程結(jié)構(gòu)重新編譯和驗證結(jié)果。目前已有104人學(xué)習(xí)下載。資源除完整可運(yùn)行的PL/0編譯器外還包含模塊劃分清晰的工程組織、多組PL/0測試程序如素數(shù)、乘方、公約數(shù)計算及對應(yīng)截圖可直接用于課程設(shè)計參考、實驗報告撰寫和編譯原理備考復(fù)習(xí)。1. PL0-Compiler是什么把編譯原理課程實驗壓成一臺能跑的小編譯器第一次打開“PL0-Compiler 山東大學(xué)SDU編譯原理課程實驗”這個項目標(biāo)題時我差點(diǎn)把它當(dāng)成又一個普通的課程設(shè)計。真正動手之后才發(fā)現(xiàn)它要求你為一種叫 PL/0 的教學(xué)語言寫一個完整的小型編譯器從詞法分析到語法分析再到符號表、語義檢查、中間代碼生成最后還要有一個解釋器把程序跑起來。PL/0 本質(zhì)上是 Pascal 的極小核心子集只有常量、變量、過程、賦值、if、while、call 這些最基礎(chǔ)的語法單位但恰好把編譯原理課程里最該掌握的主干線全部覆蓋了。所以這篇筆記的服務(wù)對象很明確你要么是剛拿到 PL0-Compiler 實驗、不知道從哪下手要么已經(jīng)寫完一版但總在某幾個邊界用例上翻車。很多學(xué)校的編譯原理實驗都在 PL/0 上做或大或小的剪裁SDU 的版本也跳不出“語言說明 編譯器框架 解釋器”這個套路。下文我會按順序拆開詞法、語法、語義和代碼生成每一步都給出能直接抄的代碼和參數(shù)最后再把我踩過的幾個坑完整復(fù)述一遍。用 Java 來寫編譯原理實驗是最常見的選型對象化改造也順手這篇就默認(rèn)用 Java 落地。2. 詞法分析先從源文件榨出干凈的 Token 流PL0-Compiler 的地基詞法分析是整個 PL0-Compiler 里最先動手的部分也是很多初學(xué)者“看著簡單、寫起來全是暗坑”的地方。PL/0 的詞匯很少十幾個保留字、一個標(biāo)識符、一個整數(shù)、幾個運(yùn)算符和界符所以常見做法是只寫一個 getsym() 函數(shù)每次調(diào)用從源代碼里取出下一個 Token。這里有兩個決策會直接影響后面所有代碼Token 用什么結(jié)構(gòu)表達(dá)關(guān)鍵字怎么識別。2.1 Token 結(jié)構(gòu)設(shè)計枚舉、保留字表和行號定位我一般會用枚舉把單詞類型固定下來而不是用 int 常量手寫一堆 0/1/2。原因很簡單后面的遞歸下降解析器里到處要比較sym Kind.IF或者switch(sym)枚舉能讓錯誤消息和調(diào)試輸出自然可讀寫的時候還不會把 3 和 4 記混。public enum Kind { IDENT(標(biāo)識符), NUMBER(整數(shù)), CONST(const), VAR(var), PROCEDURE(procedure), BEGIN(begin), END(end), IF(if), THEN(then), ELSE(else), WHILE(while), DO(do), CALL(call), ODD(odd), ASSIGN(:), PLUS(), MINUS(-), TIMES(*), DIV(/), EQ(), NEQ(#), LT(), LE(), GT(), GE(), LPAREN((), RPAREN()), COMMA(,), SEMICOLON(;), PERIOD(.); final String label; Kind(String label) { this.label label; } }這段枚舉基本就是 PL/0 詞法范圍的全集。注意末尾的PERIOD對應(yīng)程序結(jié)束的“.”很多人會漏掉它結(jié)果語法分析在收尾時總是報“缺 .”。除了枚舉之外還需要一個 EOF表示文件讀完放在 Token 類型里比較合適。Token 本身我建議做成一個小類kind 表示詞性text 保留原始字符intVal 只對 NUMBER 有意義line 用來給后續(xù)報錯定位。public class Token { public Kind kind; public String text; public int intVal; public int line; }這樣一個 Token 對象從詞法階段傳到語法分析再傳進(jìn)符號表字符串只在最開始保留一份后面全程都用對象引用查錯了也知道該把錯誤定位到第幾行。2.2 getsym 主循環(huán)先收標(biāo)識符再查表收編關(guān)鍵字PL/0 的保留字不多但如果你寫成if word.equals(const) else if word.equals(var)這種長串一旦要加關(guān)鍵字或者調(diào)整大小寫策略函數(shù)會臭不可聞。編譯原理實驗里最穩(wěn)妥的做法是源程序里以字母開頭的連續(xù)串一律先當(dāng)作“可能是標(biāo)識符”來掃描然后查一個 Map查不到就是 IDENT查得到就改成對應(yīng)保留字。先定義保留字表private static final MapString, Kind KEYWORDS new HashMap(); static { KEYWORDS.put(const, Kind.CONST); KEYWORDS.put(var, Kind.VAR); KEYWORDS.put(procedure, Kind.PROCEDURE); KEYWORDS.put(begin, Kind.BEGIN); KEYWORDS.put(end, Kind.END); KEYWORDS.put(if, Kind.IF); KEYWORDS.put(then, Kind.THEN); KEYWORDS.put(else, Kind.ELSE); KEYWORDS.put(while, Kind.WHILE); KEYWORDS.put(do, Kind.DO); KEYWORDS.put(call, Kind.CALL); KEYWORDS.put(odd, Kind.ODD); }掃描主流程private void getsym() { skipSpaceAndComment(); if (pos source.length()) { token new Token(Kind.EOF, EOF, line); return; } char c source.charAt(pos); if (Character.isLetter(c)) { int start pos; while (pos source.length() (Character.isLetterOrDigit(source.charAt(pos)) || source.charAt(pos) _)) { pos; } String word source.substring(start, pos); Kind kind KEYWORDS.get(word.toLowerCase()); token new Token(kind null ? Kind.IDENT : kind, word, line); } else if (Character.isDigit(c)) { scanNumber(); } else { scanOperatorOrPunctuation(c); } }這段邏輯里我允許了標(biāo)識符中包含數(shù)字和下劃線這是很多課程實驗會給的小放寬。如果你拿到的文檔嚴(yán)格規(guī)定“標(biāo)識符只能以字母開頭后續(xù)只能是字母或數(shù)字”把_的分支去掉就行。大小寫策略也值得提前定好我做了toLowerCase()所以Begin和BEGIN都會被識別成 begin如果你們的實驗區(qū)分大小寫刪掉 toLowerCase 并且保證保留字表全小寫也可以。注意關(guān)鍵字識別采用“先當(dāng)標(biāo)識符掃再查表改判”的順序比邊掃描邊逐字符匹配要穩(wěn)得多。這樣標(biāo)識符和關(guān)鍵字共用同一套字符推進(jìn)邏輯少一個分支就少一類 bug。2.3 三個容易埋雷的邊界多字符符號、整數(shù)溢出、非法字符多字符符號是詞法階段最容易留坑的地方。PL/0 的不等號是#而不是!小于等于和大于等于分別是、賦值號是:。每次 getsym 只推進(jìn)一個字符所以遇到時必須看一眼下一個字符是不是是就合成一個 LE同時 pos 要推進(jìn)兩位漏掉這次 peek 的錯誤非常難查癥狀是x 2被解析成和兩個符號語法分析直接懵掉。數(shù)字掃描我建議用 long 做累加再判溢出不能等 int 已經(jīng)溢出之后再補(bǔ)救private void scanNumber() { int start pos; long v 0; while (pos source.length() Character.isDigit(source.charAt(pos))) { v v * 10 (source.charAt(pos) - 0); if (v Integer.MAX_VALUE) { error(ERR_NUM_TOO_LARGE, 整數(shù)溢出: source.substring(start, pos)); while (pos source.length() Character.isDigit(source.charAt(pos))) { pos; } token new Token(Kind.NUMBER, source.substring(start, pos), line); token.intVal 0; return; } pos; } token new Token(Kind.NUMBER, source.substring(start, pos), line); token.intVal (int) v; }判溢出時必須把剩余數(shù)字全部消費(fèi)掉否則一個大整數(shù)會被拆成兩段數(shù)字后面可能誤判成合法程序。非法字符的處理同理、^、$這類誰都不是的字符如果分支里只報錯不推進(jìn) pos下一輪 getsym 還會看到同一個字符輕則錯誤刷屏嚴(yán)重時直接死循環(huán)。正確做法是報錯之后pos繼續(xù)。注釋要不要支持一定要看實驗文檔。有的 PL/0 版本沿用 Wirth 原書的{ }注釋有的學(xué)校改成/* */有的是壓根不要求。如果要求支持我一般只做非嵌套的/* */private void skipSpaceAndComment() { while (pos source.length()) { if (Character.isWhitespace(source.charAt(pos))) { pos; } else if (source.charAt(pos) / pos 1 source.length() source.charAt(pos 1) *) { pos 2; while (pos 1 source.length() !(source.charAt(pos) * source.charAt(pos 1) /)) { pos; } pos 2; } else { break; } } }這段代碼的最大好處是空白和注釋可以交替出現(xiàn)中間不需要反復(fù)調(diào)用 getsym。缺點(diǎn)是注釋不閉合時 pos 會一路走到文件尾所以主流程里最好檢查一下pos是否已經(jīng)越界并報“注釋未閉合”。寫完詞法器我建議先跑一個臨時 main把源文件里的 Token 流打出來看一眼確認(rèn)無誤再往下寫語法分析public static void main(String[] args) { Lexer lexer new Lexer(begin x : 1 2; end.); Token t; while ((t lexer.next()).kind ! Kind.EOF) { System.out.printf(%d\t%s\t%s\t%d%n, t.line, t.kind, t.text, t.intVal); } }這一步能幫你把問題隔離在詞法階段。別急著往后寫Token 流不對后面所有解析結(jié)果都是空中樓閣。3. 語法分析用遞歸下降扣住 PL/0 文法表達(dá)式優(yōu)先級不再翻車詞法分析把源程序切成 Token 流之后語法分析負(fù)責(zé)按文法把這些 Token 組織成語法結(jié)構(gòu)。PL/0 的文法是經(jīng)典的自上而下文法常見做法是手寫遞歸下降一個非終結(jié)符對應(yīng)一個函數(shù)。它和 LL(1) 文法長得幾乎一樣手工實現(xiàn)也不需要額外的表驅(qū)動框架調(diào)試時還能直接看到調(diào)用鏈最適合作為編譯原理實驗的骨干。3.1 PL/0 的文法全貌先把 block 和 statement 遞歸關(guān)系畫清楚一份標(biāo)準(zhǔn)的 PL/0 文法可以縮寫成下面這套 BNFprogram block . block [constDecl] [varDecl] {procDecl} statement constDecl const ident number {, ident number} ; varDecl var ident {, ident} ; procDecl procedure ident ; block ; statement [ident : expression | call ident | begin statement {; statement} end | if condition then statement [else statement] | while condition do statement] condition odd expression | expression relop expression expression [|-] term {(|-) term} term factor {(*|/) factor} factor ident | number | ( expression ) relop | # | | | | 這套文法里有幾個地方值得先說破。block是絕對核心它同時處理常量聲明、變量聲明、過程聲明和一條語句而且過程聲明里又會遞歸調(diào)用block也就是說過程可以嵌套定義。statement的兩種寫法里if后面可以跟可選的elsebegin...end內(nèi)部是用分號分隔的語句序列最后一個分號可寫可不寫這里最容易產(chǎn)生多余的錯誤報錯。函數(shù)劃分不需要什么高深設(shè)計每個非終結(jié)符寫一個私有方法方法名直接叫block、statement、condition、expression、term、factor。程序結(jié)構(gòu)和文法一一對應(yīng)答辯的時候別人問哪段對應(yīng)哪條產(chǎn)生式你指一下方法名就行。private void block() { table.enterBlock(); int savedVarOffset currentVarOffset; if (sym Kind.CONST) { constDecl(); } if (sym Kind.VAR) { varDecl(); } while (sym Kind.PROCEDURE) { procDecl(); } statement(); currentVarOffset savedVarOffset; table.exitBlock(); }這里的currentVarOffset要格外小心。每個塊進(jìn)入時都從某個固定偏移開始給局部變量分配槽位但這個偏移不能一直累加否則不同塊的變量地址會互相踩踏。所以進(jìn)入 block 時保存舊值塊結(jié)束再恢復(fù)正是這段代碼里savedVarOffset的職責(zé)。3.2 expression/term/factor 的調(diào)用層級乘除為何排在加減下面表達(dá)式是語法分析里最好檢驗優(yōu)先級的地方。PL/0 的表達(dá)式定義成[加號|減號] term { (加號|減號) term }term 定義成factor { (乘號|除號) factor }factor 才是真正出現(xiàn)標(biāo)識符、整數(shù)和括號的那一層。這種分層結(jié)構(gòu)保證了乘除先算、加減后算括號通過遞歸回到 expression 實現(xiàn)。private void expression() { if (sym Kind.PLUS || sym Kind.MINUS) { boolean minus sym Kind.MINUS; getsym(); term(); if (minus) { gen(OPR, 0, OPR_NEGATIVE); } } else { term(); } while (sym Kind.PLUS || sym Kind.MINUS) { Kind op sym; getsym(); term(); if (op Kind.PLUS) { gen(OPR, 0, OPR_ADD); } else { gen(OPR, 0, OPR_SUB); } } }這段代碼先處理一元正負(fù)號再通過 while 循環(huán)把同層級的加減法運(yùn)算符全部消耗掉。如果沒有最前面的if (sym Kind.PLUS || sym Kind.MINUS)-x1就會被理解成“負(fù)號后面缺一個操作數(shù)”從而誤報語法錯誤。term 的結(jié)構(gòu)和 expression 幾乎一樣區(qū)別只是把因子換成低一層private void term() { factor(); while (sym Kind.TIMES || sym Kind.DIV) { Kind op sym; getsym(); factor(); if (op Kind.TIMES) { gen(OPR, 0, OPR_MUL); } else { gen(OPR, 0, OPR_DIV); } } }factor 是真正查符號表、生成 LIT 或 LOD 指令的地方private void factor() { if (sym Kind.IDENT) { Symbol s table.find(token.text); if (s null) { error(ERR_UNDEFINED, 未定義標(biāo)識符 token.text); } else if (s.kind() Kind.CONST) { gen(LIT, 0, s.val()); } else if (s.kind() Kind.VAR) { gen(LOD, levelDiff(myLevel, s.level()), s.addr()); } else { error(ERR_INVALID_EXPR, 過程名不能出現(xiàn)在表達(dá)式中 token.text); } getsym(); } else if (sym Kind.NUMBER) { gen(LIT, 0, token.intVal); getsym(); } else if (sym Kind.LPAREN) { getsym(); expression(); if (sym ! Kind.RPAREN) { error(ERR_RPAREN_EXPECTED, 缺少右括號); } else { getsym(); } } else { error(ERR_FACTOR_EXPECTED, 因子開始符號非法); getsym(); } }factor 里的getsym()必須放在每個分支的公共出口否則解析到非法因子時會原地重復(fù)處理同一個 Token遞歸下降立刻被打成死循環(huán)。寫完這三層拿12*3和(12)*3兩個用例分別驗證一個結(jié)果應(yīng)該對另一個應(yīng)該不對如果輸出反了多半是 expression 和 term 的層級倒掛了。3.3 test() 錯誤同步語法分析如何從第一個錯里活下來遞歸下降解析器遇到一個不期望的符號時如果只是簡單報錯并 return后續(xù)語句大概率會被連環(huán)誤報。經(jīng)典 PL/0 教材里的做法是寫一個test()函數(shù)它接收一個期望符號集合如果當(dāng)前符號不在集合里就報錯并向前同步直到找到集合中的某個符號為止。private void test(int[] expected, int errCode, String msg) { if (!inSet(expected)) { error(errCode, msg); do { getsym(); } while (!inSet(expected) sym ! Kind.EOF); } } private boolean inSet(int[] expected) { for (int s : expected) { if (s sym.ordinal()) { return true; } } return false; }這里的ordinal()是因為我用了枚舉類型如果你用 int 常量表示符號直接比較數(shù)字即可。調(diào)用方式就像這樣// 解析 statement 前先確認(rèn)當(dāng)前符號是語句合法的開頭 test(new int[]{Kind.IDENT.ordinal(), Kind.CALL.ordinal(), Kind.BEGIN.ordinal(), Kind.IF.ordinal(), Kind.WHILE.ordinal()}, ERR_STMT_EXPECTED, 語句開始符號非法);“同步”這個詞聽起來玄實際含義就是跳過那些既不屬于當(dāng)前集合、也不像錯誤終結(jié)符的 Token直到找到一段可以繼續(xù)分析的結(jié)構(gòu)邊界。比如begin x : ; end里面賦值號后面缺表達(dá)式expression 會報錯但同步到end后statement 還能繼續(xù)往下走不會把“end 后面缺分號”這種假錯誤也報出來。錯誤同步是答辯論時老師大概率會問的點(diǎn)它不追求報錯數(shù)量追求報錯質(zhì)量。4. 符號表與語義動作PL0-Compiler 的判斷力藏在這里語法分析只回答“這串 Token 合不合文法”但x : 1里的 x 到底有沒有定義、能不能給常量賦值、過程名能不能當(dāng)變量用這些必須靠符號表和語義檢查來回答。符號表就是編譯器的“業(yè)務(wù)現(xiàn)場”所有聲明信息、作用域關(guān)系、變量地址都要在這里落地。4.1 符號表設(shè)計按塊管理進(jìn)入和退出 block 時自動清理PL/0 支持過程嵌套所以符號表必須按塊劃分。常見做法是給每個符號記錄一個 blockId進(jìn)入塊時壓棧并遞增編號退出塊時把屬于當(dāng)前塊的符號全部彈出。public record Symbol(String name, Kind kind, int val, int level, int addr, int blockId) { } public class SymbolTable { private final ListSymbol symbols new ArrayList(); private int currentBlock; private final DequeInteger blockMarks new ArrayDeque(); public void enterBlock() { blockMarks.push(currentBlock); currentBlock; } public void exitBlock() { int mark blockMarks.pop(); while (!symbols.isEmpty() symbols.get(symbols.size() - 1).blockId() mark) { symbols.remove(symbols.size() - 1); } currentBlock blockMarks.peek(); } public Symbol find(String name) { for (int i symbols.size() - 1; i 0; i--) { Symbol s symbols.get(i); if (s.name().equals(name)) { return s; } } return null; } public boolean existsInCurrentBlock(String name) { for (Symbol s : symbols) { if (s.blockId() currentBlock s.name().equals(name)) { return true; } } return false; } }因為符號列表是從表尾開始查找的所以內(nèi)層聲明的同名符號總會被先找到這正好實現(xiàn)了內(nèi)層遮蔽外層的語義。退出內(nèi)層塊時符號被清理內(nèi)層名稱對外不可見外層名稱重新變回可見。Symbol用 Java record 寫很緊湊val 字段對常量才有意義addr 字段對變量和過程才有意義別在語義檢查里混淆它們。4.2 聲明處理與語義檢查查重、未定義變量、常量賦值攔截處理 const 聲明和 var 聲明時重復(fù)定義是最需要攔截的錯誤。判斷規(guī)則不是“全局唯一”而是“當(dāng)前塊內(nèi)不得重名”。private void constDecl() { getsym(); // 跳過 const do { if (sym ! Kind.IDENT) { error(ERR_IDENT_EXPECTED, 常量聲明缺少標(biāo)識符); return; } String name token.text; if (table.existsInCurrentBlock(name)) { error(ERR_DUP_DECL, 重復(fù)定義: name); } getsym(); if (sym ! Kind.EQ) { error(ERR_EQ_EXPECTED, 常量聲明缺少 ); getsym(); } else { getsym(); } if (sym ! Kind.NUMBER) { error(ERR_NUM_EXPECTED, 常量值必須是整數(shù)); return; } int val token.intVal; table.add(new Symbol(name, Kind.CONST, val, currentLevel, 0, currentBlock)); getsym(); } while (sym Kind.COMMA); if (sym ! Kind.SEMICOLON) { error(ERR_SEMI_EXPECTED, 常量聲明缺少分號); } else { getsym(); } }變量聲明類似只是不給值而是分配偏移量。給變量分配地址時記住一個原則過程符號不占用數(shù)據(jù)槽位常量符號也不占用只有 VAR 才會讓currentVarOffset遞增。PL/0 的棧式虛擬機(jī)里每個棧幀通常要留出三個固定槽給動態(tài)鏈、靜態(tài)鏈和返回地址所以局部變量從偏移 3 開始分配是常見約定。如果你沒有這三槽設(shè)計可以從 0 開始但要保證調(diào)用過程時棧幀布局和解釋器一致。賦值語句的語義檢查尤其要攔常量賦值private void assignment() { String name token.text; Symbol s table.find(name); if (s null) { error(ERR_UNDEFINED, 未定義變量: name); } else if (s.kind() Kind.CONST) { error(ERR_CONST_ASSIGN, 不能給常量賦值: name); } getsym(); if (sym ! Kind.ASSIGN) { error(ERR_ASSIGN_EXPECTED, 缺少賦值號 :); return; } getsym(); expression(); if (s ! null s.kind() Kind.VAR) { gen(STO, levelDiff(currentLevel, s.level()), s.addr()); } }如果變量未定義語法分析可以繼續(xù)但不應(yīng)生成 STO 指令如果變量其實是常量就更不能生成存儲指令。語義錯誤和代碼生成要分開這類“報錯但不再生成錯誤代碼”的處理是實驗評分里很容易被檢查的細(xì)節(jié)。4.3 中間代碼生成一個指令八條的表驅(qū)動虛擬機(jī)PL/0 不生成 x86 匯編而是生成一套精簡的中間指令再由解釋器執(zhí)行。我習(xí)慣用八條指令指令參數(shù)含義LITval整常數(shù)壓棧OPRop對棧頂做運(yùn)算LODlevel offset從指定層取變量壓棧STOlevel offset棧頂存入指定層變量CALlevel offset調(diào)用過程INTsize給當(dāng)前塊分配?？臻gJMPaddr無條件跳轉(zhuǎn)JPCaddr棧頂為假時跳轉(zhuǎn)OPR 的子操作碼屬于內(nèi)部約定你完全可以用自己的一套編號只需要保證生成器和解釋器一致。我常用0 返回、1 取負(fù)、2 加、3 減、4 乘、5 除、6 判斷奇數(shù)、7 到 12 是六個比較運(yùn)算、13 讀入、14 輸出。生成代碼時if 和 while 都要用“先留空地址生成完畢再回填”的 backpatch 技巧// if cond then stmt else stmt condition(); int jpc gen(JPC, 0, 0); // 條件為假時跳出 then 分支 statement(); if (sym Kind.ELSE) { int jmp gen(JMP, 0, 0); // then 分支執(zhí)行完要跳過 else patch(jpc, pc()); // 回填假跳轉(zhuǎn)到 else 的語句 getsym(); statement(); patch(jmp, pc()); // 回填跳過 else } else { patch(jpc, pc()); // 沒有 else 時跳到整個語句之后 }回填的位置差一行就會讓程序邏輯徹底變樣比如 if 的兩個分支都執(zhí)行或者 while 循環(huán)永遠(yuǎn)多跑一次。寫完之后把指令流打印出來逐條核對你會發(fā)現(xiàn)這套虛擬機(jī)對排錯非常友好。5. 避坑PL0-Compiler 調(diào)試中我反復(fù)踩的四個編譯原理實驗坑這門實驗最大的特點(diǎn)是代碼量不大但每類錯誤都藏在最不起眼的位置。下面四個問題是我在類似 PL0-Compiler 實現(xiàn)里見過最多、自己也踩過的坑全部按“現(xiàn)象 → 原因 → 解決”的順序?qū)憽?.1 詞法死循環(huán)非法字符被吞掉后 getsym 原地打轉(zhuǎn)現(xiàn)象給詞法器一個包含或者^的測試程序編譯進(jìn)程不退出CPU 卻跑滿有的實現(xiàn)則表現(xiàn)為錯誤消息洪流刷屏到幾乎停不下來。原因getsym 在 popup fallback 里識別不了這個字符只是報錯但沒有推進(jìn) pos。下一輪 getsym 還是讀同一個字符于是無限循環(huán)。有些代碼在錯誤分支里調(diào)用了自己卻沒在遞歸前先推進(jìn) pos效果同樣。解決非法字符分支里必須先pos再報錯保證每一次 getsym 調(diào)用最多只處理一個字符。詞法主函數(shù)里凡是能返回 Token 的分支都必須有明確的字符推進(jìn)動作。我在 2.3 節(jié)里把它寫在代碼注釋里就是因為它太容易漏。5.2 優(yōu)先級翻車12*3 算出 9term 層沒把 factor 包起來現(xiàn)象語法分析沒報錯解釋執(zhí)行的結(jié)果卻不對12*3輸出 9而不是 7。原因expression 里沒有調(diào)用 term而是直接調(diào)用了 factor或者 term 里沒有 while 循環(huán)只解析了一個因子就 return。遞歸下降的每層函數(shù)都對應(yīng)文法的每一層優(yōu)先級少一層就退化成完全左結(jié)合或右結(jié)合。解決嚴(yán)格按照expression → term → factor三層來寫。第一層處理加減第二層處理乘除第三層處理標(biāo)識符、數(shù)字和括號。調(diào)試時用12*3、(12)*3、-x1三個用例同時驗證任何一個不對都說明層級關(guān)系有誤。5.3 作用域污染內(nèi)層過程退出后同名變量仍然可見現(xiàn)象內(nèi)層過程聲明了一個和外層同名的變量返回外層后外層變量居然被內(nèi)層的那個同名變量遮蔽了更嚴(yán)重的是外層之后訪問這個變量時程序行為完全錯亂。原因符號表只做增加不做清理退出內(nèi)層塊時沒有把本塊符號彈出去。find 函數(shù)又總是從表尾往前查于是內(nèi)層符號一直“穿透”作用域屏障。解決用 4.1 節(jié)的 blockId 方案進(jìn)入塊時記 mark退出塊時按 mark 彈出本塊符號。寫完作用域測試用例后最好打印一份符號表觀察名字和 blockId 的對應(yīng)關(guān)系不要只靠運(yùn)行結(jié)果判斷。5.4 跳轉(zhuǎn)目標(biāo)差一行if/while 的 backpatch 算錯位置現(xiàn)象if 的 then 和 else 兩個分支同時執(zhí)行或者 while 循環(huán)多執(zhí)行一次、少執(zhí)行一次而詞法、語法、符號表都查不出問題。原因JPC 或 JMP 的后綴位置填錯了。常見做法是把回填時機(jī)放在 getsym 之后結(jié)果實際地址已經(jīng)比預(yù)期多跑了一段也有的是把“語句結(jié)束后的地址”當(dāng)成了“else 分支的地址”來填。解決把生成指令的 pc 值打印出來對照中間代碼人工走一遍。沒有 else 時JPC 應(yīng)跳到整個 if 語句之后有 else 時JPC 跳到 else 語句首條指令JMP 跳到整個語句之后。while 的回填目標(biāo)則是條件判斷指令之前形成一個向后循環(huán)的 JMP。注意不要迷信“程序跑通了就沒問題”。PL0-Compiler 這類實驗的評分點(diǎn)通常很細(xì)建議把中間代碼和符號表都保留成可打印狀態(tài)答辯時這些比嘴上講原理更能說明問題。6. 驗證 PL0-Compiler從最小用例集到自動化 diff 的收尾等到詞法、語法、語義和代碼生成都跑通之后最需要做的不是著急寫完整測試而是建立一套能反復(fù)執(zhí)行的回歸用例集。PL/0 語言小每個語法成分都不難測真正的風(fēng)險在于“改動一處帶來別處回退”這種問題只有靠自動化 diff 才抓得住。6.1 最小用例集每個語法成分都要有一個正例和一個反例我建議準(zhǔn)備這樣一個 cases 目錄每個.pl0文件對應(yīng)一個測試主題用例文件覆蓋點(diǎn)期望結(jié)果const.pl0常量聲明、常量引用輸出 3var_assign.pl0變量聲明、賦值輸出 2priority.pl012*3與(12)*37 和 9if_else.pl0if/else 分支分支選擇正確while.pl0循環(huán) 0 次和多次輸出累計結(jié)果nested_proc.pl0過程嵌套、作用域遮蔽內(nèi)外變量互不干擾err_dup.pl0重復(fù)定義編譯期報錯err_undef.pl0未定義標(biāo)識符編譯期報錯err_const_assign.pl0給常量賦值編譯期報錯每個用例文件旁邊放一個.out文件保存期望輸出。數(shù)量不用多但每個語法成分都必須覆蓋到“能跑”和“不能跑”兩個方向。反向用例的價值在于驗證編譯期的錯誤報告和退出碼而不是看解釋器執(zhí)行。6.2 自動化 diff把“好像能跑”變成“回歸全綠”在項目根目錄放一個run_tests.sh把每一個.pl0文件編譯后執(zhí)行再和期望輸出對拍#!/usr/bin/env bash if ! java -cp . com.sdu.pl0.Main $src real.out 21; then ... fi for src in cases/*.pl0; do base${src%.pl0} java -cp . PL0Compiler $src /dev/null real_${base}.out 21 if [ -f ${base}.out ]; then if ! diff -u ${base}.out real_${base}.out diff.log; then echo FAIL: $src cat diff.log exit 1 fi fi rm -f real_${base}.out done echo test all passed這段腳本的邏輯很簡單編譯產(chǎn)物和期望輸出做diff -u任何不一致都立刻失敗并打印現(xiàn)場。跑一次全綠才算這個頁面的最小可用版本真正穩(wěn)住了。后續(xù)不管改詞法、改語法還是加新指令集都要重跑一遍這個腳本而不是只手動試一兩個例子。6.3 一個看棧的底牌給解釋器加 trace 開關(guān)調(diào)試 PL/0 生成指令時最抓狂的情況是“我知道結(jié)果不對但不知道是哪一條指令開始不對”。給解釋器加一個全局布爾變量trace在每條指令執(zhí)行后打印當(dāng)前 pc、操作碼、操作數(shù)和棧頂內(nèi)容if (trace) { System.out.printf(pc%04d op%s level%d addr%d stackTop%d%n, pc - 1, opName(ins.op()), ins.level(), ins.addr(), stack.empty() ? Integer.MIN_VALUE : stack.peek()); }開 trace 之后把12*3的指令序列和手算結(jié)果逐條對照很快就能發(fā)現(xiàn)是1*2先算還是2*3先算。這個習(xí)慣我當(dāng)時一直保持到實驗結(jié)束先小用例開 trace 驗證指令序列再關(guān)掉 trace 跑完整測試套件兩者配合幾乎沒有排不掉的邏輯錯誤。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取