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