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