簡介這份資源是華中科技大學(xué)2019級(jí)編譯原理實(shí)驗(yàn)的源碼成果面向正在學(xué)習(xí)編譯原理、需要?jiǎng)邮謱?shí)現(xiàn)編譯器前端的高校學(xué)生與自學(xué)者尤其適合對(duì)照課程實(shí)驗(yàn)進(jìn)度進(jìn)行參考與二次開發(fā)。項(xiàng)目圍繞詞法分析、語法分析、符號(hào)表管理、靜態(tài)語義分析、中間代碼生成等核心環(huán)節(jié)展開并包含基于PL0語言的編譯器部分實(shí)現(xiàn)能夠處理基本PL0源代碼并生成虛擬機(jī)代碼雖只完成部分實(shí)驗(yàn)但已覆蓋編譯器前端的主要流程。壓縮包共19個(gè)文件以C語言源文件與頭文件為主輔以詞法/語法定義文件、Makefile構(gòu)建腳本、Markdown說明文檔及PDF語言定義資料整體約878KB結(jié)構(gòu)緊湊便于導(dǎo)入IDE閱讀調(diào)試。目前已有32人瀏覽學(xué)習(xí)適合作為課程實(shí)驗(yàn)的對(duì)照參考幫助理解AST構(gòu)建、語法錯(cuò)誤處理與符號(hào)表組織等關(guān)鍵實(shí)現(xiàn)思路。1. 編譯原理課設(shè)到底在做什么從一個(gè)壓縮包說起很多人第一次看到“基于編譯原理的課程設(shè)計(jì)項(xiàng)目”這類標(biāo)題第一反應(yīng)是“這不就是寫個(gè)詞法分析器嗎”。真動(dòng)手才發(fā)現(xiàn)一個(gè)完整的編譯原理課設(shè)通常包含詞法分析、語法分析、語義分析、中間代碼生成、目標(biāo)代碼生成這一整條鏈路任何一個(gè)環(huán)節(jié)沒打通后面的環(huán)節(jié)全是空中樓閣。這個(gè)壓縮包里的項(xiàng)目本質(zhì)上就是一套把源語言翻譯成目標(biāo)代碼的完整流水線適合正在上編譯原理課、需要交大作業(yè)的本科生也適合想通過一個(gè)真實(shí)項(xiàng)目把“龍書”里那些抽象概念落地的人。它解決的核心問題是讓你不再對(duì)著課本上的自動(dòng)機(jī)圖發(fā)呆而是真正跑通一條從源碼到結(jié)果的編譯鏈路。如果你正在為課設(shè)發(fā)愁或者想找一個(gè)能拆開看內(nèi)部結(jié)構(gòu)的編譯器實(shí)現(xiàn)這個(gè)方向值得投入時(shí)間。2. 先看清全貌編譯流水線的五個(gè)階段與選型邏輯2.1 為什么大多數(shù)課設(shè)選擇“類C語言”作為源語言在動(dòng)手拆代碼之前得先搞清楚這個(gè)項(xiàng)目在編譯什么。絕大多數(shù)編譯原理課設(shè)不會(huì)選擇完整的C語言或Java作為源語言原因很直接完整的工業(yè)級(jí)語言語法太龐大光是預(yù)處理指令和模板就能把課設(shè)周期撐爆。常見的做法是定義一個(gè)“類C語言”子集保留核心語法結(jié)構(gòu)——變量聲明、賦值、算術(shù)表達(dá)式、if-else、while循環(huán)、函數(shù)定義與調(diào)用、基本輸入輸出。這個(gè)子集足夠覆蓋編譯原理的所有核心知識(shí)點(diǎn)又不會(huì)讓語法分析器膨脹到無法維護(hù)。我一般會(huì)建議在選型階段就把源語言的文法用EBNF寫清楚貼在項(xiàng)目根目錄的README里。這一步看似多余實(shí)際上能省掉后面大量的扯皮。比如表達(dá)式優(yōu)先級(jí)如果文法里沒寫清楚語法分析階段就會(huì)出現(xiàn)“12*3”被解析成“(12)*3”的玄學(xué)問題。這個(gè)項(xiàng)目的文法定義通常放在parser目錄下的.y文件或者手寫遞歸下降的parser源碼里找到它整個(gè)項(xiàng)目的骨架就清楚了。2.2 詞法分析與語法分析的邊界在哪里一個(gè)常見的誤解是把詞法分析和語法分析混在一起寫結(jié)果代碼變成一團(tuán)亂麻。正確的做法是讓詞法分析器只負(fù)責(zé)把字符流切分成Token流每個(gè)Token帶上類型和值語法分析器只負(fù)責(zé)根據(jù)Token流和文法規(guī)則構(gòu)建抽象語法樹AST。兩者之間通過一個(gè)Token隊(duì)列解耦。看這個(gè)項(xiàng)目的結(jié)構(gòu)通常會(huì)有一個(gè)lexer模塊和一個(gè)parser模塊。lexer里最關(guān)鍵的是正則表達(dá)式到NFA到DFA的轉(zhuǎn)換邏輯或者直接用狀態(tài)機(jī)手寫。parser部分如果是遞歸下降每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)函數(shù)如果是用工具生成會(huì)有一個(gè).y或.l文件。判斷項(xiàng)目用的是哪種方式直接看有沒有Makefile里調(diào)用flex/bison的命令。# 查看項(xiàng)目構(gòu)建方式判斷是手寫還是工具生成 ls -la # 如果看到 .l 或 .y 文件說明用了flex/bison # 如果只有 .c/.cpp 和手寫的 lexer/parser說明是純手寫 find . -name *.l -o -name *.y -o -name *.lex -o -name *.yacc上面這段命令的作用是快速判斷項(xiàng)目的技術(shù)路線。如果找到.l/.y文件說明詞法/語法分析依賴flex和bison構(gòu)建時(shí)需要先安裝這兩個(gè)工具如果沒有說明是純手寫實(shí)現(xiàn)編譯時(shí)只需要常規(guī)的C/C工具鏈。參數(shù)上沒什么可調(diào)的關(guān)鍵是看Makefile里的依賴聲明。2.3 語義分析與中間代碼生成課設(shè)里最容易翻車的地方語義分析是很多課設(shè)的“黑匣子”——做得好的能查出變量未聲明、類型不匹配、函數(shù)參數(shù)個(gè)數(shù)不對(duì)做得差的直接跳過等到生成目標(biāo)代碼時(shí)才報(bào)錯(cuò)。這個(gè)項(xiàng)目通常會(huì)在AST遍歷階段做符號(hào)表管理和類型檢查。符號(hào)表一般用哈希表或棧式結(jié)構(gòu)實(shí)現(xiàn)作用域管理靠進(jìn)入/退出塊時(shí)壓棧彈棧。中間代碼生成常見的有三地址碼和四元式兩種形式。四元式更直觀格式是(op, arg1, arg2, result)適合后續(xù)做優(yōu)化。如果項(xiàng)目里有optimizer模塊那說明它還做了常量折疊、死代碼消除之類的簡單優(yōu)化。沒有優(yōu)化模塊也不影響正確性只是生成的代碼效率低一些。# 四元式生成的核心邏輯示意偽代碼幫助理解項(xiàng)目結(jié)構(gòu) # 遍歷AST節(jié)點(diǎn)遇到二元運(yùn)算就生成一條四元式 def gen_quad(node): if node.type BinaryOp: left gen_quad(node.left) # 遞歸處理左子樹 right gen_quad(node.right) # 遞歸處理右子樹 temp new_temp() # 申請(qǐng)臨時(shí)變量 emit(node.op, left, right, temp) # 生成四元式 return temp elif node.type Number: return node.value # 數(shù)字直接返回 elif node.type Identifier: return node.name # 變量返回名字這段邏輯說明的是中間代碼生成本質(zhì)上是AST的后序遍歷每個(gè)節(jié)點(diǎn)返回一個(gè)“地址”臨時(shí)變量名、變量名或常量父節(jié)點(diǎn)用子節(jié)點(diǎn)返回的地址來構(gòu)造自己的四元式。參數(shù)上需要注意的是臨時(shí)變量的命名策略常見的是t1、t2遞增避免和用戶變量沖突。如果項(xiàng)目里臨時(shí)變量命名和用戶變量重名那就是個(gè)隱藏的坑。3. 把項(xiàng)目跑起來環(huán)境配置與最小可運(yùn)行路徑3.1 依賴安裝與構(gòu)建命令的逐條拆解拿到壓縮包后第一步不是急著看代碼而是先讓它跑起來。編譯原理課設(shè)項(xiàng)目通常依賴以下工具鏈GCC或ClangC/C編譯器、Flex和Bison如果用了工具生成、Make構(gòu)建工具、Python如果項(xiàng)目里有腳本輔助。在Ubuntu或WSL環(huán)境下一條命令就能裝齊。# 安裝編譯原理課設(shè)常用工具鏈 sudo apt update sudo apt install -y build-essential flex bison make python3 # build-essential 包含gcc/g/make # flex 用于詞法分析器生成 # bison 用于語法分析器生成裝完依賴后進(jìn)入項(xiàng)目目錄先看README或Makefile里的構(gòu)建說明。如果沒有README直接嘗試make。常見的構(gòu)建失敗原因有三個(gè)一是flex/bison版本不兼容老項(xiàng)目可能用了舊版語法二是文件路徑大小寫問題Windows下不區(qū)分大小寫Linux下區(qū)分三是缺少某個(gè)頭文件或庫。# 嘗試構(gòu)建觀察報(bào)錯(cuò)信息 make 21 | tee build.log # 如果報(bào)錯(cuò)先看第一條錯(cuò)誤不要被后面的連鎖錯(cuò)誤干擾 head -50 build.log構(gòu)建成功后通常會(huì)生成一個(gè)可執(zhí)行文件名字可能是compiler、main或項(xiàng)目自定義的名字。用ls -la看最新生成的可執(zhí)行文件是哪個(gè)。然后找一個(gè)測(cè)試用例跑一下。項(xiàng)目里一般會(huì)有test或examples目錄里面放了示例源碼。# 運(yùn)行編譯器編譯一個(gè)測(cè)試用例 ./compiler test/example.c -o output # 如果編譯器輸出的是匯編代碼用gcc匯編并鏈接 gcc output.s -o output_exec ./output_exec這里的關(guān)鍵參數(shù)是輸入文件路徑和輸出選項(xiàng)。有些項(xiàng)目的編譯器直接輸出可執(zhí)行文件有些輸出匯編有些輸出四元式文本。看編譯器的usage信息就能確定。如果運(yùn)行時(shí)報(bào)“段錯(cuò)誤”大概率是語法分析或語義分析階段有空指針解引用需要回到代碼里加打印調(diào)試。3.2 用一個(gè)小例子驗(yàn)證整條鏈路是否打通構(gòu)建成功只是第一步真正要確認(rèn)的是編譯鏈路是否完整。我一般會(huì)寫一個(gè)最小測(cè)試用例覆蓋變量聲明、賦值、算術(shù)運(yùn)算和輸出。// test/minimal.c int main() { int a 3; int b 4; int c a b * 2; print(c); // 期望輸出 11 return 0; }用這個(gè)例子跑一遍如果輸出11說明詞法、語法、語義、代碼生成、運(yùn)行時(shí)都通了。如果輸出不是11就要逐階段排查。一個(gè)實(shí)用的技巧是在編譯器里加一個(gè)-dump-ast選項(xiàng)把AST打印出來看解析結(jié)果是否符合預(yù)期。如果項(xiàng)目沒有這個(gè)選項(xiàng)可以自己加就是在parser構(gòu)建完AST后加幾行打印代碼。# 如果項(xiàng)目支持中間代碼輸出查看四元式 ./compiler test/minimal.c --dump-quad # 期望看到類似 # (, a, b, t1) # (*, t1, 2, t2) # (, t2, -, c)四元式的順序和內(nèi)容能直接反映語義分析和中間代碼生成是否正確。如果四元式里出現(xiàn)了未定義的變量名說明符號(hào)表管理有問題如果運(yùn)算順序不對(duì)說明AST構(gòu)建時(shí)優(yōu)先級(jí)處理有誤。3.3 目標(biāo)代碼生成從中間代碼到可執(zhí)行結(jié)果的最后一公里目標(biāo)代碼生成階段通常有兩種選擇生成匯編代碼然后調(diào)用gcc匯編鏈接或者直接生成字節(jié)碼由虛擬機(jī)執(zhí)行。課設(shè)里更常見的是前者因?yàn)槟苤苯永孟到y(tǒng)工具鏈不用自己寫鏈接器。這個(gè)項(xiàng)目如果是生成x86匯編代碼里會(huì)有一個(gè)codegen模塊里面針對(duì)每種四元式操作生成對(duì)應(yīng)的匯編指令。# 目標(biāo)代碼生成示意四元式到x86匯編的映射 # (, a, b, t1) 對(duì)應(yīng) # mov eax, [a] # add eax, [b] # mov [t1], eax def gen_asm(quad): op, arg1, arg2, result quad if op : print(fmov eax, [{arg1}]) print(fadd eax, [{arg2}]) print(fmov [{result}], eax) elif op *: print(fmov eax, [{arg1}]) print(fimul eax, [{arg2}]) print(fmov [{result}], eax) # ... 其他操作類似這段邏輯說明的是目標(biāo)代碼生成就是把每條四元式翻譯成等價(jià)的匯編指令序列。參數(shù)上需要注意的是寄存器分配策略簡單項(xiàng)目直接用eax做累加器復(fù)雜項(xiàng)目會(huì)做寄存器分配優(yōu)化。如果生成的匯編跑起來結(jié)果不對(duì)先用gcc -S看編譯器自己生成的匯編作為參照對(duì)比差異。4. 避坑指南編譯原理課設(shè)里最容易踩的五個(gè)坑4.1 現(xiàn)象語法分析報(bào)“unexpected token”但Token明明是對(duì)的原因這種情況九成是文法沖突導(dǎo)致的。最常見的是表達(dá)式文法里的左遞歸沒有消除或者優(yōu)先級(jí)和結(jié)合性沒有在文法里聲明。比如E - E E | E * E | num這個(gè)文法有二義性bison會(huì)報(bào)沖突警告但很多人忽略警告直接跑結(jié)果解析出來的AST和預(yù)期不一致。解決在bison文件里用%left、%right聲明優(yōu)先級(jí)和結(jié)合性或者改寫文法消除左遞歸。如果是手寫遞歸下降確保每個(gè)二元運(yùn)算的解析函數(shù)正確處理了優(yōu)先級(jí)層次。4.2 現(xiàn)象語義分析階段報(bào)“變量未聲明”但變量明明在上一行定義了原因符號(hào)表的作用域管理有問題。常見的是進(jìn)入新塊時(shí)沒有創(chuàng)建新作用域或者退出塊時(shí)沒有正確彈出。另一個(gè)可能是符號(hào)表的查找邏輯只查了當(dāng)前作用域沒有遞歸查外層作用域。解決檢查符號(hào)表的push/pop邏輯確保每個(gè){對(duì)應(yīng)一次push每個(gè)}對(duì)應(yīng)一次pop。查找變量時(shí)從當(dāng)前作用域往外層逐層查找。如果項(xiàng)目用的是哈希表注意哈希沖突處理是否正確。4.3 現(xiàn)象生成的匯編代碼能編譯但運(yùn)行結(jié)果和預(yù)期差很多原因寄存器使用沖突。比如在計(jì)算一個(gè)復(fù)雜表達(dá)式時(shí)eax被中間結(jié)果占用但后續(xù)指令又覆蓋了eax導(dǎo)致前面的計(jì)算結(jié)果丟失。另一個(gè)常見原因是棧幀管理錯(cuò)誤函數(shù)調(diào)用時(shí)參數(shù)沒有正確傳遞或返回值沒有正確取出。解決在生成匯編時(shí)如果表達(dá)式嵌套超過一層用棧來保存中間結(jié)果而不是全部依賴寄存器。函數(shù)調(diào)用遵循cdecl或sysv調(diào)用約定參數(shù)從右到左入棧返回值放eax。4.4 現(xiàn)象編譯器自己編譯自己時(shí)崩潰自舉失敗原因如果項(xiàng)目嘗試自舉即用自己編譯自己那么任何微小的語義錯(cuò)誤都會(huì)被放大。常見的是某個(gè)語法特性在編譯器源碼里用了但編譯器本身還不支持這個(gè)特性導(dǎo)致解析自己的源碼時(shí)失敗。解決自舉前先用一個(gè)已知正確的編譯器如gcc編譯出第一版可執(zhí)行文件然后用這個(gè)可執(zhí)行文件去編譯編譯器源碼。如果失敗逐步縮小范圍找到編譯器不支持的那個(gè)語法特性先把它實(shí)現(xiàn)。4.5 現(xiàn)象測(cè)試用例在Windows下能跑在Linux下報(bào)錯(cuò)原因換行符差異\r\n vs \n導(dǎo)致詞法分析器把\r當(dāng)成非法字符。另一個(gè)可能是文件路徑分隔符差異Windows用反斜杠Linux用正斜杠。還有可能是編譯器對(duì)未初始化變量的處理不同。解決在詞法分析器的空白字符處理里同時(shí)接受\r和\n。文件路徑統(tǒng)一用正斜杠或者在代碼里做兼容處理。編譯時(shí)加上-Wall -Wextra打開所有警告把未初始化變量的問題暴露出來。5. 進(jìn)階技巧如何驗(yàn)證編譯器正確性并做簡單優(yōu)化5.1 用差分測(cè)試驗(yàn)證編譯器輸出差分測(cè)試是驗(yàn)證編譯器正確性最實(shí)用的方法。思路很簡單寫一個(gè)解釋器直接解釋執(zhí)行源語言再用編譯器把同樣的源碼編譯成可執(zhí)行文件兩者運(yùn)行結(jié)果對(duì)比如果一致說明編譯器在這個(gè)用例上是正確的。# 差分測(cè)試框架示意 import subprocess def run_interpreter(source_file): # 假設(shè)項(xiàng)目里有一個(gè)解釋器模式 result subprocess.run([./interpreter, source_file], capture_outputTrue) return result.stdout.strip() def run_compiled(source_file): # 先編譯再運(yùn)行 subprocess.run([./compiler, source_file, -o, temp_exec]) result subprocess.run([./temp_exec], capture_outputTrue) return result.stdout.strip() # 對(duì)一批測(cè)試用例做差分 for test in [test1.c, test2.c, test3.c]: interp_out run_interpreter(test) comp_out run_compiled(test) if interp_out ! comp_out: print(fDIFF FOUND in {test}: interp{interp_out}, comp{comp_out}) else: print(f{test} PASS)這個(gè)框架的關(guān)鍵在于解釋器的正確性。如果解釋器本身有bug差分測(cè)試就會(huì)誤報(bào)。所以解釋器要先用人工驗(yàn)證過的用例確認(rèn)正確。參數(shù)上測(cè)試用例要覆蓋邊界情況整數(shù)溢出、除零、空循環(huán)、遞歸深度大的函數(shù)調(diào)用。5.2 常量折疊與死代碼消除的最小實(shí)現(xiàn)常量折疊是在編譯期把23直接算成5減少運(yùn)行時(shí)計(jì)算。實(shí)現(xiàn)位置在中間代碼生成之后、目標(biāo)代碼生成之前。遍歷四元式序列如果發(fā)現(xiàn)兩個(gè)操作數(shù)都是常量就直接計(jì)算結(jié)果把四元式替換成賦值操作。# 常量折疊遍歷四元式合并常量運(yùn)算 def constant_folding(quads): folded [] for op, arg1, arg2, result in quads: # 判斷兩個(gè)操作數(shù)是否都是數(shù)字 if arg1.isdigit() and arg2.isdigit(): val eval(f{arg1} {op} {arg2}) # 簡單求值 folded.append((, str(val), -, result)) else: folded.append((op, arg1, arg2, result)) return folded死代碼消除是刪掉永遠(yuǎn)不會(huì)執(zhí)行的代碼比如if (0) { ... }里的內(nèi)容。實(shí)現(xiàn)上可以在AST階段就把條件為常量的分支剪掉或者在四元式階段刪除不可達(dá)的基本塊。這兩個(gè)優(yōu)化加起來代碼量不大但能讓課設(shè)的“優(yōu)化”部分有東西可寫。5.3 用AST可視化輔助調(diào)試調(diào)試編譯器時(shí)光看代碼很難定位問題。把AST打印成樹形結(jié)構(gòu)一眼就能看出解析是否正確。不需要復(fù)雜的圖形庫用縮進(jìn)打印就行。# AST樹形打印用縮進(jìn)表示層級(jí) def print_ast(node, indent0): prefix * indent if node.type BinaryOp: print(f{prefix}BinaryOp({node.op})) print_ast(node.left, indent 1) print_ast(node.right, indent 1) elif node.type Number: print(f{prefix}Number({node.value})) elif node.type Identifier: print(f{prefix}Identifier({node.name})) elif node.type Assign: print(f{prefix}Assign) print_ast(node.target, indent 1) print_ast(node.value, indent 1)這個(gè)打印函數(shù)在parser構(gòu)建完AST后調(diào)用一次輸出到文件或終端。對(duì)比預(yù)期結(jié)構(gòu)能快速發(fā)現(xiàn)優(yōu)先級(jí)錯(cuò)誤、結(jié)合性錯(cuò)誤、遺漏節(jié)點(diǎn)等問題。我一般會(huì)在每個(gè)測(cè)試用例跑完后自動(dòng)dump AST存成.txt文件方便回溯。5.4 一個(gè)我反復(fù)使用的調(diào)試習(xí)慣每次修改編譯器代碼后不要直接跑大測(cè)試用例。先跑最小用例確認(rèn)基本功能沒退化再跑完整測(cè)試集。這個(gè)習(xí)慣幫我省了很多時(shí)間——有一次改符號(hào)表查找邏輯大用例報(bào)了一堆錯(cuò)最小用例一跑就發(fā)現(xiàn)是變量查找時(shí)把全局作用域和局部作用域搞反了。如果直接看大用例的報(bào)錯(cuò)很容易被誤導(dǎo)到錯(cuò)誤的方向。編譯器開發(fā)就是這樣輸入和輸出之間的映射太復(fù)雜不用小步驗(yàn)證很容易在某個(gè)環(huán)節(jié)翻車。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取