簡(jiǎn)介西北工業(yè)大學(xué)編譯原理試點(diǎn)班大作業(yè)完成了一個(gè)可正常工作的 SysY 語(yǔ)法編譯器并附源代碼、文檔說(shuō)明與實(shí)驗(yàn)報(bào)告適合計(jì)算機(jī)相關(guān)專業(yè)學(xué)生用于課程設(shè)計(jì)、編譯原理實(shí)驗(yàn)或畢設(shè)初期演示。壓縮包共168個(gè)文件大小為113KB包含大量SysY測(cè)試用例與輸入文件、C/C實(shí)現(xiàn)源碼如抽象語(yǔ)法樹(shù)、中間表示與靜態(tài)單賦值構(gòu)造、Python工具腳本、Markdown說(shuō)明文檔等結(jié)構(gòu)清晰便于學(xué)習(xí)。代碼均已測(cè)試運(yùn)行成功功能正常作者答辯評(píng)審平均分達(dá)到96分上傳前經(jīng)過(guò)驗(yàn)證可放心使用。已有249人學(xué)習(xí)下載項(xiàng)目對(duì)初學(xué)者友好作者支持私聊遠(yuǎn)程教學(xué)幫助解決運(yùn)行環(huán)境與編譯問(wèn)題。通過(guò)閱讀源碼和實(shí)驗(yàn)報(bào)告可系統(tǒng)理解編譯器前端的語(yǔ)法分析、中間代碼生成、靜態(tài)單賦值形式與優(yōu)化流程也能在此基礎(chǔ)擴(kuò)展功能滿足課設(shè)、畢設(shè)等不同需求。1. 拿到一個(gè)“能正常工作的SysY編譯器”大作業(yè)資源它到底在訓(xùn)練什么如果你正在做的編譯原理實(shí)驗(yàn)課要求是“寫(xiě)一個(gè)編譯器”那么西北工業(yè)大學(xué)這套試點(diǎn)班大作業(yè)的核心載體——SysY語(yǔ)言編譯器就是你最值得參照的完整樣本。它不是那種只跑通教材示例的玩具而是一個(gè)覆蓋了詞法、語(yǔ)法、語(yǔ)義、中間代碼生成和目標(biāo)代碼生成的完整鏈路產(chǎn)物最終能把你手寫(xiě)的C/C代碼變成可執(zhí)行的匯編程序。很多人第一次看到這個(gè)標(biāo)題會(huì)問(wèn)這和用IDE里那個(gè)“編譯器”有什么區(qū)別區(qū)別在于你在用編輯器寫(xiě)代碼而這份大作業(yè)要求你成為“編譯器”本身——把字符串變成抽象語(yǔ)法樹(shù)再把樹(shù)變成機(jī)器能認(rèn)的指令。本文會(huì)把這份大作業(yè)從規(guī)格到實(shí)現(xiàn)拆開(kāi)講適合正在做編譯原理實(shí)驗(yàn)的學(xué)生對(duì)照復(fù)現(xiàn)也適合工作后想補(bǔ)上“前端到底怎么和后端接起來(lái)”的開(kāi)發(fā)者。你不必照著西工大的題目一字不差地做因?yàn)镾ysY本身已經(jīng)成了國(guó)內(nèi)多所高校編譯實(shí)驗(yàn)的事實(shí)標(biāo)準(zhǔn)理解了它你就理解了絕大多數(shù)教學(xué)編譯器的骨架。2. 先讀懂SysY語(yǔ)言規(guī)格、子集邊界與設(shè)計(jì)取舍2.1 SysY不是一門(mén)新語(yǔ)言而是C語(yǔ)言的一個(gè)精心裁剪子集很多第一次接觸SysY的人會(huì)誤以為它是某種需要重新學(xué)習(xí)語(yǔ)法的學(xué)術(shù)語(yǔ)言實(shí)際上它就是你熟悉的C語(yǔ)言去掉若干難點(diǎn)之后剩下的骨架。SysY保留了int和float兩種基本類型、一維數(shù)組以及可選的n維數(shù)組擴(kuò)展、全局和局部變量、函數(shù)定義與調(diào)用、if/else、while、return、賦值、算術(shù)和邏輯運(yùn)算。它刻意刪掉了指針、結(jié)構(gòu)體、位運(yùn)算、函數(shù)指針、遞歸部分版本允許、字符串處理和復(fù)雜類型轉(zhuǎn)換目的只有一個(gè)讓一個(gè)學(xué)期內(nèi)、兩三個(gè)人的小組能從零寫(xiě)出一套能通過(guò)自動(dòng)化評(píng)測(cè)的編譯器。這里面的課程設(shè)計(jì)思路值得你留意——它不是要求你發(fā)明新語(yǔ)言而是要求你在一門(mén)已有語(yǔ)言的約束內(nèi)實(shí)現(xiàn)完整編譯流程。SysY規(guī)格的其余部分幾乎和C一致表達(dá)式優(yōu)先級(jí)是括號(hào)大于單目大于乘除模大于加減大于比較大于邏輯與大于邏輯或聲明語(yǔ)句用分號(hào)結(jié)尾函數(shù)可以無(wú)參也可以帶參全局變量必須在編譯期確定初值。這套子集邊界帶來(lái)的直接好處是做語(yǔ)法分析時(shí)你不必處理C語(yǔ)言里那種“類型名和表達(dá)式難以區(qū)分”的lexer hack也就是著名的“最棘手解析”問(wèn)題因?yàn)镾ysY的聲明關(guān)鍵字只有int、float、void不存在typedef引入新類型名的情況。這意味著你的遞歸下降解析器可以放心地看到標(biāo)識(shí)符就當(dāng)作變量引用不必像真實(shí)C編譯器那樣回溯或做符號(hào)表預(yù)查詢。我在做這類實(shí)驗(yàn)時(shí)習(xí)慣先把語(yǔ)言規(guī)格打印出來(lái)貼在屏幕邊上因?yàn)閹缀跛小翱雌饋?lái)是Bug”的問(wèn)題最后都發(fā)現(xiàn)是自己實(shí)現(xiàn)的語(yǔ)義和規(guī)格不一致而不是代碼寫(xiě)錯(cuò)了。2.2 類型系統(tǒng)與作用域規(guī)則兩個(gè)必須提前定的設(shè)計(jì)決策理論上你可以在動(dòng)手寫(xiě)代碼前先定好兩個(gè)決策否則后面改起來(lái)會(huì)很痛。第一個(gè)是類型檢查的嚴(yán)格程度。SysY要求int和float不能直接混用所以你在語(yǔ)義分析階段需要一套類型推導(dǎo)規(guī)則二元運(yùn)算的兩個(gè)操作數(shù)類型必須一致才能“直接”運(yùn)算不一致時(shí)需要插入int到float的隱式轉(zhuǎn)換節(jié)點(diǎn)賦值時(shí)右值類型必須能無(wú)損轉(zhuǎn)換到左值類型函數(shù)返回值要和聲明類型一致。這些規(guī)則的落點(diǎn)通常是AST節(jié)點(diǎn)的類型標(biāo)注字段我會(huì)用枚舉來(lái)處理Type::Int、Type::Float、Type::Void、Type::ArrayInt(size)其中數(shù)組類型要帶尺寸因?yàn)镾ysY的數(shù)組是靜態(tài)的編譯期必須知道總大小來(lái)計(jì)算棧上偏移。第二個(gè)決策是作用域模型。SysY的作用域規(guī)則和C一致全局作用域在最外層函數(shù)參數(shù)屬于函數(shù)體作用域塊語(yǔ)句{}內(nèi)部可以聲明新的局部變量遮蔽外層同名變量。常見(jiàn)做法是用一個(gè)作用域鏈來(lái)實(shí)現(xiàn)符號(hào)表每個(gè)作用域是一個(gè)unordered_mapstring, Symbol并帶一個(gè)指向父作用域的指針。查符號(hào)時(shí)從當(dāng)前作用域往上逐層找插入符號(hào)只插當(dāng)前層。這里有一個(gè)隱藏的大坑函數(shù)名和變量名是否共用命名空間。SysY規(guī)格一般允許函數(shù)和全局變量各自命名——有些評(píng)測(cè)用例會(huì)故意聲明一個(gè)全局變量名和之前的函數(shù)同名用來(lái)測(cè)試你的符號(hào)表是否把函數(shù)和變量分開(kāi)存儲(chǔ)了。我在別的實(shí)驗(yàn)里因?yàn)橥祽邪押瘮?shù)和變量塞進(jìn)同一張表結(jié)果評(píng)測(cè)時(shí)遇到這種用例直接翻車只能回頭把符號(hào)表拆成兩張。2.3 從規(guī)格到可執(zhí)行計(jì)劃把大作業(yè)拆成四個(gè)里程碑這一步不是寫(xiě)代碼但能決定你后面的節(jié)奏。我一般會(huì)把整個(gè)工期拆成四個(gè)階段第一階段寫(xiě)詞法分析和AST數(shù)據(jù)結(jié)構(gòu)跑通“讀源碼、輸出Token流、構(gòu)建語(yǔ)法樹(shù)”并打印出來(lái)人工校驗(yàn)第二階段做符號(hào)表建立和語(yǔ)義檢查讓編譯器能報(bào)出“未定義變量”“類型不匹配”“返回值缺失”三類典型錯(cuò)誤第三階段生成中間代碼通常是三地址碼或棧式指令這一階段不關(guān)心具體目標(biāo)機(jī)器只保證邏輯正確第四階段把中間代碼翻譯成目標(biāo)匯編常見(jiàn)是RISC-V并處理?xiàng)季趾图拇嫫鞣峙洹Ｃ總€(gè)階段都有一個(gè)可驗(yàn)證的產(chǎn)物不要試圖一步到位直接產(chǎn)出匯編——因?yàn)橐坏┙Y(jié)果不對(duì)你完全無(wú)法定位是語(yǔ)法解析的問(wèn)題還是代碼生成的問(wèn)題。Stage 1: 源碼字符串 - Token流 - AST (驗(yàn)證打印AST結(jié)構(gòu)) Stage 2: AST 符號(hào)表 - 帶類型標(biāo)注的AST (驗(yàn)證人為制造錯(cuò)誤源碼檢查報(bào)錯(cuò)位置) Stage 3: 帶類型AST - 三地址碼IR (驗(yàn)證逐條解釋執(zhí)行IR并與源碼邏輯對(duì)比) Stage 4: IR - RISC-V匯編 (驗(yàn)證用模擬器運(yùn)行匯編比對(duì)輸出)這個(gè)階段劃分的本質(zhì)是讓你每一次運(yùn)行都能看到“新東西”詞法不對(duì)時(shí)你看Token流語(yǔ)法不對(duì)時(shí)你看AST形狀語(yǔ)義不對(duì)時(shí)你看報(bào)錯(cuò)信息IR不對(duì)時(shí)你看中間代碼逐條執(zhí)行結(jié)果最后才輪到匯編。很多同學(xué)把大量時(shí)間花在選框架、選工具鏈上其實(shí)教學(xué)編譯器最穩(wěn)的路線就是手寫(xiě)全部模塊不用生成器。理由后面會(huì)展開(kāi)。3. 前端三件套詞法、語(yǔ)法、語(yǔ)義分析的最小可跑實(shí)現(xiàn)3.1 詞法分析手寫(xiě)狀態(tài)機(jī)遠(yuǎn)比Flex實(shí)用SysY的關(guān)鍵字只有int、float、void、return、if、else、while七個(gè)運(yùn)算符也只有算術(shù)、比較、賦值、邏輯、位取反部分規(guī)格有和括號(hào)分號(hào)花括號(hào)等幾十個(gè)Token類型。手寫(xiě)詞法分析器的工作量很小——一個(gè)switch驅(qū)動(dòng)的逐字符掃描就夠用而且出錯(cuò)時(shí)調(diào)試成本比Flex生成的代碼低得多。我的做法是定義Token結(jié)構(gòu)體記錄類型、詞素文本、行號(hào)和列號(hào)其中行號(hào)和列號(hào)必須從一開(kāi)始就維護(hù)好因?yàn)楹竺娴恼Z(yǔ)法錯(cuò)誤提示要依賴它們定位。enum class TokenType { Int, Float, Void, If, Else, While, Return, Identifier, IntLiteral, FloatLiteral, Assign, Plus, Minus, Star, Slash, Percent, Eq, Ne, Lt, Gt, Le, Ge, And, Or, Not, LParen, RParen, LBrace, RBrace, LBracket, RBracket, Semicolon, Comma }; struct Token { TokenType type; std::string lexeme; // 實(shí)際文本數(shù)字常量保留原始字符串用于后續(xù)轉(zhuǎn)換 std::string value; // 已轉(zhuǎn)換的字面值int存十進(jìn)制float存十六進(jìn)制比特位 int line, col; };詞法分析的主循環(huán)邏輯是跳過(guò)空白和注釋“讀到一個(gè)字符就決定下一個(gè)Token的掃描方式”。標(biāo)識(shí)符或關(guān)鍵字用首字符是字母或下劃線來(lái)觸發(fā)數(shù)字用首字符是數(shù)字來(lái)觸發(fā)運(yùn)算符按最長(zhǎng)匹配原則一個(gè)個(gè)試。SysY的注釋是//行注釋和/* */塊注釋塊注釋不嵌套這一點(diǎn)要在狀態(tài)機(jī)里明確處理——如果你圖省事寫(xiě)成“遇到*/就結(jié)束”遇到注釋里出現(xiàn)/*就會(huì)提前關(guān)閉注釋直接改變后續(xù)Token流。處理數(shù)字常量時(shí)有一個(gè)容易忽略的細(xì)節(jié)SysY的float字面量允許1f這樣的后綴但沒(méi)有double類型所有浮點(diǎn)數(shù)常量按32位存輸出匯編時(shí)用十六進(jìn)制立即數(shù)表示IEEE 754位模式而不是打印成可讀的小數(shù)——因?yàn)閰R編器的語(yǔ)法不一定接受十進(jìn)制浮點(diǎn)。3.2 語(yǔ)法分析遞歸下降配上“每個(gè)函數(shù)一個(gè)語(yǔ)法產(chǎn)生式”的寫(xiě)法語(yǔ)法分析是整個(gè)編譯器里最機(jī)械也最不能出錯(cuò)的部分我強(qiáng)烈建議你手寫(xiě)遞歸下降解析器不要用Yacc/Bison。SysY的語(yǔ)法沒(méi)有左遞歸問(wèn)題因?yàn)楸磉_(dá)式文法用優(yōu)先級(jí)爬升或分層展開(kāi)就能避開(kāi)也沒(méi)有LL(1)沖突的經(jīng)典陷阱。常見(jiàn)做法是給每個(gè)語(yǔ)法產(chǎn)生式寫(xiě)一個(gè)parseXxx()方法返回對(duì)應(yīng)的AST節(jié)點(diǎn)指針遇到語(yǔ)法錯(cuò)誤時(shí)調(diào)用統(tǒng)一的error()函數(shù)打印行號(hào)和期望的Token類型然后做panic-mode恢復(fù)——跳過(guò)當(dāng)前語(yǔ)句到下一個(gè)分號(hào)或右花括號(hào)為止這樣一次編譯能報(bào)出多個(gè)錯(cuò)誤而不是卡在第一個(gè)錯(cuò)誤上。std::unique_ptrStmtNode Parser::parseStmt() { if (match(TokenType::LBrace)) { auto block std::make_uniqueBlockNode(); // 花括號(hào)內(nèi)的語(yǔ)句序列每個(gè)語(yǔ)句可以是聲明、表達(dá)式語(yǔ)句、if、while、return while (!check(TokenType::RBrace) !atEOF()) { block-stmts.push_back(parseStmt()); } expect(TokenType::RBrace); return block; } // 允許空語(yǔ)句直接一個(gè)分號(hào) if (match(TokenType::Semicolon)) { return std::make_uniqueEmptyStmtNode(); } // 識(shí)別聲明語(yǔ)句的關(guān)鍵是前看兩個(gè)Tokenint或float 標(biāo)識(shí)符 if ((check(TokenType::Int) || check(TokenType::Float)) peekNextIsIdentifier()) { return parseLocalDecl(); } if (match(TokenType::If)) { return parseIf(); } if (match(TokenType::While)) { return parseWhile(); } if (match(TokenType::Return)) { return parseReturn(); } return parseExprStmt(); }這段代碼的關(guān)鍵點(diǎn)有兩個(gè)。第一是“如何區(qū)分聲明和表達(dá)式語(yǔ)句”——實(shí)現(xiàn)方式是向前看兩個(gè)Token如果當(dāng)前位置是int或float且下一個(gè)位置是標(biāo)識(shí)符就按聲明解析否則可能是一個(gè)函數(shù)調(diào)用表達(dá)式語(yǔ)句或老式的int類型出現(xiàn)在表達(dá)式中這在SysY里不應(yīng)該出現(xiàn)。第二是空語(yǔ)句必須顯式處理因?yàn)樵u(píng)測(cè)用例里會(huì)出現(xiàn)在循環(huán)體直接寫(xiě)一個(gè)分號(hào)的情況。AST節(jié)點(diǎn)全部用std::unique_ptr管理避免手寫(xiě)析構(gòu)和拷貝帶來(lái)的內(nèi)存問(wèn)題——這是我踩過(guò)的一個(gè)很實(shí)際的坑C11時(shí)代的課程代碼用裸指針很容易在遞歸解析拋異常時(shí)造成內(nèi)存泄漏而智能指針能讓異常安全變得幾乎免費(fèi)。表達(dá)式解析用優(yōu)先級(jí)爬升法比較簡(jiǎn)潔邏輯是為每個(gè)優(yōu)先級(jí)層級(jí)寫(xiě)一個(gè)函數(shù)parseExpr處理賦值parseOr處理邏輯或parseAnd處理邏輯與parseEq處理相等比較parseRel處理大小比較parseAdd處理加減parseMul處理乘除模parseUnary處理一元正負(fù)和邏輯非parsePrimary處理字面量、標(biāo)識(shí)符、括號(hào)表達(dá)式和函數(shù)調(diào)用。每一層遞減地調(diào)用下一層函數(shù)并在循環(huán)中檢查當(dāng)前運(yùn)算符是否屬于本層這就避免了寫(xiě)十幾層嵌套的尷尬。3.3 語(yǔ)義分析符號(hào)表建立、類型檢查和錯(cuò)誤恢復(fù)三位一體語(yǔ)義分析階段做的事情可以概括為兩次遍歷AST第一次遍歷收集所有函數(shù)聲明與全局變量聲明填入符號(hào)表——這一步必須在分析函數(shù)體之前完成否則函數(shù)體內(nèi)調(diào)用后面定義的函數(shù)時(shí)會(huì)報(bào)“未定義”而這在SysY里是合法的C語(yǔ)言也一樣第二次遍歷逐函數(shù)檢查函數(shù)體的語(yǔ)句和表達(dá)式做類型推導(dǎo)與驗(yàn)證。兩次遍歷的原因很樸素函數(shù)可以互相調(diào)用如果只做一次遍歷解析到a()時(shí)a還沒(méi)被收集就會(huì)誤報(bào)錯(cuò)誤。符號(hào)表?xiàng)l目需要記錄三類信息符號(hào)名、類型包含數(shù)組尺寸信息、存儲(chǔ)位置是全局變量、局部變量還是函數(shù)參數(shù)。對(duì)局部變量和參數(shù)還要在代碼生成階段之前就分配一個(gè)假的“棧偏移”這個(gè)偏移決定它在棧幀中的位置。我習(xí)慣在語(yǔ)義分析階段就完成偏移分配因?yàn)楹罄m(xù)生成匯編時(shí)每條訪問(wèn)變量的指令都需要知道偏移量。struct Symbol { std::string name; Type type; // Type::Int / Type::Float / Type::ArrayInt(64) 等 int offset; // 局部變量為相對(duì)幀指針的偏移全局變量為數(shù)據(jù)段標(biāo)簽 bool isGlobal; }; struct Scope { std::unordered_mapstd::string, Symbol symbols; std::shared_ptrScope parent; // nullptr 表示是全局作用域 };類型檢查的核心函數(shù)是checkExpr它遞歸地處理AST節(jié)點(diǎn)并返回該表達(dá)式的類型。比如遇到二元運(yùn)算節(jié)點(diǎn)時(shí)先遞歸檢查左右操作數(shù)如果兩邊類型不同一邊int一邊f(xié)loat就按SysY的隱式轉(zhuǎn)換規(guī)則在AST中插入一個(gè)ConvNode指明這是把int轉(zhuǎn)成float——這個(gè)轉(zhuǎn)換節(jié)點(diǎn)后續(xù)在代碼生成階段會(huì)翻譯成具體的匯編指令序列。遇到函數(shù)調(diào)用節(jié)點(diǎn)時(shí)要檢查函數(shù)是否存在、實(shí)參個(gè)數(shù)和形參個(gè)數(shù)是否一致、每個(gè)實(shí)參類型能否轉(zhuǎn)換為對(duì)應(yīng)形參類型。遇到return語(yǔ)句時(shí)要檢查當(dāng)前所在函數(shù)的返回類型是否匹配如果函數(shù)聲明返回int而return后面是float需要插入轉(zhuǎn)換如果返回void的函數(shù)寫(xiě)了return 5;則必須報(bào)錯(cuò)。這一階段的所有報(bào)錯(cuò)信息格式建議統(tǒng)一為[error] line X: 具體描述——評(píng)測(cè)系統(tǒng)一般不檢查你的報(bào)錯(cuò)文本但你自己調(diào)試時(shí)一個(gè)清晰的行號(hào)能省去大量時(shí)間。這里還有一個(gè)容易忽略的點(diǎn)作用域退出時(shí)要彈出當(dāng)前作用域否則離開(kāi)一個(gè)塊后塊內(nèi)聲明的變量仍然可見(jiàn)符號(hào)表會(huì)“漏”到后面。常見(jiàn)做法是在parseBlock時(shí)創(chuàng)建新的子作用域在塊解析完成后恢復(fù)父作用域?yàn)楫?dāng)前作用域。如果你用了作用域鏈加“當(dāng)前作用域指針”的方案注意在異常路徑上也要恢復(fù)——可以用RAII或者defer風(fēng)格的清理來(lái)保證。3.4 中間代碼生成把AST壓平成三地址碼指令流中間代碼的經(jīng)典選擇是三地址碼Three-Address CodeTAC每條指令至多一個(gè)運(yùn)算符和三個(gè)操作數(shù)比如t1 a b、t2 t1 * 4、store t2 - arr[0]。選擇三地址碼有三個(gè)實(shí)際理由第一它離AST很近每個(gè)AST節(jié)點(diǎn)都能映射成一到幾條TAC指令按后序遍歷生成即可第二它和匯編之間有清晰的映射關(guān)系你可以逐條把TAC翻譯成RISC-V指令第三它可以被解釋執(zhí)行——我在調(diào)試編譯器時(shí)寫(xiě)了一個(gè)極簡(jiǎn)的TAC解釋器這樣拿到IR就能檢查邏輯是否正確不必等到匯編跑起來(lái)。struct Instruction { OpCode op; // ADD, SUB, MUL, DIV, MOD, NEG, LT, LE, GT, GE, EQ, NE, JMP, JZ, JNZ, ... std::string dst; // 目標(biāo)臨時(shí)變量或標(biāo)簽 std::string arg1; std::string arg2; int line; // 對(duì)應(yīng)源碼行號(hào)出問(wèn)題時(shí)能溯源 }; struct FunctionIR { std::string name; std::vectorstd::string params; std::vectorInstruction instructions; std::vectorSymbol localSymbols; // 每個(gè)函數(shù)攜帶自己的符號(hào)表副本 int stackSize; // 幀大小由語(yǔ)義分析階段統(tǒng)計(jì) };生成TAC時(shí)有一個(gè)典型的難點(diǎn)是控制流的翻譯。if語(yǔ)句翻譯成“條件失敗跳轉(zhuǎn)到else或end標(biāo)簽”while翻譯成“循環(huán)開(kāi)始標(biāo)簽、條件檢查、循環(huán)體、跳回標(biāo)簽、循環(huán)結(jié)束標(biāo)簽”。這套邏輯本身就是一個(gè)小型設(shè)計(jì)建議畫(huà)一張“l(fā)abel與跳轉(zhuǎn)關(guān)系”的草圖再動(dòng)手while (A) { B }翻譯成Label_Loop、條件求值、JZ Label_End、執(zhí)行B、JMP Label_Loop、Label_End。條件表達(dá)式如果是A B這類短路運(yùn)算不能直接翻譯成“先算A再算B”——因?yàn)锳為假時(shí)不應(yīng)計(jì)算B。常見(jiàn)做法是把A B展開(kāi)成兩條跳轉(zhuǎn)指令計(jì)算A為假就跳轉(zhuǎn)到“結(jié)果0”的公共出口為真才繼續(xù)計(jì)算B。短路求值是教學(xué)編譯器評(píng)測(cè)中必考的點(diǎn)因?yàn)楹芏啻笞鳂I(yè)的復(fù)雜度都體現(xiàn)在“表達(dá)式的控制流化”上。關(guān)于臨時(shí)變量的命名我統(tǒng)一用%t0、%t1遞增編號(hào)最終在代碼生成階段把這些臨時(shí)變量映射到寄存器或棧位置。這一階段不需要關(guān)心目標(biāo)機(jī)器的寄存器數(shù)量因?yàn)槿刂反a的臨時(shí)變量是“無(wú)限”的后端的寄存器分配才會(huì)引入約束。4. 后端兩步走從抽象語(yǔ)法樹(shù)到目標(biāo)代碼的關(guān)鍵映射4.1 從IR到匯編先理解寄存器機(jī)再理解SysY的棧幀約定目標(biāo)代碼生成是整個(gè)大作業(yè)里最“硬”的部分。常見(jiàn)方案是生成RISC-V匯編因?yàn)樗噶罴?guī)整、教程多、還有RARS這種模擬器可以直接跑很多教學(xué)編譯器都默認(rèn)輸出RISC-V。你不需要一臺(tái)真實(shí)的板子模擬器足夠驗(yàn)證正確性。在做代碼生成之前你得先想清楚一個(gè)關(guān)鍵約定棧幀怎么排我采用的標(biāo)準(zhǔn)做法是函數(shù)入口先保存返回地址RISC-V中的ra寄存器和舊幀指針fp然后把fp指向當(dāng)前幀sp向下移動(dòng)棧幀大小函數(shù)體內(nèi)所有局部變量和臨時(shí)變量的訪問(wèn)都通過(guò)fp加固定偏移來(lái)完成函數(shù)返回時(shí)恢復(fù)sp、fp、ra并跳轉(zhuǎn)返回。這個(gè)布局的好處是訪問(wèn)局部變量不需要?jiǎng)討B(tài)計(jì)算偏移結(jié)構(gòu)最簡(jiǎn)單也最容易調(diào)試。高地址 | 調(diào)用者幀 | --------- | ra | 保存的返回地址 | 舊 fp | 保存的幀指針 | 局部變量| 第1個(gè)局部變量偏移為 -8 或 -12依對(duì)齊 | 臨時(shí)變量| | 參數(shù)區(qū) | 如果需要重定位不用SysY參數(shù)可以直接放寄存器 --------- sp 指向當(dāng)前幀底 低地址局部變量的偏移分配規(guī)則是從fp-8開(kāi)始向下分配因?yàn)閞a占8字節(jié)、舊fp占8字節(jié)每個(gè)int占4字節(jié)每個(gè)float占4字節(jié)數(shù)組按元素個(gè)數(shù)乘元素大小分配連續(xù)空間。所有局部變量偏移都在語(yǔ)義分析階段就算好代碼生成階段直接查符號(hào)表取偏移即可。如果遇到需要對(duì)齊的場(chǎng)景某些指令要求16字節(jié)對(duì)齊你可以在分配時(shí)把每個(gè)變量的大小按8字節(jié)向上一取整代價(jià)是浪費(fèi)一點(diǎn)?？臻g但換來(lái)的是不會(huì)出現(xiàn)非對(duì)齊訪問(wèn)。4.2 表達(dá)式求值的兩種策略棧式求值與寄存器分配生成表達(dá)式求值代碼有兩條路線。一條是棧式求值每算一個(gè)子表達(dá)式就把結(jié)果壓入棧需要時(shí)再?gòu)臈棾?。這種策略實(shí)現(xiàn)最簡(jiǎn)單——每個(gè)二元運(yùn)算翻譯成“右操作數(shù)壓棧、左操作數(shù)壓棧、彈出右操作數(shù)到t0、彈出左操作數(shù)到t1、執(zhí)行運(yùn)算、把結(jié)果壓?！?。但它生成的代碼效率低、棧指令多而且對(duì)熟悉后續(xù)優(yōu)化的同學(xué)來(lái)說(shuō)不是好基礎(chǔ)。另一條是寄存器求值為每個(gè)臨時(shí)變量嘗試分配一個(gè)物理寄存器用完就釋放。SysY大作業(yè)對(duì)性能沒(méi)有硬性要求但用寄存器策略寫(xiě)出來(lái)的后端從結(jié)構(gòu)上更接近真實(shí)編譯器。我在做這類后端時(shí)用的是統(tǒng)一寄存器分配策略給每個(gè)TAC臨時(shí)變量分配一個(gè)虛擬寄存器編號(hào)然后用一個(gè)簡(jiǎn)單的映射表把虛擬寄存器映射到RISC-V物理寄存器上——t0到t6共7個(gè)。分配的規(guī)則是定義一個(gè)“活躍區(qū)間”的概念如果一個(gè)臨時(shí)變量在它的最后一次使用之后就可以釋放寄存器。最簡(jiǎn)版本是“線性掃描”遍歷指令序列維護(hù)一個(gè)“當(dāng)前活躍變量”集合變量第一次出現(xiàn)時(shí)分配一個(gè)空寄存器沒(méi)有空寄存器就把最早被使用的變量溢出到棧上。對(duì)教學(xué)編譯器來(lái)說(shuō)溢出邏輯可以簡(jiǎn)化——你把所有臨時(shí)變量都映射到棧上的固定偏移運(yùn)行時(shí)一條指令從棧取出來(lái)算完再存回去物理寄存器只用t0/t1/t2三個(gè)即可正確性完全不受影響。我更喜歡這種簡(jiǎn)化方案因?yàn)樗膮R編可讀性極高你一眼能看出哪條指令對(duì)應(yīng)哪條IR。// 代碼生成的簡(jiǎn)化映射臨時(shí)變量 %t0 映射到棧偏移 -36%t1 映射到 -40 int tempOffset(const std::string temp, int currentOffset) { // 維護(hù)一個(gè) mapstring,int每個(gè)臨時(shí)變量分配8字節(jié)偏移遞減 }4.3 函數(shù)調(diào)用與數(shù)組尋址兩個(gè)“寫(xiě)錯(cuò)了不報(bào)錯(cuò)但結(jié)果錯(cuò)”的重災(zāi)區(qū)SysY的函數(shù)傳參規(guī)則通常被稱為“整型按值傳、數(shù)組退化為指針傳地址”——但是SysY里沒(méi)有指針類型所以數(shù)組參數(shù)的正確保數(shù)方式是按“基址尺寸”傳遞。我的做法是調(diào)用函數(shù)時(shí)實(shí)參如果是普通變量或常量直接加載到a0~a7寄存器超過(guò)8個(gè)參數(shù)的部分壓棧實(shí)參如果是數(shù)組名則把數(shù)組首地址加載到寄存器。這樣被調(diào)用函數(shù)內(nèi)部就可以通過(guò)基址加偏移訪問(wèn)數(shù)組元素。這兩個(gè)方向的映射都必須測(cè)一遍調(diào)用者把數(shù)組首地址放進(jìn)了a0被調(diào)用者也要按“a0里是數(shù)組首地址”來(lái)取元素。這里最容易出bug的是嵌套函數(shù)調(diào)用如果foo(bar(x))在計(jì)算bar(x)時(shí)覆蓋了a0那么foo的第一個(gè)參數(shù)必須在你計(jì)算bar之前就保存到棧上——很多同學(xué)的編譯器是在這里翻車的。數(shù)組尋址的另一個(gè)細(xì)節(jié)是下標(biāo)類型。SysY允許int a[10]; a[i1] 3;其中i1是int表達(dá)式你需要在IR層面生成“計(jì)算下標(biāo)表達(dá)式、乘以元素大小、加上基址、訪存”的指令序列。如果數(shù)組是float類型下標(biāo)還要乘以4字節(jié)。這一步比較容易出錯(cuò)的地方是減法下標(biāo)和負(fù)數(shù)下標(biāo)——SysY沒(méi)有規(guī)定越界檢查所以負(fù)數(shù)下標(biāo)會(huì)訪問(wèn)到數(shù)組基址之前的地址這其實(shí)是內(nèi)存安全漏洞但在教學(xué)評(píng)測(cè)中不會(huì)觸發(fā)崩潰你要做的是保證“合法的下標(biāo)計(jì)算正確”而不是“非法的下標(biāo)有保護(hù)”。5. 大作業(yè)最容易翻車的五個(gè)坑現(xiàn)象、原因與修復(fù)5.1 編譯通過(guò)但模擬器報(bào)“未包含main類型”癥狀是匯編器或鏈接器提示找不到main符號(hào)或者分配器報(bào)“entry point not found”。根本原因是你的編譯器在處理全局變量時(shí)把全局變量聲明當(dāng)成了函數(shù)聲明導(dǎo)致main函數(shù)沒(méi)被識(shí)別為入口。另一種可能更隱蔽你的詞法分析把main識(shí)別成了關(guān)鍵字而非標(biāo)識(shí)符從而無(wú)法在符號(hào)表中登記main這個(gè)函數(shù)名。我的解決方法是檢查三個(gè)位置詞法分析器的標(biāo)識(shí)符判定規(guī)則里是否意外包含了main語(yǔ)法分析器的全局聲明解析是否把所有以int或float開(kāi)頭的語(yǔ)句都吞掉代碼生成時(shí)入口標(biāo)簽是否用了統(tǒng)一格式通常匯編器要求.globl main。這類問(wèn)題排查最快的辦法是把你生成的匯編寫(xiě)到文件里人工查看開(kāi)頭20行看到main:標(biāo)簽缺失就知道問(wèn)題出在哪兒了。5.2 本地測(cè)試全過(guò)評(píng)測(cè)機(jī)上一個(gè)用例崩潰這是最經(jīng)典的血淚經(jīng)驗(yàn)。本地跑一個(gè)簡(jiǎn)單用例正常評(píng)測(cè)一上去就掛——多半是數(shù)組越界沒(méi)有崩潰、但破壞了相鄰變量的值。原因是你的棧幀分配過(guò)于緊湊局部變量a占4字節(jié)、b占4字節(jié)它們的偏移緊挨著如果代碼生成對(duì)數(shù)組的偏移計(jì)算多乘或少乘了一個(gè)元素大小可能訪問(wèn)到另一個(gè)局部變量的位置數(shù)據(jù)被污染但程序沒(méi)崩。解決辦法是回歸到最簡(jiǎn)單的確定性測(cè)試寫(xiě)一個(gè)int a[4]; int b; b 5; a[3] 1; return a[3] b;的用例人工檢查生成匯編中每次對(duì)a和b的訪存偏移是否和符號(hào)表記錄一致。如果對(duì)b的訪問(wèn)出現(xiàn)在數(shù)組地址附近就說(shuō)明數(shù)組偏移基準(zhǔn)或下標(biāo)乘數(shù)有問(wèn)題。5.3 全局變量和局部變量同名語(yǔ)義分析直接“串味”癥狀是函數(shù)內(nèi)聲明了一個(gè)和全局變量同名的局部變量結(jié)果全局變量在該函數(shù)內(nèi)被意外修改或者出現(xiàn)“重復(fù)定義”錯(cuò)誤。原因是你的符號(hào)表在進(jìn)入函數(shù)體時(shí)沒(méi)有創(chuàng)建新的作用域并把全局符號(hào)表作為父作用域而是還在全局表上繼續(xù)插入。解決方法是嚴(yán)格執(zhí)行作用域鏈在解析每個(gè)函數(shù)體之前新建一個(gè)子作用域parent指向全局作用域在解析每個(gè)塊語(yǔ)句時(shí)再往下建一層。查詢符號(hào)時(shí)從當(dāng)前層向上找找到第一層為止插入時(shí)只插入當(dāng)前層。這樣同名遮蔽天然就正確。5.4 短路求值被優(yōu)化成了“先算兩邊”癥狀是int a 0; if (a (1/a ! 0))這類用例你的編譯器輸出結(jié)果與C語(yǔ)義不符——因?yàn)槿绻劝?/a算出來(lái)就會(huì)觸發(fā)除零錯(cuò)誤而正確行為是短路跳過(guò)右操作數(shù)。問(wèn)題在于你的IR生成對(duì)和||做了直接求值而不是控制流展開(kāi)。修復(fù)方式是把A B翻譯成如下IR序列計(jì)算A如果A為假則跳轉(zhuǎn)到“結(jié)果0”標(biāo)簽如果A為真再計(jì)算B結(jié)果就是B的值公共出口標(biāo)簽處把結(jié)果整合。這個(gè)修復(fù)必須在IR階段做不能留到匯編階段再打補(bǔ)丁因?yàn)閰R編階段看不到“短路”的語(yǔ)義信息只有跳轉(zhuǎn)結(jié)構(gòu)。5.5 遞歸函數(shù)導(dǎo)致棧無(wú)限增長(zhǎng)本地跑著跑著就卡死SysY規(guī)格中的遞歸支持因版本而異如果你的版本允許遞歸那么函數(shù)調(diào)用的棧幀必須每次調(diào)用都重新分配。很多人圖省事把局部變量映射到了“固定的全局地址”這導(dǎo)致遞歸時(shí)第二次調(diào)用覆蓋了第一次調(diào)用的數(shù)據(jù)。修復(fù)方式就是嚴(yán)格執(zhí)行動(dòng)態(tài)棧幀分配每次函數(shù)調(diào)用入口都更新sp局部變量的偏移始終相對(duì)當(dāng)前fp計(jì)算而不是絕對(duì)地址。檢查方法也簡(jiǎn)單寫(xiě)一個(gè)int fact(int n) { if (n 1) return 1; return n * fact(n-1); }如果計(jì)算結(jié)果對(duì)說(shuō)明棧幀做得正確如果結(jié)果不對(duì)看生成的匯編是否在遞歸調(diào)用時(shí)重復(fù)使用了同一塊棧偏移。6. 收尾驗(yàn)證用SysY官方測(cè)試集框架做回歸再動(dòng)手優(yōu)化走到這個(gè)階段你的編譯器已經(jīng)能通過(guò)手寫(xiě)用例了但大作業(yè)能不能拿高分取決于驗(yàn)證方法的系統(tǒng)性。SysY社區(qū)有一套公開(kāi)的測(cè)試樣例組織方式常見(jiàn)結(jié)構(gòu)是每個(gè)功能點(diǎn)一個(gè)目錄目錄下多個(gè).sysy源文件每個(gè)源文件配一個(gè).out文件保存期望輸出。你可以照著這個(gè)思路搭建自己的回歸測(cè)試腳本用Python寫(xiě)一個(gè)簡(jiǎn)單的測(cè)試運(yùn)行器遍歷測(cè)試目錄、逐個(gè)調(diào)用編譯器、用模擬器運(yùn)行生成的目標(biāo)代碼、與期望輸出比對(duì)并統(tǒng)計(jì)通過(guò)率。import subprocess, pathlib, sys compiler ./mysysy # 你的編譯器可執(zhí)行文件 simulator java -jar rars.jar # RISC-V模擬器參數(shù)按模擬器文檔調(diào)整 base pathlib.Path(tests) passed failed 0 for src in sorted(base.rglob(*.sysy)): exp_file src.with_suffix(.out) asm_file src.with_suffix(.s) subprocess.run([compiler, str(src), -o, str(asm_file)], checkTrue) result subprocess.run( simulator.split() [str(asm_file)], capture_outputTrue, textTrue ) expected exp_file.read_text().strip() actual result.stdout.strip() if actual expected: passed 1 print(fPASS {src.name}) else: failed 1 print(fFAIL {src.name}: expected {expected!r}, got {actual!r}) print(fpassed {passed}, failed {failed}) sys.exit(1 if failed else 0)這套框架有幾個(gè)好處跑完一輪你能立刻知道哪個(gè)功能點(diǎn)掛了第二次回歸時(shí)只需重跑腳本就能防止“改好了東墻拆了西墻”。我的習(xí)慣是每實(shí)現(xiàn)一個(gè)新功能就立刻增加對(duì)應(yīng)測(cè)試用例而不是等所有功能都寫(xiě)完再一次性測(cè)試——一次性測(cè)試時(shí)面對(duì)20個(gè)失敗用例你根本不知道從哪兒開(kāi)始查。腳本里的編譯器參數(shù)-o指定輸出文件和模擬器調(diào)用方式都要按你自己的實(shí)現(xiàn)改這不是能直接復(fù)用的代碼而是一個(gè)可參考的驗(yàn)證骨架。驗(yàn)證通過(guò)之后下一步才是“優(yōu)化”。大作業(yè)評(píng)分通常包含“性能測(cè)試”——同樣一個(gè)復(fù)雜用例你的編譯器生成的代碼比別人的慢就會(huì)丟分。但教學(xué)編譯器優(yōu)化的起點(diǎn)不是做復(fù)雜的寄存器分配、指令調(diào)度或循環(huán)優(yōu)化而是消除那些容易消除的低效模式表達(dá)式中的冗余棧操作、常數(shù)運(yùn)算的提前折疊、if (1)這種永真條件的分支消除。我在做了基礎(chǔ)正確性驗(yàn)證后會(huì)加一個(gè)輕量的窺孔優(yōu)化掃描生成的匯編把“把常數(shù)加載到寄存器、再和另一個(gè)常量做運(yùn)算”的指令序列替換成直接用常數(shù)的立即數(shù)指令。這個(gè)優(yōu)化代碼量不大但性能提升非常明顯是一種成本收益比極高的技巧。另一個(gè)必須做的收尾工作是文檔和實(shí)驗(yàn)報(bào)告。西工大這套大作業(yè)的資源包包含源代碼、文檔說(shuō)明和實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告的重點(diǎn)不是抄代碼而是講清楚你的設(shè)計(jì)決策為什么用遞歸下降而不是LL/LR生成器、為什么用三地址碼而不是棧式指令、符號(hào)表和棧幀是怎么設(shè)計(jì)的、測(cè)試數(shù)據(jù)覆蓋了哪些邊界。把這些決策寫(xiě)清楚比你貼200行代碼更能體現(xiàn)工作量。我的習(xí)慣是每完成一個(gè)里程碑就寫(xiě)一小節(jié)報(bào)告而不是最后一周集中補(bǔ)——集中補(bǔ)出來(lái)的報(bào)告讀起來(lái)像流水賬缺失了設(shè)計(jì)過(guò)程里的取舍記錄。最后說(shuō)一個(gè)我做編譯器實(shí)驗(yàn)時(shí)養(yǎng)成的習(xí)慣永遠(yuǎn)保留“最小復(fù)現(xiàn)用例”。每遇到一個(gè)bug不要急著改代碼先把這個(gè)bug縮成一個(gè)20行以內(nèi)的SysY程序保存到regression/目錄下修復(fù)之后把它加進(jìn)回歸測(cè)試。這個(gè)習(xí)慣看起來(lái)樸素但能保證你離校之后回頭看這份代碼時(shí)任何一次改動(dòng)都能被測(cè)試保護(hù)住。編譯器的坑大多藏在語(yǔ)義邊界上——短路求值、類型轉(zhuǎn)換、數(shù)組偏移、作用域遮蔽哪個(gè)方向想漏了都會(huì)在評(píng)測(cè)時(shí)給你一個(gè)措手不及的失敗。希望這份從規(guī)格到驗(yàn)證的完整路徑能幫到你讓你在做自己的SysY編譯器時(shí)少走幾個(gè)通宵。本文還有配套的精品資源點(diǎn)擊獲取