語法分析器實驗報告

實驗三語法分析器一、實驗目的：理解和掌握LL(1)語法分析方法的基本原理；根據(jù)給出的LL(1)文法，掌握LL(1)分析表的構造及分析過程的實現(xiàn)，掌握語法分析方法和程序設計方法。二、實驗要求：對每個非終極符按其產(chǎn)生式結(jié)構構造相應語法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過程調(diào)用命令。因為文法遞歸相應子程序也遞歸，所以稱這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結(jié)構與。產(chǎn)生式結(jié)構幾乎是一致的，通過設計、編程、調(diào)試出一個具體語法分析程序。三、實驗原理：語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結(jié)構是否符合語法規(guī)則。語法分析器的工作本質(zhì)上是按文法的產(chǎn)生式，識別輸入串是否是一個句子。自上而下分析法的主旨是，對任何輸入串，試圖用一切可能的方法，從文法開始符號出發(fā)，自上而下地為輸入串建立一棵語法樹。這種方法本質(zhì)上是一種試探過程，是反復使用不同產(chǎn)生式謀求匹配輸入串的過程。對于一個文法滿足以下三個條件，則稱該文法為LL(1)文法。文法不含有左遞歸。對于文法中的每一個非終結(jié)符A的各個產(chǎn)生式的侯選首符集兩兩不相交。即，若A->Q1|Q2|…|Qn則FIRST(Qi)^FIRST(Qj)=null(i!=j)對文法中的每個非終結(jié)符號A，若他存在某個侯選首符集包含空串，則FIRST(A)^FOLLOW(A)=null對于一個文法滿足LL(1)條件時，我們就可以對其輸入串進行有效的無回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終結(jié)符號。四、實驗步驟：1、功能描述：根據(jù)給定的文法，由程序生成項集族和語法分析表，對輸入的源程序進行詞法分析，得到語法分析的輸入串，經(jīng)過語法分析后得到三個棧，它們分別是狀態(tài)棧，字符棧，輸入棧，從而分析出輸入的源程序是否有語法錯誤。2、構造自己設計的小語言的語法分析器：(1)語言的語法描述(語法規(guī)則)的設計即文法的設計；(2)把文法形式符號中所隱含的信息內(nèi)容挖掘出來并用LL或LR的資料形式(分析表)表示出來；(3)語法分析的數(shù)據(jù)輸入形式和輸出形式的確定；(4)語法分析程序各個模塊的設計與調(diào)試。3、主程序流程圖：開始開始定義各個數(shù)據(jù)結(jié)構定義find()，first()，closure()，mygoto()，sign(),items()，reloatoken()函數(shù)main()函數(shù)開始從“in_gram.txt”文件中讀入文法；計算產(chǎn)生式的個數(shù)調(diào)用sign（）提取文法符號序列調(diào)用item（）分析項集簇輸出各狀態(tài)自動機，即項集簇輸出語法分析表首行根據(jù)anatab[i][j]的數(shù)值填寫分析表從“in_code.txt”讀入待分析代碼調(diào)用reload（）進行詞法分析把詞法分析的結(jié)果寫入“in_out.txt”從“in_out.txt”讀入詞法分析結(jié)果語法分析，把分析過程棧的狀態(tài)輸出結(jié)束五、程序的設計與實現(xiàn)：1、主要函數(shù)說明：1)find(state&unclosure,intn)函數(shù)：功能：判斷是否已包含某一產(chǎn)生式。在求閉包closure()函數(shù)中對其進行調(diào)用；參數(shù)說明：unclosure還沒有求閉包的狀態(tài)；n表示第幾個產(chǎn)生式；2)first(chartmp)函數(shù)：求各文法符號的first集，確定搜索符時使用到。在求閉包的函數(shù)中隊其進行調(diào)用；參數(shù)說明：tmp為需要求first集的文法符號；3)sign()函數(shù)：功能：提取文法符號序列，將所有的文法符號+’$’都存放在一個一維數(shù)組中，該數(shù)組在輸出分析表及語法分析中對棧進行處理時是需要使用；4)reloadtoken()函數(shù)：功能：詞法分析的結(jié)果。從文件中讀入字符到buff中，將得到的單詞定義成相應的運算符、分隔符，關鍵字k，標識符i，實數(shù)f'，整數(shù)n；寫入到out_in.txt文件中，該文件為詞法分析的輸出，語法分析的輸入；5)voiditems(coll&head)函數(shù)：功能：求LR(1)項目集族；6)voidclosure(state&unclosure)函數(shù)：功能：求LR(1)項目集族的閉包；7)statemygoto(conststate&cur,intk,inttmp)函數(shù)：功能：寫分析表anatab[][]，使用數(shù)字，空白用0，S移入為負數(shù)，r規(guī)約為正數(shù)，-32767表示acc接受。六、實驗結(jié)果（1）輸入一個文法（2）輸入一個符號串七、實驗結(jié)果分析：本次實驗借助語法分析，設計一個表達式的判斷分析器，從鍵盤上輸入算術表達式，分析器對該表達式的正確與否進行分析。若是正確的算術表達式，則符合文法，輸出正確；若是錯誤的算術表達式，則表達式不符合文法，輸出其錯誤之處并顯示異常。該程序執(zhí)行過程無誤，輸出結(jié)果正常。但由于我們的疏忽，該程序未能完全滿足實驗要求，并不能夠構造其LR分析表，并不是由該分析表驅(qū)動的語法分析器程序，這是本次實驗的一個缺陷。八、實驗總結(jié)：此次實驗，讓我對編譯原理的基本知識有了深入的了解，加強