第一篇：編譯原理課程設計 LL遞歸下降分析器
仲愷農業技術學院
編譯原理課程設計
課程設計題目 ：LL(1)遞歸下降分析器
姓
名 ： 院（系）：
專業班級 ： 學
號 ：
指導教師 ：
設計日期 ：
目 錄
1、需求分析...................................................................................................1
2、概要設計...................................................................................................2
3、詳細設計...................................................................................................3
4、測試分析...................................................................................................8
5、用戶手冊...................................................................................................9
6、課程總結...................................................................................................9
7、參考文獻.................................................................................................10
題目：LL（1）遞歸下降分析器
1、需求分析
語法分析是編譯過程的核心部分。語法分析器的任務是識別和處理比單詞更大的語法單位。如：程序設計語言中的表達式，各種說明和語句乃至全部源程序，指出其中的語法錯誤；必要時，可生成內部形式，便于下一階段處理。
我們知道，語言的語法結構是用上下文無關文法描述的。按照語法分析樹的建立方法，我們可以粗略地把語法分析辦法分成兩類，一類是自上而下分析，另一類是自下而上分析法。而自上而下這種方法是帶“回溯”的，且存在許多困難和缺點。
首先，是文法的左遞歸性問題。一個文法是含有左遞歸的，如果存在非終結符P且?P?P?，含有左遞歸的文法使上述的自上而下的分析過程陷入無限循環。即，當試圖用P去匹配輸入串時，我們會發現，在沒有識別任何輸入符號的情況下，有得重新要求P去進行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。
其次，由于回溯，就碰到一大堆麻煩問題。如果我們走了一大段錯路，最后必須回頭，那么，就應把已經做的一大堆語義工作（指中間代碼產生工作和各種表格的簿記工作）推倒重來。這些事情既麻煩又費時間，所以，最好應設法消除回溯。
第三，在自上而下分析過程中，當一個非終結符用某一候選匹配成功時，這種成功可能僅是暫時的。
第四，當最終報告分析不成功時，我們難于知道輸入串中出錯的確切位置。
最后，由于帶回溯的自上而下分析實際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價極高。嚴重的低效使得這種分析法只有理論意義，而在實踐上價值不大。
由于上述原因，我們需要把原算術表達式改寫為LL(1)文法，LL(1)文法的文法條件如下： 文法不含左遞歸。
對于文法中每一個非終結符A的各個產生式的候選首集符兩兩不相交。即，若A??1|?2|?|?n，則FIRST??i??FIRST??j??? ?i?j?
對文法中的每個非終結符A，若它存在某個候選首符集包含ε，則FIRS?TA??FOLLO?WA???
LL(1)中的第一個L表示從左到右掃描輸入串，第二個L表示最左推導，1表示分析時每 一步只需向前查看一個符號。當一個文法滿足LL(1)條件時，我們就可以為它構造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。
2、概要設計
編程實現給定算術表達式的遞歸下降分析器。算術表達式文法如下： E-->E+T|E-T|T T-->T*F|T/F|F F-->(E)| i 首先改寫文法為LL(1)文法；然后為每一個非終結符，構造相應的遞歸過程，過程的名字表示規則左部的非終結符；過程體按規則右部符號串的順序編寫。
上述算法表達式文法屬于比較典型的遞歸下降語法分析。需要先將原算術表達式方法改寫為LL(1)文法為：
E-->TE’
E’-->+TE’|-TE’| ε T-->FT’
T’-->*FT’|/FT’| ε F-->(E)| i 然后再為每個非終結符設計一個對應的函數，通過各函數之間的遞歸調用從而實現遞歸下降語法分析的功能。
具體方法為：
（1）當遇到終結符a時，則編寫語句
If(當前讀到的輸入符號==a)讀入下一個輸入符號（2）當遇到非終結符A時，則編寫語句調用A()。（3）當遇到A-->ε規則時，則編寫語句
If(當前讀到的輸入符號不屬于Follow(A))error()（4）當某個非終結符的規則有多個候選式時，按LL(1)文法的條件能唯一地選擇一個候選式進行推導.遞歸下降子程序流程圖：
圖1遞歸下降子程序流程圖
3、詳細設計
#include
void main(){
}
void e(){
}
void e1()right=1;cout<<“--------------------”< } void t(){ } if(inputstream[temp]=='+'){ } else if(inputstream[temp]=='-'){ } else if(inputstream[temp]!='#'||inputstream[temp]!=')'){ } else right=0;cout<<“T'->^”< if(inputstream[temp]=='*'){ } else if(inputstream[temp]=='/'){ } else cout<<“T'->/FT'”< } void f(){ { } cout<<“T'->^”< } } else if(inputstream[temp]=='('){ cout<<“F->(E)”< } else } right=0;cout<<“F->(E)”< 4、測試分析 圖2 測試分析成功 圖3 測試分析失敗 5、用戶手冊 開發工具：visual c++ 6.0 開發環境：windows XP操作系統 運行環境：windows 9x,windows NT,Windows 2000,windows XP 注意：輸入時，程序最多只能接受50個字符，輸入完算術表達式后要以“#”號結束。 6、課程總結 通過一個星期的努力，終于把編譯原理課程設計給完成了。我覺得編譯原理這門課是一門非常難學的課程，它涉及文法、詞法分析、語法分析屬性文法和語義分析等等一系列內容，課本里的內容和定義也非常的抽象且枯燥。如果上課沒有好好的認真聽課，自己獨自學習就感到非常的吃力，而且效果也不好。本人因為上課無法做到打醒十二分專心聽課，經常會分神，所以學習的效果也不怎么好。這也給做編譯原理課程設計帶來了困難。本次課程設計，我選的課程設計題目是LL(1)遞歸下降分析器，這個題目涉及的內容有關課本第四章 語法分析——自上而下分析里面的內容。在開始動手對題目進行設計和編程之前，我重復的仔細認真的閱讀和理解課本第四章里面的內容，弄懂自上而下分析面臨的問題、何謂左遞歸，搞清楚如何消除左遞歸、如何消除回溯、提左因子，理解構造LL(1)文件需要什么條件。雖然這花費了一定的時間和精力，但那點付出也是值得的，通過復習讓我加深理解了有關自上而下語法分析的內容，而且也為用高級語言實現遞歸下降分析器帶來便利。 在用C++編程時，基本上沒有遇到什么困難，只需把所有遞歸過程都寫出就行了。但是要注意的是，在編寫代碼時，要根據LL(1)文法的工作原理去設計。通過本次課程設計清楚地了解到遞歸下降分析法的優缺點，其優點是簡單、直觀，易于構造分析程序。缺點是對文法要求高，必須是LL(1)文法，同時由于遞歸調用較多，影響分析器的效率。 課程設計雖然只有短短的一周，但讓我認識到學習好編譯原理，是對程序設計和編譯的一個很好的進化橋梁和奠基石。今后學習的日子還很長，希望通過這次編譯原理的課程設計，不僅對編程語言的進一步復習，還是對更深層次的學習作一個簡單的準備。編程的能力不是一朝一夕能鍛煉出來，堅持學習，堅持編程的學習，多看，多編是最好的學習和提高方法。 通過本次編譯原理課程設計，對面向對象的定義又有了更深一步的理解，對編譯程序有了進一步的理解，同時也認識到自己各方面知識的薄弱點，以后在學習中也能有針對性對這方面進行深入學習。學習更好的知識重在基礎，編譯原理的學習為我們提供非常好的橋梁和道路。 7、參考文獻 《編譯原理》 機械工業出版社出版 Alfred V.Aho Ravi Sethi Jeffrey D,Ullman著 李建中 姜守旭等譯 《程序設計語言 編譯原理（第三版）》 國防工業出版社出版 陳火旺 劉春林 譚慶平趙克佳 劉越 著 201X-201X學年第x學期 《編譯原理》課程設計報告 院 系： 計算機科學與技術 班 級： XX級XX 班 學生姓名： XXXXXX 學 號： XXXXXXXX 指導老師： XXXXXX 計算機科學與技術學院監制 20XX年X月 目錄 1.課程設計的目的 2.課程設計的內容和要求 3.問題分析和相關知識介紹 4.設計思路和關鍵問題及其解決方案 5.測試和結果分析 6.總結和心得體會 附件1：參考文獻 附件2：核心源代碼 1.課程設計的目的（1）編寫詞法分析器 （2）加深對詞法分析器工作原理的了解和認識 2.課程設計的內容和要求 編寫詞法分析器，詞法分析器能夠識別關系算符，詞法分析器能夠識別標識符和關鍵字，詞法分析器能夠識別無符號數。 3.問題分析和相關知識介紹 構成詞法分析器的一種簡單方法是用狀態轉換圖來描述源語言詞法記號的結構，然后手工把這種狀態轉換圖翻譯成為識別詞法記號的程序。詞法分析器的任務是把構成源程序的字符流翻譯成詞法記號流。 4.設計思路和關鍵問題及其解決方案 把自然語言構造成正規式，把正規式構造成有限自動機NFA，然后根據子集構造法把有限自動機構造成無限自動機DFA，根據極小化DFA狀態數算法把DFA構造成最簡DFA,其次根據最簡DFA畫出轉換表，根據轉換表畫出裝換圖，最后根據裝換圖就可以編寫詞法分析器。 5.測試和結果分析 6.總結和心得體會 通過本次試驗，不僅僅是我學會了C#基礎知識，而且還是我對詞法分析器有了更深入的認識，雖然在編寫詞法分析器過程中遇到了很多困難，例如：C#語言不熟悉，對此法分析器的工作原理分析的不透徹，但在老師和同學的幫助下，我有了很大的提高，通過不斷的努力最終順利的完成了課程設計，很感謝幫助我的XX同學和XX老師。附件1：參考文獻 《編譯原理（第2版）》 高等教育出版社； 《C#程序設計及應用教程（第2版）》 人民教育出版社。附件2： 1．Code文檔截圖 2.程序源代碼 using System;using System.Collections.Generic;using System.Text;using System.IO; namespace LexicalAnalysis { class Program { static string[] keys = { “static”, “true”, “return”, “string”, “Length”, “break”, “Console”, “WriteLine”, “bool”, “false”, “ture”, “void”, “if”, “else”, “while”, “int”, “float”, “for”, “enum”, “default”, “case”, “double”, “do” }; static List static List static List static List static List //數字，標識符，空白，關系符,運算符 static void Main(string[] args){ string[] date = File.ReadAllLines(@“d:code.txt”);//路徑，并存入data for(int i = 0;i < date.Length;i++){ Console.WriteLine(“第” +(i + 1)+ “行code: ” + date.GetValue(i));analysisByLine(date[i]); } //分別輸出存儲在四個List中的String Console.WriteLine(“關鍵字，輸入回車”);//輸出所有的關鍵字 Console.ReadLine(); foreach(string id in key){ Console.WriteLine(id); } Console.WriteLine(“標識符，輸入回車”);//輸出所有的標識符 Console.ReadLine();foreach(string id in bsf){ Console.WriteLine(id); } Console.WriteLine(“數字，輸入回車”);Console.ReadLine();foreach(string id in sz){ Console.WriteLine(id); } Console.WriteLine(“關系運算符，輸入回車”);Console.ReadLine();foreach(string id in gx){ Console.WriteLine(id); } Console.WriteLine(“算數運算符，輸入回車”);Console.ReadLine();foreach(string id in ys){ Console.WriteLine(id); } Console.WriteLine(“輸入回車退出”); Console.ReadLine(); } static void analysisByLine(string code) //輸出所有的數字 //輸出所有的關系運算符//輸出所有的算數運算符 { char a = ' ';string temp = “";int j = 0;while(j < code.Length){ a = code[j];temp = ”“;if(Char.IsLetter(a)|| a == '_')//是否為標識符 { temp = temp + a.ToString();j++;a = code[j];while(Char.IsLetterOrDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} if(isKey(temp)){ //Console.WriteLine(”保留字：“+temp); if(!key.Contains(temp)){ // Console.WriteLine(”添加成功“);key.Add(temp);} } else { //Console.WriteLine(”標識符：“+temp); if(!bsf.Contains(temp)){ //Console.WriteLine(”添加成功標識符==“);bsf.Add(temp);} } } else if(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j]; } //判斷是否是小數 if(a.Equals('.')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} //判讀是否是科學記數法 if(a.Equals('E')|| a.Equals('e')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} } } // Console.WriteLine(”數字:“+temp);if(!sz.Contains(temp)){ //Console.WriteLine(”添加成功標識符==“);sz.Add(temp);} } else if(a == '<'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];} else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];} //Console.WriteLine(”關系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功標識符==“);gx.Add(temp);} } else if(a == '='){ temp = temp + a.ToString();j++; a = code[j];// Console.WriteLine(”關系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功關系==“);gx.Add(temp);} } else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];} // Console.WriteLine(”關系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功標識符==“);gx.Add(temp);} } else { if(a == '+' || a == '-' || a == '/' || a == '*'){ temp = temp + a.ToString();j++;a = code[j];//Console.WriteLine(”運算符“+temp);if(!ys.Contains(temp)){ //Console.WriteLine(”添加成功標識符==“);ys.Add(temp);} } else { j++;} } } } //判斷是不是保留字的IsKey方法 static bool isKey(string key){ bool flag = false;for(int i = 0;i < keys.Length;i++) if(keys[i] == key){ flag = true;//Console.WriteLine(key+”是不是key“+flag);break;} else { flag = false; } //Console.WriteLine(key+”是不是key“);// Console.WriteLine(flag+”是不是key");return flag; } } } 課 程 設 計 報 告 設計題目：一個簡單文法的編譯器前端的設計與實現 班 級： 計算機1206 組長學號：201239 組長姓名：閆智宣 指導教師：李曉華 設計時間：2014年12月 [在此處鍵入] 設計分工 組長學號及姓名： 20123974 閆智宣 分工： 語法分析，四元式生成，目標代碼優化及生成 組員1學號及姓名：20123977 廖峭 分工： 詞法分析，錯誤處理 組員2學號及姓名：20123959 郭天龍 分工： 符號表生成，語義動作插入，操作界面[在此處鍵入] 摘要 編譯原理課程設計是通過C語言編譯器相關子系統的設計，進一步加深對編譯器構造的理解；第一部分詞法分析，設計各單詞的狀態轉換圖，并為不同的單詞設計種別碼，制作掃描器識別一個個單詞，返回值為識別碼的序號，返回Token序列。將詞法分析器設計成供語法分析器調用的子程序。詞法分析器具備預處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設計一個供詞法分析調用的預處理子程序；第二部分，語法分析，用遞歸下降法，實現對表達式、各種說明語句、控制語句進行語法分析。若語法正確，則用語法制導翻譯法進行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質和出錯位置（行號）。 我們還做了附加功能，即編譯后端，有中間代碼優化，生成目標代碼匯編語言。通過此次課程設計，提高了我們的獨立分析問題、解決問題的能力，以及系統軟件設計的能力； 提高程序設計能力、程序調試能力，團結協作能力 關鍵詞：詞法分析，語法分析，四元式生成，錯誤處理，符號表生成，語義動作插入，中間代碼優化，生成目標代碼 [在此處鍵入] 目錄 摘要 1.概述 2.課程設計任務及要求 2.1 設計任務 2.2 設計要求 3.算法及數據結構 3.1算法的總體思想（流程） 3.2 詞法分析模塊 3.2.1 功能 3.2.2 數據結構 3.2.3 算法 3.3 語法分析模塊 3.3.1功能 3.3.2 數據結構 3.3.3算法 3.4 符號表模塊 3.4.1功能 3.4.2 數據結構 3.4.3算法 3.5 四元式模塊 3.5.1功能 [在此處鍵入] 3.5.2 數據結構 3.5.3算法 3.6 語義動作分析模塊 3.6.1功能 3.6.2 數據結構 3.6.3算法 3.7 錯誤處理模塊 3.7.1功能 3.7.2 數據結構 3.7.3算法 3.8 目標代碼模塊 3.8.1功能 3.8.2 數據結構 3.8.3算法 4.程序設計與實現 4.1 程序流程圖 4.2 程序說明 4.3 實驗結果 5.結論 6.參考文獻。7.收獲、體會和建議。 [在此處鍵入] 1.概述 編譯器是將C語言翻譯為匯編語言代碼的計算機程序。編譯器將源程序（source language）編寫的程序作為輸入，翻譯產生目標語言（target language）機器代碼的等價程序。通常地，源程序為高級語言（high-level language），C語言程序，而目標則是 機器語言的目標代碼（object code），也就是可以在計算機硬件中運行的機器代碼軟件程序。這一過程可以表示為： 源程序→編譯器 →目標機器代碼程序 2.課程設計任務及要求 2.1設計任務 學生在學習《編譯原理》課程過程中，結合各章節的構造編譯程序的基本理論，要求用C#語言描述及上機調試，實現一個 C編譯程序（包括詞法分析，語法分析等重要子程序），使學生將理論與實際應用結合起來，受到軟件設計等開發過程的全面訓練，從而提高學生軟件開發的能力。 2.2設計要求 要求： （1）設計詞法分析器 設計各單詞的狀態轉換圖，并為不同的單詞設計種別碼。將詞法分析器設計成供語法分析器調用的子程序。功能包括： a.具備預處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設計一個供詞法分析調用的預處理子程序； b.能夠拼出語言中的各個單詞； [在此處鍵入] c.返回（種別碼，屬性值，行號）。 （2）語法分析 要求用學習過的自底向上或自頂向下的分析方法等，實現對表達式、各種說明語句、控制語句進行語法分析。若語法正確，則用語法制導翻譯法進行語義翻譯；生成并打印出語法樹；若語法錯誤，要求指出出錯性質和出錯位置（行號）。 3.算法及數據結構 3.1算法的總體思想（流程） 本節主要分析程序的代碼結構和代碼工程文件的劃分。（程序由幾個類組成: Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類，分別為詞法分析和語法分析類。工程分為幾個文件：Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分別對應Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類的聲明和實現文件）。本程序采用C#語言以面向對象的思想編寫，程序分為幾部分：詞法分析（Lexical），語法分析（Grammer），目標代碼生成（ObjectCode）。Lexical類主要的工作是詞法分析獲取Token。Grammer類的主要工作是根據Lexical類詞法分析之后的Token進行語法分析，生成語法樹，最后并輸出語法樹。在處理過程中，Token類的對象作為Lexical類的一個成員變量，配合Grammer類進行語法分析。 工程文件總體上是按照九個類的格局分為十個文件，分別是九個類的聲明文件和實現文件。十個文件為Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs，他們分別是Lexical類聲明文件、Lexical類實現文件、Grammer類聲明文件、Grammer類實現文件。[在此處鍵入] 程序流程 在程序中，Lexical類的對象(Token)作為Grammer類中的一個成員變量，配合Grammer類進行語法分析。它們的關系是這樣的：Grammer類的一個成員變量temp首先對源程序刪除注釋，然后進行詞法分析獲取所有Token，并將獲取的Token存儲在Token對象的tokenList（List類型）中。然后Grammer類的語法分析程序就根據tokenList中的Token進行語法分析，生成語法樹，最后打印語法樹。同時，這也是程序的流程。[在此處鍵入] 3.2 詞法分析模塊 3.2.1功能 Lexical類主要的工作是詞法分析獲取Token序列。 3.2.2數據結構 詞法分析階段的代碼被封裝成一個類——Lexical，Token中主要是Lexical類的聲明代碼，Lexical.cs中主要是Lexical類的實現代碼。Lexical類對外提供的函數主要有： static public int RecogId(string str, int i)，static public int RecogDig(string str,int i)，static public int RecogOperator(string str, int i)，static public int RecogBound(string str, int i)，以上幾個函數構成了詞法分析的骨架，在Lexical類中還有其他成員變量和函數，主要作為這三個函數處理過程的中間步驟，為這三個函數服務。Lexical類的代碼結構和主要的成員變量和函數及其含義如下圖所示： 3.2.3算法 算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是[在此處鍵入] 根據掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。 主程序示意圖： 主程序示意圖如圖3-1所示。 ⑴ 關鍵字表的初值。 關鍵字作為特殊標識符處理，把它們預先安排在一張表格中（稱為關鍵字表），當掃描程序識別出標識符時，查關鍵字表。如能查到匹配的單詞，則該單詞為關鍵字，否則為一般標識符。 （2）程序中需要用到的主要變量為type和number 掃描子程序的算法思想： 首先設置3個變量： [在此處鍵入] ①token用來存放構成單詞符號的字符串； ②number用來整型單詞； ③type用來存放單詞符號的種別碼。 Token定義 Token定義: Token類型（TokenType）: 3.3 語法分析模塊 3.3.1功能 語法分析是編譯過程的一個邏輯階段。語法分析的功能是在詞法分析的基礎上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達式”等等.語法分析程序判斷源程序在結構上是否正確.源程序的結構由上下文無關文法描述.3.3.2 數據結構 下圖為實現語法分析的類Grammar，屬性與方法的作用都已說明 在此處鍵入] 3.3.3算法 1.文法 下面終結符與非終結符意義 B程序開始 Z 數據類型，如int,char,float等 V 標識符 S 語句 P 語句塊 E 加減算術表達式 D 逗號表達式 T 乘除算術表達式 C 關系表達式 L 邏輯表達式 Q 標識符或圓括號 e 表示空 i 表示標識符 a)函數文法 B----ZV()S [ [在此處鍵入] b)語句塊文法 P----SP|e S----{P} c)語句文法 表達式語句文法 S----V=E goto語句文法 S----i:S S----goto i if語句文法 S----if(E)S[else S] while語句文法 S----while(E)S 聲明語句文法 S----ZVD D----,VD|=ED|e d)表達式文法 E----T|E+T|E-T T----F|T*F|T/F C----C|C L----Q|L&&Q|L||Q Q----i|(E)|!Q 2.遞歸下降程序流程圖 對應于每個文法編寫如下遞歸下降子程序 主程序（B）[在此處鍵入] [在此處鍵入] 3.4 符號表模塊 3.4.1功能 進行符號表的儲存，添加，更新，查找，保存標識符活躍信息以及輸出。3.4.2 數據結構 在此處鍵入] 3.4.3算法 3.5 四元式模塊 3.5.1功能 四元式為中間代碼，編譯程序進行完語義分析后，先生成中間代碼作為過渡，此時中間代碼與目標代碼已經比較相似 3.5.2 數據結構 [ 在此處鍵入] 3.5.3算法 3.6語義動作分析模塊 3.6.1功能 在語法分析中嵌入相應的語義動作，生成四元式 3.6.2 數據結構 [ [在此處鍵入] 3.6.3算法 GEQ(+)(-)(*)(/) (+,i1,i2,t)PUSH(i)ASSI(=) (=,t,_,POP)LABER(i) (lb,_,_,i)GOTO(i) (gt,_,_,i)IF(if) (if,a,_,_)EL(el) (el,_,_,_)IE(ie) (ie,_,_,_)WH() (wh,_,_,_)DO() (do,a,_,_)WE(we) (we,_,_,_) 3.7 錯誤處理模塊 3.7.1功能 保存運行時發現的錯誤，儲存行號已經詳細信息并輸出。 3.7.2 數據結構 3.7.3算法 [在此處鍵入] public static void AddErrorMessage(int lineno,string content)函數用作在發現錯誤時保存錯誤信息以及行號。 public static string PrintErrorList()把所有發現的錯誤格式化后統一輸出。 錯誤信息在語法分析，語義分析，符號表檢錯中添加。3.8 目標代碼模塊 3.8.1功能 目標代碼生成把優化后的中間代碼變換成目標代碼，此處的目標代碼為匯編代碼，采用單寄存器生成目標代碼 3.8.2 數據結構[在此處鍵入] 3.8.3算法 對于一個基本塊有如下流程圖 W：操作符，B：第一操作數，C：第二操作數，R：寄存器 5.結論 網上找一段話抄上 [在此處鍵入] 6.測試 測試打開文件 測試保存文件 如果沒打開文件，直接敲代碼，點保存時會彈出另存為窗口[在此處鍵入] 測試錯誤檢測，程序缺少main函數的類型，錯誤列表中顯示第一行函數缺少錯誤類型。 測試錯誤檢測，程序缺少分號，錯誤列表中顯示該行缺少語句結束標志';' 單擊錯誤列表，會自動選定錯誤行 編譯成功，生成并顯示token串、符號表、四元式與目標代碼 [在此處鍵入] 測試if與while語句，而且while嵌套在if當中 測試goto語句，結果正確。[在此處鍵入] 測試優化，輸入課件中的代碼，結果與課件一樣 6.參考文獻。 1、陳火旺.《程序設計語言編譯原理》（第3版）.北京：國防工業出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中，姜守旭譯.《編譯原理》.24 [在此處鍵入] 北京：機械工業出版社.2003.3、美 Kenneth C.Louden著.馮博琴等譯.《編譯原理及實踐》.北京：機械工業出版社.2002.4、金成植著.《編譯程序構造原理和實現技術》.北京：高等教育出版社.2002.7.收獲、體會和建議。 直接拷貝好歹也檢查一下錯誤 對于編譯原理的這次課程設計，自己經歷了從剛開始的不懂?明白任務的要求和內容?理論知識的了解?開始著手寫代碼?完成基本功能?根據DFA及自頂向下等理論修改完善代碼等這些過程。 自己著手寫詞法分析的時候還不清楚詞法分析的任務內容，還不知道詞法分析的結果是什么，詞法分析出錯的情況和類型有哪些，也總是將詞法分析和語法分析混在一起，不明白哪些錯誤在詞法分析中報，哪些錯誤在語法分析中判斷，后來經過查書、網上資料、請教同學等途徑逐步清晰了詞法分析的工作內容是從源代碼文件中獲取出Token，供語法分析使用。在充分了解了語法分析需要哪些信息時，我才真正了解了詞法分析的工作內容和目標，才知道詞法分析需要完成哪些任務獲取到哪些信息。充分了解了詞法分析的任務之后，就開始理論知識的學習。經過揣摩書上的例子，自己理解和掌握了怎么設計過濾注釋和分析程序中Token的DFA，于是開始根據設計好的DFA進行編碼，最后經過調試已經可以正確地完成詞法階段的任務了。這只是詞法分析的原始代碼，在之后還進行了兩次徹底的改動。雖然之前寫的詞法分析的代碼已經完成了詞法分析的需求，也是根據DFA的原理編寫的，但是在代碼結構上卻難以體現，在對書上的根據已知DFA寫代碼的例子進行了詳細的研究之后，發現自己的代碼并沒有像書上那樣完全按照所依據的DFA各狀態轉移的關系進行編寫，所以對代碼進行了重寫，像書上一樣嚴格按照狀態之間轉移的方式進行編寫，將狀態劃分成11個狀態，狀態分別按1~11進行標注，程序也按照DFA來編寫，也實現了詞法分析的功能。再后來寫報告的時候，發現分析出Token的那個DFA并不是最簡的，有很多多余的狀態，完全可以用一個flag標志來標識，從而簡化代碼結構，于是又重寫了一次詞法分析函數scan()的代碼，將狀態縮減為5個，且不再用1-5來表示，而是像書上那樣分別取了名字（START、INNUM、INID、INDBSYM、DONE），同時為了簡化代碼將輸出Token到文件的部分從scan()中剝離開來，而在Lexical類中加了一個printToken()的函數，使scan()函數邏輯更加清晰，使讀者能夠容易地將代碼與DFA進行查看比照。 在寫語法分析的時候，已經對編譯器的語法分析的內容有了一定的了解，所以直接進行了理論的學習。首先自己對遞歸向下分析法進行了學習，將書上的幾個遞歸向下分析的偽代碼看過之后，自己對遞歸向下的分析方法的原理有了初步的認識，大概知道了根據文法怎么分析，但是對于如何編寫代碼卻還在此處鍵入] 是難以下手，于是就對照TINY語言的文法看了幾遍書后面的TINY語言的遞歸向下分析的語法分析程序，這樣就基本知道了C-語言的語法分析程序怎么寫。由于C-語言給出的文法有左遞歸存在，于是自己將存在左遞歸的文法改寫成EBNF的形式，并據此進行代碼編寫。由于在編寫代碼的過程中需要確定分析是否正確或選擇多個文法中的某一個文法進行分析，有時必須探測需要的或下一個Token的類型，在這種情況下需要求First集合，在推導中若存在empty，又需要求Follow集合，所以這樣又需要我了解First集合和Follow集合，自己在程序中也根據求出的First集合和Follow集合進行判斷，以確定程序的走向。在編寫過程中，還有一類問題，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子為ID，在分析過程中，由于已經取出了一個ID的Token，且生成了一個IdK的節點，但是在當前狀態無法確定是哪一個推導，然而IdK節點已經生成，又無法回退，并且是使用自頂向下的分析方法，已經生成的IdK在程序上方無法使用，自己通過查閱資料等途徑的學習確定了在這種情形下的處理方式：將已經生成的IdK節點傳到下方的處理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函數都被設計成有節點類型參數的函數，目的就是將已經生成的節點傳到下面的分析函數中去。 通過這次的編譯原理課程的學習和實踐，自己獲益良多。首先最基本的成果是完成了課程設計的任務，實現了編譯器的詞法分析和語法分析階段的功能，詞法分析主要能過濾注釋、分析出語法分析階段需要的Token并滿足語法階段的所有要求，能夠判別詞法分析階段是否出錯和出錯類型和位置。語法分析主要能根據遞歸向下的分析思想和C-文法對詞法分析獲取的Token進行語法分析，能夠構造出語法樹，能夠判別語法分析過程中是否出錯以及出錯位置和錯誤類型。 由于在編寫程序過程中，涉及到了正則表達式、DFA、提取公共左因子、消除左遞歸、EBNF、求First集合和Follow集合、遞歸向下分析方法以及編程語言方面的知識，所以，通過本次的課程設計的實踐，使得自己對編譯原理這門課的許多知識點有了更加深刻和具體的理解，而不再只限制于做題。此外，對以前那些已掌握的知識有了溫習和動手鍛煉的機會。如：以前在編譯原理課上雖然知道First集合和Follow集合怎么求的，卻不知道First集合和Follow集合到底是干什么的，通過編寫程序自己明白了他們的實際作用，使得自己不僅知其然還知其所以然，從而使得自己加深了對知識點的理解和掌握。由于以前編寫代碼都是使用JAVA語言，所以C/C++很多內容都忘記了，通過本次的實踐，自己又重新拾起了以前的知識。此外，由于在做報告的時候，需要描繪DFA和程序流程圖，使得自己初步掌握了使用visio和word畫圖的能力。此外，對于文檔的編寫和美化自己也獲得了許多有用的經驗。[ 武 漢 紡 織 大 學 編譯原理課程設計實驗報告 學院：數學與計算機 專業：計算機 姓名： 班級： 學號： 編譯原理 編譯原理課設報告 一、實驗目的 加強對編譯程序的整體認識和了解，鞏固《編譯原理》課程所學知識。通過本次課程設計掌握編譯程序調試技巧和設計編譯程序一般的原則，加深對詞法分析、語法分析、語義分析等編譯階段及實用編譯系統的認識。使學生能將編譯理論與實際應用結合起來，提高學生軟件開發的能力。 二、實驗內容 1）仔細閱讀PL/0編譯程序文本（編譯原理(第二版)張素琴 呂映芝 蔣維杜 戴桂蘭 主編 清華大學出版社），并上機調試通過。 2）對PL/0語言進行下列擴充（1）擴充一維整型數組。 擴充var數組：VAR <數組標識名>（<下界>：<上界>）〈下界〉和〈上界〉可用常量標識名。 （2）擴充條件語句的功能使其為：IF<條件>THEN<語句>[ELSE<語句>]（3）增加repeat重復語句: REPEAT<語句>{;<語句>}UNTIL<條件> 可根據自己具體情況從中選擇2個以上題目進行擴充。 三、實驗原理 PL/0語言可以看成PASCAL語言的子集，它的編譯程序是一個編譯解釋執行系統。PL/0的目標程序為假想棧式計算機的匯編語言，與具體計算機無關。 PL/0的編譯程序和目標程序的解釋執行程序都是用PASCAL語言書寫的，因此PL/0語言可在配備PASCAL語言的任何機器上實現。其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法分析正確需要生成相應的目標代碼時，則調用代碼生成程序。 用表格管理程序建立變量、常量和過程表示符的說明與引用之間的信息聯系。 當源程序編譯正確時，PL/0編譯程序自動調用解釋執行程序，對目標代碼進行解釋執行，并按用戶程序的要求輸入數據和輸出運行結果。 四、實驗分析 PL/0語言編譯程序采用以語法分析為核心、一遍掃描的編譯方法。詞法分析和代碼生成作為獨立的子程序供語法分析程序調用。語法分析的同時，提供了出錯報告和出錯恢復的功能。在源程序沒有錯誤編譯通過的情況下，調用類PCODE解釋程序解釋執行生成的類PCODE代碼。 詞法分析子程序分析： 詞法分析子程序名為GETSYM，功能是從源程序中讀出一個單詞符號（TOTAKEN），把它的信息放入全局變量 SYM、ID和NUM中，字符變量放入CH中，語法分析器需要單詞時，直接從這三個變量中獲得。Getch過程通過反復調用Getch子過程從源程序過獲取字符，并把它們拼成單詞。GETCH過程中使用了行緩沖區技術以提高程序運行效率。 詞法分析器的分析過程：調用GETSYM時，它通過GETCH過程從源程序中獲得一個字符。如果這個字符是字母，則繼續獲取字符或數字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把SYM變量賦成相應的保留字類型值；如果沒有查到，則這個單詞應是一個用戶自定義的標識符（可能是變量名、常量名或是過程的名字），把SYM置為IDENT，把這個單詞存入ID變量。查保留字表時使用了二分法查找以提高效率。如果Getch獲得的字符是數字，則繼續用Getch獲取數字，并把它們拼成一個整數或實數，然后把SYM置為 INTEGER或REAL，并把拼成的數值放入NUM變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把SYM則成相應的類型。如果遇到不合法的字符，把SYM置成NUL。 語法分析子程序分析： 語法分析子程序采用了自頂向下的遞歸子程序法，語法分析同時也根據程序的語義生成相應三元代碼，并提供了出錯處理的機制。語法分析主要由分程序分析過程（BLOCK）、參數變量分析過程（ParaDeclaration）、參數變量處理過程（ParaGetSub）、數組處理過程（ParaGetSub）、常量定義分析過程（ConstDeclaration）、變量定義分析過程（Vardeclaration）、語句分析過程（Statement）、表達式處理過程（Expression）、項處理過程（Term）、因子處理過程（Factor）和條件處理過程（Condition）構成。這些過程在結構上構成一個嵌套的層次結構。除此之外，還有出錯報告過程（Error）、代碼生成過程（Gen）、測試單詞合法性及出錯恢復過程（Test）、登錄名字表過程（Enter）、查詢名字表函數（Position）以及列出類 PCODE代碼過程（Listcode）作過語法分析的輔助過程。 由PL/0的語法圖可知：一個完整的PL/0程序是由分程序和句號構成的。因此，本編譯程序在運行的時候，通過主程序中調用分程序處理過程block來分析分程序部分（分程序分析過程中還可能會遞歸調用block過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的PL/0程序，可以運行生成的代碼，否則就說明源PL/0程序是不合法的，輸出出錯提示即可。 if-then-else語句的處理： 按if語句的語法，首先調用邏輯表達式處理過程處理if語句的條件，把相應的真假值放到數據棧頂。接下去記錄下代碼段分配位置（即下面生成的jpc指令的位置），然后生成 條件轉移jpc指令（遇0或遇假轉移），轉移地址未知暫時填0。然后調用語句處理過程處理 then語句后面的語句或語句塊。then后的語句處理完后，如果遇到else，就調用語句處理過程處理else語句后面的語句或語句塊，這時當前代碼段分配指針的位置就應該是上面的jpc指令的轉移位置。通過前面記錄下的jpc指令的位置，把它的跳轉位置改成當前的代碼段指針位置，否則沒遇到else，那么此時的當前代碼段分配指針的位置也是上面jpc指令的轉移位置，也是通過前面記錄下的jpc位置指令的位置，把它的跳轉到當前的代碼段指針位置。 Repeat語句的處理： 首先用CX1變量記下當前代碼段分配位置，作為循環的開始位置。然后通過遞歸調用語句分析過程分析，直到遇到until保留字，如果未對應until則出錯。調用條件表達式處理過程生成相應代碼把結果放在數據棧頂，再生成條件轉移指令，轉移位置為上面記錄的CX1。 五、相關代碼及運行結果 實驗代碼； PL0.h代碼： #include #ifndef WIRTH_ZYC_ #define WIRTH_ZYC_ using namespace std; const int norw = 16; // no.of reserved words 保留字的個數 const int txmax = 100; // length of identifier table 標示符表的長度（容量）const int al = 10; // length of identifiers 標示符的最大長度 const int nmax = 14; // max.no.of digits in numbers 數字的最大長度 const int amax = 2047; // maximum address 尋址空間 const int levmax = 3; // maximum depth of block nesting 最大允許的塊嵌套層數 const int cxmax = 200; // size of code array 類PCODE目標代碼數組長度（可容納代碼行數） const int lineLength = 82;// 行緩沖區長度 typedef enum {NUL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN，RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM，WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM,ELSESYM,REPEATSYM,UNTILSYM} symbol;// symobl類型標識了不同類型的詞匯 typedef char alfa[al+1]; // alfa類型用于標識符 typedef enum {CONSTANT,VARIABLE,PROCEDURE,ARRAY} obj0; // 三種標識符的類型 typedef enum {LIT,OPR,LOD,STO,CAL,INT,JMP,JPC} fct; // functions typedef set struct instruction{ fct f;// function code int l;// level,cann't big than levmax int a;// displacement address,cann't big than amax }; // 類PCODE指令類型，包含三個字段：指令f、層差l和另一個操作數a /******************************************* * lit 0,a: load constant a * * opr 0,a: execute operation a * * lod l,a: load variable l,a * * sto l,a: store variable l,a * * cal l,a: call procedure a at level l * * int 0,a: increment t-register by a * * jmp 0,a: jump to a * * jpc 0,a: jump conditional to a * *******************************************/ typedef struct{ alfa name;obj0 kind;union { struct{int level,adr,size;}inOther; int val;}other;} Table; class PL0 { protected: bool listswitch,sourceEnd;char ch; // last character read symbol sym; // last symbol read alfa id; // last identifier read int num; // last number read int cc; // character count int ll; // line length int kk,err;int cx; // code allocation index int codeNo; // code line no.static string errStr[]; // error string char line[lineLength]; // code line vector // error array alfa a; // 詞法分析器中用于臨時存放正在分析的詞 instruction code[cxmax+1]; // destination code array alfa word[norw+1]; // 保留字表 symbol wsym[norw+1]; // 保留字表中每一個保留字對應的symbol類型 symbol ssym[100]; // 一些符號對應的symbol類型表 合 char mnemonic[8][6]; // 類PCODE指令助記符表 symset declbegsys,statbegsys,facbegsys;// 聲明開始、表達式開始和項開始符號集 Table table[txmax+1]; // 符號表 FILE* fin,*fout; public: PL0(char* source,char*destination); ~PL0(){fclose(fin),fclose(fout);} void error(int n); 位置和出錯代碼 void getsym(); 個單詞 void getch(); 個字符 void gen(fct x,int y,int z); 程序區 void test(symset s1,symset s2,int n); 合法 void block(int lev,int tx,symset fsys); void enter(obj0 k,int &tx,int &dx,int lev); int position(alfa id,int tx);的位置 void constdeclaration(int&tx,int&dx,int lev); void vardeclaration(int&tx,int&dx,int lev); void listcode(int cx0); void statement(symset fsys,int tx,int lev); void expression(symset fsys,int tx,int lev); void term(symset fsys,int tx,int lev); void factor(symset fsys,int tx,int lev); void condition(symset fsys,int tx,int lev); void arraydeclaration(int& tx,int& dx,int lev); void interpret(); 執行程序 int base(int l,int b,int s[]); 基地址 void SaveCode(); // 構造函數 // 析構函數 // 出錯處理，打印出錯 // 詞法分析，讀取一 // 漏掉空格，讀取一// 生成目標代碼，并送入目標 // 測試當前單詞符號是否 // 分程序分析處理過程 // 登入名字表 // 查找標示符在名字表中 // 常量定義處理 // 變量說明處理 // 列出目標代碼清單 // 語句部分處理 // 表達式處理 // 項處理 // 因子處理 // 條件處理 // 數組說明處理 // 對目標代碼的解釋 // 通過靜態鏈求出數據區的 // 保存代碼 };#endif PL0.cpp代碼： #include “pl0.h” // 錯誤字符串數組 string PL0::errStr[]={“",”error 0001: 常數說明中“=”寫成“：=”“, ”error 0002: 常數說明中的“=”后應為數字“, ”error 0003: 常數說明中的標識符后應是“=”“, ”error 0004: const,var,procedure后應為標識符“, ”error 0005: 漏掉了‘,’或‘;’“, ”error 0006: 過程說明后的符號不正確（應是語句開始符或過程開始符）“, ”error 0007: 應是語句開始符“, ”error 0008: 過程體內語句部分的后跟符不正確“, ”error 0009: 程序皆為丟了句號‘.’“, ”error 0010: 語句之間漏了‘;’“, ”error 0011: 標識符沒說明“, ”error 0012: 賦值語句中，賦值號左部標識符屬性應是變量“, ”error 0013: 賦值語句左部標識符應是賦值號:=“, ”error 0014: call后應為標識符“, ”error 0015: call后標識符屬性應為過程“, ”error 0016: 條件語句中丟了then“, ”error 0017: 丟了end或;“, ”error 0018: while型循環語句中丟了do“, ”error 0019: 語句后的標識符不正確“, ”error 0020: 應為關系運算符“, ”error 0021: 表達式內標識符屬性不能是過程“, ”error 0022: 表達式中漏掉了右括號‘)’“, ”error 0023: 因子后的非法符號“, ”error 0024: 表達式開始符不能是此符號“, ”error 0025: 文件在不該結束的地方結束了“, ”error 0026: 結束符出現在不該結束的地方“, ”error 0027: “,”error 0028: “,”error 0029: “,”error 0030: “, ”error 0031: 數越界“, ”error 0032: read語句括號中標識符不是變量“, ”error 0033: else附近錯誤“ , ”error 0034: repeat附近錯誤“}; // PL0構造函數 PL0::PL0(char* source,char*destination){ listswitch=true,sourceEnd=false; strcpy(word[1],”begin“); // 初始化存儲保留字 strcpy(word[2],”call“);strcpy(word[3],”const“); strcpy(word[4],”do“);strcpy(word[5],”else“);strcpy(word[6],”end“);strcpy(word[7],”if“);strcpy(word[8],”odd“);strcpy(word[9],”procedure“);strcpy(word[10],”read“); strcpy(word[11],”repeat“);strcpy(word[12],”then“);strcpy(word[13],”until“);strcpy(word[14],”var“); strcpy(word[15],”while“);strcpy(word[16],”write“); wsym[1]= BEGINSYM; wsym[2]= CALLSYM;留字對應的symbol類型 wsym[3]= CONSTSYM; wsym[4]= DOSYM;wsym[5]= ELSESYM; wsym[6]= ENDSYM;wsym[7]= IFSYM; wsym[8]= ODDSYM;wsym[9]= PROCSYM; wsym[10]= READSYM; wsym[11]= REPEATSYM;wsym[12]= THENSYM;wsym[13]= UNTILSYM;wsym[14]= VARSYM; wsym[15]= WHILESYM;wsym[16]= WRITESYM; memset(code,0,sizeof(code));memset(ssym,0,100*sizeof(symbol));memset(table,0,sizeof(table));memset(line,0,sizeof(line)); ssym['+']= PLUS; 類型表 ssym['-']= MINUS;ssym['*']= TIMES;ssym['/']= SLASH;ssym['(']= LPAREN;ssym[')']= RPAREN;ssym['=']= EQL;ssym[',']= COMMA;ssym['.']= PERIOD; // 初始化保留字表中每一個保 // 初始化一些符號對應的symbol ssym['#']= NEQ;ssym['<']= LSS;ssym['>']= GTR;ssym[';']= SEMICOLON; strcpy(mnemonic[LIT],” lit “); // 初始化類PCODE指令助記符表 strcpy(mnemonic[OPR],” opr “);strcpy(mnemonic[LOD],” lod “);strcpy(mnemonic[STO],” sto “);strcpy(mnemonic[CAL],” cal “);strcpy(mnemonic[INT],” int “);strcpy(mnemonic[JMP],” jmp “);strcpy(mnemonic[JPC],” jpc “); declbegsys.insert(CONSTSYM),declbegsys.insert(VARSYM),declbegsys.insert(PROCSYM);// 初始化聲明開始符號集合 statbegsys.insert(BEGINSYM),statbegsys.insert(CALLSYM),statbegsys.insert(IFSYM),statbegsys.insert(WHILESYM);// 初始化表達式開始符號集合facbegsys.insert(IDENT),facbegsys.insert(NUMBER),facbegsys.insert(LPAREN);// 初始化項開始符號集合 err= 0;cc= 0; // 行緩沖區指針 cx= 0; // 代碼分配指針，代碼生成模塊總在cx所指位置生成新的代碼 ll= 0; // 行緩沖區長度 ch= ' '; // last character read } kk= al; // 引入此變量是出于程序性能考慮 codeNo=0; // code line no.fin=fopen(source,”r“);fout=fopen(destination,”w“);// 出錯處理，打印出錯位置和出錯代碼 void PL0::error(int n){ char s[10];sprintf(s,”第 %d 行:“,codeNo);errorString.push_back(s+errStr[n]);err= err+1;//error count }//error end // 詞法分析，讀取一個單詞 void PL0::getsym(){ if(sourceEnd) return;int i,j,k;while(ch ==' '||ch==9) getch(); // cls space and tab if(isalpha(ch))// id or reserved word { k=0; memset(a,0,al+1); // 檢測一個單詞長度 do{ if(k < al){ a[k]= ch; k= k+1;} getch();if(sourceEnd) return;}while(isalpha(ch)||isdigit(ch));if(k >= kk)kk = k;else { do{ a[kk]= ' '; kk= kk-1;}while(kk > k);} strcpy(id,a);i= 1;j= norw;// 判斷是否是關鍵字（二分搜索）do{ k=(i+j)/ 2;if(strcmp(id, word[k])<=0) j= k-1;if(strcmp(id,word[k])>=0) i= k+1;}while(i<=j);if(i-1 > j) sym= wsym[k];else sym= IDENT;} else if(isdigit(ch))// number { k= 0;num= 0;sym= NUMBER;do{ num= 10 * num + ch-'0'; k= k+1; getch();}while(isdigit(ch));if(k > nmax) error(30);} else if(ch == ':'){ getch();if(ch == '='){ sym= BECOMES; getch();} else sym= NUL;} else if(ch == '<') // extra stuff added to support <= { getch();if(ch== '='){ sym= LEQ; getch();} else sym= LSS;} else if(ch == '>'){ getch();if(ch == '='){ sym= GEQ; getch();} else sym= GTR;} else // end of extra stuff { sym= ssym[ch];// 其它符號的賦值 getch();} } // 漏掉空格，讀取一個字符 void PL0::getch(){ if(cc == ll){ if(feof(fin)) { if(sym!=PERIOD) error(25); sourceEnd=true; return; } cc= 0; fgets(line,lineLength,fin); codeNo++; ll=strlen(line); if(line[ll-1]==10)ll--;} ch= line[cc];cc= cc+1;} // 生成目標代碼，并送入目標程序區void PL0::gen(fct x,int y,int z){ if(cx > cxmax){ cout<<”Program too longn“; return;} code[cx].f= x;code[cx].l= y;code[cx].a= z; cx= cx+1;}//gen end // 測試當前單詞符號是否合法 void PL0::test(symset s1,symset s2,int n){ if(sourceEnd) return;if(s1.find(sym)==s1.end()){ error(n); symset::iterator it; for(it=s2.begin();it!=s2.end();it++) s1.insert(*it);//s1=s1+s2 while(s1.find(sym)==s1.end()) getsym();} }//test end // 分程序分析處理過程 void PL0::block(int lev,int tx,symset fsys){ if(sourceEnd) return;int dx;// data allocation index int tx0;// initial table index int cx0;// initial code index dx= 3; // 變量的個數 tx0= tx;// 表指針 table[tx].other.inOther.adr= cx;gen(JMP,0,0);if(lev>levmax)error(32);do{ if(sym == CONSTSYM) // 處理常量聲明 { getsym(); do{ constdeclaration(tx,dx,lev); while(sym == COMMA) { } getsym(); constdeclaration(tx,dx,lev);} if(sym ==SEMICOLON) getsym();else error(5);}while(sym==IDENT);if(sym == VARSYM) // 處理變量聲明 { getsym();do{ vardeclaration(tx,dx,lev); while(sym == COMMA){ getsym(); vardeclaration(tx,dx,lev); } if(sym ==SEMICOLON) getsym(); else error(5);}while(sym==IDENT);} while(sym ==PROCSYM) // 處理過程的聲明 { getsym();if(sym ==IDENT){ enter(PROCEDURE,tx,dx,lev); getsym();} else error(4);if(sym ==SEMICOLON) getsym();else error(5);symset tmp = fsys;tmp.insert(SEMICOLON);block(lev+1,tx,tmp);if(sym == SEMICOLON){ getsym(); symset tmp = statbegsys; for(int i= IDENT;i<=PROCSYM;i++) tmp.insert((symbol)i); test(tmp,fsys,6); } else error(5); } symset tmp=statbegsys; tmp.insert(IDENT); test(tmp,declbegsys,7);}while(declbegsys.find(sym)!=declbegsys.end()); code[table[tx0].other.inOther.adr].a= cx;table[tx0].other.inOther.adr= cx;// start adr of code table[tx0].other.inOther.size=dx; cx0= cx;gen(INT,0,dx);symset tmp=statbegsys;for(int i=SEMICOLON;i <= ENDSYM;i++) tmp.insert((symbol)i);statement(tmp,tx,lev);gen(OPR,0,0);// return symset s2;test(fsys,s2,8);listcode(cx0);}// block end // 登入名字表 void PL0::enter(obj0 k,int &tx,int &dx,int lev){ tx= tx+1;strcpy(table[tx].name,id);table[tx].kind=k;switch(k){ case CONSTANT: if(num>amax) { error(31); num=0; } table[tx].other.val=num; break;case VARIABLE: table[tx].other.inOther.level=lev; table[tx].other.inOther.adr=dx; dx++; break;case PROCEDURE: table[tx].other.inOther.level=lev; break;case ARRAY: table[tx].other.inOther.size = lev; break;} }//enter end // 查找標示符在名字表中的位置 int PL0::position(alfa id,int tx)//find identifier id in table { int i;strcpy(table[0].name, id);i= tx;while(strcmp(table[i].name,id)!=0)i--;return i;}//position end // 常量定義處理 void PL0::constdeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){ getsym(); if(sym>=EQL&&sym<=BECOMES) { if(sym ==BECOMES) error(1); getsym(); if(sym == NUMBER) { enter(CONSTANT,tx,dx,lev); getsym(); } else error(2); } else error(3);} else error(4);}// constdeclaration end // 變量說明處理 void PL0::vardeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){ enter(VARIABLE,tx,dx,lev); getsym();} else error(4);}//vardeclaration end // 數組說明處理 void PL0::arraydeclaration(int&tx,int&dx,int lev){ int upscript=0,downscript=0;getsym();if(sym == NUMBER || sym == CONSTSYM){ if(num == 0) { upscript = num; getsym(); } else error(32);} if(sym == COMMA) getsym();else error(32);if(sym == NUMBER || sym == CONSTSYM){ downscript = num; getsym();} if(sym!= RPAREN) } error(32);else { enter(ARRAY,tx,dx,downscript+1);getsym();} // 列出目標代碼清單 void PL0::listcode(int cx0)//list code generated for this block { int i;if(listswitch) for(i= cx0;i cout<<”“< <<”“< // 語句部分處理 void PL0::statement(symset fsys,int tx,int lev){ if(sourceEnd) return;int i,cx1,cx2;if(sym ==IDENT){ i= position(id,tx); if(i == 0) error(11); else if(table[i].kind!=VARIABLE) { error(12); i= 0; } getsym(); if(sym ==BECOMES) getsym(); else error(13); expression(fsys,tx,lev); if(sym!= SEMICOLON) error(10); if(i!= 0) gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } else if(sym == READSYM){ getsym();if(sym!=LPAREN) error(34);else do{ getsym(); if(sym==IDENT) i=position(id,tx); else i=0; if(i==0) error(35); else { gen(OPR,0,16); gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } getsym(); }while(sym == COMMA); if(sym!= RPAREN) { error(33); while(fsys.find(sym)!=fsys.end())getsym(); } else getsym();} else if(sym == WRITESYM){ getsym();if(sym==LPAREN){ do{ getsym(); symset tmp=fsys; for(int t=RPAREN;t<=COMMA;t++) tmp.insert((symbol)t); expression(tmp,tx,lev); gen(OPR,0,14); }while(sym==COMMA); if(sym!=RPAREN) error(33); else getsym();} gen(OPR,0,15);} else if(sym ==CALLSYM){ getsym();if(sym!=IDENT) error(14);else { i= position(id,tx); if(i == 0) error(11); else if(table[i].kind = PROCEDURE) gen(CAL,lev-table[i].other.inOther.level,table[i].other.inOther.adr); else error(15); getsym();} } else if(sym ==IFSYM){ getsym();symset tmp=fsys;for(int i = THENSYM;i<= DOSYM;i++) tmp.insert((symbol)i);condition(tmp,tx,lev);if(sym == THENSYM) getsym();else error(16);cx1= cx;gen(JPC,0,0);tmp.insert(ELSESYM);statement(tmp,tx,lev);getsym(); code[cx1].a= cx; if(sym == ELSESYM){ getsym(); cx2=cx; gen(JMP,0,0); code[cx1].a=cx; statement(fsys,tx,lev); code[cx2].a=cx;} } else if(sym ==BEGINSYM){ getsym();symset tmp=fsys;for(int i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i);statement(tmp,tx,lev);tmp=statbegsys;tmp.insert(SEMICOLON);while(tmp.find(sym)!=tmp.end()){ if(sourceEnd)return; if(sym ==SEMICOLON||sym ==ENDSYM) getsym(); else if(sym=PERIOD) { error(26); getsym(); } else error(10); tmp=fsys; for(i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i); if(sourceEnd)return; if(sym==ENDSYM) break; statement(tmp,tx,lev);} if(sym ==ENDSYM) getsym();else if(!sourceEnd) error(17);} else if(sym ==WHILESYM){ cx1= cx; // 記下當前代碼分配位置，這是while循環的開始位置 getsym();symset tmp=fsys;tmp.insert(DOSYM);condition(tmp,tx,lev); cx2= cx; // 記下當前代碼分配位置，這是while的do中的語句的開始位置 gen(JPC,0,0); if(sym ==DOSYM) getsym(); else error(18); statement(fsys,tx,lev); gen(JMP,0,cx1); code[cx2].a= cx;} else if(sym == REPEATSYM){ symset temp1, temp2; temp1= fsys,temp1.insert(SEMICOLON),temp1.insert(UNTILSYM); cx1= cx; getsym(); statement(temp1,tx,lev); temp2 = statbegsys; temp2.insert(SEMICOLON); while(temp2.find(sym)!= temp2.end()) { if(sym == SEMICOLON) getsym(); else error(34); statement(temp1,tx,lev); } if(sym == UNTILSYM) { getsym(); condition(fsys,tx,lev); gen(JPC,0,cx1); } else error(34); } symset setT;test(fsys,setT,19);}//statement end // 表達式處理 void PL0::expression(symset fsys,int tx,int lev){ symbol addop;symset tmp=fsys;for(int t=PLUS;t<=MINUS;t++) tmp.insert((symbol)t);if(sym>=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==MINUS) gen(OPR,0,1);} else term(tmp,tx,lev);while(sym >=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==PLUS) gen(OPR,0,2); else gen(OPR,0,3);} }// expression end // 項處理 void PL0::term(symset fsys,int tx,int lev){ if(sourceEnd) return;symbol mulop;symset tmp=fsys;for(int t=TIMES;t<=SLASH;t++) tmp.insert((symbol)t);factor(tmp,tx,lev);while(sym>=TIMES && sym<=SLASH){ mulop= sym; getsym(); factor(tmp,tx,lev); if(mulop ==TIMES) gen(OPR,0,4); else gen(OPR,0,5);} }// term end // 因子處理 void PL0:: factor(symset fsys,int tx,int lev){ int i;test(facbegsys,fsys,24);while(facbegsys.find(sym)!=facbegsys.end()){ if(sym ==IDENT) { i= position(id,tx); if(i == 0) error(11); else switch(table[i].kind) { case CONSTANT: gen(LIT,0,table[i].other.val); break; case VARIABLE: gen(LOD,lev-table[i].other.inOther.level,table[i].other.inOther.adr); break; case PROCEDURE: error(21); break; } getsym(); } else if(sym ==NUMBER) { if(num>amax) { error(31); num= 0; } gen(LIT,0,num); getsym(); } else if(sym ==LPAREN) { getsym(); symset tmp=fsys; tmp.insert(RPAREN); expression(tmp,tx,lev); if(sym == RPAREN) getsym(); else error(22); } test(fsys,facbegsys,23);} }//factor end // 條件處理 void PL0::condition(symset fsys,int tx,int lev){ symbol relop;symset tmp=fsys;tmp.insert(EQL),tmp.insert(NEQ),tmp.insert(LSS),tmp.insert(LEQ),tmp.insert(GTR),tmp.insert(GEQ); if(sym == ODDSYM){ getsym(); expression(fsys,tx,lev); gen(OPR,0,6);} else { expression(tmp,tx,lev); if(tmp.find(sym)==tmp.end()) error(20); else { relop= sym; getsym(); expression(fsys,tx,lev); switch(relop) { case EQL: gen(OPR,0,8); break; case NEQ: gen(OPR,0,9); break; case LSS: gen(OPR,0,10); break; case GEQ: gen(OPR,0,11); break; case GTR: gen(OPR,0,12); break; case LEQ: gen(OPR,0,13); break; } } } }//condition end // 對目標代碼的解釋執行程序 void PL0::interpret(){ int err1=errorString.size();if(err1>0){ cout<<”存在%d個錯誤:“< cout< t= t+1; s[t]= i.a; break;case OPR: switch(i.a)//operator { case 0:// return t= b-1; p= s[t+3]; b= s[t+2];break;case 1: s[t]=-s[t];break;case 2: t= t-1;s[t]= s[t]+s[t+1];break;case 3: t= t-1;s[t]= s[t]-s[t+1];break;case 4: t= t-1;s[t]= s[t]*s[t+1];break;case 5: t= t-1;s[t]= s[t] / s[t+1];break;case 6: if(s[t]%2) s[t]=1;else s[t]=0;break;case 8: t= t-1;if(s[t]==s[t+1]) s[t]=1;else s[t]=0;break;case 9: t= t-1;if(s[t]==s[t+1]) s[t]=0;else s[t]=1;break; case 10: t= t-1;if(s[t] s[t]=1;else s[t]=0;break;case 11: t= t-1;if(s[t]>=s[t+1]) s[t]= 1;else s[t]=0;break;case 12: t= t-1;if(s[t]>s[t+1]) s[t]= 1;else s[t]=0;break;case 13: t= t-1;if(s[t]<=s[t+1]) s[t]= 1;else s[t]=0;break;case 14: cout<<”“< t= t+1; s[t]= s[base(i.l,b,s)+i.a]; break; case STO: s[base(i.l,b,s)+i.a]= s[t]; t= t-1; break; case CAL:// generate new block mark s[t+1]= base(i.l,b,s); s[t+2]= b; s[t+3]= p; b= t+1; p=i.a; break; case INT: t= t+i.a; break; case JMP: p= i.a; break; case JPC: if(s[t] == 0) p= i.a; t= t-1; break; }//switch end }while(p!=0); cout<<” End PL/0n“;} // interpret end // 通過靜態鏈求出數據區的基地址 int PL0::base(int l,int b,int s[]){ int b1;b1= b;//find base l levels down while(l>0){ b1= s[b1]; l= l-1;} return b1;} // 保存代碼 void PL0::SaveCode(){ if(fout) for(int i=0;i fprintf(fout,”%d %s %d %dn “,i,mnemonic[code[i].f],code[i].l,code[i].a);} TestPL0.cpp代碼： #include ”pl0.h“ void main(){ PL0 cp(”testPas2.txt“,”nasm.txt"); symset fsys; fsys.insert(PERIOD);fsys.insert(CONSTSYM),fsys.insert(VARSYM),fsys.insert(PROCSYM);fsys.insert(BEGINSYM),fsys.insert(CALLSYM),fsys.insert(IFSYM),fsys.insert(WHILESYM);cp.getsym(); // 詞法分析，分析一個詞 cp.block(0,0,fsys); // 分程序分析處理功能 cp.SaveCode(); // 保存代碼 cp.interpret(); // 對目標代碼的解釋執行程序 } 實驗運行結果： 運行的的文件見下圖右側：實驗中我是固定了文件名的，可以是改寫成動態輸入，由于在測試中我把所有的測試語句都放在同一個文件中了，沒有太多的必要。 六、心得體會 在編譯程序實現的過程中反復使用了遞歸調用的思想，且也使用了模塊化處理問題的思想，使用模塊化的思想關鍵是在抽象階段要抽象出對應的模塊，且模塊的層次必須是清晰的。 在實現此程序中，由于要實現關鍵字和符號表中字段的搜索，實現中就必須注意快速查找的方法，而在實現的過程中多次用到了二分搜索的方法，這是個比較快的搜索方法。 由于此程序的實現相對比較復雜，且不方便調試，改進時可以把此程序的詞法分析，語法分析和執行原代碼作為單獨的測試程序來測試，這樣也方便大家來調試。 通過本次的課設我知道了一個算法的設計是需要靜下心來仔細的研究的，且實現中必須先了解程序的整個流程，也就是說在編程中首先必須看懂那些對應的UML圖，只有在圖的指導下，編程中才不會盲目，也有一定的方向性。同樣在編程中必須注意代碼的規范，多寫一些對應的注釋是很必要的，要時刻想這代碼并不是給你自己看的，而是必須要給別人看，因此我覺得代碼的規范是相當重要的。 編譯原理課程設計任務書 1、目的學生在學習《程序設計語言編譯原理》課程過程中，結合各章節的構造編譯程序的基本理論，總共用10個課時完成課程設計。在基本實驗完成的基礎上，逐步完成課程設計。要求用C或C++語言描述及上機調試，實現一個小編譯器（詞法分析，語法分析，中間代碼產生，優化，目標代碼生成等重要子程序，其中詞法分析、語法分析及語義分析功能必須完成），使學生將理論與實際應用結合起來，受到軟件設計等開發過程的全面訓練，從而提高學生軟件開發的能力。 2、課程設計的任務 （1）設計符號表 確定符號表的組織方式，一般應包括名字欄和信息欄，其中名字欄作為關鍵字。要考慮能夠存儲有關名字的信息，并可以高效地完成如下操作： a.查找：根據給定的名字，在符號表中查找其信息。如果該名字在符號表中不存在，則將其加入到符號表中，否則返回指向該名字的指針； b.刪除：從符號表中刪除給定名字的表項。 （2）設計詞法分析器 設計各單詞的狀態轉換圖，并為不同的單詞設計種別碼。將詞法分析器設計成供語法分析器調用的子程序。功能包括： a.具備預處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設計一個供詞法分析調用的預處理子程序； b.能夠拼出語言中的各個單詞； c.將拼出的標識符填入符號表； d.返回（種別碼，屬性值）。 （3）語法分析與中間代碼產生器 要求用預測分析法、遞歸下降分析法、算符優先分析法、SLR分析法（幾種方法任選），實現對表達式、各種說明語句、控制語句進行語法分析。 若語法正確，則用語法制導翻譯法進行語義翻譯：對說明語句，要求將說明的各符號記錄到相應符號表中；對可執行語句，應產生出四元式中間代碼并填寫到三地址碼表中； 若語法錯誤，要求指出出錯性質和出錯位置（行號）。出錯處理應設計成一個出錯處理子程序。 （4）優化器 a.局部優化：設計出劃分基本塊的算法，在每一個基本塊中實現：合并已知量、刪除多余運算和刪除無用賦值三種局部優化。設計構造基本塊的DAG圖的算法，以及將DAG圖還原實現基本塊的優化的算法。 b.循環優化：只做一重循環優化，完成代碼外提，強度削弱和刪除歸納變量等三種優化。要求實現while循環和for循環語句的優化。 （5）目標代碼生成器 能完成指定寄存器個數的情況下將一中間代碼程序段翻譯成匯編語言目標代碼（匯編指令應包括加、減、乘、除），要求指令條數最少的情況下，盡量使用寄存器，盡量少訪問內存，這樣才能做到運行效率高。 3、樣本語言 樣本語言為C-語言(見附錄)，其中基本的語句要求必須實現，其余部分可根據自己的實際情況選擇實現。 4、要求 各函數和過程應有框圖描述，有功能說明，有入口和出口參數說明。 5、參考資料 《程序設計語言編譯原理》，陳火旺編著，國防工業出版社 《編譯原理》，呂映芝、張素琴、蔣維杜編著，清華大學出版社 《編譯原理》，Alfred V.Aho等，李建中譯，機械工業出版社 6、考察方式 最終完成一個完整的編譯程序。要求輸入一小段完整的C-語言源程序，輸出各編譯階段的運行結果。在課程設計結束時上機運行，展示運行效果。 7、作業提交 最晚在期末（第17周課程結束時）提交紙質作業及可運行程序，格式參考學院的規定課程設計任務書模板。第二篇：《編譯原理》課程設計報告--詞法分析器
第三篇：編譯原理課程設計
第四篇：編譯原理課程設計報告
第五篇：編譯原理課程設計設計任務書
點擊咨詢 