簡(jiǎn)介面向高校編譯原理課程學(xué)習(xí)者與實(shí)驗(yàn)開(kāi)發(fā)者這份資料圍繞教學(xué)型 PL/0 編譯程序的修改擴(kuò)充展開(kāi)可用于完成詞法分析、語(yǔ)法分析與語(yǔ)義處理等課程實(shí)驗(yàn)適合需要對(duì)照源碼理解編譯前端改造過(guò)程的學(xué)生。壓縮包共 24 個(gè)文件約 644KB包含 PL/0 的 cpp 與 h 源碼、實(shí)驗(yàn)報(bào)告文檔以及 dsp/dsw 工程配置、Debug 編譯產(chǎn)物和臨時(shí)文件便于直接打開(kāi)工程復(fù)現(xiàn)實(shí)驗(yàn)并核對(duì)輸出。內(nèi)容覆蓋保留字 ELSE、FOR、TO、DOWNTO、RETURN 的加入運(yùn)算符 、-、、-- 的擴(kuò)充不等號(hào)由 # 改為 以及條件語(yǔ)句 ELSE 子句的實(shí)現(xiàn)等要求可幫助讀者定位詞法表、語(yǔ)法規(guī)則與語(yǔ)義動(dòng)作的修改點(diǎn)。已有 790 人學(xué)習(xí)資源中的源碼、報(bào)告和工程文件可用于參考實(shí)驗(yàn)組織方式、檢查實(shí)現(xiàn)思路與整理實(shí)驗(yàn)文檔適合在課程設(shè)計(jì)或驗(yàn)收前查漏補(bǔ)缺。1. 一份 PL/0 實(shí)驗(yàn)包為什么卡人的總是保留字和 ELSEPL/0 的名聲是“小”十幾個(gè)保留字、幾個(gè)遞歸過(guò)程、百來(lái)行核心代碼看起來(lái)一天就能吃透。但某高校編譯原理課程的這份實(shí)驗(yàn)包真正讓人返工兩三輪的從來(lái)不是遞歸下降的主干而是兩件小活往保留字表里塞進(jìn)新詞之后標(biāo)識(shí)符識(shí)別突然對(duì)不上號(hào)把if-then擴(kuò)成帶 ELSE 語(yǔ)句的分支之后跳轉(zhuǎn)指令回填位置差一條指令運(yùn)行結(jié)果忽大忽小。這份實(shí)驗(yàn)包給的是能直接編譯運(yùn)行的 PL/0 骨架詞法掃描、語(yǔ)法分析、符號(hào)表管理和 P-code 解釋執(zhí)行四層齊全附帶若干示例程序適合剛學(xué)完語(yǔ)法分析、想在一個(gè)晚上跑通完整鏈路的人也適合需要交課程設(shè)計(jì)、想弄清楚“文法改一行、代碼改一片”到底該改在哪的讀者。下面按我拆包時(shí)實(shí)際動(dòng)手的順序記錄。2. 拆開(kāi) PL/0 實(shí)驗(yàn)包的骨架四個(gè)模塊的職責(zé)邊界與改動(dòng)點(diǎn)很多人拿到包第一件事是瞎翻代碼翻到statement()就開(kāi)始改改完之后發(fā)現(xiàn)編譯能過(guò)、運(yùn)行結(jié)果錯(cuò)再回頭懷疑解釋器。我的習(xí)慣是先畫(huà)一張職責(zé)邊界表把“誰(shuí)產(chǎn)生指令、誰(shuí)消費(fèi)指令、誰(shuí)只讀不寫(xiě)”釘死后面的每一次改動(dòng)都能落到具體文件上排錯(cuò)范圍立刻縮小一半。2.1 文件職責(zé)表先定位改動(dòng)點(diǎn)再動(dòng)手不同版本的實(shí)驗(yàn)包文件切分方式不完全一樣有的拆成六個(gè).c文件有的合成一個(gè)pl0.c但邏輯邊界是一致的。把邏輯模塊和物理文件對(duì)應(yīng)清楚再判斷擴(kuò)展 ELSE 語(yǔ)句需要觸碰哪幾處。邏輯模塊典型文件關(guān)鍵符號(hào)職責(zé)擴(kuò)展 ELSE 是否必改詞法lexer.cgetsym、ch、id、num跳空白、切標(biāo)識(shí)符/數(shù)字/界符、判保留字是新增else詞語(yǔ)法parser.cblock、statement、condition、expression遞歸下降邊解析邊調(diào)gen是if 分支要重寫(xiě)代碼生成codegen.cgen、cx、code[]輸出 P-code回填跳轉(zhuǎn)地址是新增一條JMP符號(hào)表symtab.ctable[]、btab[]、enter、position名字、層級(jí)、地址分配否解釋執(zhí)行interpret.cbase、interp、s[]按code[]逐條執(zhí)行否除非新增操作符公共頭pl0.hSYM_*、OPR_*、外置全局量常量與全局狀態(tài)是加SYM_ELSE表里“否”的那一行最值得注意符號(hào)表和解釋器在 ELSE 擴(kuò)展中完全不動(dòng)。這是 PL/0 結(jié)構(gòu)帶來(lái)的便利——ELSE 只是控制流不引入新作用域、不引入新類型、不需要新的運(yùn)行時(shí)原語(yǔ)。凡是有人告訴你“ELSE 要在解釋器里加分支”基本都是把JMP和JPC記混了這兩個(gè)操作碼在原始解釋器里本來(lái)就實(shí)現(xiàn)好了。提示改之前先把這份表抄進(jìn)實(shí)驗(yàn)報(bào)告評(píng)審時(shí)能直接說(shuō)明改動(dòng)范圍比事后回憶靠譜得多。2.2 詞法層保留字、標(biāo)識(shí)符、界符在一趟掃描里怎么分家PL/0 的詞法掃描是一趟式的getsym()被語(yǔ)法分析反復(fù)調(diào)用每次至少吃掉一個(gè)詞法單元。核心判定順序是固定的先跳空白再按首字符分三路——字母走標(biāo)識(shí)符/保留字?jǐn)?shù)字走無(wú)符號(hào)整數(shù)其余走界符表。第三路里最容易翻車的是雙字符界符:、、、必須先讀第二個(gè)字符再?zèng)Q定否則:會(huì)被單獨(dú)吐出去語(yǔ)法分析端立刻報(bào)“缺少:”。/* lexer.c —— getsym 主流程節(jié)選 */ void getsym(void) { while (ch || ch \t || ch \r || ch \n) getch(); /* 跳過(guò)空白注意不要吞掉 EOF */ if (isalpha(ch)) { /* 字母開(kāi)頭標(biāo)識(shí)符或保留字 */ int n 0; do { if (n ID_MAX - 1) id[n] ch; /* 超長(zhǎng)截?cái)嗟^續(xù)掃描 */ getch(); } while (isalnum(ch)); id[n] \0; sym lookup_kw(id); /* 命中返回保留字編號(hào)否則 SYM_IDENT */ } else if (isdigit(ch)) { /* 數(shù)字開(kāi)頭無(wú)符號(hào)整數(shù) */ num 0; do { num num * 10 (ch - 0); getch(); } while (isdigit(ch)); sym SYM_NUMBER; if (num NUM_MAX) error(31); /* 溢出要在詞法階段就攔住 */ } else if (ch :) { /* 雙字符界符必須先看第二個(gè)字符 */ getch(); if (ch ) { sym SYM_BECOMES; getch(); } else sym SYM_COLON; } else if (ch ) { getch(); if (ch ) { sym SYM_LEQ; getch(); } else if (ch ) { sym SYM_NEQ; getch(); } else sym SYM_LSS; } else { sym SYM_NULL; /* 非法字符交給上層報(bào)錯(cuò) */ getch(); } }幾個(gè)參數(shù)要交代清楚。ID_MAX是標(biāo)識(shí)符緩沖長(zhǎng)度一般取 32 就夠但循環(huán)里我用的是“超長(zhǎng)截?cái)嗟^續(xù)掃描”的寫(xiě)法——如果直接break剩余字符會(huì)被下一輪當(dāng)成新的標(biāo)識(shí)符錯(cuò)誤信息會(huì)指向一個(gè)根本不存在的名字排查時(shí)極其迷惑。NUM_MAX對(duì)應(yīng)目標(biāo)機(jī)整數(shù)上限標(biāo)準(zhǔn) PL/0 取 32767超了必須報(bào)錯(cuò)而不是靜默截?cái)喾駝t運(yùn)行期會(huì)得到一個(gè)莫名其妙的負(fù)數(shù)。lookup_kw是唯一與保留字表打交道的地方第 3 章會(huì)專門(mén)重寫(xiě)它。else這個(gè)詞加進(jìn)來(lái)之后詞法層面只需要?jiǎng)觾商幈Ａ糇直砝锛右粭l記錄pl0.h里加SYM_ELSE枚舉。但有個(gè)順序問(wèn)題——枚舉值一旦插入中間位置所有用數(shù)字硬編碼的地方都會(huì)錯(cuò)位。安全做法是把SYM_ELSE追加到枚舉尾部或者干脆全部用符號(hào)名不寫(xiě)數(shù)字。2.3 語(yǔ)法層表達(dá)式、語(yǔ)句、分程序的三級(jí)遞歸結(jié)構(gòu)PL/0 的語(yǔ)法分析是教科書(shū)式遞歸下降三層嵌套block處理分程序常量、變量、過(guò)程聲明 復(fù)合語(yǔ)句statement處理語(yǔ)句expression → term → factor處理表達(dá)式。三者的調(diào)用關(guān)系是單向的statement調(diào)expression求條件expression回頭不會(huì)調(diào)statement所以不存在相互遞歸的復(fù)雜度。原始版本的 if 語(yǔ)句處理邏輯很簡(jiǎn)短理解它是后面改 ELSE 的前提/* parser.c —— 原版 if 語(yǔ)句無(wú) else */ case SYM_IF: getsym(); condition(); /* 生成條件表達(dá)式代碼結(jié)果留在棧頂 */ if (sym SYM_THEN) getsym(); else error(16); /* 缺少 then */ { int jpc cx; /* 記住 JPC 指令在 code[] 中的下標(biāo) */ gen(JPC, 0, 0); /* 占位條件為假時(shí)跳轉(zhuǎn)地址待回填 */ statement(); /* then 分支 */ code[jpc].a cx; /* 回填跳到 then 分支之后 */ } break;cx是“下一條指令將寫(xiě)入的位置”也就是當(dāng)前代碼區(qū)指針gen(op, l, a)往code[cx]寫(xiě)指令然后cx。這里的關(guān)鍵動(dòng)作是“先占位、后回填”——gen的時(shí)候還不知道跳轉(zhuǎn)目標(biāo)在哪只能寫(xiě) 0等 then 分支編譯完cx正好指向分支之后的指令再把地址塞回去。這個(gè)模式會(huì)在 ELSE 擴(kuò)展里用兩次一次給JPC一次給JMP。真正容易忽略的是condition()之后棧的狀態(tài)條件表達(dá)式執(zhí)行完棧頂恰好有一個(gè) 0/1 值JPC的語(yǔ)義是“彈出棧頂為 0 則跳轉(zhuǎn)”。所以JPC必須緊跟在條件代碼之后中間不能插入任何其他指令。這一點(diǎn)決定了THEN之前不能做任何額外操作包括“為了調(diào)試打印點(diǎn)東西”——加一條gen就破壞棧平衡。2.4 符號(hào)表與運(yùn)行時(shí)棧為什么 ELSE 擴(kuò)展可以完全不碰它們符號(hào)表部分由table[]名字表和btab[]分程序表組成enter負(fù)責(zé)登記名字position負(fù)責(zé)在作用域鏈上查找。變量的地址不是絕對(duì)地址而是“層差 偏移”的二元組運(yùn)行時(shí)由base()沿著動(dòng)態(tài)鏈回溯到目標(biāo)層再加上偏移定位。ELSE 擴(kuò)展不涉及任何新名字、新作用域、新類型所以這兩個(gè)數(shù)據(jù)結(jié)構(gòu)一行都不用改。語(yǔ)法分析進(jìn)入statement時(shí)沒(méi)有enter調(diào)用level和dx保持不變btab里也不會(huì)多一條記錄。換句話說(shuō)if ... then ... else ...里的兩條分支共享同一個(gè)分程序上下文變量可見(jiàn)性完全一致這也是 Pascal 系語(yǔ)言的標(biāo)準(zhǔn)行為。運(yùn)行時(shí)棧同理。JMP和JPC在標(biāo)準(zhǔn)解釋器的switch里都有現(xiàn)成實(shí)現(xiàn)JPC彈棧判斷后修改pcJMP直接修改pc。只要回填的地址正確執(zhí)行流就正確。所以排查運(yùn)行結(jié)果異常時(shí)第一優(yōu)先級(jí)不是去讀interpret.c而是把code[]反匯編打出來(lái)逐條核對(duì)跳轉(zhuǎn)目標(biāo)。這個(gè)習(xí)慣我保持了很久能省掉大量猜測(cè)。3. 保留字識(shí)別改造從全表 strcmp 到分桶查表的落地保留字識(shí)別在實(shí)驗(yàn)包里通常是一個(gè)十行左右的小函數(shù)全表線性strcmp命中即返回。教學(xué)代碼這么寫(xiě)沒(méi)問(wèn)題但只要你往里加詞就會(huì)開(kāi)始暴露兩個(gè)問(wèn)題一是每次標(biāo)識(shí)符識(shí)別都要走完整張表程序里變量越多越虧二是新增保留字后如果忘了同步SYM_*枚舉編譯器會(huì)把else當(dāng)普通標(biāo)識(shí)符放過(guò)去語(yǔ)法分析端報(bào)出來(lái)的錯(cuò)誤位置完全對(duì)不上真實(shí)原因。第 3 章就是把這個(gè)函數(shù)重做一遍并把驗(yàn)證手段補(bǔ)齊。3.1 三種組織方式的對(duì)比與選型保留字表怎么存取決于你更在意哪一點(diǎn)改動(dòng)量、查找速度還是出錯(cuò)時(shí)的可診斷性。常見(jiàn)做法有三種我在不同場(chǎng)合都用過(guò)。方案平均比較次數(shù)改動(dòng)量主要風(fēng)險(xiǎn)適用場(chǎng)景線性數(shù)組 strcmp約 n/2n≈14 時(shí)約 7 次最小加一行即可詞越多越慢容易漏改枚舉課程實(shí)驗(yàn)原始形態(tài)按首字母/長(zhǎng)度分桶約 12 次中等需要建桶桶下標(biāo)算錯(cuò)導(dǎo)致漏查保留字 1540 個(gè)完美散列/查表1 次較大需要生成器生成表與源碼不同步工業(yè)級(jí)關(guān)鍵字集對(duì) PL/0 這種規(guī)模我一般選分桶比線性快一截比完美散列省事而且桶的構(gòu)造邏輯本身可以寫(xiě)在源碼里評(píng)審時(shí)一眼能看懂。關(guān)鍵點(diǎn)是桶的下標(biāo)必須由函數(shù)算不能靠手寫(xiě)常量——手寫(xiě)常量就是把“表”和“哈希函數(shù)”兩份真相分開(kāi)維護(hù)早晚不同步。3.2 用拉鏈法把保留字表掛進(jìn)桶里下面這段是可直接替換的版本靜態(tài)表kw_pool是唯一真相啟動(dòng)時(shí)由kw_init按哈希值掛鏈lookup_kw只做“算下標(biāo)、走鏈、比較”。/* lexer.c —— 分桶 拉鏈的保留字表 */ #define KW_BUCKET 16 #define KW_MAX 32 typedef struct { const char *name; int sym; /* 必須與 pl0.h 中的 SYM_* 枚舉嚴(yán)格一致 */ int next; /* 同桶內(nèi)下一條下標(biāo)-1 表示鏈尾 */ } kw_entry; static const kw_entry kw_pool[] { {begin, SYM_BEGIN}, {call, SYM_CALL}, {const, SYM_CONST}, {do, SYM_DO}, {else, SYM_ELSE}, {end, SYM_END}, {if, SYM_IF}, {odd, SYM_ODD}, {procedure, SYM_PROCEDURE}, {read, SYM_READ}, {then, SYM_THEN}, {var, SYM_VAR}, {while, SYM_WHILE}, {write, SYM_WRITE}, }; static kw_entry kw_tab[KW_MAX]; /* 運(yùn)行期副本next 字段會(huì)被改寫(xiě) */ static int kw_head[KW_BUCKET]; static int kw_cnt; /* FNV-1a 簡(jiǎn)化版位運(yùn)算夠快且不需要額外鏈接庫(kù) */ static unsigned kw_hash(const char *s) { unsigned h 2166136261u; while (*s) { h ^ (unsigned char)*s; h * 16777619u; } return h % KW_BUCKET; } void kw_init(void) { int i; kw_cnt (int)(sizeof(kw_pool) / sizeof(kw_pool[0])); if (kw_cnt KW_MAX) error(99); /* 表溢出編譯期就該攔 */ for (i 0; i KW_BUCKET; i) kw_head[i] -1; for (i 0; i kw_cnt; i) { unsigned b kw_hash(kw_pool[i].name); kw_tab[i] kw_pool[i]; kw_tab[i].next kw_head[b]; /* 頭插順序無(wú)所謂 */ kw_head[b] i; } } int lookup_kw(const char *name) { int i kw_head[kw_hash(name)]; while (i ! -1) { if (strcmp(kw_tab[i].name, name) 0) return kw_tab[i].sym; i kw_tab[i].next; } return SYM_IDENT; /* 未命中即普通標(biāo)識(shí)符 */ }邏輯上有三點(diǎn)需要說(shuō)明。第一kw_pool用const修飾把“源表”和“運(yùn)行期表”分開(kāi)kw_init只寫(xiě)kw_tab這樣即使某個(gè)環(huán)節(jié)把鏈表寫(xiě)壞了下次初始化依然能恢復(fù)正確狀態(tài)調(diào)試時(shí)少一個(gè)變量。第二kw_hash用的是 FNV-1a字符串短的時(shí)候性能差別不明顯但它分布均勻、實(shí)現(xiàn)只有三行比“首字母減 a 再取?！边@種寫(xiě)法穩(wěn)得多——后者在大小寫(xiě)混排或新增以數(shù)字結(jié)尾的詞時(shí)容易撞成一堆。第三頭插法意味著同桶內(nèi)的順序與聲明順序相反這無(wú)所謂因?yàn)椴檎抑魂P(guān)心命中與否。參數(shù)方面KW_BUCKET取 16 對(duì)應(yīng) 14 個(gè)保留字平均每桶不到一條比全表掃描少一個(gè)數(shù)量級(jí)的比較如果后續(xù)擴(kuò)展到 30 個(gè)以上把它改成 32 或 64 即可kw_hash里的取模會(huì)自動(dòng)跟隨不需要改其他地方。KW_MAX是硬上限比kw_pool實(shí)際條數(shù)大一些留余量一旦超了就在初始化階段報(bào)錯(cuò)而不是運(yùn)行時(shí)越界寫(xiě)內(nèi)存——這種錯(cuò)誤在實(shí)驗(yàn)環(huán)境里極難定位。lookup_kw的返回值直接決定getsym里sym的取值所以它的契約必須寫(xiě)死命中返回對(duì)應(yīng)保留字的SYM_*未命中返回SYM_IDENT絕不返回 0 或 -1。這一點(diǎn)在原始代碼里經(jīng)常被寫(xiě)成“未命中返回 0”一旦SYM_NULL恰好也是 0非法字符和普通標(biāo)識(shí)符就分不開(kāi)了。3.3 編譯期自檢一張覆蓋表把回歸擋住改完詞法最怕的是“看起來(lái)能用”。我一般會(huì)在實(shí)驗(yàn)包里加一個(gè)自檢入口把每個(gè)保留字單獨(dú)寫(xiě)成一個(gè)最小程序跑一遍確認(rèn)都能被正確識(shí)別再補(bǔ)幾個(gè)“長(zhǎng)得像保留字”的標(biāo)識(shí)符確認(rèn)不會(huì)被誤傷。# 逐個(gè)保留字走查每個(gè)詞拼一個(gè)最小可編譯片段 for kw in begin call const do else end if odd procedure read then var while write; do printf %s\n $kw /tmp/probe.pl0 ./pl0c /tmp/probe.pl0 /tmp/probe.out 21 grep -q SYM_$(echo $kw | tr a-z A-Z) /tmp/probe.out \ echo [OK] $kw \ || echo [FAIL] $kw - $(head -1 /tmp/probe.out) done這段腳本依賴編譯器帶一個(gè)-d之類的詞法調(diào)試開(kāi)關(guān)把每次getsym的結(jié)果打出來(lái)。如果沒(méi)有這個(gè)開(kāi)關(guān)就臨時(shí)在getsym返回前加一行打印驗(yàn)完再刪。腳本本身不復(fù)雜價(jià)值在于把“我記得改過(guò)”變成“每次都跑一遍”。緊接著要跑反向用例elsewhere、ifx、end1、do_2這類名字必須被識(shí)別為SYM_IDENT。原始線性表版本偶爾會(huì)在strncmp的長(zhǎng)度參數(shù)上寫(xiě)錯(cuò)導(dǎo)致前綴匹配——elsewhere被當(dāng)成else后面跟一個(gè)where報(bào)錯(cuò)位置飄到下一行這種 bug 靠讀代碼很難發(fā)現(xiàn)靠用例一秒鐘暴露。3.4 枚舉與表的同步機(jī)制最后一件事SYM_*枚舉和kw_pool的sym字段是兩份數(shù)據(jù)天然有不同步的風(fēng)險(xiǎn)。低成本的做法是在kw_init里加一次斷言式檢查——遍歷kw_pool確認(rèn)每個(gè)sym值都在合法區(qū)間內(nèi)且互不重復(fù)。重復(fù)檢測(cè)用一個(gè)位圖幾十行以內(nèi)解決。/* kw_init 末尾追加枚舉值唯一性檢查 */ static void kw_check(void) { static unsigned char seen[SYM_MAX]; int i; for (i 0; i kw_cnt; i) { int s kw_pool[i].sym; if (s SYM_NULL || s SYM_MAX) error(98); /* 越界 */ if (seen[s]) error(97); /* 重復(fù) */ seen[s] 1; } }這類自檢不是“為了規(guī)范”是實(shí)打?qū)嵤r(shí)間的。血淚經(jīng)驗(yàn)是插入新枚舉值到中間導(dǎo)致if和then的編號(hào)整體后移詞法層照舊返回舊編號(hào)語(yǔ)法層switch全部走空分支——編譯器不報(bào)錯(cuò)生成的代碼是空的運(yùn)行結(jié)果一切正常因?yàn)槭裁炊紱](méi)執(zhí)行。這種“靜默錯(cuò)”最難查加一次唯一性檢查就徹底堵死。4. ELSE 語(yǔ)句落地文法、遞歸下降、P-code 回填的三處聯(lián)動(dòng)ELSE 語(yǔ)句的擴(kuò)展是這個(gè)實(shí)驗(yàn)包里改動(dòng)鏈條最長(zhǎng)的一處文法要改、語(yǔ)法分析要改、代碼生成要多一條JMP三處任何一處不同步表現(xiàn)都是“能編譯、結(jié)果錯(cuò)”。我按依賴順序拆成四步走每一步都能單獨(dú)驗(yàn)證。4.1 文法改造與 FIRST/FOLLOW 快速自檢原始 if 語(yǔ)句的產(chǎn)生式只有一支改成兩支帶 else 和不帶 else之后必須確認(rèn)它不會(huì)和后續(xù)語(yǔ)句的首符集沖突。語(yǔ)句 :: 賦值語(yǔ)句 | 條件語(yǔ)句 | 循環(huán)語(yǔ)句 | 復(fù)合語(yǔ)句 | 讀語(yǔ)句 | 寫(xiě)語(yǔ)句 | ε 條件語(yǔ)句 :: if 子句 then 子句 [ else 子句 ] if 子句 :: IF 條件 then 子句 :: THEN 語(yǔ)句 else 子句 :: ELSE 語(yǔ)句用方括號(hào)表示可選而不是拆成兩條產(chǎn)生式是因?yàn)檫f歸下降實(shí)現(xiàn)里“可選”對(duì)應(yīng)的是if (sym SYM_ELSE)一次判斷拆成兩條反而要在入口處做回溯或者提取公因子。檢查點(diǎn)有兩個(gè)then 子句的 FOLLOW 集里含ELSE所以語(yǔ)句不能以ELSE開(kāi)頭——PL/0 的語(yǔ)句首符集里確實(shí)沒(méi)有ELSE這一條安全條件語(yǔ)句的 FOLLOW 集里含END、;、ELSE其中ELSE的出現(xiàn)正是“懸掛 else”的來(lái)源。4.2 遞歸下降里的懸掛 else 與向前看一個(gè)符號(hào)PL/0 的語(yǔ)法分析器只維護(hù)一個(gè)當(dāng)前符號(hào)sym沒(méi)有回溯。這在處理懸掛 else 時(shí)反而是優(yōu)勢(shì)statement()解析完 then 分支返回后sym恰好是緊隨其后的那個(gè)詞法單元如果是ELSE就歸當(dāng)前這個(gè)if如果不是就歸外層。這天然實(shí)現(xiàn)了“else 就近匹配”和 Pascal 的語(yǔ)義一致。/* parser.c —— if 語(yǔ)句含 else先占位后回填 */ case SYM_IF: { int jpc, jmp -1; getsym(); condition(); /* 結(jié)果 0/1 留在棧頂 */ jpc cx; gen(JPC, 0, 0); /* 條件為假 → 跳到 else 段起點(diǎn) */ if (sym SYM_THEN) getsym(); else error(16); statement(); /* then 分支sym 停在分支之后的符號(hào)上 */ if (sym SYM_ELSE) { jmp cx; gen(JMP, 0, 0); /* then 走完 → 跳過(guò) else 段 */ code[jpc].a cx; /* 回填JPC 落到 else 段第一條指令 */ getsym(); statement(); /* else 分支 */ } code[jpc].a (jmp 0) ? code[jpc].a : cx; /* 無(wú) else 時(shí) JPC 落到 if 之后 */ if (jmp 0) code[jmp].a cx; /* 回填JMP 落到 if 之后 */ break; }這段代碼里有三處細(xì)節(jié)值得展開(kāi)。第一jmp初始化為 -1 而不是 0因?yàn)?0 是合法的指令下標(biāo)用它當(dāng)“未設(shè)置”標(biāo)志會(huì)在 if 語(yǔ)句位于程序第一條指令時(shí)誤判。第二code[jpc].a在帶 else 和不帶 else 兩種情況下回填的值不同帶 else 時(shí)指向 else 分支起點(diǎn)不帶 else 時(shí)指向 if 之后——后者等價(jià)于“沒(méi)有要跳過(guò)的內(nèi)容”所以可以省略回填但顯式寫(xiě)出來(lái)更清楚。第三JMP的下標(biāo)必須在statement()之前就記下來(lái)因?yàn)?then 分支的編譯會(huì)推進(jìn)cx事后再想找位置就得靠搜索容易出錯(cuò)。關(guān)于懸掛 else還有一個(gè)容易踩的點(diǎn)如果 then 分支里嵌套了一個(gè)不帶 else 的 if內(nèi)層 if 會(huì)把外層想留給自己的ELSE搶走。這不是 bug是“就近匹配”的必然結(jié)果標(biāo)準(zhǔn) Pascal 也是這個(gè)行為。如果你的實(shí)驗(yàn)要求里明確寫(xiě)了“else 與最近的未匹配 if 配對(duì)”那這段代碼就是對(duì)的如果要求是“與外層配對(duì)”就必須在 then 分支里禁止裸 if 語(yǔ)句或者引入begin...end強(qiáng)制包裹。動(dòng)手前先確認(rèn)要求別寫(xiě)完才發(fā)現(xiàn)語(yǔ)義不對(duì)。4.3 目標(biāo)代碼生成JPC 與 JMP 的回填格式gen本身很樸素作用就是把四元組寫(xiě)進(jìn)code[]并推進(jìn)cx。真正決定正確性的是回填時(shí)機(jī)和地址語(yǔ)義。/* codegen.c —— 指令生成與地址回填 */ void gen(int op, int l, int a) { if (cx CODE_MAX) error(30); /* 代碼區(qū)溢出 */ code[cx].f op; /* 操作碼 */ code[cx].l l; /* 層級(jí)跳轉(zhuǎn)指令恒為 0 */ code[cx].a a; /* 目標(biāo)地址或立即數(shù) */ cx; }參數(shù)含義需要明確l對(duì)JMP/JPC沒(méi)有意義一律寫(xiě) 0a在LIT里是立即數(shù)在LOD/STO里是偏移在JMP/JPC里是絕對(duì)指令下標(biāo)。正因?yàn)閍的語(yǔ)義隨操作碼變化回填時(shí)最容易發(fā)生的錯(cuò)誤是“把 bx 的相對(duì)偏移寫(xiě)進(jìn)了 a”——JPC的a必須是絕對(duì)下標(biāo)解釋器執(zhí)行pc code[pc].a是直接賦值不做任何加法。一個(gè)完整的 if-else 結(jié)構(gòu)編譯出來(lái)應(yīng)該是這樣的形態(tài)用一組具體數(shù)字看得更清楚下標(biāo)指令含義10JPC 0 14條件為假跳到 14else 段1112...then 分支代碼13JMP 0 18then 結(jié)束跳過(guò) else 段1417...else 分支代碼18...if 語(yǔ)句之后的代碼這張表是我的排錯(cuò)模板。每次結(jié)果不對(duì)先把code[]打出來(lái)找JPC和JMP看它們的目標(biāo)下標(biāo)是不是恰好落在“else 段第一條”和“if 之后第一條”上。對(duì)不上就是回填次序錯(cuò)了對(duì)上了還錯(cuò)就是解釋器或者別的地方有問(wèn)題判斷路徑非常干脆。4.4 用對(duì)照程序驗(yàn)證跳轉(zhuǎn)鏈驗(yàn)證不能只跑一個(gè)“結(jié)果是 1”的用例必須覆蓋四條路徑條件真 有 else、條件假 有 else、條件真 無(wú) else、條件假 無(wú) else。下面這個(gè)程序一次跑完前兩條。{ test_else.pl0 —— 覆蓋 if-else 的兩條分支 } var a, b; begin a : 1; b : 0; if a 0 then b : 10 else b : 20; write(b); { 期望輸出 10 } if a 0 then b : 30 else b : 40; write(b) { 期望輸出 40 } end.兩個(gè)write的輸出必須分別是 10 和 40。如果第一個(gè)輸出 20說(shuō)明JPC的目標(biāo)指到了 else 段但條件判斷反了如果第一個(gè)輸出 10、第二個(gè)輸出 30說(shuō)明JMP沒(méi)生效then 分支執(zhí)行完直接掉進(jìn)了 else 段。這兩種現(xiàn)象對(duì)應(yīng)兩種不同的回填錯(cuò)誤靠輸出值就能把范圍鎖定到一行代碼。再把 else 分支換成嵌套 if確認(rèn)跳轉(zhuǎn)鏈沒(méi)有串位{ test_nest.pl0 —— else 分支里再嵌 if-else } var x, y; begin x : 2; y : 0; if x 1 then if x 5 then y : 1 else y : 2 else y : 3; write(y) { 就近匹配期望輸出 2 } end.這個(gè)用例的價(jià)值在于它會(huì)同時(shí)考驗(yàn)“就近匹配”和三層跳轉(zhuǎn)的回填。如果輸出 3說(shuō)明內(nèi)層 if 的 else 被外層搶走了語(yǔ)法分析的實(shí)現(xiàn)與預(yù)期語(yǔ)義不一致如果輸出 1說(shuō)明條件比較方向錯(cuò)了。跑通這四個(gè)用例ELSE 擴(kuò)展的代碼生成部分基本可以判定為正確。5. 避坑排查五條讓實(shí)驗(yàn)結(jié)果飄掉的細(xì)節(jié)下面五條是我在拆這類實(shí)驗(yàn)包時(shí)反復(fù)遇到的真實(shí)故障每條都按“現(xiàn)象 → 原因 → 解決”記錄可以直接當(dāng)排錯(cuò)清單用?，F(xiàn)象一加了else之后變量名elsewhere、else1報(bào)“非法符號(hào)”。原因多半是保留字判定用了前綴比較strncmp(id, else, 4)返回 0 就當(dāng)命中elsewhere被切成elsewhere。解決是把比較改成等長(zhǎng)判定strcmp或者“先比長(zhǎng)度再比內(nèi)容”并在反向用例里加上三五個(gè)以保留字為前綴的標(biāo)識(shí)符作為固定回歸項(xiàng)。現(xiàn)象二條件為真時(shí)走了 else 分支。先別懷疑JPC的實(shí)現(xiàn)九成是condition()生成的代碼把結(jié)果壓反了或者JPC被插在了條件代碼中間。檢查方法是看JPC是否緊跟在條件表達(dá)式的最后一條指令之后中間只要夾了一條LOD或OPR棧頂就不是條件值。這類錯(cuò)誤在嵌套表達(dá)式里特別隱蔽因?yàn)橥鈱涌雌饋?lái)完全正?！，F(xiàn)象三then 分支只有一條語(yǔ)句時(shí)正確有兩條就崩。原因通常是語(yǔ)句之間的分號(hào)處理。PL/0 的復(fù)合語(yǔ)句是begin 語(yǔ)句; 語(yǔ)句; ... end最后一個(gè)分號(hào)可有可無(wú)如果statement()里沒(méi)有正確吃掉分隔符第二條語(yǔ)句會(huì)被當(dāng)成新語(yǔ)句的開(kāi)始而cx已經(jīng)推進(jìn)回填位置整體偏移。解決是回到block的語(yǔ)句循環(huán)確認(rèn)“分號(hào)在語(yǔ)句之間、不在語(yǔ)句之后”的處理邏輯?，F(xiàn)象四JMP的目標(biāo)地址總是差 1。這是最經(jīng)典的回填錯(cuò)誤code[jmp].a cx寫(xiě)在了cx之前或之后的位置不對(duì)。cx的語(yǔ)義是“下一條待寫(xiě)指令的下標(biāo)”所以回填必須在“else 分支已經(jīng)編譯完、接下來(lái)要寫(xiě)下一條指令”的那一刻執(zhí)行。如果提前一條跳轉(zhuǎn)會(huì)落在 else 分支的最后一條指令上重復(fù)執(zhí)行一次如果晚一條會(huì)跳過(guò) if 之后的第一條語(yǔ)句。用 4.3 那張下標(biāo)表對(duì)照一眼能看出來(lái)。現(xiàn)象五詞法改了、語(yǔ)法改了編譯通過(guò)運(yùn)行時(shí)“什么都不做”。這是枚舉不同步的典型癥狀SYM_ELSE插在枚舉中間導(dǎo)致后續(xù)編號(hào)整體后移詞法層返回的是新編號(hào)而某個(gè)switch里還寫(xiě)著舊編號(hào)的case落到了default的空分支。解決是把枚舉值全部改成顯式賦值SYM_IF 20這種或者在kw_init里加唯一性檢查讓問(wèn)題在啟動(dòng)階段就暴露。這類“靜默錯(cuò)”比崩潰難查十倍值得多花十分鐘做防御。注意以上五條里前四條都能靠“打印code[]反匯編”快速定位第五條只能靠自檢。所以我在任何 PL/0 改造里都會(huì)保留一個(gè)-d編譯開(kāi)關(guān)輸出詞法單元序列和 P-code 清單驗(yàn)完再關(guān)掉。6. 進(jìn)階驗(yàn)證把 ELSE 擴(kuò)成 ELSIF 并跑通三段式檢查ELSE 跑通之后很多人會(huì)順手想加ELSIF。這件事的難度不在語(yǔ)法而在“少一層嵌套、多一次跳轉(zhuǎn)”的等價(jià)變換是否徹底。我的做法是先把else if手寫(xiě)成嵌套形式確認(rèn)語(yǔ)義基線再做詞法層面的合并。6.1 兩種 ELSIF 實(shí)現(xiàn)路徑的取舍路徑一是在詞法層把elsif當(dāng)成新保留字語(yǔ)法層新增一條產(chǎn)生式代碼生成時(shí)把它展開(kāi)成“else 分支里再套一個(gè) if”。路徑二是干脆不做新關(guān)鍵字只允許else if連寫(xiě)靠遞歸下降自然形成嵌套。后者零改動(dòng)前者能少一層JMP但要多維護(hù)一個(gè)保留字和一條產(chǎn)生式。維度新增elsif關(guān)鍵字復(fù)用else if嵌套詞法改動(dòng)加一條表項(xiàng) 一個(gè)枚舉無(wú)語(yǔ)法改動(dòng)新增產(chǎn)生式需處理懸掛無(wú)生成代碼少一條JMP每層多一條JMP出錯(cuò)風(fēng)險(xiǎn)枚舉同步、優(yōu)先級(jí)基本為零適用場(chǎng)景分支鏈超過(guò) 4 層分支鏈 23 層實(shí)驗(yàn)場(chǎng)景下我一般選第二條因?yàn)?PL/0 的程序規(guī)模小多幾條JMP對(duì)解釋執(zhí)行沒(méi)有可感知影響而少一處改動(dòng)就少一處可能出錯(cuò)的地方。真要練手第一條更有價(jià)值——它逼你重新走一遍第 3 章和第 4 章的全部流程。6.2 三段式檢查詞法、P-code、運(yùn)行結(jié)果缺一不可不管選哪條路驗(yàn)證都必須分三段做不能只看最終輸出。第一段查詞法把源程序喂給帶調(diào)試開(kāi)關(guān)的編譯器確認(rèn)每個(gè)else、elsif都返回正確的SYM_*elsewhere這類名字仍是SYM_IDENT。第二段查 P-code人工核對(duì)每個(gè)JPC和JMP的目標(biāo)下標(biāo)確保落在段邊界上用 4.3 那張表逐行比對(duì)。第三段才跑運(yùn)行結(jié)果并且至少覆蓋“全真”“全假”“真假交替”三種輸入。# 三段式檢查的落地腳本詞法 → P-code → 運(yùn)行 ./pl0c -d test_else.pl0 lex.log 21 # 第一段詞法單元序列 grep -c SYM_ELSE lex.log # 期望等于源文件里 else 的個(gè)數(shù) ./pl0c -p test_else.pl0 pcode.log 21 # 第二段P-code 反匯編 awk /JPC|JMP/ {print} pcode.log # 人工核對(duì)目標(biāo)下標(biāo) ./pl0vm pcode.log # 第三段解釋執(zhí)行腳本里的-d和-p需要自己在實(shí)驗(yàn)包里加加起來(lái)不到三十行但它把“憑感覺(jué)判斷對(duì)錯(cuò)”變成了“看數(shù)據(jù)判斷對(duì)錯(cuò)”。我吃過(guò)一次虧某個(gè)版本的JMP回填在“else 分支是空語(yǔ)句”時(shí)會(huì)指到下一條指令的中間輸出碰巧正確直到換了一個(gè)分支里有write的用例才暴露。從那以后我每次改完語(yǔ)法或代碼生成都強(qiáng)制走一遍這三段一段不過(guò)就不往下走。如果實(shí)驗(yàn)要求交報(bào)告這三段日志本身就是最好的材料詞法日志證明保留字改造生效P-code 日志證明跳轉(zhuǎn)鏈正確運(yùn)行輸出證明語(yǔ)義符合預(yù)期三樣?xùn)|西放一起比任何文字描述都有說(shuō)服力。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取