源碼解析：從詞法分析到語義檢查的完整實(shí)現(xiàn))
簡介吉林大學(xué)計算機(jī)學(xué)院2022年編譯原理課程設(shè)計項(xiàng)目是一份基于C實(shí)現(xiàn)的SNL語言編譯器完整方案面向需要完成同類課程設(shè)計或系統(tǒng)學(xué)習(xí)詞法分析、語法分析、語義分析的本科生。項(xiàng)目采用LL(1)分析法構(gòu)建語法解析配合詞法分析器、語義分析器與符號表管理代碼模塊劃分清晰且由作者獨(dú)立完成、相似性低適合直接借鑒或二次拓展。壓縮包共91個文件以cpp、h源文件為主體涵蓋詞法分析、LL(1)語法分析、語義分析等關(guān)鍵模塊另含obj、exe、pdb等編譯產(chǎn)物、Visual Studio工程文件以及多組txt測試用例與錯誤測試文本壓縮包整體142.28MB。內(nèi)容還涉及DS文法定義、保留字表、Token輸出與語義檢查用例工程配置完整便于構(gòu)建運(yùn)行和對照學(xué)習(xí)。已有1374人學(xué)習(xí)該資源對于希望獲得高分課程設(shè)計范例、深入理解編譯原理各階段實(shí)現(xiàn)的讀者具有較高的參考價值。1. SNL 語言編譯器課設(shè)源碼包為什么一個能拿滿績的參考值這個價某高校的編譯原理課程設(shè)計要求手寫一個 SNL 語言編譯器詞法、語法、語義三個階段全部真實(shí)跑通。SNL 是類 Pascal 的教學(xué)語言規(guī)模不大但保留字、算術(shù)表達(dá)式、函數(shù)調(diào)用、作用域和類型檢查一個不少。網(wǎng)上能翻到的參考要么是表達(dá)式計算器級別要么是公開倉庫里流傳爛大街的模板相似性高到不敢交。這份源碼包是 2022 年的完整交付C 編寫從 config 下的 reserved_words.txt 到 LexAnalyzer.cpp再到 LL1.cpp、ParseLL1.cpp、SemAnalyzer.cpp 和 symtable.h整條鏈路全在還自帶 lex_error_test、sem_error_test、sem_correct_test 三組測試樣本。它適合正在寫課設(shè)找不到語法樹接語義思路的人也適合已經(jīng)寫完詞法、卡在 LL(1) 遞歸下降的人。下面我按自己復(fù)現(xiàn)的順序把文件、參數(shù)和坑一個個過一遍。2. 從 main.cpp 到 SemAnalyzer先盤清源碼包的數(shù)據(jù)流2.1 文件清單哪些是核心代碼哪些是 Visual Studio 編譯殘留解壓后是一個標(biāo)準(zhǔn)的 Visual Studio 工程Project2.sln 可以直接雙擊打開。先把根目錄文件分個類避免一頭扎進(jìn) Debug 目錄里看那些 obj 和 pdb。文件/目錄定位說明main.cpp程序入口串聯(lián)詞法、語法、語義三個階段讀源文件并輸出結(jié)果config / reserved_words.txt詞法配置保留字表LexAnalyzer 運(yùn)行時加載LexAnalyzer.h / LexAnalyzer.cpp詞法分析器產(chǎn)出 Token 流輸出到 tokens.txt / new_tokens.txtLL1.h / LL1.cppLL(1) 集合與沖突檢測計算 First/Follow 或維護(hù)預(yù)測邏輯ParseLL1.h / ParseLL1.cpp語法分析器遞歸下降主程序按文法產(chǎn)生式構(gòu)建語法樹ds_grammer.h文法定義產(chǎn)生式、終結(jié)符/非終結(jié)符編號TreeNode.h / TreeNode.cpp語法樹節(jié)點(diǎn)孩子兄弟鏈表供語義分析遍歷Kind2Str.h / Kind2Str.cpp可讀化輸出把節(jié)點(diǎn)枚舉轉(zhuǎn)成字符串調(diào)試輸出靠它SemAnalyzer.h / SemAnalyzer.cpp語義分析器符號表查詢、類型檢查、作用域管理symtable.h / symtable.cpp符號表記錄變量/函數(shù)的名字、類型、層級、偏移量test1.txt ~ test8.txt輸入樣本混合覆蓋詞法、語法、語義的正確與錯誤用例lex_error_test / sem_error_test / sem_correct_test分類測試集分別用于驗(yàn)收詞法錯誤、語義錯誤和完全正確程序Debug 目錄下的 vc142.pdb、Project2.pdb、.obj、.tlog 全是 Visual Studio 的編譯殘留不影響理解邏輯。Project2.vcxproj.user 是用戶級配置換機(jī)器后建議直接刪掉讓 VS 重新生成。從 main.cpp 往下看標(biāo)準(zhǔn)數(shù)據(jù)流是讀入源文件 → LexAnalyzer 產(chǎn)出 Token 流 → ParseLL1 按文法組織語法樹 → SemAnalyzer 遍歷語法樹并查符號表 → 最后把結(jié)果打印到 rc.txt 或 outout.txt。tokens.txt 和 new_tokens.txt 同時存在說明詞法階段至少有兩種輸出模式常見的是普通 Token 流和帶行號位置的 Token 流。調(diào)試詞法錯誤時這兩個文件能直接告訴你錯誤發(fā)生在哪一行。2.2 詞法分析reserved_words.txt 與 LexAnalyzer.cpp 怎么配合很多人的詞法分析是把關(guān)鍵字硬編碼在幾十個 if-else 里這份資源把保留字單獨(dú)放在 reserved_words.txt代碼里用映射表查類型。下面這個加載函數(shù)是這類實(shí)現(xiàn)的標(biāo)準(zhǔn)骨架和你最后在 cpp 里看到的結(jié)構(gòu)基本一致void LoadReservedWords(const std::string path, std::unordered_mapstd::string, int kw) { std::ifstream in(path); std::string word; int kind 0; while (in word) { // 文件每行格式保留字 類型編號例如if 1 else 2 while 3 // 這里把字符串和編號分別讀進(jìn) word 和 kind in kw[word]; } }這段代碼的邏輯說明先用ifstream打開保留字文件然后以空白為分隔符連續(xù)讀。第一次in word拿到保留字本身第二次in kw[word]讀入后面的整數(shù)并直接作為映射值。unordered_map的選擇有講究詞法分析階段每個標(biāo)識符都要查一次表哈希查找能保證均攤 O(1)不會成為瓶頸。這樣組織的好處一是新增一個保留字只需要改 txt不需要動代碼二是不容易出現(xiàn)滿屏魔法數(shù)字查重時的代碼觀感也干凈很多。LexAnalyzer 里識別標(biāo)識符的邏輯就是逐字符拼遇到字母開頭就持續(xù)收集字母和數(shù)字拼完先查這個unordered_map查得到就是保留字查不到就是普通標(biāo)識符。Token 本身一般是struct Token { int type; std::string value; int line_no; };type 枚舉定義在 macro.h 或 LexAnalyzer.h 里。注意 reserved_words.txt 的編碼必須和源文件一致。最常見的坑是 UTF-8 帶 BOM導(dǎo)致第一個關(guān)鍵字額外多出一個不可見字符后面避坑章會專門講。2.3 語法樹TreeNode 的孩子兄弟鏈表與 Kind2Str 的可讀化輸出一段程序光有 Token 流不夠語義分析要在一個能表達(dá)嵌套結(jié)構(gòu)的樹上跑。TreeNode.cpp 用的是孩子兄弟表示法節(jié)點(diǎn)骨架長這樣struct TreeNode { int kind; // 節(jié)點(diǎn)類型對應(yīng) Kind2Str 里的枚舉名 TreeNode* child; // 第一個子節(jié)點(diǎn) TreeNode* sibling; // 右兄弟節(jié)點(diǎn) std::string value; // 標(biāo)識符名或字面量 int line_no; // 來源行號語義報錯全靠它 };為什么不用子節(jié)點(diǎn)數(shù)組因?yàn)?SNL 文法里 if 語句的子節(jié)點(diǎn)個數(shù)不固定有 else 是三個子節(jié)點(diǎn)沒有 else 是兩個用孩子兄弟鏈表可以動態(tài)掛節(jié)點(diǎn)遍歷函數(shù)統(tǒng)一走child和sibling兩條指針即可。Kind2Str.cpp 就是把 kind 整數(shù)映射成字符串比如某個節(jié)點(diǎn) kind 是 101打印出來是AddExpr比對輸出文件時一目了然。打印語法樹的遞歸函數(shù)一般長這樣void PrintTree(TreeNode* node, int depth) { while (node ! nullptr) { // 縮進(jìn)表示層級Kind2Str 負(fù)責(zé)把枚舉轉(zhuǎn)成可讀名 std::cout std::string(depth * 2, ) Kind2Str(node-kind) node-value std::endl; PrintTree(node-child, depth 1); node node-sibling; } }depth是當(dāng)前樹深度每次遞歸子節(jié)點(diǎn)時加一sibling在同一層橫向遍歷。main.cpp 遍歷語法樹后輸出到 rc.txt 或 outout.txt對照輸出文件就能驗(yàn)證遞歸下降函數(shù)的調(diào)用順序是否正確。3. 語法分析LL(1) 遞歸下降如何組織文法與預(yù)測3.1 為什么選 LL(1) 而不是 LR課設(shè)文法規(guī)模決定的取舍從文件命名能看出設(shè)計意圖LL1.h/cpp 帶著預(yù)測分析的味道ParseLL1.cpp 是實(shí)際的遞歸下降入口。SNL 這種課程語言文法一般就四五十條產(chǎn)生式用 LL(1) 手工寫一組遞歸下降函數(shù)完全可控。LR 系雖然能處理更多文法但要引入自動生成工具課設(shè)老師更希望你解釋清楚預(yù)測邏輯所以 LL(1) 是這類資源的主流選擇。LL1.cpp 通常負(fù)責(zé)計算 First/Follow 集合或者在建表過程中發(fā)現(xiàn)沖突時給出提示ParseLL1.cpp 按非終結(jié)符寫函數(shù)一個非終結(jié)符對應(yīng)一個 C 函數(shù)。ds_grammer.h 里的產(chǎn)生式就是這些函數(shù)的直接來源比如expr → term { (|-) term }對應(yīng)的就是下面這樣的函數(shù)。3.2 四則運(yùn)算表達(dá)式的遞歸下降一個可直接抄的結(jié)構(gòu)算術(shù)表達(dá)式是最典型的一層。下面的代碼是遞歸下降實(shí)現(xiàn)里必然會出現(xiàn)的結(jié)構(gòu)你會在 ParseLL1.cpp 里看到它的變體TreeNode* ParseExpr() { TreeNode* left ParseTerm(); // 先解析優(yōu)先級更高的項(xiàng) while (cur_token TOKEN_PLUS || cur_token TOKEN_MINUS) { TokenKind op cur_token; // 保存當(dāng)前運(yùn)算符 Match(cur_token); // 吃掉當(dāng)前運(yùn)算符 TreeNode* right ParseTerm(); // 解析右側(cè)操作數(shù) TreeNode* parent CreateNode(KIND_BIN_EXPR); parent-child left; // 左操作數(shù)掛到 child left-sibling right; // 右操作數(shù)掛到 sibling parent-value TokenToText(op); // 記錄運(yùn)算符文本 left parent; // 新節(jié)點(diǎn)作為左側(cè)繼續(xù)循環(huán) } return left; }邏輯說明ParseExpr先調(diào)ParseTerm因?yàn)槌顺齼?yōu)先級高于加減這步是文法層級決定的。while循環(huán)處理同優(yōu)先級運(yùn)算符的左結(jié)合每次構(gòu)造一個KIND_BIN_EXPR父節(jié)點(diǎn)把已有的left掛在child新解析出來的right掛在sibling。因?yàn)?TreeNode 是孩子兄弟結(jié)構(gòu)左操作數(shù)右操作數(shù)實(shí)際上是一條鏈而不是兩個獨(dú)立指針。這個循環(huán)不會產(chǎn)生左遞歸因?yàn)樗盐姆ɡ锏淖筮f歸改寫成了迭代。參數(shù)說明cur_token是全局當(dāng)前 TokenMatch斷言當(dāng)前 Token 類型等于參數(shù)并推進(jìn)到下一個。每個非終結(jié)符函數(shù)都必須在入口處至少調(diào)一次Match或NextToken否則可能死循環(huán)。3.3 if-else 懸空與同步恢復(fù)語法錯誤后還能繼續(xù)往下跑if 語句是另一個高頻踩坑點(diǎn)。LL(1) 遞歸下降處理 else 懸空靠的是前看一個 TokenTreeNode* ParseIfStmt() { Match(TOKEN_IF); TreeNode* cond ParseExpr(); // 條件表達(dá)式 Match(TOKEN_THEN); TreeNode* thenStmt ParseStmt(); // 必選分支 TreeNode* elseStmt nullptr; if (cur_token TOKEN_ELSE) { // 前看一個 Token 決定分支 Advance(); elseStmt ParseStmt(); // 可選分支 } Match(TOKEN_END); return BuildIfNode(cond, thenStmt, elseStmt); }邏輯說明解析完 then 分支后并不急著消費(fèi)TOKEN_ELSE而是看當(dāng)前 Token 是不是 else。是則額外解析一個語句不是則直接匹配END。這樣嵌套的 if-else 會自動就近配對不會出現(xiàn)懸空 else。注意這里ParseStmt的調(diào)用位置決定了遞歸深度遇到復(fù)雜嵌套時要確認(rèn)每個函數(shù)都在推進(jìn) Token。語法錯誤不能一遇到就停否則一個錯誤只報一行后面全被屏蔽。常見做法是同步恢復(fù)Match失敗時從出錯位置跳過 Token直到遇到分號、END、ELSE這類同步記號再重新嘗試。test1.txt、test2.txt 這類輸入里故意放了幾處缺分號或括號不匹配輸出能看出行號能報到哪里這就是同步恢復(fù)在起作用。調(diào)試時重點(diǎn)看 ParseLL1.cpp 里所有return false或主動Abort的地方錯誤信息通常會標(biāo)unexpected token at line N。4. 語義分析與符號表symtable 與 SemAnalyzer 如何完成作用域檢查4.1 符號表設(shè)計層級、類型、偏移量怎么填語義分析的核心是符號表和類型檢查。symtable.h 里的符號條目通常包含名字、類型、層級和偏移量。作用域是一個棧全局在最底層進(jìn)入函數(shù)壓一層進(jìn)入內(nèi)層塊再壓一層。SNL 里同名變量能不能重復(fù)聲明就看棧頂那一層有沒有同名條目。一個可用的符號表?xiàng)l目結(jié)構(gòu)長這樣struct Symbol { std::string name; // 變量名或函數(shù)名 int type; // 0int, 1boolean, 2array int level; // 0 是全局1 是第一個函數(shù)級 int offset; // 局部變量在棧幀里的偏移或數(shù)組長度 bool is_param; // 是形參就在函數(shù)入口登記 };符號表按層分組常見做法是std::vectorstd::vectorSymbol scopes。聲明變量時push_back到scopes[current_level]退出代碼塊時把整層pop_back。level字段不是必須的因?yàn)閺膕copes的下標(biāo)能推出來但保留它能讓調(diào)試信息更友好。4.2 聲明檢查和類型檢查落地一邊遍歷語法樹一邊查表語義分析從語法樹根節(jié)點(diǎn)開始遞歸下降和語法分析不同它不再消費(fèi) Token而是消費(fèi) TreeNode。賦值語句的類型檢查是一個典型例子void CheckAssign(TreeNode* node) { Symbol* left FindSymbol(node-child-value); // 左值查符號表 if (left nullptr) { SemError(variable %s not declared, node-child-value.c_str()); // 未聲明變量 return; } int rightType ExprType(node-child-sibling); // 遞歸求右式類型 if (left-type ! rightType) { SemError(type mismatch at line %d, node-line_no); } }邏輯說明FindSymbol從最內(nèi)層作用域向外層查因?yàn)閮?nèi)層同名變量會遮蔽外層。這和聲明重復(fù)檢查正好相反聲明查重只看當(dāng)前層類型檢查要看所有可見層。這兩個方向很容易搞反我的習(xí)慣是先讀懂函數(shù)名Find和CheckDecl分開寫不要把兩個語義混進(jìn)一個函數(shù)。數(shù)組下標(biāo)檢查是另一個加分點(diǎn)取 array 類型的長度比較下標(biāo)表達(dá)式是否越界。課設(shè)不要求運(yùn)行時求值但下標(biāo)是常量時可以當(dāng)場報越界這類實(shí)現(xiàn)會明顯提升代碼完成度。4.3 三組測試樣本為什么錯誤測試和正確測試同樣重要資源里的測試文件夾分三個這是最容易忽視的財富。lex_error_test 里是詞法錯誤樣本比如非法字符、未閉合注釋sem_error_test 是能過語法但過不了語義的樣本比如未聲明變量、類型不匹配sem_correct_test 是應(yīng)該完全通過的合法程序。拿到源碼后最好按順序跑判斷標(biāo)準(zhǔn)很明確正確樣本輸出不能有錯誤標(biāo)記錯誤樣本每個都要在正確的行號上報錯。如果你發(fā)現(xiàn)某個詞法錯誤樣本被語法分析攔截了說明詞法階段對非法字符沒有攔截干凈如果某個語義錯誤樣本到最后都沒有報錯說明 SemAnalyzer 的某個檢查分支根本沒被走到。三組樣本一起跑能驗(yàn)證編譯器不只是好路徑上不崩潰。5. 常見問題排查拿這份資源跑通時最容易翻車的五個點(diǎn)5.1 現(xiàn)象編譯成功但 Debug 目錄里沒有新生成的 Project2.exe按下 F7 編譯成功運(yùn)行卻發(fā)現(xiàn)跑的是舊 exe或者 Debug 目錄下根本沒有 exe。這個情況我遇到過不止一次。原因是工程被復(fù)制后.vcxproj 里的輸出目錄還指向原作者機(jī)器的絕對路徑比如D:\someone\Debug你編譯到別人目錄去了。解決方式很直接右鍵 Project2 屬性 → 常規(guī) → 輸出目錄改成$(SolutionDir)Debug\目標(biāo)文件名改成Project2.exe然后重新生成。改完后看輸出窗口的編譯日志確認(rèn)傳到的是你當(dāng)前工程的 Debug 目錄。5.2 現(xiàn)象源碼里明明有 if、while詞法分析卻全部識別成標(biāo)識符代碼里讀保留字表時第一個關(guān)鍵字永遠(yuǎn)匹配不上后面幾個正常。原因是 reserved_words.txt 用了 UTF-8 帶 BOM 編碼BOM 頭在文件開頭加了一個不可見字符導(dǎo)致第一個單詞讀出來是\xEF\xBB\xBFif和代碼里的if字符串不同。另一個常見變體是 Windows 行尾的\r沒去掉行末單詞多一個回車符。解決方式是用 Visual Studio 的文件 → 高級保存選項(xiàng)把 reserved_words.txt 改成 UTF-8 無 BOM同時養(yǎng)成習(xí)慣讀入每個單詞后做一次裁剪去掉非打印字符。從那以后我每次加載外部配置文件都會先打印一條調(diào)試信息看看第一個鍵到底是什么。5.3 現(xiàn)象語法分析跑到一半棧溢出或者直接死循環(huán)遞歸下降最常見的死循環(huán)來自左遞歸文法。比如你照著教科書寫expr → expr term函數(shù)里第一句又調(diào)ParseExpr自己Token 還沒消費(fèi)就無限遞歸下去棧很快爆掉。解決方式是把左遞歸改寫成迭代ParseExpr里先ParseTerm再用 while 循環(huán)吃掉和-這樣每個循環(huán)都會消耗一個 Token永遠(yuǎn)不會原地打轉(zhuǎn)。另外還有一種隱蔽情況某個非終結(jié)符函數(shù)里漏了Match連續(xù)調(diào)用同一個函數(shù)兩次卻沒有推進(jìn)cur_token。排查技巧很簡單在每個非終結(jié)符函數(shù)入口加一行斷點(diǎn)觀察cur_token的 type 有沒有變化沒變化的函數(shù)就是兇手。5.4 現(xiàn)象語義分析把內(nèi)層作用域的同名變量誤判成重復(fù)聲明內(nèi)層聲明了一個與外層同名的變量編譯器直接報重復(fù)聲明。原因是符號表沒有真正實(shí)現(xiàn)作用域棧進(jìn)函數(shù)前沒壓新層所有名字都堆在同一個全局表里。解決方式是把scopes.push_back({})放到函數(shù)入口退出前scopes.pop_back()。聲明查重只遍歷scopes.back()也就是當(dāng)前層查找符號則從back()往 0 方向遍歷。如果把這兩個方向?qū)懛淳蜁霈F(xiàn)外層變量找不到、內(nèi)層同名變量全報錯的情況。調(diào)試時可以在符號表每次 push/pop 時打印當(dāng)前作用域大小一眼就能看出棧有沒有正常退層。5.5 現(xiàn)象用新版 Visual Studio 打開工程提示 v142 工具集未安裝Debug 目錄里的 vc142.pdb 已經(jīng)暴露了工程生成環(huán)境v142 是 Visual Studio 2019 的工具集。如果你用 VS2022 直接打開會提示找不到 v142 生成工具編譯直接失敗。解決方式有三個任選其一裝 VS2019 的生成工具在項(xiàng)目屬性 → 常規(guī) → 平臺工具集里改成 v143也就是 VS2022 自帶工具集或者直接改 .vcxproj 文件里的PlatformToolsetv142/PlatformToolset為v143再重新加載工程。順手檢查一下 Windows SDK 版本如果機(jī)器上只有新 SDK把屬性里的 SDK 版本改成已安裝的那個別讓它自動選擇錯誤的版本。6. 最后一關(guān)用三組測試樣本把自己的交付變成證據(jù)分享一個能讓編譯器課設(shè)少走彎路的驗(yàn)收習(xí)慣。拿到這份資源后我先把 main.cpp 里默認(rèn)讀取的文件名改成從命令行參數(shù)讀取然后寫一個腳本把三組測試樣本全部跑一遍而不是在 IDE 里手動一個個改文件名。這個改動很小收益卻很直接它可以自動跑完幾十個樣本并用文件對比工具檢查輸出。# 以 test5.txt 為輸入把結(jié)果寫到 out5.txt Project2.exe test5.txt out5.txt # 用 fc 對比實(shí)際輸出與期望輸出 fc out5.txt expected5.txt跑完后的檢查清單我每次都會過一遍lex_error_test 里的每個樣本是否都在詞法階段報錯sem_error_test 里的未聲明變量和類型不匹配是否都有正確的行號sem_correct_test 里的合法程序是否一次通過且輸出語法樹結(jié)構(gòu)完整。如果某個樣本的錯誤出現(xiàn)在錯誤的階段比如詞法錯誤被語法分析彈出那說明詞法階段的攔截不夠優(yōu)先回 LexAnalyzer 找原因而不是在 ParseLL1 里打補(bǔ)丁。一開始我只盯著正確樣本跑覺得能跑通就等于完成。后來某次調(diào)試一個數(shù)組下標(biāo)越界正確樣本全都正常語義錯誤樣本卻一個都沒攔住我才意識到反面測試才是判斷編譯器脆不脆的關(guān)鍵。從那以后我每拆一份編譯器源碼都會先看它的錯誤測試樣本有沒有被歸類好沒有的話自己補(bǔ)。這個習(xí)慣幫我避開了很多正例全過、反例全崩的假完成。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取 SNL編譯器課設(shè)源碼解析：從詞法分析到語義檢查的完整實(shí)現(xiàn)
簡介吉林大學(xué)計算機(jī)學(xué)院2022年編譯原理課程設(shè)計項(xiàng)目是一份基于C實(shí)現(xiàn)的SNL語言編譯器完整方案面向需要完成同類課程設(shè)計或系統(tǒng)學(xué)習(xí)詞法分析、語法分析、語義分析的本科生。項(xiàng)目采用LL(1)分析法構(gòu)建語法解析配合詞法分析器、語義分析器與符號表管理代碼模塊劃分清晰且由作者獨(dú)立完成、相似性低適合直接借鑒或二次拓展。壓縮包共91個文件以cpp、h源文件為主體涵蓋詞法分析、LL(1)語法分析、語義分析等關(guān)鍵模塊另含obj、exe、pdb等編譯產(chǎn)物、Visual Studio工程文件以及多組txt測試用例與錯誤測試文本壓縮包整體142.28MB。內(nèi)容還涉及DS文法定義、保留字表、Token輸出與語義檢查用例工程配置完整便于構(gòu)建運(yùn)行和對照學(xué)習(xí)。已有1374人學(xué)習(xí)該資源對于希望獲得高分課程設(shè)計范例、深入理解編譯原理各階段實(shí)現(xiàn)的讀者具有較高的參考價值。1. SNL 語言編譯器課設(shè)源碼包為什么一個能拿滿績的參考值這個價某高校的編譯原理課程設(shè)計要求手寫一個 SNL 語言編譯器詞法、語法、語義三個階段全部真實(shí)跑通。SNL 是類 Pascal 的教學(xué)語言規(guī)模不大但保留字、算術(shù)表達(dá)式、函數(shù)調(diào)用、作用域和類型檢查一個不少。網(wǎng)上能翻到的參考要么是表達(dá)式計算器級別要么是公開倉庫里流傳爛大街的模板相似性高到不敢交。這份源碼包是 2022 年的完整交付C 編寫從 config 下的 reserved_words.txt 到 LexAnalyzer.cpp再到 LL1.cpp、ParseLL1.cpp、SemAnalyzer.cpp 和 symtable.h整條鏈路全在還自帶 lex_error_test、sem_error_test、sem_correct_test 三組測試樣本。它適合正在寫課設(shè)找不到語法樹接語義思路的人也適合已經(jīng)寫完詞法、卡在 LL(1) 遞歸下降的人。下面我按自己復(fù)現(xiàn)的順序把文件、參數(shù)和坑一個個過一遍。2. 從 main.cpp 到 SemAnalyzer先盤清源碼包的數(shù)據(jù)流2.1 文件清單哪些是核心代碼哪些是 Visual Studio 編譯殘留解壓后是一個標(biāo)準(zhǔn)的 Visual Studio 工程Project2.sln 可以直接雙擊打開。先把根目錄文件分個類避免一頭扎進(jìn) Debug 目錄里看那些 obj 和 pdb。文件/目錄定位說明main.cpp程序入口串聯(lián)詞法、語法、語義三個階段讀源文件并輸出結(jié)果config / reserved_words.txt詞法配置保留字表LexAnalyzer 運(yùn)行時加載LexAnalyzer.h / LexAnalyzer.cpp詞法分析器產(chǎn)出 Token 流輸出到 tokens.txt / new_tokens.txtLL1.h / LL1.cppLL(1) 集合與沖突檢測計算 First/Follow 或維護(hù)預(yù)測邏輯ParseLL1.h / ParseLL1.cpp語法分析器遞歸下降主程序按文法產(chǎn)生式構(gòu)建語法樹ds_grammer.h文法定義產(chǎn)生式、終結(jié)符/非終結(jié)符編號TreeNode.h / TreeNode.cpp語法樹節(jié)點(diǎn)孩子兄弟鏈表供語義分析遍歷Kind2Str.h / Kind2Str.cpp可讀化輸出把節(jié)點(diǎn)枚舉轉(zhuǎn)成字符串調(diào)試輸出靠它SemAnalyzer.h / SemAnalyzer.cpp語義分析器符號表查詢、類型檢查、作用域管理symtable.h / symtable.cpp符號表記錄變量/函數(shù)的名字、類型、層級、偏移量test1.txt ~ test8.txt輸入樣本混合覆蓋詞法、語法、語義的正確與錯誤用例lex_error_test / sem_error_test / sem_correct_test分類測試集分別用于驗(yàn)收詞法錯誤、語義錯誤和完全正確程序Debug 目錄下的 vc142.pdb、Project2.pdb、.obj、.tlog 全是 Visual Studio 的編譯殘留不影響理解邏輯。Project2.vcxproj.user 是用戶級配置換機(jī)器后建議直接刪掉讓 VS 重新生成。從 main.cpp 往下看標(biāo)準(zhǔn)數(shù)據(jù)流是讀入源文件 → LexAnalyzer 產(chǎn)出 Token 流 → ParseLL1 按文法組織語法樹 → SemAnalyzer 遍歷語法樹并查符號表 → 最后把結(jié)果打印到 rc.txt 或 outout.txt。tokens.txt 和 new_tokens.txt 同時存在說明詞法階段至少有兩種輸出模式常見的是普通 Token 流和帶行號位置的 Token 流。調(diào)試詞法錯誤時這兩個文件能直接告訴你錯誤發(fā)生在哪一行。2.2 詞法分析reserved_words.txt 與 LexAnalyzer.cpp 怎么配合很多人的詞法分析是把關(guān)鍵字硬編碼在幾十個 if-else 里這份資源把保留字單獨(dú)放在 reserved_words.txt代碼里用映射表查類型。下面這個加載函數(shù)是這類實(shí)現(xiàn)的標(biāo)準(zhǔn)骨架和你最后在 cpp 里看到的結(jié)構(gòu)基本一致void LoadReservedWords(const std::string path, std::unordered_mapstd::string, int kw) { std::ifstream in(path); std::string word; int kind 0; while (in word) { // 文件每行格式保留字 類型編號例如if 1 else 2 while 3 // 這里把字符串和編號分別讀進(jìn) word 和 kind in kw[word]; } }這段代碼的邏輯說明先用ifstream打開保留字文件然后以空白為分隔符連續(xù)讀。第一次in word拿到保留字本身第二次in kw[word]讀入后面的整數(shù)并直接作為映射值。unordered_map的選擇有講究詞法分析階段每個標(biāo)識符都要查一次表哈希查找能保證均攤 O(1)不會成為瓶頸。這樣組織的好處一是新增一個保留字只需要改 txt不需要動代碼二是不容易出現(xiàn)滿屏魔法數(shù)字查重時的代碼觀感也干凈很多。LexAnalyzer 里識別標(biāo)識符的邏輯就是逐字符拼遇到字母開頭就持續(xù)收集字母和數(shù)字拼完先查這個unordered_map查得到就是保留字查不到就是普通標(biāo)識符。Token 本身一般是struct Token { int type; std::string value; int line_no; };type 枚舉定義在 macro.h 或 LexAnalyzer.h 里。注意 reserved_words.txt 的編碼必須和源文件一致。最常見的坑是 UTF-8 帶 BOM導(dǎo)致第一個關(guān)鍵字額外多出一個不可見字符后面避坑章會專門講。2.3 語法樹TreeNode 的孩子兄弟鏈表與 Kind2Str 的可讀化輸出一段程序光有 Token 流不夠語義分析要在一個能表達(dá)嵌套結(jié)構(gòu)的樹上跑。TreeNode.cpp 用的是孩子兄弟表示法節(jié)點(diǎn)骨架長這樣struct TreeNode { int kind; // 節(jié)點(diǎn)類型對應(yīng) Kind2Str 里的枚舉名 TreeNode* child; // 第一個子節(jié)點(diǎn) TreeNode* sibling; // 右兄弟節(jié)點(diǎn) std::string value; // 標(biāo)識符名或字面量 int line_no; // 來源行號語義報錯全靠它 };為什么不用子節(jié)點(diǎn)數(shù)組因?yàn)?SNL 文法里 if 語句的子節(jié)點(diǎn)個數(shù)不固定有 else 是三個子節(jié)點(diǎn)沒有 else 是兩個用孩子兄弟鏈表可以動態(tài)掛節(jié)點(diǎn)遍歷函數(shù)統(tǒng)一走child和sibling兩條指針即可。Kind2Str.cpp 就是把 kind 整數(shù)映射成字符串比如某個節(jié)點(diǎn) kind 是 101打印出來是AddExpr比對輸出文件時一目了然。打印語法樹的遞歸函數(shù)一般長這樣void PrintTree(TreeNode* node, int depth) { while (node ! nullptr) { // 縮進(jìn)表示層級Kind2Str 負(fù)責(zé)把枚舉轉(zhuǎn)成可讀名 std::cout std::string(depth * 2, ) Kind2Str(node-kind) node-value std::endl; PrintTree(node-child, depth 1); node node-sibling; } }depth是當(dāng)前樹深度每次遞歸子節(jié)點(diǎn)時加一sibling在同一層橫向遍歷。main.cpp 遍歷語法樹后輸出到 rc.txt 或 outout.txt對照輸出文件就能驗(yàn)證遞歸下降函數(shù)的調(diào)用順序是否正確。3. 語法分析LL(1) 遞歸下降如何組織文法與預(yù)測3.1 為什么選 LL(1) 而不是 LR課設(shè)文法規(guī)模決定的取舍從文件命名能看出設(shè)計意圖LL1.h/cpp 帶著預(yù)測分析的味道ParseLL1.cpp 是實(shí)際的遞歸下降入口。SNL 這種課程語言文法一般就四五十條產(chǎn)生式用 LL(1) 手工寫一組遞歸下降函數(shù)完全可控。LR 系雖然能處理更多文法但要引入自動生成工具課設(shè)老師更希望你解釋清楚預(yù)測邏輯所以 LL(1) 是這類資源的主流選擇。LL1.cpp 通常負(fù)責(zé)計算 First/Follow 集合或者在建表過程中發(fā)現(xiàn)沖突時給出提示ParseLL1.cpp 按非終結(jié)符寫函數(shù)一個非終結(jié)符對應(yīng)一個 C 函數(shù)。ds_grammer.h 里的產(chǎn)生式就是這些函數(shù)的直接來源比如expr → term { (|-) term }對應(yīng)的就是下面這樣的函數(shù)。3.2 四則運(yùn)算表達(dá)式的遞歸下降一個可直接抄的結(jié)構(gòu)算術(shù)表達(dá)式是最典型的一層。下面的代碼是遞歸下降實(shí)現(xiàn)里必然會出現(xiàn)的結(jié)構(gòu)你會在 ParseLL1.cpp 里看到它的變體TreeNode* ParseExpr() { TreeNode* left ParseTerm(); // 先解析優(yōu)先級更高的項(xiàng) while (cur_token TOKEN_PLUS || cur_token TOKEN_MINUS) { TokenKind op cur_token; // 保存當(dāng)前運(yùn)算符 Match(cur_token); // 吃掉當(dāng)前運(yùn)算符 TreeNode* right ParseTerm(); // 解析右側(cè)操作數(shù) TreeNode* parent CreateNode(KIND_BIN_EXPR); parent-child left; // 左操作數(shù)掛到 child left-sibling right; // 右操作數(shù)掛到 sibling parent-value TokenToText(op); // 記錄運(yùn)算符文本 left parent; // 新節(jié)點(diǎn)作為左側(cè)繼續(xù)循環(huán) } return left; }邏輯說明ParseExpr先調(diào)ParseTerm因?yàn)槌顺齼?yōu)先級高于加減這步是文法層級決定的。while循環(huán)處理同優(yōu)先級運(yùn)算符的左結(jié)合每次構(gòu)造一個KIND_BIN_EXPR父節(jié)點(diǎn)把已有的left掛在child新解析出來的right掛在sibling。因?yàn)?TreeNode 是孩子兄弟結(jié)構(gòu)左操作數(shù)右操作數(shù)實(shí)際上是一條鏈而不是兩個獨(dú)立指針。這個循環(huán)不會產(chǎn)生左遞歸因?yàn)樗盐姆ɡ锏淖筮f歸改寫成了迭代。參數(shù)說明cur_token是全局當(dāng)前 TokenMatch斷言當(dāng)前 Token 類型等于參數(shù)并推進(jìn)到下一個。每個非終結(jié)符函數(shù)都必須在入口處至少調(diào)一次Match或NextToken否則可能死循環(huán)。3.3 if-else 懸空與同步恢復(fù)語法錯誤后還能繼續(xù)往下跑if 語句是另一個高頻踩坑點(diǎn)。LL(1) 遞歸下降處理 else 懸空靠的是前看一個 TokenTreeNode* ParseIfStmt() { Match(TOKEN_IF); TreeNode* cond ParseExpr(); // 條件表達(dá)式 Match(TOKEN_THEN); TreeNode* thenStmt ParseStmt(); // 必選分支 TreeNode* elseStmt nullptr; if (cur_token TOKEN_ELSE) { // 前看一個 Token 決定分支 Advance(); elseStmt ParseStmt(); // 可選分支 } Match(TOKEN_END); return BuildIfNode(cond, thenStmt, elseStmt); }邏輯說明解析完 then 分支后并不急著消費(fèi)TOKEN_ELSE而是看當(dāng)前 Token 是不是 else。是則額外解析一個語句不是則直接匹配END。這樣嵌套的 if-else 會自動就近配對不會出現(xiàn)懸空 else。注意這里ParseStmt的調(diào)用位置決定了遞歸深度遇到復(fù)雜嵌套時要確認(rèn)每個函數(shù)都在推進(jìn) Token。語法錯誤不能一遇到就停否則一個錯誤只報一行后面全被屏蔽。常見做法是同步恢復(fù)Match失敗時從出錯位置跳過 Token直到遇到分號、END、ELSE這類同步記號再重新嘗試。test1.txt、test2.txt 這類輸入里故意放了幾處缺分號或括號不匹配輸出能看出行號能報到哪里這就是同步恢復(fù)在起作用。調(diào)試時重點(diǎn)看 ParseLL1.cpp 里所有return false或主動Abort的地方錯誤信息通常會標(biāo)unexpected token at line N。4. 語義分析與符號表symtable 與 SemAnalyzer 如何完成作用域檢查4.1 符號表設(shè)計層級、類型、偏移量怎么填語義分析的核心是符號表和類型檢查。symtable.h 里的符號條目通常包含名字、類型、層級和偏移量。作用域是一個棧全局在最底層進(jìn)入函數(shù)壓一層進(jìn)入內(nèi)層塊再壓一層。SNL 里同名變量能不能重復(fù)聲明就看棧頂那一層有沒有同名條目。一個可用的符號表?xiàng)l目結(jié)構(gòu)長這樣struct Symbol { std::string name; // 變量名或函數(shù)名 int type; // 0int, 1boolean, 2array int level; // 0 是全局1 是第一個函數(shù)級 int offset; // 局部變量在棧幀里的偏移或數(shù)組長度 bool is_param; // 是形參就在函數(shù)入口登記 };符號表按層分組常見做法是std::vectorstd::vectorSymbol scopes。聲明變量時push_back到scopes[current_level]退出代碼塊時把整層pop_back。level字段不是必須的因?yàn)閺膕copes的下標(biāo)能推出來但保留它能讓調(diào)試信息更友好。4.2 聲明檢查和類型檢查落地一邊遍歷語法樹一邊查表語義分析從語法樹根節(jié)點(diǎn)開始遞歸下降和語法分析不同它不再消費(fèi) Token而是消費(fèi) TreeNode。賦值語句的類型檢查是一個典型例子void CheckAssign(TreeNode* node) { Symbol* left FindSymbol(node-child-value); // 左值查符號表 if (left nullptr) { SemError(variable %s not declared, node-child-value.c_str()); // 未聲明變量 return; } int rightType ExprType(node-child-sibling); // 遞歸求右式類型 if (left-type ! rightType) { SemError(type mismatch at line %d, node-line_no); } }邏輯說明FindSymbol從最內(nèi)層作用域向外層查因?yàn)閮?nèi)層同名變量會遮蔽外層。這和聲明重復(fù)檢查正好相反聲明查重只看當(dāng)前層類型檢查要看所有可見層。這兩個方向很容易搞反我的習(xí)慣是先讀懂函數(shù)名Find和CheckDecl分開寫不要把兩個語義混進(jìn)一個函數(shù)。數(shù)組下標(biāo)檢查是另一個加分點(diǎn)取 array 類型的長度比較下標(biāo)表達(dá)式是否越界。課設(shè)不要求運(yùn)行時求值但下標(biāo)是常量時可以當(dāng)場報越界這類實(shí)現(xiàn)會明顯提升代碼完成度。4.3 三組測試樣本為什么錯誤測試和正確測試同樣重要資源里的測試文件夾分三個這是最容易忽視的財富。lex_error_test 里是詞法錯誤樣本比如非法字符、未閉合注釋sem_error_test 是能過語法但過不了語義的樣本比如未聲明變量、類型不匹配sem_correct_test 是應(yīng)該完全通過的合法程序。拿到源碼后最好按順序跑判斷標(biāo)準(zhǔn)很明確正確樣本輸出不能有錯誤標(biāo)記錯誤樣本每個都要在正確的行號上報錯。如果你發(fā)現(xiàn)某個詞法錯誤樣本被語法分析攔截了說明詞法階段對非法字符沒有攔截干凈如果某個語義錯誤樣本到最后都沒有報錯說明 SemAnalyzer 的某個檢查分支根本沒被走到。三組樣本一起跑能驗(yàn)證編譯器不只是好路徑上不崩潰。5. 常見問題排查拿這份資源跑通時最容易翻車的五個點(diǎn)5.1 現(xiàn)象編譯成功但 Debug 目錄里沒有新生成的 Project2.exe按下 F7 編譯成功運(yùn)行卻發(fā)現(xiàn)跑的是舊 exe或者 Debug 目錄下根本沒有 exe。這個情況我遇到過不止一次。原因是工程被復(fù)制后.vcxproj 里的輸出目錄還指向原作者機(jī)器的絕對路徑比如D:\someone\Debug你編譯到別人目錄去了。解決方式很直接右鍵 Project2 屬性 → 常規(guī) → 輸出目錄改成$(SolutionDir)Debug\目標(biāo)文件名改成Project2.exe然后重新生成。改完后看輸出窗口的編譯日志確認(rèn)傳到的是你當(dāng)前工程的 Debug 目錄。5.2 現(xiàn)象源碼里明明有 if、while詞法分析卻全部識別成標(biāo)識符代碼里讀保留字表時第一個關(guān)鍵字永遠(yuǎn)匹配不上后面幾個正常。原因是 reserved_words.txt 用了 UTF-8 帶 BOM 編碼BOM 頭在文件開頭加了一個不可見字符導(dǎo)致第一個單詞讀出來是\xEF\xBB\xBFif和代碼里的if字符串不同。另一個常見變體是 Windows 行尾的\r沒去掉行末單詞多一個回車符。解決方式是用 Visual Studio 的文件 → 高級保存選項(xiàng)把 reserved_words.txt 改成 UTF-8 無 BOM同時養(yǎng)成習(xí)慣讀入每個單詞后做一次裁剪去掉非打印字符。從那以后我每次加載外部配置文件都會先打印一條調(diào)試信息看看第一個鍵到底是什么。5.3 現(xiàn)象語法分析跑到一半棧溢出或者直接死循環(huán)遞歸下降最常見的死循環(huán)來自左遞歸文法。比如你照著教科書寫expr → expr term函數(shù)里第一句又調(diào)ParseExpr自己Token 還沒消費(fèi)就無限遞歸下去棧很快爆掉。解決方式是把左遞歸改寫成迭代ParseExpr里先ParseTerm再用 while 循環(huán)吃掉和-這樣每個循環(huán)都會消耗一個 Token永遠(yuǎn)不會原地打轉(zhuǎn)。另外還有一種隱蔽情況某個非終結(jié)符函數(shù)里漏了Match連續(xù)調(diào)用同一個函數(shù)兩次卻沒有推進(jìn)cur_token。排查技巧很簡單在每個非終結(jié)符函數(shù)入口加一行斷點(diǎn)觀察cur_token的 type 有沒有變化沒變化的函數(shù)就是兇手。5.4 現(xiàn)象語義分析把內(nèi)層作用域的同名變量誤判成重復(fù)聲明內(nèi)層聲明了一個與外層同名的變量編譯器直接報重復(fù)聲明。原因是符號表沒有真正實(shí)現(xiàn)作用域棧進(jìn)函數(shù)前沒壓新層所有名字都堆在同一個全局表里。解決方式是把scopes.push_back({})放到函數(shù)入口退出前scopes.pop_back()。聲明查重只遍歷scopes.back()也就是當(dāng)前層查找符號則從back()往 0 方向遍歷。如果把這兩個方向?qū)懛淳蜁霈F(xiàn)外層變量找不到、內(nèi)層同名變量全報錯的情況。調(diào)試時可以在符號表每次 push/pop 時打印當(dāng)前作用域大小一眼就能看出棧有沒有正常退層。5.5 現(xiàn)象用新版 Visual Studio 打開工程提示 v142 工具集未安裝Debug 目錄里的 vc142.pdb 已經(jīng)暴露了工程生成環(huán)境v142 是 Visual Studio 2019 的工具集。如果你用 VS2022 直接打開會提示找不到 v142 生成工具編譯直接失敗。解決方式有三個任選其一裝 VS2019 的生成工具在項(xiàng)目屬性 → 常規(guī) → 平臺工具集里改成 v143也就是 VS2022 自帶工具集或者直接改 .vcxproj 文件里的PlatformToolsetv142/PlatformToolset為v143再重新加載工程。順手檢查一下 Windows SDK 版本如果機(jī)器上只有新 SDK把屬性里的 SDK 版本改成已安裝的那個別讓它自動選擇錯誤的版本。6. 最后一關(guān)用三組測試樣本把自己的交付變成證據(jù)分享一個能讓編譯器課設(shè)少走彎路的驗(yàn)收習(xí)慣。拿到這份資源后我先把 main.cpp 里默認(rèn)讀取的文件名改成從命令行參數(shù)讀取然后寫一個腳本把三組測試樣本全部跑一遍而不是在 IDE 里手動一個個改文件名。這個改動很小收益卻很直接它可以自動跑完幾十個樣本并用文件對比工具檢查輸出。# 以 test5.txt 為輸入把結(jié)果寫到 out5.txt Project2.exe test5.txt out5.txt # 用 fc 對比實(shí)際輸出與期望輸出 fc out5.txt expected5.txt跑完后的檢查清單我每次都會過一遍lex_error_test 里的每個樣本是否都在詞法階段報錯sem_error_test 里的未聲明變量和類型不匹配是否都有正確的行號sem_correct_test 里的合法程序是否一次通過且輸出語法樹結(jié)構(gòu)完整。如果某個樣本的錯誤出現(xiàn)在錯誤的階段比如詞法錯誤被語法分析彈出那說明詞法階段的攔截不夠優(yōu)先回 LexAnalyzer 找原因而不是在 ParseLL1 里打補(bǔ)丁。一開始我只盯著正確樣本跑覺得能跑通就等于完成。后來某次調(diào)試一個數(shù)組下標(biāo)越界正確樣本全都正常語義錯誤樣本卻一個都沒攔住我才意識到反面測試才是判斷編譯器脆不脆的關(guān)鍵。從那以后我每拆一份編譯器源碼都會先看它的錯誤測試樣本有沒有被歸類好沒有的話自己補(bǔ)。這個習(xí)慣幫我避開了很多正例全過、反例全崩的假完成。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取