1、精選優質文檔-傾情為你奉上編譯原理課程設計任務書1、 本課題的目的及意義課程設計實踐對學生鞏固所學基礎專業課程知識、進行編譯系統基本技能訓練、培養實踐動手能力，從而掌握編譯系統的基本工作原理、基本方法和基本開發技術，最終達到具有一定的編譯系統的實際開發能力有重要意義。通過課程設計，主要達到以下目的：1.幫助學生深入理解編譯原理的有關理論和鞏固編譯原理相關知識。2. 鞏固學生學習的編譯原理、程序設計語言、數據結構等課程的基礎知識，訓練學生分析和解決編譯系統的相關問題的能力，提高學生的綜合素質。3. 從軟件工程的角度來看，編譯原理課程設計是一個很好的實例，可以訓練學生軟件設計的能力以及編碼調試能力

2、。2、本課題任務的主要內容本課程設計主要內容包括以下幾點:1、根據選定的題目，查閱資料，熟悉相關理論、方法；（1）掌握文獻檢索方法，以獲得編譯系統開發技術等相關資料；（2）學習并熟練使用一種4GL開發平臺（如VC+、Java、Dephi、PB、VB等）；2、分析問題，確定系統邏輯結構；3、確定系統所需模塊及模塊結構，并用流程圖描述各模塊；4、編碼及調試程序；5、撰寫課程設計說明書。3、提交的成果1、一份符合課程設計說明書撰寫規范的課程設計說明書。2、一套系統原型。器的設計指導教師 王勇 作者 陳慧娟摘 要語法分析的主要任務是接收詞法分析程序識別出來的單詞符由某種號串，判斷它們是否語言的文法產生

3、，即判斷被識別的符號串是否為某語法部分。 一般語法分析常用自頂向下方法中的LL（1）分析法，采用種方法時，語法分程序將按自左向右的順序掃描輸入的的符號串，并在此過程中產生一個句子的最左推導，即LL（1）是指自左向右掃描，自左向右分析和匹配輸入串。我們使用VC+作為前端開發工具，在分析語法成分時比較方便直觀，更便于操作。運行程序的同時不斷修正改進程序，直至的到最優源程序。關 鍵 字 語法分析 文法 自頂向下分析 LL(1)分析 最左推導AbstractGrammatical analysis of the main tasks was to receive lexical analysis pr

4、ocedure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. General syntax analysis commonly used top-down methods of LL analysis, using methods, Grammar hours will be from

5、the procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, LL is scanned from left to right, From left to right analysis and matching input strings. After analysis, we use VC + + as a front-end development too

6、l for the analysis of syntax ingredients more convenient visual, more easy to operate. Operational procedures at the same time constantly improving procedures, until the source of optimal. Key WordsGrammatical analysis grammar Top-down analysis LL (1) Analysis Most left Derivation目錄引言第1章 概述51.1 編寫目的

7、51.2 項目背景51.3 軟件定義61.4 開發環境6第2章 需求分析72.1問題陳述72.2功能要求72.3數據流圖8第3章 設計任務分工 103.1 小組的任務分工103.2 本人主要工作10第4章 系統設計 114.1總體設計 114.1.1 LL(1)文法改造和源程序預處理114.1.2 LL(1)文法的判別、消除左公因子、消除左遞歸144.1.3預測分析器的構造 164.1.4構造生成LL(1)語法樹184.2詳細設計21第5章 運行與測試結果 295.1測試數據295.2界面實現情況29結論與展望30參考文獻 31致謝32引言編譯器的構造工具是根據用戶輸入的語言的文法，編譯器的構

8、造工具可以生成程序來處理以用戶輸入的文法書寫的文本。隨著計算機應用范圍的擴大，在軟件自動生成，文檔處理，特定專業的語言等領域，編譯器的構造工具這一技術顯得越來越重要。一個編譯程序在對某個源程序完成了詞法分析工作之后，就進入語法分析階段，分析檢查源程序是否是語法上正確的程序，并生成相應的內部中間表示供下一階段使用。程序設計語言是一般形式語言的特例，程序語法正確性的檢查正是語法句子的識別，語法分析問題也就是句型識別問題。按照識別句子時語法樹建立的方式，有自頂向下與自底向上兩大類分析技術。本課程設計討論自頂向下的情況。本次課程設計所做的工作是用VC要建立一個針對LL(1)文法的編譯器的編譯器。本文既

9、可以以定義好的文法書寫的文件作為輸入，其中包括語法及語義動作，鑒于輸入文件的所用的文法可以用LL(1)分析，于是對輸入的文件用遞歸下降的分析方法在內存中建立它的存儲結構，然后分別計算所輸入的文法的非終結符號是否可以生成空，每個非終結符號的first集合，每個非終結符號的follow集合，以及每個規則的predict集合，接著判斷任意一個非終結符號的任意兩個規則的Predict集的交集是不是都為空，如果是則輸入文法可以用遞歸下降法分析，否則不可以，用戶應該對所輸入的文法作適當的修改，使其滿足LL(1)文法分析的要求，。如果所輸入的文法可以用遞歸下降法分析，生成相應文法的語法分析程序。也可以自行添

10、加文法，本課程設計有根據相應文法自動生成分析表和語法樹，并將分析信息和結果保存到一個外部文件中的的功能，能靈活實現語法編譯器的相應功能。 第1章 概述1.1 編寫目的語法分析器通過接受詞法分析程序識別出來的單詞符號串，判斷它們是否由某種語言的文法產生，即判斷被識別符號串是否為某語法成分，同時進行語法檢查，為后面的語義分析和代碼生成作準備。本次課程設計所做的工作是用VC要建立一個針對LL(1)文法的編譯器的編譯器。本文既可以以定義好的文法書寫的文件作為輸入，其中包括語法及語義動作，鑒于輸入文件的所用的文法可以用LL(1)語法分析，根據相應文法自動生成分析表和語法樹，并將分析信息和結果保存到一個外

11、部文件中的的功能，能靈活實現語法編譯器的相應功能。1.2 項目背景 編譯程序是現代計算機系統的基本組成部分之一，而且多數計算機系統都配有不止一個高級語言的編譯程序。由于早期的機器語言、匯編語言編寫起來不容易、又枯燥無味，所以開發一種更類似數學定義和自然語言的簡潔形式來編寫程序的操作，應與任何機器無關的編譯器十分重要。編譯器的構造工具是根據用戶輸入的語言的文法，可以生成程序來處理以用戶輸入的文法書寫的文本。隨著計算機應用范圍的擴大，在軟件自動生成，文檔處理，特定專業的語言等領域，編譯器的構造工具這一技術顯得越來越重要。一個編譯程序在對某個源程序完成了詞法分析工作之后，就進入語法分析階段，分析檢查

12、源程序是否是語法上正確的程序，并生成相應的內部中間表示供下一階段使用。程序設計語言是一般形式語言的特例，程序語法正確性的檢查正是語法句子的識別，語法分析問題也就是句型識別問題。按照識別句子時語法樹建立的方式，有自頂向下與自底向上兩大類分析技術。本課程設計討論自頂向下的情況。1.3 軟件定義Microsoft visual C+ 6.0:-Visual C+ 6.0是一個功能強大的可視化軟件開發工具。自1993年Microsoft公司推出Visual C+1.0后，隨著其新版本的不斷問世，Visual C+已成為專業程序員進行軟件開發的首選工具Visual C+6.0不僅是一個C+編譯器，而且是

13、一個基于Windows操作系統的可視化集成開發環境（integrated development environment,IDE）。Visual C+6.0由許多組件組成，包括編輯器、調試器以及程序向導AppWizard、類向導Class Wizard等開發工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發環境。Microsoft office Visio 2003：是微軟公司出品的一款的軟件，它有助于 IT 和商務專業人員輕松地可視化、分析和交流復雜信息。它能夠將難以理解的復雜文本和表格轉換為一目了然的 Visio 圖表。該軟件通過創建與數據相關的 Visio

14、 圖表（而不使用靜態圖片）來顯示數據，這些圖表易于刷新，并能夠顯著提高生產率。使用 Office Visio 2007 中的各種圖表可了解、操作和共享企業內組織系統、資源和流程的有關信息。1.4 開發環境操作系統：Microsoft Windows XP開發平臺：Microsoft visual C+ 6.0第2章 需求分析LL(1)分析法中，第一個L的含義是：從左向右的處理輸入進行分析，第二個L的含義是：為每個輸入串描繪出一個最左推導，1的含義是：向輸入串中輸入一個符號就可以唯一確定當前將要的產生式。構造出一個LL(1）語法分析器可以更加直觀的解決文法輸入串在面臨不同產生式的選擇上，所要進行

15、的分析操作，從而為開發人員帶來方便。2.1問題陳述建立一個針對LL(1)文法編譯器的自動生成器，要完成此編譯器需要對源文件進行兩遍處理：第一遍詞法分析、第二遍語法分析，語法分析程序應用LL(1)語法分析方法。首先輸入(打開)定義好的文法文件，然后建立詞法分析器，包括詞法分析主程序、掃描部分、關鍵字表等等。經詞法分析后分別計算所輸入的文法的每個非終結符號的FIRST集合、每個非終結符號的FOLLOW集合，以及每個規則的SELECT集合，并判斷任意一個非終結符號的任意兩個規則的SELECT集的交集是不是為空，如果是，則輸入文法符號是LL(1)文法，可以進行分析。在對文法的語法進行分析的過程中，要解

16、決各方面的問題如(1)當文法出現做遞歸時可能使分析過程陷入無限循環、(2)在推導過程中選擇哪一右部展開時，如果選擇錯誤，將導致回溯。對文法進行改造，要實現把某些非LL(1)文法到LL(1)文法的等價變換。其總起過程大體包括以下各方面：1、提取左公因子 2、消除左遞歸。2.2 功能要求設計一個給定LL（1）語法分析器，輸入一個句子，能由依據LL（1）分析表輸出與句子對應的語法樹。能對語法樹生成過程進行模擬。動態模擬算法的基本功能是： 1、 詞法分析：打開或輸入一個文法文件或句子，能對其進行詞法分析，顯示token表信息，當存在錯誤時，能給出良好的錯誤提示。2、 語法分析：打開或輸入一個文法文件或

17、句子，能對其進行語法分析，能顯示器中間代碼信息，當存在錯誤時，能顯示出語法分析錯誤信息。3、 LL(1)文法判別:打開(輸入)一個形如E-abc的LL(1)文法，能對其求出FIRST集，FOLLOW集，并能用直觀的關系圖顯示；4、 預測分析： 打開(輸入)一個形如E-abc的LL(1)文法，能直觀的形成表達式文法的預測分析表。5、 句子語法樹；根據確認LL(1)文法，確認輸入串是否為文法的句子，是，則形成該符號串的分析過程，并直觀的顯示分析過程。6、 該語法分析器具有粘貼、復制、剪切、保存、退出功能！7、 總控程序：顯示各模塊功能！2.3數據流圖：數據流圖是結構化分析方法中使用的工具,它以圖形

18、的方式描繪數據在系統中流動和處理的過程，由于它只反映系統必須完成的邏輯功能，所以它是一種功能模型。數據流圖英文縮寫DFD（Data Flow Diagram）它是描繪信息流和數據從輸入移動到輸出的過程中所經受的變換。 數據流圖從數據傳遞和加工的角度，以圖形的方式刻畫數據流從輸入到輸出的移動變換過程。該系統的實現的整個過程的數據流圖大體如下：LL(1)語法分析器0層圖LL(1)語法分析器1層圖：LL(1)語法分析器2層圖：第3章 設計任務分工3.1 小組的任務分工本小組的任務是編寫一個程序，進行分析表的構造。學號姓名職責主要任務鄒紀標組長消除間接左遞歸，構造分析表 陳春輝組員計算SELECT集，

19、提取左公因子閆瑞雪組員LL(1)文法的判定江於組員計算FIRST集龔玉靜組員計算FIRST集陳慧娟組員計算FOLLOW集趙夢組員計算FOLLOW集王報興組員消除直接左遞歸3.2 本人主要工作 在這次課程設計中本人的任務是計算FOLLOW集，為后面求SELECT集、判斷所給文法是否是LL（1）文法。第四章 系統設計4.1 總體設計4.1.1文法改造和源程序預處理假設條件：（1） 文法G = (N, , P, S) 的產生式規則都取如下的形式：V - w，則稱之為上下文無關的，其中 VN ，w(N)* 。N（A|.|Z），N=，SN。（2） 源程序中的注釋只支持格式：/注釋內容設計相關任務說明：（

20、1） 打開文件（當然也可以手工輸入），在窗口中顯示文法內容。點擊“加載”，選擇文件，確定，界面如下。（2）若手工輸入，輸入文法，則界面如下：1. 保存文法，點擊“保存”按鈕，輸入文件名，確定，即可將文法以一定的格式保存在文件中。2. 在編輯框中輸入源程序，點擊“Token串”，則對源程序濾掉空格，跳過注釋、換行符，變為可被語法分析部分識別的輸入串。3. 判斷文法是否為上下文無關文法。4. 文法改造部分，去掉形如AA的有害產生式。5. 文法改造部分，去掉不可終止符及其產生式。6. 文法改造部分，去掉不可達符及其產生式。7. 符號表的構造。 4.1.2分析表的構造分析表的構造模塊由以下幾個部分組成

21、：集合的求解，判斷文法是否是LL(1)文法、消除左公共因子及左遞歸、構造分析表。該模塊的結構框圖如下：該模塊的構造共完成以下任務該部分的功能是判斷一個文法是否為LL(1)文法，它通過對輸入的文法求解FIRST集、FOLLOW集、SELECT集，最后根據SELECT集是否相交來判斷，如果SELECT集相交，測通過提取左公因子，消除左遞歸看是否可以構成LL(1)文法；如果SELECT集不相交，則該文法是LL(1)文法。消除左公共因子及左遞歸這部分能夠對非LL(1)文法進行改造，使其可能成為LL(1)文法。它先對文法進行判斷，看其是否含有左公共因子，若有則消除，若無則不作任何處理，然后再判斷文法是否

22、含有直接或間接左遞歸，若有則消除，若無則不作任何處理。構造分析表通過以上first，follow，select集的求解，判斷是否是LL（1），然后通過流程圖及算法描述，編寫程序構造分析表。4.1.3 LL(1)預測語法分析LL（1）語法分析的模塊原理如下：首先初始化棧，#進棧，E進棧作為文法開始的狀態。初始化產生式表、非終結符表、終結符表。根據產生式表的產生式生成每個非終結符的FIRST集及FOLLOW集。參考2、3模塊，由一個算法生成預測分析表，該預測分析表是由一個二維數組Mn1n2構成。由定理可知：若aSELECT(A ),則把A 放于矩陣MA,a。而這里生成的二維數組Mn1n2與該定理類

23、似。不過這里n1是指A在非終結符表中的序號，n2是指a在終結符表中的序號，而Mn1n2的值是指產生式A 在產生式表中的序號。這樣做就為下面的預測分析程序帶來了方便。預測分析程序分為檢測不合法輸入模塊和對輸入字符串的語法分析模塊。對輸入字符串的語法分析是通過棧及產生式表和預測分析表的相關聯系構建一個算法來對這個字符串進行語法分析。通過算法將棧頂元素與輸入字符串的比對、出棧及相關產生式的推導的右部的逆序入棧等操作可完成對輸入字符串的語法分析。LL（1）語法預測分析總流程圖4.1.4構造生成LL(1)語法樹算法思想：本模塊的主要功能是將產生式的序列以語法樹的方式顯示，本組對其進行詳細研究后，發現可以

24、將其分成兩個模塊分別處理。第一個模塊是將產生式結構轉換成樹形的結構進行存儲，第二個模塊是將以樹形結構存儲的語法樹以樹形目錄的方式輸出。第一個模塊，涉及到兩個數據結構：產生式的數據結構和樹的數據結構。產生式的結構定義存放在Generation.h文件中，在此簡述，有兩個屬性：產生式左部string類型的left和產生式右部vector類型的right。對于傳送到本模塊的產生式序列，要求它們以vector的形式存放，使用的時候則可以用下標的方式逐個引用。樹的結構定義在Tree.h中。整體思想如下：產生式的序列一定是按照最左推導得到的序列，所以樹的構造也應按照最左構造，對于如下的簡單的語法樹 其產生

25、式序列必然為： S-BaFB-ACDA-aC-cD-dF-a如此在構造樹的時候必然也要按照如下次序：構造節點S構造S的子節點構造B的子節點構造A的子節點構造C的子節點構造D的子節點構造F的子節點1可設置一個current指向當前節點，最初current指向根節點。2掃描產生式，每次得到一個產生式，將其左部存到current指向的節點，然后申請若干新節點存放產生式右部的符號。3 若右部有非終結符，則將current指向第一個，進行下一次掃描4 若右部沒有非終結符，則說明這次推導已到一個子樹的樹葉。向上回溯，找父節點的相鄰非終結符節點，若父節點沒有相鄰非終結符則繼續向上回溯，直到找到為止，并將cu

26、rrent指向它，進行下一次掃描。若回溯到根節點則說明樹已構造完畢。在構造非終結符節點的時候需要設置該節點的next指針，例如構造A時要設置其next指針指向C，目的是構造完a之后可以尋找下一個要構造的節點，father指針指向B，目的是在構造完D之后可以向上回溯通過B的next指針找到下一個要構造的節點F。對于第二個顯示模塊，思想如下：1首先current指向根節點，并輸出根節點2 輸出current的子節點，并將current指向最左的一個非終結符子節點，用遞歸的思想輸出該節點的子樹，然后current繼續第二個非終結符子節點，并用遞歸輸出其子樹。4.2詳細設計自頂向下語法分析方法 語法分

27、析方法是編譯程序的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子（程序），目前語法分析方法有自頂向下分析和自底向上分析兩大類。自頂向下分析包括確定分析和不確定分析，自底向上分析又包括算符優先分析和LR分析這些分析方法各有優缺點。然而除了自頂向下的不確定分析方法外，都是當今編譯程序構造的使用方法。 自頂向下的分析也稱面向目標的分析方法，也就是從文法的開始符號出發企圖推到出一輸入的單詞串完全像匹配的句子，若輸入串是給定文法的句子，則必能退出，反之必然出錯。自頂向下的確定分析方法需對文法有一定的限制，但由于實現方法簡單、直觀，便于手工構造或自動生成語法分析器，因而

28、仍是目前常用的方法之一。確定的自頂向下分析方法，是從文法的開始符號出發，考慮如何根據當前的輸入符號（單詞符號）唯一地確定選用哪個產生式替換相應非終結符一往下推導，或如何夠著一顆相應的語法樹。當我們需選用自頂向下分析技術時，首先必須判別所給文法是否是LL（1）文法。因而對任給文法需計算FIRST、FOLLOW、SELECT集合，進而判別文法是否是（）文法。有關已有其他同學詳細敘述，在這里就不在贅述。在此詳細敘述關于集的定義及有關算法。預測分析方法是自頂向下分析的另一種方法，一個預測分析器是由三個部分組成。預測分析程序先進后出棧預測分析表其中只有預測分析表與文法有關，而分析表有可用一個矩陣（或二維

29、數組）表示。矩陣的元素，中的下表表示非終結符，為終結符或句子括號“”，矩陣元素，中的內容是一條關于的產生式，表明當用非終結符向下推導時，面臨輸入符時，所應采取的候選產生式，當元素內容物產生式時，則表明用為左部向下推導遇到了不該出現的符號，因此元素內容為轉向出錯處理的信息。預測分析程序的工作過程用下圖表示。圖中符號說明如下：“”句子括號集輸入串的括號“”文法的開始符號“”存放當前棧頂符號的工作單元“”存放當前輸入符號的工作單元開始否是否是否否是X=a ?X=a ?X=# ?結束XVT?上托棧頂符號放入X# S 進棧，當前終結符送a若產生式為Xx1x2xn按逆序即xnx2x1入棧是讀入下一符號X=

30、a ?是MX,a是產生式嗎？否出錯出錯預測分析程序的框圖1.FOLLOW集的定義 設G=（VT，Vn，S，P)是上下文無關文法，AVN，S是開始符號 FOLLOW(A)=a|S* A且aFIRST（），V*T，V+ 若有S* A，且*，則#FOLLOW(A)。其中#作為輸入串的結束符，或稱輸入串括號。2. 計算FOLLOW集(1)根據定義計算 對文法中每一AVT計算FOLLLOW（A） 設S為文法的開始符號，把#加入FOLLOW（S)中（這里“#”為句子括號）。 若AB是一個產生式，則把FIRST（）的非空元素加入FOLLOW（B）中。如果*則把FOLLOW（A)也加入FOLLOW（B）中。

31、反復使用直到每個非終結符的FOLLOW集不再增大為止。（2） 用關系圖法球非終結符的FOLLOW集 文法G中的每一個符號和“#”對應圖中的一個結點，對應終結符和“#”的結點用符號本身標記。對應終結符的結點（如ACVT）則用FOLLOW（A)標記。 從開始符號S的FOLLOW（S)結點到“#”號的結點連一條箭弧。 如果文法中有產生式ABX，且*，則從FOLLOW（B)結點到FIRST（X)結點連一條弧，當XVT時，則與X相連。 如果文法中有產生式AB且*則從FOLLOW（）結點到FOLLOW（A)結點連一條弧。對每一FIRST（）結點如果有產生式 AX，且*，則從FIRST（）到FOLLOW（）

32、連一條箭弧。 凡是從FOLLOW（A)結點有路徑可以到達的終結符或“#”號的結點，其所標記的終結符或“#”號即為FOLLOW（A)的成員。如文法為 得（）（），（）（）（）FOLLOW(B)FOLLOW(D)FOLLOW(S)FOLLOW(A)FOLLOW(C)FIRST(D)FIRST(B)#ac計算集的關系圖3.求解FOLLOW集合的算法 逐一掃描代碼中的產生式, 將產生式右部賦給 串,j表示 串中的第j 個字符。 逐一掃描產生式的右部, 若j為非終結符X, 找出j后繼的第一個字符k。若k為終結符, 則將該終結符加入到FOLLOW 集合, 結束, 跳出;若k為非終結符, 則FIRST 集合

33、- , 執行。 逐一掃描X 后的字符串,分為下面兩種情況:a.若非終結符k能推出空字符串, 則k+, 繼續執行、兩步;b.若非終結符k為產生式最后一個字符, 則將該產生式的左部非終結符的FOLLOW 集合加入該非終結符的FOLLOW集合。 若掃描完全部的產生式, 則求得所有非終結符的FOLLOW 集合。在計算FOLLOW 集中也存在“ 環”和重復的終結符的問題, 解決的辦法與FIRST 集的相同。 計算FOLLOW集的流程圖產生式為：Xx1x2xnYk=i+1iVT?YXi=iN0i=n?Y#FOLLOW(X)X=S?NkVN?FOLLOW(X)FOLLOW(Xk)xk+1xk+2xn*YNk

34、*k+kFOLLOW(X)FIRST(k）-FOLLOW（i）結束6、部分代碼：void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri; /*c為待求的非終結符*/temp0=c;temp1=0;merge(fo,temp,1);if(c=start) /*若為開始符號*/temp0=#;temp1=0;merge(followi,temp,1); for(j=0;j=count-1;j+)if(in(c,rightj)=1) /*找一個右部含有c的產生式*/for(k=0;k+)if(rightjk=c)break; /

35、*k為c在該產生式右部的序號*/ for(m=0;m+)if(vm=leftj)break; /*m為產生式左部非終結符在所有符號中的序號*/if(k=strlen(rightj)-1) /*如果c在產生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue; if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1);else /*如果c不在產生式右部的最后*/for(n=k+1;n=strlen(rightj)-1;n+)empt0=0;result*=_emp(rightjn);if(result=1) /*如果右部c后面的符號串能推出*/ if(in(vm,fo)=1) /*避免循環遞歸*/merge(followi,followm,1);continue;if(