【正文】 華北電力大學(xué)（北京）編譯原理課程設(shè)計(jì)LL(1)文法判定 c語(yǔ)言實(shí)現(xiàn)專(zhuān)業(yè)班號(hào)____計(jì)算機(jī)021_____學(xué)生姓名____3122020130____指導(dǎo)教師____齊林海________ 2006年 3 月 6 日35目 錄第一章 前 言 1 LL(1)文法概述 1 設(shè)計(jì)思想概述 1第二章 語(yǔ)言文法規(guī)則 1 語(yǔ)言的詞法規(guī)則 1 語(yǔ)言的語(yǔ)法規(guī)則 2第三章 程序設(shè)計(jì) 2 詞法分析程序的實(shí)現(xiàn) 2 文法輸入規(guī)則 2 數(shù)據(jù)結(jié)構(gòu) 2 程序流程 4 求解FIRST集、FOLLOW集和SELECT集的實(shí)現(xiàn) 5 求出能推出的非終結(jié)符ε 5 求解產(chǎn)生式的右部的FIRST集 6 求解非終結(jié)符的FOLLOW集 7 求解產(chǎn)生式的SELECT集 7 判定是否是LL(1)文法的實(shí)現(xiàn) 7 預(yù)測(cè)分析表的生成實(shí)現(xiàn) 7 判定給定符號(hào)串是否是文法中的句子的實(shí)現(xiàn) 8第四章 系統(tǒng)運(yùn)行及測(cè)試 9 運(yùn)行和安裝環(huán)境 9 系統(tǒng)運(yùn)行 9 系統(tǒng)測(cè)試 9 測(cè)試一 9 測(cè)試二 10第五章 結(jié) 論 11 系統(tǒng)結(jié)論 11 存在的不足 12參考文獻(xiàn) 12附 錄 13源程序 13第一章 前 言 本設(shè)計(jì)使用C語(yǔ)言實(shí)現(xiàn)了對(duì)簡(jiǎn)單方法描述的LL(1)文法的判定。該設(shè)計(jì)程序?qū)崿F(xiàn)了：⑴分別求出每一產(chǎn)生式的右部的FIRST 集、每一個(gè)非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集；⑵判定是否是LL(1)文法；⑶畫(huà)出預(yù)測(cè)分析表；⑷對(duì)給定的符號(hào)串判定是否是文法中的句子，分析過(guò)程用計(jì)算機(jī)打印出來(lái)。 LL(1)文法概述LL(1)文法是一種2型文法 ，由它所描述的語(yǔ)言可以使用自頂向下語(yǔ)法分析方法進(jìn)行語(yǔ)法分析。LL(1)文法的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)即選擇哪一個(gè)產(chǎn)生式（規(guī)則）進(jìn)行推導(dǎo)。一個(gè)上下文無(wú)關(guān)文法（即2型文法）是LL（1）文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A→α，A→β，滿(mǎn)足SELECT（A→α）∩SELECT（A→β）= 248。其中α、β不同時(shí)能ε[1]。 設(shè)計(jì)思想概述首先對(duì)輸入的文法進(jìn)行詞法分析，識(shí)別出所有的文法符號(hào)（終結(jié)符和非終結(jié)符）并對(duì)其編碼生成相應(yīng)ID，同時(shí)用單鏈表型數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)單個(gè)產(chǎn)生式，產(chǎn)生式的文法符號(hào)在單鏈表中以其相應(yīng)ID表示，即所有的產(chǎn)生式以規(guī)定形式存儲(chǔ)在一個(gè)單鏈表集中。第二步，針對(duì)單鏈表型數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)算法計(jì)算出每一個(gè)表達(dá)式右部的FIRST 集、每一非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集，其結(jié)果均以單鏈表集的形式存儲(chǔ)。最后，由求出的SELECT集經(jīng)由相應(yīng)算法判定出該輸入文法是否為L(zhǎng)L(1)文法，若是，則在屏幕上輸出預(yù)測(cè)分析表，并對(duì)給定的符號(hào)串判定是否是文法中的句子，分析過(guò)程用計(jì)算機(jī)打印出來(lái)。第二章 語(yǔ)言文法規(guī)則 語(yǔ)言的詞法規(guī)則為簡(jiǎn)單起見(jiàn)，本設(shè)計(jì)規(guī)定非終結(jié)符集VN為所有大寫(xiě)字母的集合，終結(jié)符集VT為所有小寫(xiě)字母、數(shù)字和四則運(yùn)算符號(hào)的集合，取所有文法符號(hào)均為單個(gè)字符。 語(yǔ)言的語(yǔ)法規(guī)則由2型文法的定義，定義如下：設(shè)G=（VN，VT，P，S），若P中的每一個(gè)產(chǎn)生式α→β滿(mǎn)足： α是一非終結(jié)符， β∈(VN∪VT)*則此文法稱(chēng)為2型的或上下文無(wú)關(guān)的[1]。規(guī)定產(chǎn)生式的左部必須為非終結(jié)符。第三章 程序設(shè)計(jì) 詞法分析程序的實(shí)現(xiàn) 文法輸入規(guī)則源文法的輸入采用文件輸入的方式，每讀入一個(gè)字符就進(jìn)行文法符號(hào)的判定、記錄和編碼，同時(shí)對(duì)產(chǎn)生式以特定格式存儲(chǔ)。文件中源產(chǎn)生式的書(shū)寫(xiě)格式規(guī)定如下：格式為“左部右部”，左部為一非終結(jié)符，右部的文法符號(hào)之間不允許有空格，右部結(jié)束后直接回車(chē)或文件結(jié)束，規(guī)定文件的第一個(gè)字符為文法的開(kāi)始符號(hào)；格式中使用“”而非“”的原因在于簡(jiǎn)化詞法分析，可以避免在讀入字符“”時(shí)的分情況處理（因?yàn)椤啊币彩且粋€(gè)終結(jié)符）。舉例如下：/*file:e:\*/SABSbCAamp。AbBamp。BaDCADCbDaSDc 數(shù)據(jù)結(jié)構(gòu)對(duì)非終結(jié)符和終結(jié)符分別采用以下的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)：typedef struct Vn_stru{ unsigned int ID。 char Nch。 unsigned int ifgetnull。 }Vn_type。Vn_type Vn[100]。 int Vn_ID_next。以上為非終結(jié)符的存儲(chǔ)結(jié)構(gòu)，對(duì)非終結(jié)符采用結(jié)構(gòu)體數(shù)組存儲(chǔ)。結(jié)構(gòu)體中ID存儲(chǔ)非終結(jié)符的編碼（關(guān)于編碼，程序中規(guī)定非終結(jié)符的編碼從200開(kāi)始，第一個(gè)被“發(fā)現(xiàn)”的非終結(jié)符被編碼為200，按照被“發(fā)現(xiàn)”順序依次編碼為201,202,…,程序最多允許100個(gè)非終結(jié)符，即編碼范圍在200~299之間。對(duì)于終結(jié)符，采用同樣的規(guī)則對(duì)其編碼，編碼范圍在300~399之間），Nch存儲(chǔ)其字符，ifgetnull指示該終結(jié)符能否推出ε，用于對(duì)三個(gè)集合的求解過(guò)程中。Vn[]存儲(chǔ)所有的非終結(jié)符。Vn_ID_next指示下一個(gè)可用的非終結(jié)符的編碼值，初始為200。typedef struct Vt_stru{ unsigned int ID。 char Tch。}Vt_type。Vt_type Vt[100]。 int Vt_ID_next。 以上為終結(jié)符的存儲(chǔ)結(jié)構(gòu)，在結(jié)構(gòu)體中，ID存儲(chǔ)其編碼，Tch存儲(chǔ)其字符。所有終結(jié)符存儲(chǔ)在Vt[]中。Vt_ID_next提示下一個(gè)可用的終結(jié)符的編碼值。需要指出的是，出于降低程序復(fù)雜度的考慮，‘ε’（程序中以‘a(chǎn)mp?！复┖汀灰越K結(jié)符的身份處理。如前所述，分析所得的文法存儲(chǔ)在單鏈表集中。鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：typedef struct IDNode{ unsigned int ID。 struct IDNode *next。}IDNode。結(jié)點(diǎn)中存儲(chǔ)文法符號(hào)的編碼和指向下一結(jié)點(diǎn)的指針。單鏈表集用IDNode*指針數(shù)組表示，即：IDNode *ppro[100]。 詞法分析的結(jié)果，即第i個(gè)產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：左部作為第一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的地址存儲(chǔ)在ppro[i]中，即第i個(gè)產(chǎn)生式的首結(jié)點(diǎn)地址存儲(chǔ)在ppro[]的第i個(gè)元素中,右部第一個(gè)符號(hào)作為第二個(gè)結(jié)點(diǎn)，向右依次將右部所有文法符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)加入到單鏈表的尾部。例如：SABSbC存儲(chǔ)方法為如圖31所示ppro[0]ppro[1]ppro[2]200201202 NULL200300300 NULL 100 101 102 100 200 103 圖31（假定S、A、B、C、b的編碼分別為100、101010200） 程序流程 詞法分析由函數(shù)File_Input (FILE *fp)實(shí)現(xiàn)，具體實(shí)現(xiàn)見(jiàn)附錄源程序。以下是程序的流程圖：否從文件中讀入一個(gè)字符否否是檢查Vn[]中是否存在此符號(hào),若無(wú),填之是準(zhǔn)備在ppro[i+1]中填入結(jié)點(diǎn)若字符不是判定為終結(jié)符檢查Vt[]中是否存在此符號(hào),若無(wú),填之在ppro[i]中填入代表該字符的結(jié)點(diǎn)讀入下一個(gè)字符是結(jié)束是否為非終結(jié)符是否為EOF文件結(jié)束符是否為回車(chē)換行圖32 求解FIRST集、FOLLOW集和SELECT集的實(shí)現(xiàn)存儲(chǔ)FIRST集、FOLLOW集和SELECT集的數(shù)據(jù)結(jié)構(gòu)采用如圖31的單鏈表集，分別命名為FirstRight[]、Follow[]和Select[]，在這里，每個(gè)結(jié)點(diǎn)的ID必然大于等于300，因?yàn)檫@些集合的元素都必然是終結(jié)符。每個(gè)單鏈表中的結(jié)點(diǎn)將按其ID的大小順序由小到大排列。需要指出的是，對(duì)三個(gè)集合的求解在算法上是對(duì)單鏈表集ppro[]進(jìn)行若干種鏈表操作的組合，故具體過(guò)程（分別由getFirstVn()、getFirstRight()、etFollow()和getSelect()實(shí)現(xiàn)）不再給出，下面給出的是邏輯算法。 求出能推出的非終結(jié)符ε算法如下：1) 將結(jié)構(gòu)體數(shù)組Vn[]中對(duì)應(yīng)每一非終結(jié)符的能否推出ε的標(biāo)記ifgetnull（如前所述，ifgetnull為結(jié)構(gòu)體變量Vn_type的成員變量，）置初值“未定”即2。2) 掃描方法中的產(chǎn)生式（程序中的掃描對(duì)象為ppro[]的拷貝pprotemp[]）。a) 刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)記值改為“否”，說(shuō)明該非終結(jié)符不能推出ε。（在程序中的操作為：刪除含有ID大于或等于300的結(jié)點(diǎn)的單鏈表，若這使得表示某一非終結(jié)符為左部的產(chǎn)生式的所有單鏈表都被刪除，則將Vn[]中對(duì)應(yīng)的ifgetfull置為0）b) 若某一非終結(jié)符的某一產(chǎn)生式右部為ε,則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。（程序中的操作為：刪除含有對(duì)應(yīng)ε的ID的結(jié)點(diǎn)的單鏈表，置該單鏈表的第一個(gè)結(jié)點(diǎn)所表示的非終結(jié)符對(duì)應(yīng)的Vn[]中元素的ifgetnull為1，并從pprotemp[]刪除所有以該非終結(jié)符對(duì)應(yīng)的結(jié)點(diǎn)為第一結(jié)點(diǎn)的單鏈表。）3) 掃描產(chǎn)生式右部的每一符號(hào)a) 若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是“是”，則刪去該非終結(jié)符，若這使產(chǎn)生式右部為空，則對(duì)產(chǎn)生式左部的非終結(jié)符在數(shù)組中對(duì)應(yīng)的標(biāo)志改為“是”，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。（程序中的操作為：若所掃描到的結(jié)點(diǎn)所表示的非終結(jié)符號(hào)的ifgetnull被標(biāo)記為1,則刪去該結(jié)點(diǎn)，若這使該單鏈表只剩一個(gè)結(jié)點(diǎn)，則標(biāo)記該產(chǎn)生式左部的非終結(jié)符的ifgetnull為1，并刪除pprotemp[]中所有以該非終結(jié)符對(duì)應(yīng)的結(jié)點(diǎn)為第一結(jié)點(diǎn)的單鏈表）b) 若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是“否”，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對(duì)應(yīng)的標(biāo)志改為“否”。（程序中的操作為：刪除含有對(duì)應(yīng)的ifgetnull==0的結(jié)點(diǎn)的單鏈表，若這使表示產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式的單鏈表都被刪去，則把左部非終結(jié)符對(duì)應(yīng)的ifgetnull置為0。）4) 重復(fù)3），直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對(duì)應(yīng)的特征再?zèng)]有改變?yōu)橹?。（程序中設(shè)置了標(biāo)志變量ifVnChanged用以標(biāo)識(shí)非終結(jié)符對(duì)應(yīng)的特征有沒(méi)有改變。）[1]該過(guò)程由函數(shù)getNULLVn()實(shí)現(xiàn)，由于對(duì)存儲(chǔ)文法的鏈表有刪除操作，為保護(hù)數(shù)據(jù)，函數(shù)開(kāi)始時(shí)先從ppro[]拷貝了一個(gè)臨時(shí)單鏈表集pprotemp[],所有刪除操作均在后者中進(jìn)行，并在程序結(jié)束時(shí)釋放了pprotemp[]的地址空間。函數(shù)的結(jié)果存儲(chǔ)在Vn[]中。 求解產(chǎn)生式的右部的FIRST集首先，計(jì)算每個(gè)文法符號(hào)的FIRST集。由定義：FIRST（α）={a|aαβ,a∈VT，a、β∈V*}，若αε，則規(guī)定ε∈FIRST（α）對(duì)每一文法符號(hào)X∈V計(jì)算FIRST（X）。a) 若X∈VT，則FIRST（X）={X}b) 若X∈VN，且有產(chǎn)生式X→a…，a∈VT則a∈FIRST（X）c) 若X∈VN，X→ε，則ε∈FIRST（X）d) 若X∈VN，Y1，Y2，…，Yi都∈VN，而有產(chǎn)生式X→Y1Y2…Yn。當(dāng)Y1，Y2，…，Yi1都ε時(shí)，（其中1≤i≤n），則FIRST（Y1）{ε}，F(xiàn)IRST（Y2）{ε}，…， FIRST（Yi1）{ε}，F(xiàn)IRST（Yi）都包含在FIRST（X）中。e) 當(dāng)d)中所有Yi ε，（i=1，2，…n）則FIRST（X）=FIRST（Y1）∪FIRST（Y2）…∪FIRST（Yn）∪{ε}。反復(fù)使用上述(b)~(e)步直到每個(gè)符號(hào)的FIRST集合不再增大為止。求出每個(gè)文法符號(hào)的FIRST集合后也就不難求出一個(gè)符號(hào)串的FIRST集合。若符號(hào)串α∈V*，α=X1X2…Xn，當(dāng)X1不能ε，則置FIRST（α）=FIRST（X1）。若對(duì)任何j( 1≤j≤i1,2≤i≤n)，ε∈FIRST（Xj）則FIRST（α）=（FIRST（Xj）{ε}）∪FIRST（Xi）當(dāng)所有FIRST（Xj）( 1≤j≤n)都含有ε時(shí)，則FIRST（α）=（FIRST（Xj））∪{ε}[1]。由此算法可計(jì)算出各文法符號(hào)的FIRST集和各產(chǎn)生式的右部的FIRST集，分別存儲(chǔ)在FirstVn[]和FirstRight[]中。定義如下：/*LL(1).h*/IDNode *FirstVn[100]。 IDNode *FirstRight[100]。 該過(guò)程分別由函數(shù)getFirstVn()和getFirstRight()實(shí)現(xiàn)，兩者又調(diào)用了兩個(gè)鏈表操作函數(shù)insert2link()和add2link()以及一個(gè)輔助函數(shù)getFirstExp()來(lái)實(shí)現(xiàn)具體功能，后三都的功能分別為插入結(jié)點(diǎn)到單鏈表、拷貝單鏈表到另一單鏈表、得到任意字符串的FIRST集。詳見(jiàn)附錄源程序。 求解非終結(jié)符的FOLLOW集算法如下：對(duì)文法中每一A∈VN計(jì)算FOLLOW(A)a) 設(shè)S為文法中開(kāi)始符號(hào)，把{}加入FOLLOW（S）中。b) 若A