簡介北京郵電大學計算機科學與技術專業(yè)大三上學期的編譯原理課內(nèi)作業(yè)總分97分以詞法分析和語法分析為主線是一份高質(zhì)量課程設計范例。壓縮包內(nèi)提供完整源代碼、詳細文檔說明、實驗報告以及PPT、PDF演示文稿其中源代碼覆蓋詞法分析、語法分析的實現(xiàn)邏輯文檔說明介紹運行環(huán)境與參數(shù)配置實驗報告闡述設計思路、實現(xiàn)流程和測試結果PPT和PDF適用于答辯展示與復盤學習ZIP格式整體約2.7MB。代碼均測試運行成功功能完整既可作為編譯原理課程作業(yè)的參考實現(xiàn)也能為畢業(yè)設計、課程設計或項目初期演示提供可擴展的基礎版本。通過對照代碼與實驗報告可直觀理解詞法分析器、語法分析器的構建方法掌握編譯前端設計的關鍵環(huán)節(jié)。目前已有121人學習瀏覽適合計算機相關專業(yè)學生、課程設計初學者及需要參考高分作業(yè)方案的開發(fā)者學習使用。1. 編譯原理課內(nèi)作業(yè)97分背后是詞法分析與語法分析的工程取舍北郵大三上的編譯原理課內(nèi)作業(yè)要求完成一個C語言子集的編譯器前端包含詞法分析、語法分析并提交源代碼、文檔、實驗報告、PPT和PDF。這類作業(yè)的評分邏輯在各校都類似詞法分析器能不能完整識別全部Token語法分析器能不能處理復雜表達式和嵌套結構以及錯誤恢復機制是否自然。這份作業(yè)拿了97分答辯平均分96分比分數(shù)更值得拆開說的是四件事狀態(tài)轉移表驅(qū)動掃描器、遞歸下降加向前看Token消解LL(1)沖突、鏈式作用域符號表、恐慌模式錯誤恢復。它們的組合邏輯是前端各模塊之間存在強依賴詞法分析的結果決定語法分析的輸入粒度語法分析的錯誤恢復又反向要求詞法層補充Token分類。這不是一個線性推進的過程而是要來回調(diào)整的。2. 詞法分析狀態(tài)轉移表驅(qū)動的掃描器設計與Token容錯2.1 Token類型劃分與保留字查表順序詞法分析的第一步不是寫代碼而是確定Token集合。以這份作業(yè)實現(xiàn)的C子集為例Token被分成六大類標識符、整型常量、浮點常量、保留字、運算符和分隔符外加一個EOF標記。這里有個關鍵決策保留字不進入DFA的狀態(tài)轉移邏輯而是用一張獨立的保留字表在標識符識別完成后做一次查表。直接給每個保留字建獨立狀態(tài)狀態(tài)數(shù)量會爆炸任何改動都要重畫狀態(tài)圖。用查表方式狀態(tài)圖只需要一條字母開頭的路徑。Token類型正則表達式示例輸出示例keywordint | float | return ...KEYWORD:intidentifier[A-Za-z_][A-Za-z0-9_]*ID:tempinteger[0-9]INT:42floating[0-9].[0-9]*FLOAT:3.14operator - * / ...OP:separator; , ( ) { }SEP:;表里每一行右側的產(chǎn)出形式實際上定義了語法分析器能拿到的Token流格式。設計時要特別注意多字符運算符比如、、它們必須在狀態(tài)轉移表里作為獨立分支處理否則會把和拆成兩個Token后續(xù)語法分析階段就再也無法合并。2.2 狀態(tài)轉移表驅(qū)動的掃描循環(huán)手寫詞法分析有兩條路線if-else鏈和狀態(tài)轉移表。if-else直觀但這道作業(yè)里選擇狀態(tài)轉移表的原因有兩個一是把字符分類邏輯和狀態(tài)推進邏輯解耦調(diào)整新運算符時只改表和字符分類函數(shù)不動核心循環(huán)二是調(diào)試時能把state和char_class打印出來逐步追蹤某條輸入為什么會走到死狀態(tài)這在if-else鏈里只能靠斷點反復單步。// lexer.c —— 核心掃描循環(huán) int next_token(void) { int state 0; int last_final -1; int last_len 0; int length 0; int start_pos pos; while (1) { char ch src[pos]; int cls get_char_class(ch); // 把字符映射到0..4的類別 state trans_table[state][cls]; // 查表得到下一狀態(tài) if (state -1) { // 死狀態(tài)表示當前Token已經(jīng)讀完 if (last_final -1) { report_error(unexpected char, ch, pos); pos; return TOKEN_ERROR; } pos start_pos last_len; // 回退到最后一個終態(tài) break; } length; if (is_final[state]) { // 當前狀態(tài)是否為終態(tài) last_final token_type[state]; last_len length; } pos; if (ch \0) break; // 文件結束 } return make_token(last_final, start_pos, last_len); }邏輯說明每次循環(huán)先取當前字符并映射成類別然后查二維數(shù)組trans_table得到下一狀態(tài)。如果下一狀態(tài)是-1說明從start_pos開始的子串沒有合法轉移這時要回退到最近一次終態(tài)并返回對應Token。變量last_final保存最近終態(tài)對應的Token類型last_len保存終態(tài)離起點的偏移長度回退時用二者恢復指針。參數(shù)層面需要注意trans_table的行列含義行號是當前狀態(tài)列號是字符類別。get_char_class把字母、數(shù)字、空白、EOF、其他分別映射到0到4這樣狀態(tài)表只需要五列。某個字符類別在某狀態(tài)沒有定義轉移時對應表項填-1。最大匹配原則在這里自然落地每次進入終態(tài)都記錄但不立即返回直到死狀態(tài)才統(tǒng)一回退。2.3 注釋、空白與未知字符的容錯路徑Token流不是只含有效Token空白和注釋也必須處理否則語法分析器會拿到一堆無關節(jié)點。常見做法是空白字符在狀態(tài)轉移表里直接回到初態(tài)并推進pos不生成Token行注釋和塊注釋各自由一個獨立狀態(tài)接收在遇到換行或*/時回到初態(tài)。不要把這部分交給語法分析器處理那會污染產(chǎn)生式集合。遇到未知字符時這里采用的策略是打印帶行列號的錯誤信息跳過該字符繼續(xù)掃描。比如輸入里出現(xiàn)詞法器報第2行第5列 錯誤碼E101: unexpected char 然后繼續(xù)解析后面的代碼。相比直接終止這種方式能讓一條測試用例暴露多個錯誤實驗報告里好寫答辯時也更耐看。3. 語法分析遞歸下降中LL(1)沖突的消解與向前看策略3.1 文法改造左遞歸消除與左公因子提取語法分析器選擇遞歸下降說明文法要滿足LL(1)約束。課程作業(yè)給的文法一般不會直接滿足最常見的是兩個問題左遞歸和左公因子。表達式文法E - E T | T一旦直接照搬遞歸下降會無限調(diào)用自身。消除方式是引入新的非終結符把左遞歸變右遞歸。以算術表達式為例表里的改造順序是作業(yè)文檔中必須寫清楚的內(nèi)容因為評分時老師會直接看這一頁。改造階段產(chǎn)生式說明原始E - E T | T左遞歸無法遞歸下降消除左遞歸E - T EE - T E | ε右遞歸后用循環(huán)等價提取左公因子stmt - if (expr) stmt | if (expr) stmt else stmt兩個產(chǎn)生式共享前綴處理后stmt - if (expr) stmt restrest - ε | else stmt把else延后匹配這里有個容易踩的坑左公因子不是所有情況都需要提取只有當兩個產(chǎn)生式的FIRST集合有交集時才必須處理。比如空語句和表達式語句通常沒有交集不需要動。而if語句的兩個產(chǎn)生式共享if (expr)這一段必須提取。提取后語義上等于把else推遲到后續(xù)非終結符里匹配這也是處理懸空else的一種常用辦法。3.2 FIRST與FOLLOW集合的計算順序手算FIRST和FOLLOW時順序錯了會在復雜文法里來回返工。FIRST集合要按依賴關系自底向上算先算終結符再算以終結符開頭的產(chǎn)生式。FOLLOW集合則要持續(xù)迭代直到不再變化。作業(yè)里我用一個Python腳本驗證了手算結果腳本構造產(chǎn)生式集合跑不動點迭代最后輸出每個非終結符的FIRST和FOLLOW。# first_follow.py —— 不動點迭代計算 FIRST/FOLLOW def compute_first(productions, symbols): first {s: set() for s in symbols if not s.isupper()} first.update({s: set() for s in symbols if s.isupper()}) changed True while changed: changed False for lhs, rhs in productions: for sym in rhs: if sym not in first: continue before len(first[lhs]) first[lhs] | (first[sym] - {}) # 表示 epsilon if not in first[sym]: break else: if not in first[lhs]: first[lhs].add() changed True return first這段腳本的邏輯說明first字典同時容納終結符和非終結符的集合主循環(huán)用changed標記控制迭代直到收斂。內(nèi)層循環(huán)遍歷產(chǎn)生式右側每個符號把該符號的FIRST集合并入左側非終結符的FIRST如果該符號不可推導出epsilon就停止掃描本產(chǎn)生式否則繼續(xù)往后合并。關鍵點是只有當符號的FIRST包含epsilon時才需要合并下一個符號的FIRST這也是epsilon產(chǎn)生式單獨處理的原因。FOLLOW集合同樣用不動點方式迭代起始符號的FOLLOW必須包含EOF標記對應遞歸下降里輸入流結束的檢測。3.3 遞歸下降函數(shù)的結構與預測分支遞歸下降函數(shù)本質(zhì)上是把產(chǎn)生式右側映射成程序控制流。對于E - T EE函數(shù)先調(diào)用T然后用while循環(huán)處理E。寫成循環(huán)而不是調(diào)用另一個函數(shù)是因為E上大量的epsilon分支會在調(diào)用棧上留下多余的幀調(diào)試時棧里全是parse_E_prime看不清當前到底在解析哪個運算符。// expr_parser.cpp —— 表達式產(chǎn)生式的遞歸下降實現(xiàn) int parse_expr() { if (parse_term() 0) { return -1; } while (cur_token.type TOKEN_PLUS || cur_token.type TOKEN_MINUS) { int op cur_token.type; advance_token(); int right parse_term(); if (right 0) { return -1; } emit_binary(op, prev_result, right); } return 0; }邏輯說明parse_expr先無條件調(diào)用parse_term這對應T在E產(chǎn)生式中的位置。進入循環(huán)前當前Token必須是或-否則直接返回等價于E推導出epsilon。每次循環(huán)取出運算符、推進Token、再解析右側term。emit_binary把運算符和兩個操作數(shù)記錄到中間代碼數(shù)組中這是語法分析結果送往后續(xù)階段的標準接口。參數(shù)層面注意遞歸下降函數(shù)之間通過返回值傳遞語義值出錯統(tǒng)一返回-1讓上層提前終止并觸發(fā)錯誤恢復。cur_token是全局Token快照advance_token讀取下一個Token并更新快照分支判斷用Token類型做switch避免每輪循環(huán)做字符串比較。4. 符號表與錯誤恢復把報錯做成人話的編譯前端細節(jié)4.1 鏈式作用域符號表的插入與查找時機符號表選擇鏈式作用域而不是單層哈希表是為了匹配塊結構語言的作用域規(guī)則。每個花括號塊對應一個作用域鏈表節(jié)點當前作用域由指針cur_scope指向鏈表尾部。插入操作發(fā)生在聲明語句處查找操作發(fā)生在變量引用處。這兩個時機經(jīng)常被搞反有人把所有標識符統(tǒng)一先插入導致重復聲明檢測失效有人只在解析結束時查一次導致作用域外的引用無法被發(fā)現(xiàn)。// symbol_table.c —— 鏈式作用域符號表插入 Symbol *insert_symbol(char *name, Type type) { Symbol *s lookup_current_scope(name); if (s ! NULL) { report_error(duplicate declaration %s, name); return NULL; } s (Symbol *)malloc(sizeof(Symbol)); s-name strdup(name); s-type type; s-next_in_scope cur_scope-head; // 頭部插入同作用域可見 s-outer_binding lookup_all_scopes(name); // 保存外層同名符號 cur_scope-head s; return s; }代碼說明插入前先在當前作用域查找同名符號找到就報重復聲明錯誤這是避免遮蔽語義被破壞的關鍵。outer_binding字段保存外層同名符號的引用當前作用域結束后恢復這個引用即可重新暴露外層變量。next_in_scope用于遍歷作用域下所有符號頭部插入讓最近聲明的符號最容易被找到。查找順序是從當前作用域逐層向外寫反會導致內(nèi)層變量訪問到外層同名變量。兩處調(diào)用時機不同聲明處通過lookup_current_scope檢查重復表達式里的標識符引用通過lookup_all_scopes獲取符號類型。4.2 恐慌模式錯誤恢復的同步Token集合語法分析遇到錯誤時如果立刻終止一次只能報一個錯對測試覆蓋來說效率很低。恐慌模式恢復的做法是遇到錯誤時跳過若干Token直到找到某個同步Token再繼續(xù)分析。同步集合的選取是核心。對C子集來說分號、右花括號、EOF是最可靠的同步點因為它們通常標記某條語句或某個塊的結束。出錯上下文同步Token集合恢復動作表達式內(nèi)部; , ) ]跳過直到分號語句開頭; }跳到下一個分號或塊結束塊內(nèi)部} EOF跳到塊結束或文件末尾參數(shù)列表, )跳到逗號或右括號實現(xiàn)時做成一個函數(shù)參數(shù)是同步Token數(shù)組。出錯時先輸出錯誤消息然后調(diào)用跳過邏輯直到cur_token命中同步集合中的一個再返回上層恢復解析。容易犯的錯誤是把同步集合設得過大比如加入所有運算符這樣會把一條語句里的多個錯誤當成一個錯誤恢復掉掩蓋真實語法問題。4.3 統(tǒng)一錯誤消息格式帶來的診斷收益在錯誤恢復能跳過Token的前提下消息格式?jīng)Q定了這些錯誤在實驗報告里是否具備可讀性。這里統(tǒng)一用三元組位置、錯誤碼、描述文本。位置由詞法分析器維護的行列號提供錯誤碼按模塊分號段。// error.c —— 統(tǒng)一錯誤輸出 void report_error(int code, const char *fmt, ...) { fprintf(stderr, 第%d行 第%d列 錯誤碼E%03d: , cur_line, cur_col, code); vfprintf(stderr, fmt, va_args); fprintf(stderr, \n); }代碼說明cur_line和cur_col由詞法分析器在每次next_token推進時維護錯誤碼E001到E099給詞法錯誤E100到E199給語法錯誤E200以上保留給語義分析階段。這樣在實驗報告里貼測試日志時可以直接按錯誤碼段統(tǒng)計各類錯誤數(shù)量老師一眼能看到錯誤處理模塊是成體系的。如果錯誤消息里只有文本沒有位置答辯時被問錯誤恢復怎么驗證會比較被動。5. 源碼之外文檔組織、演示用例與README的工程寫法5.1 目錄結構與README的啟動路徑源代碼之外的交付物包括文檔說明、實驗報告、PPT和PDF。常見問題是源碼和文檔放得七零八落下載后不知道先看哪個?？蓮陀玫哪夸浗Y構把任務分成四塊src存放源碼test存放測試用例doc存放實驗報告和說明slides存放答辯PPT。目錄內(nèi)容閱讀順序README.md運行方式、支持語法、目錄說明1src/lexer.c詞法分析器實現(xiàn)2src/parser.c語法分析器實現(xiàn)3src/symbol_table.c符號表實現(xiàn)3test/正常、邊界、錯誤三類用例4doc/實驗報告含測試日志5README的核心是讓一個陌生人在五分鐘內(nèi)跑起來。當時README里寫了三行命令make、make test、make clean并在test目錄里準備了一個test_all.sh腳本逐條運行用例并把輸出重定向到result.log。答辯時直接貼result.log作為運行證據(jù)比現(xiàn)場敲命令省時間。文檔說明不要寫本程序?qū)崿F(xiàn)了詞法分析要寫清楚每個文件對應文法里的哪個模塊以及測試用例覆蓋了哪些邊界條件。5.2 演示用例的三條選型路徑test目錄里的用例數(shù)量不需要多但必須覆蓋三類正常路徑、邊界路徑、非法輸入路徑。正常路徑放一個表達式組合較多、嵌套較深的c文件同時包含函數(shù)調(diào)用、數(shù)組下標和四則運算邊界路徑放空程序、只有聲明沒有語句、連續(xù)多個運算符的情況非法輸入路徑則故意制造詞法錯誤、語法錯誤、重復聲明錯誤各一個。演示時先跑正常路徑展示中間輸出再跑錯誤路徑展示錯誤恢復的連續(xù)報告最后對照實驗報告里的日志表格逐條講解。這套順序幾乎是把得分點擺在了評審老師面前。實驗報告中截取的測試輸出一定要用統(tǒng)一錯誤消息格式的實際運行結果不要手工編造。把詞法錯誤、語法錯誤、符號表錯誤的日志按錯誤碼排序貼在文檔里你會發(fā)現(xiàn)這比多寫一段技術難點更容易拿分。本文還有配套的精品資源點擊獲取