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