簡介本資源是北京交通大學(xué)《編譯原理》課程配套的完整實(shí)驗(yàn)源碼集合面向計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生及編譯器開發(fā)初學(xué)者系統(tǒng)覆蓋編譯器前端六大核心環(huán)節(jié)詞法分析、遞歸下降語法分析、LL(1)文法分析、算符優(yōu)先文法分析、基于SLR(1)的語法制導(dǎo)翻譯、中間代碼生成。壓縮包共94個(gè)文件含33個(gè)C源文件cpp實(shí)現(xiàn)核心算法邏輯、29個(gè)頭文件h封裝數(shù)據(jù)結(jié)構(gòu)與接口、21個(gè)文本文件txt提供測試用例與文法定義、6個(gè)Makefile支持一鍵編譯另有README.md和說明文檔輔助理解整體架構(gòu)。資源僅66KB輕量精煉目錄按Lab01–Lab06清晰劃分六大實(shí)驗(yàn)?zāi)K每個(gè)模塊均含可運(yùn)行示例、測試輸入與預(yù)期輸出便于逐層驗(yàn)證與調(diào)試。目前已有88人學(xué)習(xí)下載是深入理解編譯流程、掌握語法分析表構(gòu)建、語義動(dòng)作嵌入及三地址碼生成等關(guān)鍵技術(shù)的高質(zhì)量實(shí)踐材料。1. 項(xiàng)目概述從課程實(shí)驗(yàn)到編譯器前端的完整拼圖最近在整理過往的學(xué)習(xí)資料時(shí)翻出了一個(gè)壓箱底的“寶藏”——我在北京交通大學(xué)攻讀計(jì)算機(jī)專業(yè)期間完成的《編譯原理》課程全套實(shí)驗(yàn)項(xiàng)目的完整源碼集合。這個(gè)壓縮包可以說是我學(xué)生時(shí)代在系統(tǒng)軟件領(lǐng)域投入心血最多的結(jié)晶。它不是一個(gè)玩具而是一個(gè)嚴(yán)格按照課程要求從零開始逐步構(gòu)建出一個(gè)具備完整前端功能的編譯器的實(shí)踐記錄。里面包含了從最基礎(chǔ)的詞法分析到遞歸下降、LL(1)、算符優(yōu)先、SLR(1)等多種語法分析方法的實(shí)現(xiàn)最終抵達(dá)語法制導(dǎo)翻譯和中間代碼生成這六個(gè)核心實(shí)驗(yàn)?zāi)K。每一個(gè)模塊都像是一塊拼圖單獨(dú)看是一個(gè)精巧的算法實(shí)現(xiàn)組合起來則構(gòu)成了一個(gè)編譯器前端的完整工作流。對于計(jì)算機(jī)專業(yè)的學(xué)生尤其是正在或即將學(xué)習(xí)編譯原理的同學(xué)來說編譯原理這門課常常被譽(yù)為“天書”。它充滿了抽象的概念、復(fù)雜的算法和嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)理論。課堂上的有限自動(dòng)機(jī)、上下文無關(guān)文法、LR分析表聽起來都離實(shí)際的編程很遠(yuǎn)。而實(shí)驗(yàn)正是打通理論與實(shí)踐的橋梁。這個(gè)源碼集合的價(jià)值就在于它提供了一個(gè)可運(yùn)行、可調(diào)試、可修改的完整參考。你不僅能看懂每一行代碼在做什么更能通過運(yùn)行它直觀地看到一個(gè)簡單的源程序是如何被一步步“肢解”成單詞詞法分析再根據(jù)語法規(guī)則組裝成樹語法分析最后被翻譯成一種更接近機(jī)器、但獨(dú)立于具體機(jī)器的中間表示中間代碼生成。這個(gè)過程是理解編譯器如何工作的最佳途徑。無論你是想預(yù)習(xí)課程、完成作業(yè)、準(zhǔn)備考試還是單純對編譯器內(nèi)部機(jī)制感到好奇這個(gè)項(xiàng)目都能給你帶來實(shí)實(shí)在在的幫助。它基于Java實(shí)現(xiàn)結(jié)構(gòu)清晰注釋詳盡避免了過于復(fù)雜的工程化封裝將核心算法邏輯直接呈現(xiàn)在你面前。接下來我將帶你深入這個(gè)“六合一”的編譯器前端實(shí)驗(yàn)項(xiàng)目拆解每一個(gè)模塊的設(shè)計(jì)思路、實(shí)現(xiàn)細(xì)節(jié)并分享我在實(shí)現(xiàn)過程中踩過的坑和總結(jié)的經(jīng)驗(yàn)。2. 項(xiàng)目整體架構(gòu)與設(shè)計(jì)哲學(xué)2.1 模塊化設(shè)計(jì)六個(gè)實(shí)驗(yàn)的遞進(jìn)關(guān)系這個(gè)項(xiàng)目的結(jié)構(gòu)并非隨意堆砌而是嚴(yán)格遵循了編譯器前端經(jīng)典的處理流程并對應(yīng)了課程實(shí)驗(yàn)的六個(gè)階段性目標(biāo)。理解這個(gè)遞進(jìn)關(guān)系是讀懂整個(gè)項(xiàng)目的關(guān)鍵。第一層詞法分析器Scanner/Lexer這是所有工作的起點(diǎn)。它的任務(wù)無比純粹讀入源代碼字符串忽略空格、換行、注釋等無關(guān)內(nèi)容識別出一個(gè)個(gè)具有獨(dú)立意義的“單詞”即“詞法單元”Token。例如對于語句int a 10 b;詞法分析器會輸出序列KEYWORD, int、ID, a、OPERATOR, 、INTEGER, 10、OPERATOR, 、ID, b、DELIMITER, ;。它為后續(xù)所有分析提供了原材料。在這個(gè)項(xiàng)目中詞法分析器被設(shè)計(jì)為一個(gè)獨(dú)立的類提供getNextToken()這樣的接口供語法分析器驅(qū)動(dòng)。第二層語法分析器Parser——多種方法的實(shí)踐這是項(xiàng)目的核心和難點(diǎn)。語法分析器接收詞法單元流根據(jù)預(yù)定義的語法規(guī)則通常用BNF范式表示檢查其結(jié)構(gòu)是否符合規(guī)范并通常構(gòu)建出一棵“語法分析樹”。課程實(shí)驗(yàn)的精妙之處在于它要求我們用四種不同的方法來實(shí)現(xiàn)語法分析每一種都對應(yīng)著編譯原理理論中的一個(gè)重要流派遞歸下降分析法最直觀的方法。為語法規(guī)則的每一個(gè)非終結(jié)符編寫一個(gè)遞歸函數(shù)。這種方法手工編寫方便特別適合表達(dá)式、控制語句等結(jié)構(gòu)但它要求文法必須是LL(1)的且左遞歸必須消除。LL(1)分析法一種表驅(qū)動(dòng)的自頂向下分析方法。需要預(yù)先計(jì)算FIRST集和FOLLOW集并構(gòu)造LL(1)預(yù)測分析表。分析器根據(jù)當(dāng)前棧頂符號和輸入符號查表決定使用哪條產(chǎn)生式。它比遞歸下降更形式化是理解自頂向下分析自動(dòng)化的關(guān)鍵。算符優(yōu)先分析法專門為表達(dá)式語法設(shè)計(jì)的一種簡單、高效的自底向上分析方法。它不嚴(yán)格基于語法樹而是通過比較相鄰運(yùn)算符的優(yōu)先級來決定歸約順序適合快速處理表達(dá)式但文法適用范圍窄。SLR(1)分析法一種自底向上的、能力更強(qiáng)的LR分析方法。需要構(gòu)造項(xiàng)目集規(guī)范族和SLR(1)分析表。它能處理更廣泛的文法是實(shí)踐中許多編譯器生成器如Yacc的理論基礎(chǔ)。實(shí)現(xiàn)SLR(1)分析器是對LR分析理論最深入的實(shí)踐。第三層語法制導(dǎo)翻譯與中間代碼生成這是語法分析的升華。我們不再僅僅滿足于檢查語法是否正確還要賦予語法結(jié)構(gòu)以“語義”。語法制導(dǎo)翻譯將“屬性”如類型、值、代碼地址與文法符號關(guān)聯(lián)并在語法分析過程中通過嵌入在遞歸函數(shù)或分析動(dòng)作中的代碼計(jì)算這些屬性。最終產(chǎn)出不再是樹而是一種中間表示常見的有三地址碼如t1 10 b,a t1或抽象語法樹的某種線性化形式。這個(gè)模塊將前端分析與后端優(yōu)化、代碼生成連接起來。2.2 技術(shù)選型為什么是Java你可能會問經(jīng)典的編譯原理教材多用C工業(yè)級的編譯器多用C或Rust為什么這個(gè)項(xiàng)目選擇Java這背后有幾點(diǎn)非常實(shí)際的考量教學(xué)友好性Java語言本身相對簡潔內(nèi)存管理自動(dòng)化讓學(xué)生能將精力集中于算法邏輯本身而不是指針、內(nèi)存泄漏等底層細(xì)節(jié)。其豐富的標(biāo)準(zhǔn)庫尤其是集合框架ArrayList,HashMap非常適合實(shí)現(xiàn)符號表、分析表等數(shù)據(jù)結(jié)構(gòu)?？焖僭湍芰ava的面向?qū)ο筇匦宰屇K化設(shè)計(jì)變得自然。我們可以輕松地定義Token、Production、LRItem等類并通過繼承和多態(tài)來管理不同的分析器。編寫和調(diào)試效率高?？缙脚_與可交付性“一次編寫到處運(yùn)行”的特性使得這份代碼可以在任何裝有JVM的機(jī)器上編譯運(yùn)行極大方便了同學(xué)之間的交流、以及老師的統(tǒng)一評測。最終打包成一個(gè)清晰的、包含所有依賴的工程如Maven或Gradle項(xiàng)目交付體驗(yàn)非常好。與課程理論的契合度編譯原理中的很多概念如狀態(tài)集合、表驅(qū)動(dòng)用Java的集合類來實(shí)現(xiàn)非常直觀。構(gòu)造LR(0)項(xiàng)目集規(guī)范族時(shí)對項(xiàng)目集合的哈希去重、比較等操作用Java寫起來比C流暢得多。注意選擇Java并不意味著犧牲性能或深度。這個(gè)項(xiàng)目的目標(biāo)是教學(xué)與實(shí)踐而非打造產(chǎn)品級編譯器。用Java清晰地實(shí)現(xiàn)出LL(1)或SLR(1)分析表的構(gòu)造算法其教育意義遠(yuǎn)大于用C寫一個(gè)模糊難懂的版本。事實(shí)上許多現(xiàn)代語言的處理工具如Antlr也是用Java編寫的。2.3 代碼結(jié)構(gòu)導(dǎo)覽項(xiàng)目的目錄結(jié)構(gòu)大致如下體現(xiàn)了清晰的模塊分離思想compiler-frontend-experiments/ ├── src/ │ ├── lexer/ # 詞法分析模塊 │ │ ├── Token.java # 詞法單元類類型值行號 │ │ ├── TokenType.java # 詞法單元類型枚舉INT, ID, PLUS等 │ │ └── Lexer.java # 詞法分析器核心類 │ ├── parser/ # 語法分析模塊 │ │ ├── rd/ # 遞歸下降分析器 │ │ ├── ll1/ # LL(1)分析器含F(xiàn)IRST/FOLLOW集計(jì)算 │ │ ├── op/ # 算符優(yōu)先分析器 │ │ └── slr/ # SLR(1)分析器含項(xiàng)目集、ACTION/GOTO表構(gòu)造 │ ├── grammar/ # 文法定義相關(guān) │ │ ├── Production.java # 產(chǎn)生式類 │ │ └── Grammar.java # 文法管理類從文件讀取計(jì)算閉包等 │ ├── symbol/ # 符號表管理 │ │ └── SymbolTable.java │ ├── sdts/ # 語法制導(dǎo)翻譯與中間代碼生成 │ │ ├── Attribute.java # 屬性類 │ │ ├── Quadruple.java # 四元式中間代碼表示 │ │ └── SDTVisitor.java # 基于訪問者模式的語法制導(dǎo)翻譯器 │ └── main/ # 主程序入口用于測試各個(gè)模塊 │ └── CompilerFrontendDemo.java ├── grammars/ # 存放不同分析器測試用的文法文件 │ ├── expression_grammar.txt │ └── slr_grammar.txt ├── test_cases/ # 測試用例正確的和錯(cuò)誤的 │ ├── source_code.simple │ └── ... └── README.md # 項(xiàng)目說明構(gòu)建與運(yùn)行指南這種結(jié)構(gòu)保證了每個(gè)實(shí)驗(yàn)?zāi)K的獨(dú)立性你可以單獨(dú)運(yùn)行詞法分析器看輸出也可以單獨(dú)測試SLR(1)分析器更可以串聯(lián)起整個(gè)流程。3. 核心模塊深度解析與實(shí)現(xiàn)要點(diǎn)3.1 詞法分析器編譯器視角下的“分詞工具”詞法分析器是編譯器的“眼睛”。它的實(shí)現(xiàn)看似簡單但健壯性要求極高。核心是有限自動(dòng)機(jī)DFA的思想。我們并沒有顯式地畫出狀態(tài)轉(zhuǎn)換圖而是在代碼中用條件分支邏輯隱式地實(shí)現(xiàn)了一個(gè)DFA。實(shí)現(xiàn)核心Lexer.java中的getNextToken()方法這個(gè)方法是一個(gè)大的循環(huán)每次調(diào)用都從輸入流中讀取字符直到識別出一個(gè)完整的Token。public Token getNextToken() { // 跳過空白字符空格、制表符、換行 skipWhitespace(); if (pos source.length()) { return new Token(TokenType.EOF, , line); } char currentChar source.charAt(pos); // 識別標(biāo)識符和關(guān)鍵字以字母或下劃線開頭 if (Character.isLetter(currentChar) || currentChar _) { return parseIdentifierOrKeyword(); } // 識別數(shù)字字面量 else if (Character.isDigit(currentChar)) { return parseNumber(); } // 識別運(yùn)算符和分隔符 else if (isOperator(currentChar)) { return parseOperator(); } // 識別字符串字面量 else if (currentChar \) { return parseString(); } // 處理注釋 else if (currentChar / peekNextChar() /) { skipSingleLineComment(); return getNextToken(); // 遞歸調(diào)用跳過注釋后繼續(xù)識別 } // ... 其他情況處理 }parseIdentifierOrKeyword函數(shù)會持續(xù)讀入字母數(shù)字形成一個(gè)字符串然后去關(guān)鍵字表中查找。這里的關(guān)鍵是關(guān)鍵字表的組織。我使用了一個(gè)HashSetString來存儲所有關(guān)鍵字識別出標(biāo)識符后用keywords.contains(word)來判斷是否是關(guān)鍵字。這種方式比一堆if-else判斷高效且易于維護(hù)。實(shí)操心得與避坑指南行號與列號的維護(hù)為了在報(bào)錯(cuò)時(shí)能精確定位必須在讀字符的過程中仔細(xì)維護(hù)行號和列號。每次遇到\n行號加1列號重置。這個(gè)細(xì)節(jié)很容易出錯(cuò)特別是在處理跨多行的注釋或字符串時(shí)。向前看字符Lookahead的必要性像、、!這樣的雙字符運(yùn)算符以及/*注釋的開始都需要預(yù)讀下一個(gè)字符才能確定。peekNextChar()方法只看不移動(dòng)指針在這里至關(guān)重要。錯(cuò)誤恢復(fù)策略簡單的詞法分析器在遇到無法識別的字符如、$時(shí)可能直接拋出異常終止。一個(gè)更健壯的實(shí)現(xiàn)應(yīng)該記錄錯(cuò)誤“非法字符”然后跳過該字符嘗試?yán)^續(xù)分析下一個(gè)可能的Token這樣能一次報(bào)告所有詞法錯(cuò)誤。字符串和字符字面量的處理要正確處理轉(zhuǎn)義字符如\n、\t、\。這需要一個(gè)小型的轉(zhuǎn)義字符映射表。3.2 遞歸下降語法分析最直觀的“手工”解析遞歸下降分析法將文法規(guī)則直接映射為代碼中的遞歸函數(shù)調(diào)用非常符合人類的直覺。例如對于一個(gè)簡單的算術(shù)表達(dá)式文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id | num我們可以編寫如下函數(shù)偽代碼void parseE() { parseT(); parseEPrime(); } void parseEPrime() { if (currentToken.type PLUS) { match(PLUS); // 消耗掉‘’ parseT(); parseEPrime(); } // 否則對應(yīng) ε什么都不做 } void match(TokenType expected) { if (currentToken.type expected) { currentToken lexer.getNextToken(); } else { throw new SyntaxError(Expected expected , but found currentToken.type); } }實(shí)現(xiàn)要點(diǎn)消除左遞歸上述文法是已經(jīng)消除了左遞歸的。原始文法E - E T會導(dǎo)致函數(shù)parseE()無限遞歸調(diào)用自身。必須先將文法轉(zhuǎn)換為等價(jià)的非左遞歸形式這是使用遞歸下降的前提。處理 ε 產(chǎn)生式對應(yīng)函數(shù)中的空分支通常通過判斷當(dāng)前Token是否在某個(gè)集合如FOLLOW集中來決定是否選擇該分支?；厮輪栴}純遞歸下降在遇到不確定選擇時(shí)可能需要回溯效率低。因此我們通常使用預(yù)測性遞歸下降即通過查看當(dāng)前Token的FIRST集來唯一確定使用哪條產(chǎn)生式這就要求文法是LL(1)的。踩坑記錄我曾在一個(gè)if-else語句的文法上栽過跟頭。文法規(guī)則是Stmt - if ( Expr ) Stmt else Stmt | ...。在解析if (x0) if (y0) a1; else b1;時(shí)else應(yīng)該匹配第二個(gè)if還是第一個(gè)if這就是經(jīng)典的“懸空else”問題。純遞歸下降會將其匹配到最近的if這符合大多數(shù)語言的語義但需要在設(shè)計(jì)文法時(shí)就意識到這一點(diǎn)。我的經(jīng)驗(yàn)是為這種有歧義的結(jié)構(gòu)編寫遞歸下降函數(shù)時(shí)要特別小心函數(shù)返回的時(shí)機(jī)和else的匹配邏輯。3.3 LL(1)分析法從手工到自動(dòng)化的橋梁LL(1)分析將遞歸下降的“預(yù)測”過程表格化、自動(dòng)化。實(shí)現(xiàn)一個(gè)LL(1)分析器分為兩個(gè)主要階段分析表構(gòu)造和表驅(qū)動(dòng)分析。第一階段計(jì)算FIRST集和FOLLOW集這是整個(gè)LL(1)分析中最容易出錯(cuò)的理論計(jì)算部分必須通過代碼精確實(shí)現(xiàn)。FIRST(α)串α能推導(dǎo)出的開頭終結(jié)符集合。計(jì)算時(shí)需遞歸處理特別是當(dāng)非終結(jié)符能推出ε時(shí)需要繼續(xù)看后面的符號。FOLLOW(A)緊跟非終結(jié)符A后面出現(xiàn)的終結(jié)符集合。計(jì)算時(shí)需要遍歷所有產(chǎn)生式尋找A的出現(xiàn)位置并考慮其后的串的FIRST集如果后面的串能推出ε還要并入產(chǎn)生式左部符號的FOLLOW集。我在LL1TableBuilder類中實(shí)現(xiàn)了這兩個(gè)集合的計(jì)算。算法本質(zhì)上是圖上的不動(dòng)點(diǎn)迭代反復(fù)應(yīng)用規(guī)則直到所有集合不再變化。這里一定要用while循環(huán)配合一個(gè)changed標(biāo)志確保計(jì)算到收斂。第二階段構(gòu)造預(yù)測分析表規(guī)則是對每條產(chǎn)生式A - α將(A, a)對應(yīng)的表項(xiàng)填入A - α其中終結(jié)符a屬于FIRST(α)如果ε在FIRST(α)中則對FOLLOW(A)中的每個(gè)終結(jié)符b也將(A, b)填入A - α。 構(gòu)造完成后必須檢查每個(gè)表項(xiàng)是否最多只有一個(gè)產(chǎn)生式否則文法就不是LL(1)的。第三階段表驅(qū)動(dòng)分析使用一個(gè)分析棧。初始時(shí)棧底為$棧頂為文法開始符號。根據(jù)棧頂符號X和當(dāng)前輸入符號a若X a $分析成功。若X是終結(jié)符且X a彈出X消耗輸入a。若X是非終結(jié)符查表M[X, a]。如果為空報(bào)錯(cuò)否則將表項(xiàng)中的產(chǎn)生式右部符號逆序壓入棧中保證最左推導(dǎo)。// 簡化版分析循環(huán) while (!stack.isEmpty()) { Symbol top stack.peek(); Token current inputToken; if (top.isTerminal()) { if (top.equals(current.type)) { stack.pop(); advanceInput(); } else { error(); } } else { Production prod parsingTable.get(top, current.type); if (prod null) { error(); } else { stack.pop(); // 將產(chǎn)生式右部逆序壓棧 for (int i prod.rhs.size() - 1; i 0; i--) { if (!prod.rhs.get(i).isEpsilon()) { // 不壓入 ε stack.push(prod.rhs.get(i)); } } } } }提示調(diào)試LL(1)分析器時(shí)最有效的方法是打印出每一步的分析棧、剩余輸入和將要執(zhí)行的動(dòng)作。這能幫你清晰地看到推導(dǎo)過程快速定位是FIRST/FOLLOW集算錯(cuò)了還是分析表填錯(cuò)了。3.4 算符優(yōu)先分析法快速處理表達(dá)式的利器算符優(yōu)先分析跳出了嚴(yán)格的語法樹框架它不關(guān)心完整的語法結(jié)構(gòu)只關(guān)注運(yùn)算符之間的優(yōu)先級關(guān)系。它需要兩張表優(yōu)先關(guān)系表,,。核心思想比較棧頂運(yùn)算符θ1和當(dāng)前輸入運(yùn)算符θ2的優(yōu)先關(guān)系。若θ1 θ2θ2入棧移進(jìn)。若θ1 θ2通常只有括號配對時(shí)出現(xiàn)脫括號彈出。若θ1 θ2進(jìn)行歸約在棧頂尋找一個(gè)最左的形如非終結(jié)符 運(yùn)算符 非終結(jié)符的序列將其歸約為一個(gè)非終結(jié)符。實(shí)現(xiàn)難點(diǎn)優(yōu)先關(guān)系的確定優(yōu)先關(guān)系不是任意的需要根據(jù)文法推導(dǎo)。對于簡單的表達(dá)式文法我們可以手動(dòng)定義。例如對于、-、*、/、(、)通常定義、-優(yōu)先級低于*、/。相同優(yōu)先級的運(yùn)算符左結(jié)合。(的優(yōu)先級低于所有運(yùn)算符但在棧內(nèi)時(shí)(的優(yōu)先級極低遇到)時(shí)需要找到匹配的(。 在我的實(shí)現(xiàn)中我使用了一個(gè)二維枚舉數(shù)組Relation[][]來存儲這個(gè)關(guān)系表。實(shí)操過程分析器維護(hù)一個(gè)符號棧。棧中交替存放著操作數(shù)和運(yùn)算符實(shí)際上為了簡化我們只存運(yùn)算符和作為分隔符的非終結(jié)符操作數(shù)由另一個(gè)值棧管理。算法流程是一個(gè)經(jīng)典的移進(jìn)-歸約循環(huán)但歸約動(dòng)作不是基于產(chǎn)生式而是基于“可歸約串”的模式匹配。while (輸入未結(jié)束) { a 當(dāng)前輸入符號; if (棧頂是操作數(shù) a 是操作數(shù)) { 錯(cuò)誤 // 不允許兩個(gè)操作數(shù)相鄰 } if (棧頂是終結(jié)符 θ) { 關(guān)系 優(yōu)先關(guān)系表[θ][a]; if (關(guān)系 LESS) { // θ a 移進(jìn) a; } else if (關(guān)系 GREATER) { // θ a 進(jìn)行歸約; // 歸約后棧頂變?yōu)橐粋€(gè)非終結(jié)符N // 此時(shí)需要比較新的棧頂符號可能是運(yùn)算符和 a 的關(guān)系 } else if (關(guān)系 EQUAL) { // 通常是 ( ) 脫括號彈出 (); 消耗輸入 ); } else { 錯(cuò)誤 // 優(yōu)先關(guān)系未定義語法錯(cuò)誤 } } else { // 棧頂是非終結(jié)符將其視為一個(gè)整體操作數(shù)直接移進(jìn)輸入符號a 移進(jìn) a; } }算符優(yōu)先分析速度快但能力有限無法處理復(fù)雜的非運(yùn)算符語法結(jié)構(gòu)。它是我在項(xiàng)目中實(shí)現(xiàn)的“特化工具”專門用于演示如何高效處理表達(dá)式。3.5 SLR(1)分析法自底向上分析的經(jīng)典實(shí)踐SLR(1)是LR分析家族中相對簡單但能力足夠強(qiáng)的一種。實(shí)現(xiàn)一個(gè)SLR(1)分析器是編譯原理實(shí)驗(yàn)的“畢業(yè)設(shè)計(jì)”它綜合了DFA構(gòu)造、集合運(yùn)算和表驅(qū)動(dòng)分析。第一步構(gòu)造LR(0)項(xiàng)目集規(guī)范族這是最復(fù)雜的一步。一個(gè)LR(0)項(xiàng)目形如A - α·β圓點(diǎn)表示分析進(jìn)度。我們從初始項(xiàng)目S - ·S開始通過計(jì)算閉包Closure和讀符號轉(zhuǎn)移Goto函數(shù)逐步構(gòu)造出所有的狀態(tài)項(xiàng)目集。閉包操作如果項(xiàng)目是A - α·Bβ那么對于B的所有產(chǎn)生式B - γ要把B - ·γ加入閉包。這是一個(gè)遞歸過程。Goto操作對于狀態(tài)I和文法符號XGoto(I, X)是所有形如[A - αX·β]的項(xiàng)目的集合其中[A - α·Xβ]在I中。然后再對這個(gè)集合求閉包。我使用了一個(gè)ListLR0State來存儲所有狀態(tài)并用一個(gè)MapPairLR0State, Symbol, LR0State來記錄Goto關(guān)系。為了避免生成重復(fù)狀態(tài)每次生成新狀態(tài)時(shí)都要與已有狀態(tài)比較項(xiàng)目集是否相等。第二步構(gòu)造SLR(1)分析表對于每個(gè)狀態(tài)i移進(jìn)動(dòng)作ACTION[i, a] sj如果項(xiàng)目[A - α·aβ]在狀態(tài)i中且a是終結(jié)符且Goto(i, a) j則ACTION[i, a] 移進(jìn)j。歸約動(dòng)作ACTION[i, a] rk如果項(xiàng)目[A - α·]在狀態(tài)i中則對所有a ∈ FOLLOW(A)ACTION[i, a] 按產(chǎn)生式k歸約。這里用到了FOLLOW集來解決沖突這也是SLR(1)中“S”的由來。接受動(dòng)作如果項(xiàng)目[S - S·]在狀態(tài)i中則ACTION[i, $] 接受。GOTO表如果Goto(i, X) j且X是非終結(jié)符則GOTO[i, X] j。第三步表驅(qū)動(dòng)分析分析器同樣使用一個(gè)狀態(tài)棧和一個(gè)符號棧。stack.push(initialState); // 狀態(tài)棧 symbolStack.push(END_MARKER); // 符號棧 Token lookahead lexer.getNextToken(); while (true) { int state stack.peek(); Action action actionTable[state][lookahead.type]; if (action.type SHIFT) { // 移進(jìn) stack.push(action.number); // 新狀態(tài) symbolStack.push(lookahead); lookahead lexer.getNextToken(); } else if (action.type REDUCE) { // 歸約 Production prod productions[action.number]; // 從棧中彈出右部符號及其對應(yīng)的狀態(tài) for (int i 0; i prod.rhs.size(); i) { stack.pop(); symbolStack.pop(); } // 獲取歸約后的左部符號A Symbol lhs prod.lhs; // 根據(jù)歸約前的狀態(tài)和新符號A查找GOTO表得到新狀態(tài) int newState gotoTable[stack.peek()][lhs]; // 壓入新狀態(tài)和A stack.push(newState); symbolStack.push(lhs); // 可以在這里執(zhí)行語義動(dòng)作生成四元式 executeSemanticAction(prod); } else if (action.type ACCEPT) { // 接受成功 break; } else { // 報(bào)錯(cuò) reportSyntaxError(state, lookahead); // 錯(cuò)誤恢復(fù)... } }經(jīng)驗(yàn)之談?wù){(diào)試SLR(1)分析器調(diào)試SLR(1)分析器極具挑戰(zhàn)性。我的建議是可視化狀態(tài)機(jī)將構(gòu)造出的LR(0)項(xiàng)目集規(guī)范族和Goto關(guān)系以圖的形式打印出來。這能幫你直觀地檢查狀態(tài)是否完整轉(zhuǎn)移是否正確。分步跟蹤分析過程像調(diào)試LL(1)一樣打印每一步的狀態(tài)棧、符號棧、剩余輸入和即將執(zhí)行的動(dòng)作。這是定位分析表錯(cuò)誤的唯一有效方法。關(guān)注歸約-歸約和移進(jìn)-歸約沖突如果文法不是SLR(1)的構(gòu)造表時(shí)會在同一表項(xiàng)出現(xiàn)多個(gè)動(dòng)作。你需要分析沖突原因是文法有二義性還是需要更強(qiáng)的LR(1)或LALR(1)分析。在實(shí)驗(yàn)項(xiàng)目中我們通常通過修改文法來消除沖突。FOLLOW集的計(jì)算務(wù)必準(zhǔn)確SLR(1)利用FOLLOW集來縮小歸約動(dòng)作的適用范圍。如果FOLLOW集算大了會導(dǎo)致無效的歸約算小了會導(dǎo)致該歸約時(shí)找不到動(dòng)作。這是SLR(1)分析器最常見的錯(cuò)誤來源之一。3.6 語法制導(dǎo)翻譯與中間代碼生成賦予語法以意義語法分析只解決了“結(jié)構(gòu)對不對”的問題而語法制導(dǎo)翻譯SDT要解決“做什么”的問題。我們選擇在SLR(1)分析器進(jìn)行歸約時(shí)執(zhí)行相應(yīng)的語義動(dòng)作從而生成中間代碼。語義動(dòng)作的設(shè)計(jì)我們?yōu)槊總€(gè)產(chǎn)生式關(guān)聯(lián)一段語義子程序。這些子程序可以訪問和修改與文法符號相關(guān)的屬性。最常見的屬性是綜合屬性自底向上傳遞如表達(dá)式的值、類型有時(shí)也需要繼承屬性自頂向下傳遞如變量的聲明類型。在這個(gè)項(xiàng)目中我們主要實(shí)現(xiàn)三地址碼的生成。三地址碼的基本形式是x y op z。我們用一個(gè)Quadruple四元式類來表示包含操作符op、兩個(gè)操作數(shù)arg1、arg2和一個(gè)結(jié)果result。實(shí)現(xiàn)模式在SLR(1)分析器的歸約動(dòng)作中我們根據(jù)歸約所用的產(chǎn)生式編號調(diào)用對應(yīng)的語義例程。private void executeSemanticAction(int productionIndex) { switch (productionIndex) { case 0: // S - E // E的屬性比如它的值存放的臨時(shí)變量名就是整個(gè)S的結(jié)果 break; case 1: // E - E T String temp newTemp(); // 生成新的臨時(shí)變量如t1, t2... String eAddr getAttribute(stack, -3); // 獲取E的屬性地址 String tAddr getAttribute(stack, -1); // 獲取T的屬性 emit(new Quadruple(, eAddr, tAddr, temp)); // 生成四元式temp eAddr tAddr setAttribute(stack, -3, temp); // 將新生成的臨時(shí)變量作為這個(gè)E的綜合屬性 break; case 2: // E - T // 直接傳遞屬性 break; case 3: // T - T * F // 類似加法生成乘法四元式 break; // ... 其他產(chǎn)生式 case 10: // F - id String idName getTokenValue(stack, -1); // 獲取標(biāo)識符的名字 setAttribute(stack, -1, idName); // 屬性就是標(biāo)識符的名字本身 break; } }這里的關(guān)鍵是屬性棧的管理。我們需要一個(gè)與符號棧平行的屬性棧每當(dāng)符號入?；虺鰲r(shí)其對應(yīng)的屬性也同步操作。在歸約時(shí)我們從屬性棧中彈出右部符號的屬性計(jì)算得到左部符號的屬性再壓入棧中。符號表的管理為了生成正確的代碼我們必須知道標(biāo)識符的類型、存儲位置等信息。這就需要符號表。在分析到聲明語句如int a;時(shí)我們將標(biāo)識符a及其類型信息插入符號表。在后續(xù)表達(dá)式中使用a時(shí)就從符號表中查找其信息確保使用前已聲明靜態(tài)語義檢查并獲取其類型以進(jìn)行可能的類型轉(zhuǎn)換。中間代碼的優(yōu)化簡單示例在生成四元式時(shí)我們可以進(jìn)行一些簡單的優(yōu)化。例如對于常量表達(dá)式3 5我們可以在語義動(dòng)作中直接計(jì)算出結(jié)果8并生成t1 8而不是生成t1 3 5。這稱為常量折疊是編譯器優(yōu)化中最基本的一步。4. 項(xiàng)目集成、測試與常見問題排查4.1 如何串聯(lián)六個(gè)模塊進(jìn)行端到端測試單獨(dú)測試每個(gè)模塊是基礎(chǔ)但真正的成就感來自于將它們串聯(lián)起來看著一段簡單的源代碼最終變成一串三地址碼。我編寫了一個(gè)集成測試的主類CompilerFrontendDemo它提供了命令行接口允許用戶選擇不同的分析器并指定源代碼文件。集成流程如下初始化讀取文法文件初始化對應(yīng)的分析器如SLR(1)分析器需要預(yù)先構(gòu)造分析表。詞法分析將源代碼文件送入詞法分析器得到一個(gè)Token流。可以在這里選擇是否打印Token序列以供調(diào)試。語法分析與翻譯將Token流送入選定的語法分析器如SLR(1)分析器。該分析器在工作的同時(shí)會驅(qū)動(dòng)語法制導(dǎo)翻譯模塊在歸約時(shí)生成四元式。輸出結(jié)果如果源代碼語法正確則打印“語法分析成功”并輸出生成的三地址碼序列。如果中途發(fā)現(xiàn)錯(cuò)誤則輸出詳細(xì)的錯(cuò)誤信息包括錯(cuò)誤類型、位置和可能的修正建議。一個(gè)典型的測試用例test.simple可能如下int main() { int a, b, c; a 10; b 20; c a b * 2; print(c); }期望的中間代碼輸出可能類似于t0 10 a t0 t1 20 b t1 t2 2 t3 b * t2 t4 a t3 c t4 param c call print, 14.2 常見編譯錯(cuò)誤、警告與排查技巧在實(shí)現(xiàn)和測試過程中你會遇到各種各樣的錯(cuò)誤。下面是一個(gè)快速排查指南問題現(xiàn)象可能原因排查步驟與解決方案詞法分析階段識別標(biāo)識符時(shí)吞掉了后面的數(shù)字。parseIdentifier函數(shù)沒有在遇到非字母數(shù)字字符時(shí)及時(shí)停止。檢查讀取字符的循環(huán)條件確保在Character.isLetterOrDigit()為 false 時(shí)跳出。字符串字面量處理出錯(cuò)轉(zhuǎn)義字符\n被當(dāng)成兩個(gè)字符。沒有實(shí)現(xiàn)轉(zhuǎn)義字符的邏輯。在parseString函數(shù)中當(dāng)讀到反斜杠\時(shí)預(yù)讀下一個(gè)字符根據(jù)轉(zhuǎn)義映射表如\n - 換行符進(jìn)行轉(zhuǎn)換。遞歸下降/LL(1)階段陷入無限遞歸。文法存在左遞歸未消除。檢查文法使用標(biāo)準(zhǔn)方法如引入新的非終結(jié)符消除直接和間接左遞歸。預(yù)測分析時(shí)選擇錯(cuò)誤產(chǎn)生式。FIRST/FOLLOW集計(jì)算錯(cuò)誤或文法不是LL(1)。1. 打印并仔細(xì)核對每個(gè)非終結(jié)符的FIRST和FOLLOW集。2. 檢查預(yù)測分析表是否有沖突項(xiàng)。如有可能需要改寫文法。算符優(yōu)先階段對表達(dá)式a b * c歸約順序錯(cuò)誤。算符優(yōu)先關(guān)系表定義錯(cuò)誤*的優(yōu)先級未高于。重新檢查并修正優(yōu)先關(guān)系表確保符合算術(shù)規(guī)則。遇到括號匹配錯(cuò)誤。在優(yōu)先關(guān)系表中(和)的關(guān)系未正確定義或棧內(nèi)(的特殊優(yōu)先級處理不當(dāng)。確保(在棧外時(shí)優(yōu)先級最低在棧內(nèi)時(shí)優(yōu)先級特殊(和)相遇時(shí)是“”關(guān)系并脫括號。SLR(1)階段構(gòu)造項(xiàng)目集規(guī)范族時(shí)程序死循環(huán)。Closure或Goto函數(shù)實(shí)現(xiàn)有誤導(dǎo)致不斷生成“新”的等價(jià)狀態(tài)。1. 檢查項(xiàng)目相等性的判斷邏輯比較核心項(xiàng)目和閉包項(xiàng)目。2. 在生成新狀態(tài)時(shí)打印其內(nèi)容與已有狀態(tài)對比。分析表出現(xiàn)“移進(jìn)-歸約”沖突。文法不是SLR(1)的。FOLLOW集可能無法解決沖突。1. 分析沖突狀態(tài)和符號理解沖突原因。2. 嘗試修改文法例如引入新的非終結(jié)符來推遲歸約。3. 高級考慮實(shí)現(xiàn)LR(1)或LALR(1)分析器。分析過程在某個(gè)狀態(tài)報(bào)“未定義動(dòng)作”。ACTION/GOTO表構(gòu)造不完整存在空白項(xiàng)。檢查構(gòu)造表的算法邏輯確保對所有狀態(tài)和所有終結(jié)符/非終結(jié)符都進(jìn)行了處理。特別是GOTO表要對所有非終結(jié)符進(jìn)行填寫。語法制導(dǎo)翻譯階段生成的中間代碼中臨時(shí)變量數(shù)目爆炸。每次運(yùn)算都生成新臨時(shí)變量沒有復(fù)用。實(shí)現(xiàn)簡單的臨時(shí)變量管理策略例如在一個(gè)基本塊內(nèi)如果一個(gè)臨時(shí)變量的值不再被使用可以復(fù)用其名字。屬性棧與符號棧不同步。在移進(jìn)或歸約時(shí)屬性棧的壓入彈出操作有遺漏或錯(cuò)誤。在每一步分析動(dòng)作后打印兩個(gè)棧的內(nèi)容進(jìn)行比對確保它們的高度和對應(yīng)關(guān)系始終一致。符號表查找失敗。1. 標(biāo)識符未聲明就使用。2. 作用域處理錯(cuò)誤本實(shí)驗(yàn)通常只有全局作用域。1. 在表達(dá)式中遇到標(biāo)識符時(shí)先在符號表中查找若未找到則報(bào)“未定義變量”錯(cuò)誤。2. 確保在聲明語句中正確將標(biāo)識符插入符號表。4.3 性能優(yōu)化與擴(kuò)展思考雖然這是一個(gè)教學(xué)項(xiàng)目但思考如何優(yōu)化和擴(kuò)展它能極大提升你的工程能力。文法抽象與解析當(dāng)前文法是硬編碼在代碼里或讀自文件?？梢栽O(shè)計(jì)一個(gè)更通用的文法描述語言類似Yacc的規(guī)格說明并編寫一個(gè)“分析器的分析器”來讀取它自動(dòng)構(gòu)造分析表。這會讓你的項(xiàng)目變成一個(gè)“編譯器生成器”的雛形。錯(cuò)誤恢復(fù)機(jī)制目前的錯(cuò)誤處理大多是遇到第一個(gè)錯(cuò)誤就停止?？梢詫?shí)現(xiàn)簡單的錯(cuò)誤恢復(fù)策略如恐慌模式跳過一些Token直到同步詞法單元或短語層恢復(fù)插入/刪除Token使分析器能報(bào)告更多錯(cuò)誤。更豐富的中間表示除了三地址碼可以實(shí)現(xiàn)抽象語法樹AST。AST能保留更多的結(jié)構(gòu)信息對于后續(xù)的優(yōu)化非常有利?？梢栽谶f歸下降分析器中直接構(gòu)建AST。面向更復(fù)雜的語言特性嘗試支持?jǐn)?shù)組、結(jié)構(gòu)體、函數(shù)調(diào)用等更復(fù)雜的語法和語義。這會極大地挑戰(zhàn)你的符號表設(shè)計(jì)需要支持類型系統(tǒng)、作用域嵌套和中間代碼生成能力如數(shù)組地址計(jì)算、函數(shù)調(diào)用規(guī)約。完成這六個(gè)實(shí)驗(yàn)?zāi)闶斋@的遠(yuǎn)不止是幾份能運(yùn)行的代碼。你獲得的是對編譯器前端工作流程的肌肉記憶級理解是對復(fù)雜算法如集合閉包、表構(gòu)造的工程化實(shí)現(xiàn)能力以及面對一個(gè)龐大系統(tǒng)時(shí)如何分模塊設(shè)計(jì)、編碼、調(diào)試和集成的完整經(jīng)驗(yàn)。這份源碼集合正是這段充滿挑戰(zhàn)又收獲頗豐的學(xué)習(xí)旅程的最佳見證。希望我的拆解和分享能幫助你更好地理解它并在此基礎(chǔ)上構(gòu)建出屬于你自己的、更強(qiáng)大的編譯工具。本文還有配套的精品資源點(diǎn)擊獲取