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