LL語法分析構(gòu)造表的設(shè)計 正文

《編譯原理課程設(shè)計》任務(wù)書1、 本課題的目的及意義課程設(shè)計實踐對學(xué)生鞏固所學(xué)基礎(chǔ)專業(yè)課程知識、進行編譯系統(tǒng)基本技能訓(xùn)練、培養(yǎng)實踐動手能力，從而掌握編譯系統(tǒng)的基本工作原理、基本方法和基本開發(fā)技術(shù)，最終達(dá)到具有一定的編譯系統(tǒng)的實際開發(fā)能力有重要意義。通過課程設(shè)計，主要達(dá)到以下目的：1.幫助學(xué)生深入理解編譯原理的有關(guān)理論和鞏固編譯原理相關(guān)知識。2.鞏固學(xué)生學(xué)習(xí)的編譯原理、程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)等課程的基礎(chǔ)知識，訓(xùn)練學(xué)生分析和解決編譯系統(tǒng)的相關(guān)問題的能力，提高學(xué)生的綜合素質(zhì)。3.從軟件工程的角度來看，《編譯原理》課程設(shè)計是一個很好的實例，可以訓(xùn)練學(xué)生軟件設(shè)計的能力以及編碼調(diào)試能力。2、 本課題任務(wù)的主要內(nèi)容本課程設(shè)計主要內(nèi)容包括以下幾點：1、 根據(jù)選定的題目，查閱資料，熟悉相關(guān)理論、方法；（1） 掌握文獻(xiàn)檢索方法，以獲得編譯系統(tǒng)開發(fā)技術(shù)等相關(guān)資料；（2） 學(xué)習(xí)并熟練使用一種4GL開發(fā)平臺（如VC++、Java、Dephi、PB、VB等）；2、 分析問題，確定系統(tǒng)邏輯結(jié)構(gòu)；3、 確定系統(tǒng)所需模塊及模塊結(jié)構(gòu)，并用流程圖描述各模塊；4、 編碼及調(diào)試程序；5、 撰寫課程設(shè)計說明書。3、提交的成果1、 一份符合課程設(shè)計說明書撰寫規(guī)范的課程設(shè)計說明書。2、 一套系統(tǒng)原型。LL⑴語法分析構(gòu)造器的設(shè)計指導(dǎo)教師王勇作者陳慧娟摘要語法分析的主要任務(wù)是接收詞法分析程序識別出來的單詞符由某種號串，判斷它們是否語言的文法產(chǎn)生，即判斷被識別的符號串是否為某語法部分。一般語法分析常用自頂向下方法中的LL(1)分析法，采用種方法時，語法分程序?qū)醋宰笙蛴业捻樞驋呙栎斎氲牡姆柎?，并在此過程中產(chǎn)生一個句子的最左推導(dǎo)，即LL(1)是指自左向右掃描，自左向右分析和匹配輸入串。我們使用VC++作為前端開發(fā)工具，在分析語法成分時比較方便直觀，更便于操作。運行程序的同時不斷修正改進程序，直至的到最優(yōu)源程序。關(guān)鍵字語法分析文法自頂向下分析LL(1)分析 最左推導(dǎo)AbstractGrammaticalanalysisofthemaintaskswastoreceivelexicalanalysisproceduretoidentifythewordsfromawebsite,string,andjudgewhethertheyhaveagrammarofthelanguage,thatis,judgingbytheseriesofsymbolstoidentifywhetheragrammarpart.Generalsyntaxanalysiscommonlyusedtop-downmethodsofLLanalysis,usingmethods,Grammarhourswillbefromtheproceduresoftheorderleft-to-rightscanninginputstringofsymbols,andintheprocessproducedoneofthemostleftthesentenceisderived,LLisscannedfromlefttoright,Fromlefttorightanalysisandmatchinginputstrings.Afteranalysis,weuseVC++asafront-enddevelopmenttoolfortheanalysisofsyntaxingredientsmoreconvenientvisual,moreeasytooperate.Operationalproceduresatthesametimeconstantlyimprovingprocedures,untilthesourceofoptimalKeyWordsGrammaticalanalysisgrammarTop-downanalysisLL(1)AnalysisMostleftDerivation目錄引言TOC\o"1-5"\h\z\o"CurrentDocument"第1章概述 51.1編寫目的 51.2項目背景 51.3軟件定義 61.4開發(fā)環(huán)境 6\o"CurrentDocument"第2章需求分析 7\o"CurrentDocument"2.1問題陳述 72.2功能要求 72.3數(shù)據(jù)流圖 8\o"CurrentDocument"第3章設(shè)計任務(wù)分工 103.1小組的任務(wù)分工 103.2本人主要工作 10\o"CurrentDocument"第4章系統(tǒng)設(shè)計 114.1總體設(shè)計 11LL(1)文法改造和源程序預(yù)處理 11LL(1)文法的判別、消除左公因子、消除左遞歸 144.1.3預(yù)測分析器的構(gòu)造 164.1.4構(gòu)造生成LL(1)語法樹 184.2詳細(xì)設(shè)計 21\o"CurrentDocument"第5章運行與測試結(jié)果 295.1測試數(shù)據(jù) 295.2界面實現(xiàn)情況 29結(jié)論與展望 30\o"CurrentDocument"參考文獻(xiàn) 31\o"CurrentDocument"致謝 32引言編譯器的構(gòu)造工具是根據(jù)用戶輸入的語言的文法，編譯器的構(gòu)造工具可以生成程序來處理以用戶輸入的文法書寫的文本。隨著計算機應(yīng)用范圍的擴大，在軟件自動生成，文檔處理，特定專業(yè)的語言等領(lǐng)域，編譯器的構(gòu)造工具這一技術(shù)顯得越來越重要。一個編譯程序在對某個源程序完成了詞法分析工作之后，就進入語法分析階段，分析檢查源程序是否是語法上正確的程序，并生成相應(yīng)的內(nèi)部中間表示供下一階段使用。程序設(shè)計語言是一般形式語言的特例，程序語法正確性的檢查正是語法句子的識別，語法分析問題也就是句型識別問題。按照識別句子時語法樹建立的方式，有自頂向下與自底向上兩大類分析技術(shù)。本課程設(shè)計討論自頂向下的情況。本次課程設(shè)計所做的工作是用VC要建立一個針對LL(1)文法的編譯器的編譯器。本文既可以以定義好的文法書寫的文件作為輸入，其中包括語法及語義動作，鑒于輸入文件的所用的文法可以用LL(1)分析，于是對輸入的文件用遞歸下降的分析方法在內(nèi)存中建立它的存儲結(jié)構(gòu)，然后分別計算所輸入的文法的非終結(jié)符號是否可以生成空，每個非終結(jié)符號的first集合，每個非終結(jié)符號的follow集合，以及每個規(guī)則的predict集合，接著判斷任意一個非終結(jié)符號的任意兩個規(guī)則的Predict集的交集是不是都為空，如果是則輸入文法可以用遞歸下降法分析，否則不可以，用戶應(yīng)該對所輸入的文法作適當(dāng)?shù)男薷?，使其滿足LL(1)文法分析的要求，。如果所輸入的文法可以用遞歸下降法分析，生成相應(yīng)文法的語法分析程序。也可以自行添加文法，本課程設(shè)計有根據(jù)相應(yīng)文法自動生成分析表和語法樹，并將分析信息和結(jié)果保存到一個外部文件中的的功能，能靈活實現(xiàn)語法編譯器的相應(yīng)功能。第1章概述1.1編寫目的語法分析器通過接受詞法分析程序識別出來的單詞符號串，判斷它們是否由某種語言的文法產(chǎn)生，即判斷被識別符號串是否為某語法成分，同時進行語法檢查，為后面的語義分析和代碼生成作準(zhǔn)備。本次課程設(shè)計所做的工作是用VC要建立一個針對LL(1)文法的編譯器的編譯器。本文既可以以定義好的文法書寫的文件作為輸入，其中包括語法及語義動作，鑒于輸入文件的所用的文法可以用LL(1)語法分析，根據(jù)相應(yīng)文法自動生成分析表和語法樹，并將分析信息和結(jié)果保存到一個外部文件中的的功能，能靈活實現(xiàn)語法編譯器的相應(yīng)功能。1.2項目背景編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一，而且多數(shù)計算機系統(tǒng)都配有不止一個高級語言的編譯程序。由于早期的機器語言、匯編語言編寫起來不容易、又枯燥無味，所以開發(fā)一種更類似數(shù)學(xué)定義和自然語言的簡潔形式來編寫程序的操作，應(yīng)與任何機器無關(guān)的編譯器十分重要。編譯器的構(gòu)造工具是根據(jù)用戶輸入的語言的文法，可以生成程序來處理以用戶輸入的文法書寫的文本。隨著計算機應(yīng)用范圍的擴大，在軟件自動生成，文檔處理，特定專業(yè)的語言等領(lǐng)域，編譯器的構(gòu)造工具這一技術(shù)顯得越來越重要。一個編譯程序在對某個源程序完成了詞法分析工作之后，就進入語法分析階段，分析檢查源程序是否是語法上正確的程序，并生成相應(yīng)的內(nèi)部中間表示供下一階段使用。程序設(shè)計語言是一般形式語言的特例，程序語法正確性的檢查正是語法句子的識別，語法分析問題也就是句型識別問題。按照識別句子時語法樹建立的方式，有自頂向下與自底向上兩大類分析技術(shù)。本課程設(shè)計討論自頂向下的情況。1.3軟件定義MicrosoftvisualC++6.0:--VisualC++6.0是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問世，VisualC++已成為專業(yè)程序員進行軟件開發(fā)的首選工具VisualC++6.0不僅是一個C++編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrateddevelopmentenvironment,IDE）。VisualC++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lassWizard等開發(fā)工具。這些組件通過一個名為DeveloperStudio的組件集成為和諧的開發(fā)環(huán)境。MicrosoftofficeVisio2003：是微軟公司出品的一款的軟件，它有助于IT和商務(wù)專業(yè)人員輕松地可視化、分析和交流復(fù)雜信息。它能夠?qū)㈦y以理解的復(fù)雜文本和表格轉(zhuǎn)換為一目了然的Visio圖表。該軟件通過創(chuàng)建與數(shù)據(jù)相關(guān)的Visio圖表（而不使用靜態(tài)圖片）來顯示數(shù)據(jù)，這些圖表易于刷新，并能夠顯著提高生產(chǎn)率。使用OfficeVisio2007中的各種圖表可了解、操作和共享企業(yè)內(nèi)組織系統(tǒng)、資源和流程的有關(guān)信息。1.4開發(fā)環(huán)境操作系統(tǒng)：MicrosoftWindowsXP開發(fā)平臺：MicrosoftvisualC++6.0第二章 需求分析LL（1）分析法中，第一個L的含義是：從左向右的處理輸入進行分析，第二個L的含義是：為每個輸入串描繪出一個最左推導(dǎo)，〃1〃的含義是：向輸入串中輸入一個符號就可以唯一確定當(dāng)前將要的產(chǎn)生式。構(gòu)造出一個LL（1）語法分析器可以更加直觀的解決文法輸入串在面臨不同產(chǎn)生式的選擇上，所要進行的分析操作，從而為開發(fā)人員帶來方便。2.1問題陳述建立一個針對LL（1）文法編譯器的自動生成器，要完成此編譯器需要對源文件進行兩遍處理：第一遍詞法分析、第二遍語法分析，語法分析程序應(yīng)用LL（1）語法分析方法。首先輸入（打開）定義好的文法文件，然后建立詞法分析器，包括詞法分析主程序、掃描部分、關(guān)鍵字表等等。經(jīng)詞法分析后分別計算所輸入的文法的每個非終結(jié)符號的FIRST集合、每個非終結(jié)符號的FOLLOW集合，以及每個規(guī)則的SELECT集合，并判斷任意一個非終結(jié)符號的任意兩個規(guī)則的SELECT集的交集是不是為空，如果是，則輸入文法符號是LL（1）文法，可以進行分析。在對文法的語法進行分析的過程中，要解決各方面的問題如（1）當(dāng)文法出現(xiàn)做遞歸時可能使分析過程陷入無限循環(huán)、（2）在推導(dǎo)過程中選擇哪一右部展開時，如果選擇錯誤，將導(dǎo)致回溯。對文法進行改造，要實現(xiàn)把某4SELL⑴文法到LL⑴文法的等價變換。其總起過程大體包括以下各方面：1、提取左公因子2、消除左遞歸。2.2功能要求設(shè)計一個給定LL（1）語法分析器，輸入一個句子，能由依據(jù)LL（1）分析表輸出與句子對應(yīng)的語法樹。能對語法樹生成過程進行模擬。動態(tài)模擬算法的基本功能是：1、 詞法分析：打開或輸入一個文法文件或句子，能對其進行詞法分析，顯示token表信息，當(dāng)存在錯誤時，能給出良好的錯誤提示。2、 語法分析：打開或輸入一個文法文件或句子，能對其進行語法分析，能顯示器中間代碼信息，當(dāng)存在錯誤時，能顯示出語法分析錯誤信息。3、 LL(1)文法判別:打開(輸入)一個形如E->abc的LL(1)文法，能對其求出FIRST集，F(xiàn)OLLOW集，并能用直觀的關(guān)系圖顯示；4、 預(yù)測分析：打開(輸入)一個形如E->abc的LL(1)文法，能直觀的形成表達(dá)式文法的預(yù)測分析表。5、 句子語法樹；根據(jù)確認(rèn)LL(1)文法，確認(rèn)輸入串是否為文法的句子，是，則形成該符號串的分析過程，并直觀的顯示分析過程。6、 該語法分析器具有粘貼、復(fù)制、剪切、保存、退出功能！7、 總控程序：顯示各模塊功能！2.3數(shù)據(jù)流圖：數(shù)據(jù)流圖是結(jié)構(gòu)化分析方法中使用的工具，它以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，由于它只反映系統(tǒng)必須完成的邏輯功能，所以它是一種功能模型。數(shù)據(jù)流圖英文縮寫DFD(DataFlowDiagram)它是描繪信息流和數(shù)據(jù)從輸入移動到輸出的過程中所經(jīng)受的變換。數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，以圖形的方式刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程。該系統(tǒng)的實現(xiàn)的整個過程的數(shù)據(jù)流圖大體如下：LL⑴語法分析器0層圖LL(1)語法分析器1層圖:產(chǎn)生式文件符號集文件LL(1)語法分析器2層圖:第3章設(shè)計任務(wù)分工3.1小組的任務(wù)分工本小組的任務(wù)是編寫一個程序，進行分析表的構(gòu)造。學(xué)號姓名職責(zé)主要任務(wù)3070701217鄒紀(jì)標(biāo)組長消除間接左遞歸，構(gòu)造分析表3070701219陳春輝組員計算SELECT集，提取左公因子3070701207閆瑞雪組員LL(1)文法的判定3070701205江於組員計算FIRST集3070701237龔玉靜組員計算FIRST集3070701222陳慧娟組員計算FOLLOW集3070701232趙夢組員計算FOLLOW集3070701202王報興組員消除直接左遞歸3.2本人主要工作在這次課程設(shè)計中本人的任務(wù)是計算FOLLOW集，為后面求SELECT集、判斷所給文法是否是LL（1）文法。第四章系統(tǒng)設(shè)計4.1總體設(shè)計4.1.1文法改造和源程序預(yù)處理文法輸入與改造流程開始輸入源程序打開包含文法文件或

輸入文法源程序預(yù)處

理修改編輯文法* 輸入源程序打開包含文法文件或

輸入文法源程序預(yù)處

理修改編輯文法* 保存文法外部文

件y外部文

件判斷是否是上下文尢

關(guān)文法文法改造結(jié)束假設(shè)條件：則稱之,SeN。文法G=(N,二P,S)的產(chǎn)生式規(guī)則都取如下的形式：V->w,為上下文無關(guān)的，其中VeN,we(NUE)*°NE(A|...|Z),NE^=則稱之,SeN。源程序中的注釋只支持格式：〃注釋內(nèi)容

設(shè)計相關(guān)任務(wù)說明：（1）打開文件（當(dāng)然也可以手工輸入），在窗口中顯示文法內(nèi)容。點擊“加載”選擇文件，確定，界面如下。

(2)若手工輸入，輸入文法，則界面如下:保存文法，點擊“保存”按鈕，輸入文件名，確定，即可將文法以一定的格式保存在文件中。在編輯框中輸入源程序，點擊“Token串”，則對源程序濾掉空格，跳過注釋、換行符，變?yōu)榭杀徽Z法分析部分識別的輸入串。判斷文法是否為上下文無關(guān)文法。文法改造部分，去掉形如A—A的有害產(chǎn)生式。文法改造部分，去掉不可終止符及其產(chǎn)生式。文法改造部分，去掉不可達(dá)符及其產(chǎn)生式。符號表的構(gòu)造。4.1.2分析表的構(gòu)造分析表的構(gòu)造模塊由以下幾個部分組成：集合的求解，判斷文法是否是LL(1)文法、消除左公共因子及左遞歸、構(gòu)造分析表。該模塊的結(jié)構(gòu)框圖如下：

是否LL(1消除左遞歸提取左公因子是否LL(1消除左遞歸提取左公因子求follow集求select集求first集構(gòu)造分析表該模塊的構(gòu)造共完成以下任務(wù)該部分的功能是判斷一個文法是否為LL(1)文法，它通過對輸入的文法求解FIRST集、FOLLOW集、SELECT集，最后根據(jù)SELECT集是否相交來判斷，如果SELECT集相交，測通過提取左公因子，消除左遞歸看是否可以構(gòu)成LL(1)文法；如果SELECT集不相交，則該文法是LL(1)文法。消除左公共因子及左遞歸這部分能夠?qū)Ψ荓L(1)文法進行改造，使其可能成為LL(1)文法。它先對文法進行判斷，看其是否含有左公共因子，若有則消除，若無則不作任何處理，然后再判斷文法是否含有直接或間接左遞歸，若有則消除，若無則不作任何處理。構(gòu)造分析表通過以上first，follow，select集的求解，判斷是否是LL(1)，然后通過流程圖及算法描述，編寫程序構(gòu)造分析表。4.1.3LL(1)預(yù)測語法分析LL(1)語法分析的模塊原理如下：首先初始化棧，#進棧，E進棧作為文法開始的狀態(tài)。初始化產(chǎn)生式表、非終結(jié)符表、終結(jié)符表。根據(jù)產(chǎn)生式表的產(chǎn)生式生成每個非終結(jié)符的FIRST集及FOLLOW集。參考2、3模塊，由一個算法生成預(yù)測分析表，該預(yù)測分析表是由一個二維數(shù)組M[n1][n2]構(gòu)成。由定理可知：若a^SELECT(A-a),則把A-a放于矩陣M[A,a]。而這里生成的二維數(shù)組M[n1][n2]與該定理類似。不過這里n1是指A在非終結(jié)符表中的序號，n2是指a在終結(jié)符表中的序號，而M[n1][n2]的值是指產(chǎn)生式A-a在產(chǎn)生式表中的序號。這樣做就為下面的預(yù)測分析程序帶來了方便。預(yù)測分析程序分為檢測不合法輸入模塊和對輸入字符串的語法分析模塊。對輸入字符串的語法分析是通過棧及產(chǎn)生式表和預(yù)測分析表的相關(guān)聯(lián)系構(gòu)建一個算法來對這個字符串進行語法分析。通過算法將棧頂元素與輸入字符串的比對、出棧及相關(guān)產(chǎn)生式的推導(dǎo)的右部的逆序入棧等操作可完成對輸入字符串的語法分析。LL(1)語法預(yù)測分析總流程圖輸入字符甜I不齡虎浙輸入!輸入字符甜I不齡虎浙輸入!棧項元素出棧項元素出搗并將其對應(yīng)產(chǎn)生式左尊地序壓*5中-浦出這個產(chǎn)小式“輸川；錯叩跳過F代出I’產(chǎn)年頂元親出年頂元親出棧.釧W錯誤[彈II俄頂,輸出棧頂兀素4.1.4構(gòu)造生成LL(1)語法樹(開始中請并處理根節(jié)點對輯個傳送來到的產(chǎn)生式部，將其相美信息存儲到當(dāng)前-節(jié)點*對每個產(chǎn)上式右部逐個設(shè)置其

信息及指針產(chǎn)生式遍歷完半?樹結(jié)構(gòu)獲取完成按照樹形結(jié)構(gòu)輸?出根節(jié)點從根節(jié)點開始嘉歸逐-按照例

形輸出每個昨終結(jié)點的于樹[結(jié)'束算法思想：本模塊的主要功能是將產(chǎn)生式的序列以語法樹的方式顯示，本組對其進行詳細(xì)研究后，發(fā)現(xiàn)可以將其分成兩個模塊分別處理。第一個模塊是將產(chǎn)生式結(jié)構(gòu)轉(zhuǎn)換成樹形的結(jié)構(gòu)進行存儲，第二個模塊是將以樹形結(jié)構(gòu)存儲的語法樹以樹形目錄的方式輸出。第一個模塊，涉及到兩個數(shù)據(jù)結(jié)構(gòu)：產(chǎn)生式的數(shù)據(jù)結(jié)構(gòu)和樹的數(shù)據(jù)結(jié)構(gòu)。產(chǎn)生式的結(jié)構(gòu)定義存放在Generation.h文件中，在此簡述，有兩個屬性：產(chǎn)生式左部string類型的left和產(chǎn)生式右部vector<string>類型的righto對于傳送到本模塊的產(chǎn)生式序列，要求它們以vector<Generation>的形式存放，使用的時候則可以用下標(biāo)［］的方式逐個引用。樹的結(jié)構(gòu)定義在Tree.h中。整體思想如下：產(chǎn)生式的序列一定是按照最左推導(dǎo)得到的序列，所以樹的構(gòu)造也應(yīng)按照最左構(gòu)造，對于如下的簡單的語法樹其產(chǎn)生式序列必然為:S->BaFB->ACDA->aC->cD->dF->a如此在構(gòu)造樹的時候必然也要按照如下次序：構(gòu)造節(jié)點S構(gòu)造S的子節(jié)點構(gòu)造B的子節(jié)點構(gòu)造A的子節(jié)點構(gòu)造C的子節(jié)點構(gòu)造D的子節(jié)點構(gòu)造F的子節(jié)點1可設(shè)置一個current指向當(dāng)前節(jié)點，最初current指向根節(jié)點。2掃描產(chǎn)生式，每次得到一個產(chǎn)生式，將其左部存到current指向的節(jié)點，然后申請若干新節(jié)點存放產(chǎn)生式右部的符號。3若右部有非終結(jié)符，則將current指向第一個，進行下一次掃描4若右部沒有非終結(jié)符，則說明這次推導(dǎo)已到一個子樹的樹葉。向上回溯，找父節(jié)點的相鄰非終結(jié)符節(jié)點，若父節(jié)點沒有相鄰非終結(jié)符則繼續(xù)向上回溯，直到找到為止，并將current指向它，進行下一次掃描。若回溯到根節(jié)點則說明樹已構(gòu)造完畢。在構(gòu)造非終結(jié)符節(jié)點的時候需要設(shè)置該節(jié)點的next指針，例如構(gòu)造A時要設(shè)置其next指針指向。，目的是構(gòu)造完a之后可以尋找下一個要構(gòu)造的節(jié)點，father指針指向8，目的是在構(gòu)造完D之后可以向上回溯通過B的next指針找到下一個要構(gòu)造的節(jié)點F。對于第二個顯示模塊，思想如下：1首先current指向根節(jié)點，并輸出根節(jié)點2輸出current的子節(jié)點，并將current指向最左的一個非終結(jié)符子節(jié)點，用遞歸的思想輸出該節(jié)點的子樹，然后current繼續(xù)第二個非終結(jié)符子節(jié)點，并用遞歸輸出其子樹。4.2詳細(xì)設(shè)計自頂向下語法分析方法語法分析方法是編譯程序的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子（程序），目前語法分析方法有自頂向下分析和自底向上分析兩大類。自頂向下分析包括確定分析和不確定分析，自底向上分析又包括算符優(yōu)先分析和LR分析這些分析方法各有優(yōu)缺點。然而除了自頂向下的不確定分析方法外，都是當(dāng)今編譯程序構(gòu)造的使用方法。自頂向下的分析也稱面向目標(biāo)的分析方法，也就是從文法的開始符號出發(fā)企圖推到出一輸入的單詞串完全像匹配的句子，若輸入串是給定文法的句子，則必能退出，反之必然出錯。自頂向下的確定分析方法需對文法有一定的限制，但由于實現(xiàn)方法簡單、直觀，便于手工構(gòu)造或自動生成語法分析器，因而仍是目前常用的方法之一。確定的自頂向下分析方法，是從文法的開始符號出發(fā)，考慮如何根據(jù)當(dāng)前的輸入符號（單詞符號）唯一地確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符一往下推導(dǎo)，或如何夠著一顆相應(yīng)的語法樹。當(dāng)我們需選用自頂向下分析技術(shù)時，首先必須判別所給文法是否是LL（1）文法。因而對任給文法需計算FIRST、FOLLOW、SELECT集合，進而判別文法是否是LL（1）文法。有關(guān)FIRST已有其他同學(xué)詳細(xì)敘述，在這里就不在贅述。在此詳細(xì)敘述關(guān)于FOLLOW集的定義及有關(guān)算法。預(yù)測分析方法是自頂向下分析的另一種方法，一個預(yù)測分析器是由三個部分組成。1預(yù)測分析程序2先進后出棧3預(yù)測分析表其中只有預(yù)測分析表與文法有關(guān)，而分析表有可用一個矩陣M（或二維數(shù)組）表示。矩陣的元素M[A，a]中的下表A表示非終結(jié)符，^為終結(jié)符或句子括號“#”，矩陣元素M[A，a]中的內(nèi)容是一條關(guān)于A的產(chǎn)生式，表明當(dāng)用非終結(jié)符A向下推導(dǎo)時，面臨輸入符^時，所應(yīng)采取的候選產(chǎn)生式，當(dāng)元素內(nèi)容物產(chǎn)生式時，則表明用A為左部向下推導(dǎo)遇到了不該出現(xiàn)的符號，因此元素內(nèi)容為轉(zhuǎn)向出錯處理的信息。預(yù)測分析程序的工作過程用下圖表示。圖中符號說明如下：“#”句子括號集輸入串的括號“S”文法的開始符號“X”存放當(dāng)前棧頂符號的工作單元“a”存放當(dāng)前輸入符號a的工作單元

預(yù)測分析程序的框圖FOLLOW集的定義設(shè)G=(VT，Vn，F(xiàn)OLLOW(A)={a|S：若有S^*束符，或稱輸入串括FOLLOW集的定義設(shè)G=(VT，Vn，F(xiàn)OLLOW(A)={a|S：若有S^*束符，或稱輸入串括計算FOLLOW集S,n*uAB，且B

號。nS,n*uAB，且B

號。(1)根據(jù)定義計算對文法中每一AEVT計算FOLLLOW(A)①設(shè)S為文法的開始符號，把{#}加入FOLLOW(S)中(這里“#”為句子括號)。若A-aBB是一個產(chǎn)生式，則把FIRST(6)的非空元素加入FOLLOW(B)中。如果B^*e則把FOLLOW(A)也加入FOLLOW(B)中。反復(fù)使用②直到每個非終結(jié)符的FOLLOW集不再增大為止。(2)用關(guān)系圖法球非終結(jié)符的FOLLOW集文法G中的每一個符號和“#”對應(yīng)圖中的一個結(jié)點，對應(yīng)終結(jié)符和“#”的結(jié)點用符號本身標(biāo)記。對應(yīng)終結(jié)符的結(jié)點(如ACVt)則用FOLLOW(A)標(biāo)記。從開始符號S的FOLLOW(S)結(jié)點到“#”號的結(jié)點連一條箭弧。如果文法中有產(chǎn)生式A-aBBX,且B^*e,則從FOLLOW(B)結(jié)點到FIRST(X)結(jié)點連一條弧，當(dāng)XEVt時，則與X相連。如果文法中有產(chǎn)生式A-aBB且B^*e則從FOLLOW(B)結(jié)點到FOLLOW(A)結(jié)點連一條弓瓜。對每一FIRST(A)結(jié)點如果有產(chǎn)生式A-aXB，且a^*8,則從FIRST(A)到FOLLOW(X)連一條箭弧。凡是從FOLLOW(A)結(jié)點有路徑可以到達(dá)的終結(jié)符或“#”號的結(jié)點，其所標(biāo)記的終結(jié)符或“#”號即為FOLLOW(A)的成員。如文法G[S]為S—ABStbeA—>8AtbBt8BtbDCtADJbDtbSDte得FOLLOW(S)={#}FOLLOW(A)={a，c，#}FOLLOW(B)={#}FOLLOW(C)={#}FOLLOW(D)={#}計算FOLLOW集的關(guān)系圖3.求解FOLLOW集合的算法⑴逐一掃描代碼中的產(chǎn)生式，將產(chǎn)生式右部賦給Y串,Y[j]表示Y串中的第j個字符。⑵逐一掃描產(chǎn)生式的右部,若Y[j]為非終結(jié)符X,找出Y[j]后繼的第一個字符Y[k]。若Y[k]為終結(jié)符，則將該終結(jié)符加入到FOLLOW集合，結(jié)束，跳出⑵；若Y[k]為非終結(jié)符，則FIRST集合‘-e，,執(zhí)行⑶。⑶逐一掃描X后的字符串,分為下面兩種情況：土若非終結(jié)符Y[k]能推出空字符串，則k++,繼續(xù)執(zhí)行①、②兩步；b.若非終結(jié)符Y[k]為產(chǎn)生式最后一個字符，則將該產(chǎn)生式的左部非終結(jié)符的FOLLOW集合加入該非終結(jié)符的FOLLOW集合。⑷若掃描完全部的產(chǎn)生式，則求得所有非終結(jié)符的FOLLOW集合。在計算FOLLOW集中也存在“環(huán)”和重復(fù)的終結(jié)符的問題，解決的辦法與FIRST集的相同。計算FOLLOW集的流程圖X=S?0<i<=n?X.=Y[i]NYY①Y產(chǎn)生式為：X^X1X2^Xn{#}EFOLLOW(X)6、部分代碼：voidFOLLOW(inti){intj,k,m,n,result=1;charc,temp[20];c=non_ter[i]; /*c為待求的非終結(jié)符*/temp[0]=c;temp[1]='\0';merge(fo,temp,1);if(c==start){ /*若為開始符號*/temp[0]='#';temp[1]='\0';merge(follow[i],temp,1);}for(j=0;j<=count-1;j++){if(in(c,right[j])=1) /*找一個右部含有c的產(chǎn)生式*/{for(k=0;;k++)if(right[j][k]=c)break;/*k為c在該產(chǎn)生式右部的序號*/for(m=0;;m++)if(v[m]==left[j])break;/*m為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/if(k==strlen(right[j])-1){ /*如果c在產(chǎn)生式右部的最后*/if(in(v[m],fo)==1){merge(follow[i],follow[m],1);continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}else{ /*如果c不在產(chǎn)生式右部的最后*/for(n=k+1;n<=strlen(right[j])-1;n++){empt[0]='\0';result*=_emp(right[j][n]);}if(result==1){ /*如果右部C后面的符號串能推出人*/if(in(v[m],fo)==1){ /*避免循環(huán)遞歸*/merge(follow[i],follow[m],1);Continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}for(n=k+1;n<=strlen(right[j])-1;n++)temp[n-k-1]=right[j][n];temp[strlen(right[j])-k-1]='\0';FIRST(-1,temp);merge(follow[i],TEMP,2);}}}F[i]=T;}竟文文10

入入入t=

tiUli

肯青青w竟文文10

入入入t=

tiUli

肯青青w沔3.思#3#3知LinE八g小的b-Kbrrb-KwfTT?！鰆T~t-J~|—t-jI"t-J~|—t-jI"t式式式111111H~1產(chǎn)產(chǎn)產(chǎn)E->E*TiE-I!TT->T*F：TZFSFF->CE>!1第5章運行與測試結(jié)果5.1測試數(shù)據(jù)E—E+TIE=TT—T*F}T/FIFF—(E)Ii5.2界面實現(xiàn)情況?■■■■,D;\Tij￡LuL2\DebuK\ByiLtiix.ene- 險晶董-屈MQIUH■目start：Eu：ETFfiB+-^Olnon_ter；ErFAEterniln: