TINY-C編譯器的設計與實現(xiàn)-語法分析器的設計與實現(xiàn).doc

目 錄摘 要41. 前 言62. 語法分析器的設計原理72.1 語法分析器的功能72.2 語法分析的目標和作用72.3 構(gòu)造語法分析器的步驟72.4 上下文無關(guān)文法及分析82.5 常用的語法分析方法和幾種算法的比較102.5.1自上而下分析法102.5.2自下而上分析法123. 語法分析器的設計和實現(xiàn)153.1 TINY語言的介紹153.2 TINY的文法生成153.3 TINY語法分析器算法的選擇183.4 TINY語言的遞歸下降分析程序213.5 TINY語法分析的輸出233.5.1 語法分析的輸出結(jié)果233.5.2 抽象語法樹的節(jié)點聲明243.5.3 語法樹結(jié)構(gòu)253.6 語法分析的主要函數(shù)與核心代碼293.6.1 語法分析器的主要文件和函數(shù)293.6.2 語法分析模塊304. 測試分析404.1 測試方法404.2 測試計劃404.3 測試項目說明404.4 測試結(jié)論445. 結(jié)論與心得45參 考 文 獻46致 謝47附 錄47ContentsAbstract41. Preface62. Syntax analyzer principle of design72.1 Function of parsing72.2 Purpose and function of parsing72.3 The of parsing analyzer structure72.4 Context-free grammar and analysis82.5Commonly syntax analysis method and several algorithms comparison102.5.1 From top to bottom analytic method102.5.2 From bottom to top analytic method123. Syntax analyzer design and realization153.1 Introduce of TINY language153.2 Production of TINY grammar153.3 Choice of TINY syntax analyzer algorithm183.4 Recursion decline analysis programe of TINY213.5 Output of TINY grammar analysis233.5.1 Result of parsing233.5.2 Statement of abstract syntax tree node243.5.3 The syntax tree struction253.6 Main function and core code of syntax analyzer293.6.1Master document and function of syntax analyze293.6.2Parsing module304. Testing parse404.1 Testing method404.2 Testing Propose404.3 Explanation of test item404.4 Conclusion of testing445. Conclusion and what one has learned45Bibliography46Thanks47Appendix47TINY-C編譯器的設計與實現(xiàn) -語法分析器的設計與實現(xiàn)摘 要 編譯器是將一種源語言翻譯為目標語言的計算機程序。 本項目采用一種類（ANSI）C 的小型語言：TINY 語言作為源語言，構(gòu)造TINY語言的編譯器。項目由三人共同完成，其中本人主要是完成了語法分析器的構(gòu)造，主要工作如下：研究語法分析器的設計原理，并對幾種典型的語法分析算法進行分析。生成TINY文法，并證明該文法為LL（1）文法，在此基礎上，選擇遞歸下降算法實現(xiàn)TINY語法分析。最終實現(xiàn)了一個TINY語法分析器，它以詞法分析器所產(chǎn)生的記號為輸入，采用遞歸下降分析程序進行語法分析，并輸出語法樹作為下階段編譯的輸入。我們最后構(gòu)造了一個Dephi接口程序，顯式輸出抽象語法樹。關(guān)鍵詞 : 編譯器 TINY 記號 語法分析 語法樹Tiny-C Complier design and realization -Syntax analyzer design and realization Ren JunAbstractThe compiler is a computer program which translates the source language into the target language. This project uses a language similar to (ANSI) C: Using the TINY language as the source language to construct the compiler of TINY. The whole process of the project is finished by the joint effort of three people, and I myself mainly completed the structure of syntax analyzer. The major work is as follows: Analyzing the designing principles of the syntax analyzer, and several kinds of typical parsing algorithm. Producing the TINY grammar, proving this grammar is LL (1) grammar, and in this foundation, choosing recursion drop algorithm to realize the TINY grammar analysis. A TINY grammar analyzer has thus been accomplished. It applies the symbols which are produced by the morphology analyzer as the input, and uses the recursion drop analysis program to carry on the grammar analysis, then output the syntax tree as the input for next compiling phases input. We structured a Dephi interface routine at last to display the abstract syntax tree.Keyword ：Compiler ， TINY ，Token ，Syntax analysis，Syntax tree1. 前 言系統(tǒng)概述在計算機上執(zhí)行一個高級語言程序一般要分為兩步:第一步,用一個編譯程序把高級語言翻譯成機器語言程序;第二步:運行所得的機器語言程序求得計算結(jié)果。通常所說的翻譯程序是指這樣的一個程序,它能夠把某一種語言程序轉(zhuǎn)換成另一種語言程序,而后者與前者在邏輯上是等價的。語法分析器,簡稱分析器,對單詞符號串進行語法分析(根據(jù)語法規(guī)則進行推導或規(guī)約),識別除各類語法單位,最終判斷輸入串是否構(gòu)成語法上的正確的”程序”。詞法分析器目標代碼生成器語法分析器詞義分析和中間代碼產(chǎn)生器優(yōu)化器表格管理錯誤處理目標代碼中間代碼中間代碼語法單位單詞符號源程序圖1-1編譯程序框TINY語言的概述 TINY的程序結(jié)構(gòu)很簡單，它在語法上和Pascal的語法相似：僅是一個由分號分隔開的語句序列。另外，它既無過程也無聲明。所有的變量都是整型變量，通過對其賦值可較輕易地聲明變量（類似FORTRAN或BASIC）。它只有兩個控制語句： if語句和repeat語句，這兩個控制語句本身也可包含語句序列。If語句有一個可選的else部分且必須由關(guān)鍵字end結(jié)束。除此之外，read語句和write語句完成輸入/輸出。在花括號中可以有注釋，但注釋不能嵌套。2. 語法分析器的設計原理2.1 語法分析器的功能語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器在編譯程序中的地位如圖1.1所示。詞法分析語法分析器編譯后續(xù)部分單詞符號取下一個單詞符號語法分析樹 圖2.1 語法分析器在編譯程序中的地位2.2 語法分析的目標和作用1）語法分析的目標是確定程序的語法，或稱作結(jié)構(gòu)，也正是這個原因，它又被稱作語法分析（syntax analysis）。 2）分析過程 分析程序的任務是從由掃描程序產(chǎn)生的記號中確定程序的語法結(jié)構(gòu)，以及或隱式或顯式地構(gòu)造出表示該結(jié)構(gòu)的分析樹或語法樹。因此，可將分析程序看作一個函數(shù)，該函數(shù)把由掃描程序生成的記號序列作為輸入，并生成語法樹作為它的輸出：記號序列語法樹。2.3 構(gòu)造語法分析器的步驟a寫出文法b根據(jù)文法選擇合適的分析算法。C實現(xiàn)算法 2.4 上下文無關(guān)文法及分析實際上，幾乎所有程序設計語言都是通過上下文無關(guān)文法來定義的。另一方面，上下文無關(guān)文法又足夠簡單，使得我們可以構(gòu)造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關(guān)文法產(chǎn)生的。1）上下文無關(guān)文法定義在計算機科學中，一個形式文法G = (N P S)稱之為上下文無關(guān)的，如果它的產(chǎn)生式規(guī)則都取如下的形式：V - w ，這里 VN ， w (N)* 。上下文無關(guān)文法取名為“上下文無關(guān)”的原因就是因為字符 V 總可以被字串 w 自由替換，而無需考慮字符 V出現(xiàn)的上下文。一個形式語言是上下文無關(guān)的，如果它是由上下文無關(guān)文法生成的條目上下文無關(guān)語言。上下文無關(guān)文法重要的原因在于它們擁有足夠強的表達力來表示大多數(shù)程序設計語言的語法； BNF 巴克斯-諾爾范式經(jīng)常用來表達上下文無關(guān)文法。2）上下文無關(guān)文法規(guī)則上下文無關(guān)文法規(guī)則確定了為由規(guī)則定義的結(jié)構(gòu)的記號符號符合語法的串集。文法規(guī)則通過推導確定記號符號的正規(guī)串。推導（derivation）是在文法規(guī)則的右邊進行選擇的一個結(jié)構(gòu)名字替換序列。推導以一個結(jié)構(gòu)名字開始并以記號符號串結(jié)束。在推導的每一個步驟中，使用來自文法規(guī)則的選擇每一次生成一個替換。3）上下文無關(guān)文法的形式定義定義上下文無關(guān)文法由以下各項組成：（1) 終結(jié)符（terminal）集合T。（2) 非終結(jié)符（nonterminal）集合N（與T不相交）。（3) 產(chǎn)生式（production）或文法規(guī)則（grammar rule）Aa的集合P，其中A是N的一個元素，a是（T N）*中的一個元素（是終結(jié)符和非終結(jié)符的一個可為空的序列）。（4) 來自集合N的開始符號（start symbol）。令G是一個如上所定義的文法，則G = (T, N, P, S)。G上的推導步驟（derivation step）格式a Ag abg，其中a和g是(T N) *中的元素，且有Ab在P中（終結(jié)符和非終結(jié)符的并集，有時被稱作G的符號集，set of symbol），且(T N) *中的串a(chǎn)被稱作句型（sentential form）。將關(guān)系a *b定義為推導步驟關(guān)系 的傳遞閉包；也就是：假若有零個或更多個推導步驟，就有a *b（n0）a1 a2 an- 1 an其中a=a1，b=an （如果n= 0，則a=b）。在文法G上的推導（derivation）形如S *w，且w T *（即：w 是終結(jié)符的一個串，稱作句子（sentence），S是G的開始符號。由G生成的語言（language generated by G）寫作L (G)，它被定義為集合L (G) = w T * |存在G的一個推導S *w，也就是：L (G)是由S推導出的句子的集合。最左推導（leftmost derivation）S *w 是一個推導，在其中的每一個推導步驟aAg abg都有almT*，換言之，a 僅由終結(jié)符組成。類似地，最右推導（ rightmost derivation）就是每一個推導步驟aAg abg 都有屬性g T*。文法G上的分析樹（parse tree）是一個帶有以下屬性的作了標記的樹：（1) 每個節(jié)點都用終結(jié)符、非終結(jié)符或標出。（2) 根節(jié)點用開始符號S標出。（3) 每個葉節(jié)點都用終結(jié)符或標出。（4) 每個非葉節(jié)點都用非終結(jié)符標出。（5) 如帶有標記A N的節(jié)點有n 個帶有標記X1 , X2 , . . . Xn 的孩子（可以是終結(jié)符也可以是非終結(jié)符），就有AX1 , X2 , . . . Xn P（文法的一個產(chǎn)生式）。每一個推導都引出一個分析樹，這個分析樹中的每一個步驟aAg abg 都在推導中，且b= X1 , X2 , . . . Xn 與帶有標記X1 , X2 , . . . Xn 的n 個孩子的結(jié)構(gòu)相對應，其中X1 , X2 , . . . Xn 帶有標記A。許多推導可引出相同的分析樹。但每個分析樹只有唯一的一個最左推導和一個最右推導。最左推導與分析樹的前序編號相對應，而與之相反，最右推導與分析樹的后序編號相對應。若上下文無關(guān)文法G有L=L(G)，就將串L的集合稱作上下文無關(guān)語言（ c ontext-freel anguage）。一般地，許多不同的文法可以生成相同的上下文無關(guān)語言，但是根據(jù)所使用的文法的不同，語言中的串也會有不同的分析樹。若存在串w L (G)，其中w 有兩個不同的分析樹（或最左推導或最右推導），那么文法G就有二義性（ambiguous）。2.5 常用的語法分析方法和幾種算法的比較語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描敘的。因此，語法分析器的工作本質(zhì)上就是按文法的產(chǎn)生式，識別輸入符號串（指由單詞符號組成的有限序列）是否為一個句子。對于一個文法，當給出一串符號時，怎么知道它是不是該文法的一個句子（“程序”）？就要從文法的開始符號出發(fā)推導出這個輸入串，也就是要建立一個與輸入串相匹配的語法分析樹。按照語法分析樹的建立方法，可以將語法分析辦法分成兩類，一類是自上而下分析法，另一類是自下而上分析法。2.5.1自上而下分析法1）定義： 從文法的開始符號出發(fā)，向下推導，推出句子。2）優(yōu)點：符合人的思想，比較容易理解3）缺點：a) 文法的左遞歸性問題，因此使用自上而下分析發(fā)必須消除文法的左遞歸性。b) 回溯問題c) 虛假匹配d) 效率低，代價高e) 難于確定出錯位置f) 只適合LL（1）文法*注釋：LL（1）文法：一個文法G, 若它的分析表M不含多重定義入口,則被稱為LL為(1)文法。LL(1)中的第一 個“L”意味著自左而右地掃描輸入,第二個“L”意味著生成一個最左推導,并且“1”意味著為做 出分析動作的決定，在每一步利用一個向前看符號,一個文法G是LL（1）的，那么必須滿足：1）文法不含左遞歸 2）對于文法的每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即：FIRST（）FIRST（）；它們不應該都能推出空字; 3）對于文法中的每個非終結(jié)符A，若它存在某個候選首符集包含。即：假若包含,那么,FIRST（） FOLLOW（A）. 4）主要算法A遞歸下降分析程序 定義：若一個文法G不含有左遞歸，而且每個非終結(jié)符的所有候選式的首符集都是兩兩不相交的，那么就能為G中每個非終結(jié)符編寫一個相應的遞歸過程。把該文法中所有這樣的遞歸過程組合起來就可能構(gòu)成一個不帶回溯的自上而下分析程序遞歸下降分析程序。實現(xiàn)思想：為文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串，當某非終結(jié)符的產(chǎn)生式有多個候選式時，按LL(1)形式唯一確定選擇哪個候選式進行推導，若遇到某候選式為e，認為其自動匹配。把這些遞歸過程組合起來就構(gòu)成了文法的遞歸下降分析程序。實現(xiàn)方法： a)使用LL(1)文法 先將文法消除左遞歸、提取公共左因子，使之成為LL(1)文法，后將每個非終結(jié)符對應一個遞歸過程，過程體是按照相應產(chǎn)生式的右部符號串順序編寫。每匹配一個終結(jié)符，則再讀入下一個符號，對產(chǎn)生式右部的每個非終結(jié)符，則調(diào)用相應的過程。 b)使用BNF范式先將文法改寫為BNF形式，后再書寫遞歸子程序。優(yōu)點：容易理解。缺點a）對文法的要求高，必須滿足LL(1)文法。 b）高深度的遞歸調(diào)用會影響語法分析的效率，速度慢，占空間多。B預測分析程序定義：使用高級語言的遞歸過程描述遞歸下降分析器，只有當具有實現(xiàn)這種過程的編譯系統(tǒng)時才有實際意義。實現(xiàn)LL(1)分析的另一種有效方式是使用一張分析表和一個棧進行聯(lián)合控制。實現(xiàn)思想：預測分析程序就是屬于這種類型的LL(1)分析器。實現(xiàn)方法：構(gòu)造分析表和棧，設棧頂符號為X，讀入符號為a，則a)若X=a=#，則表示識別成功，退出分析程序；b)若X=a#，則表示匹配，彈出棧頂符號X，讀頭前進一格，讓讀頭指向下一個符號，以讀入下一個符號；若X是終結(jié)符，但Xa，則調(diào)用error處理；c)若XVN，則查預測分析表M。若MX,a中存放著關(guān)于X的產(chǎn)生式，則彈出X，且將相應產(chǎn)生式右部以自右向左的順序壓入棧，在輸出帶上記下產(chǎn)生式編號；若MX,a中存放著出錯標記，則調(diào)用相應Error處理。優(yōu)點：過程比遞歸分析的效率高，速度快，占空間少，僅用表結(jié)構(gòu)。缺點: 對文法的要求高，必須滿足LL(1)文法。2.5.2自下而上分析法1）定義：所謂自下而上分析法就是從輸入串開始，逐步進行“規(guī)約”， 直至規(guī)約到文法的開始符號；或者說從語法樹的末端開始，步步向上“規(guī)約”，直到根結(jié)。2）優(yōu)點：從輸入符號串開始分析開始分析，因此進行語法分析和進行語義分析可以在一遍內(nèi)進行，而自上而下的分析法是從根節(jié)點開始進行語法分析，因此必須先經(jīng)過一遍掃描建立語法樹，讓后再經(jīng)過一遍掃描進行語法分析。因此自下而上的分析法效率更高。3）缺點：和人的思想相反，不容易理解，算法更復雜。4) 主要算法A 算符優(yōu)先分析法定義：定義算符之間(確切地說，終結(jié)符之間)的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”和進行歸約。實現(xiàn)思想：優(yōu)先表構(gòu)造優(yōu)先函數(shù)，尋找最作素短語。（設G是一個算符文法，是句型 ba關(guān)于A的短語(即有S-A且A- )且至少含有一個終結(jié)符號，并且除自身之外不再含有任何更小的 帶有終結(jié)符號的短語，則稱是句型關(guān)于A的素短語。所謂最左素短語是指處于句型最左邊的那個素短語。）實現(xiàn)方法： 算符優(yōu)先分析法自底向上地分析句子，解決了前面提到的兩個問題，即：1)可以只根據(jù)相鄰運算符的優(yōu)先關(guān)系，就能方便地并且唯一地確定歸約的“句柄”；2)可以用來分析二義性文法所產(chǎn)生的語言。是仿照算術(shù)表達式的四則運算過程而設計的一種語法分析方法。終結(jié)符號 運算符非終結(jié)符號 運算對象算符優(yōu)先分析法的關(guān)鍵在于用合適的方法去定義任何兩個可能相繼出現(xiàn)的結(jié)符號a和b(它們之間可能插有一個非終結(jié)符號)之間的優(yōu)先級。然后利用這種關(guān)系比較相鄰運算符之間的優(yōu)先級來確定可歸約串并進行歸約. 終結(jié)符號a與b之間的優(yōu)先關(guān)系有三種：ab 表示a的優(yōu)先級低于b ab 表示a的優(yōu)先級等于b ab 表示a的優(yōu)先級大于b 優(yōu)點：a）有利于表達式分析，宜于手工實現(xiàn)。b）使用優(yōu)先表，只對算符優(yōu)先比較，占用的存儲量比較小，速度快。缺點：a) 可能錯誤接受非法句子，能力有限b) 要求文法必須是算符優(yōu)先文法，這個條件比較苛刻。 B LR算法定義：從左到右掃描輸入串。并且構(gòu)造一個最右推導的逆過程。實現(xiàn)思想與方法：LR分析的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”(ACTIOB)表，另一是“狀態(tài)轉(zhuǎn)換”(C0m)表。它們都是二維數(shù)組。優(yōu)點：對文法要求較低，適合大部分文法。缺點：算法比算符優(yōu)先法復雜，占用資源較多，速度較慢。3. 語法分析器的設計和實現(xiàn)3.1 TINY語言的介紹 1) TINY的程序結(jié)構(gòu)是一個由分號分隔開的語句序列。 2) 既無過程也無聲明。3) 所有的變量都是整型變量，通過對其賦值可較輕易地聲明變量。4) 只有兩個控制語句： if語句和repeat語句，這兩個控制語句本身也可包含語句序列。If語句有一個可選的else部分且必須由關(guān)鍵字end結(jié)束。5) read語句和write語句完成輸入/輸出。6) TINY的表達式只有布爾表達式和整型算術(shù)表達式。布爾表達式由對兩個算術(shù)表達式的比較組成，該比較使用與=比較算符。算術(shù)表達式可以包括整型常數(shù)、變量、參數(shù)以及4個整型算符+、*、/，此外還有一般的數(shù)學屬性。例子：一個輸出其輸入階乘的TINY語言程序 read x;input an integer if 0x then dont compute if x stmt-sequencestmt-sequence- stmt-sequence;statement|statementprogram表示程序, stmt-sequence表示語句序列，statement表示語句由TINY語言介紹中的第2，3，4，5條可知語句分為賦值語句、if語句、repeat語句、read語句和write，其文法表示如下：statement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmt (語句) (if語句)（循環(huán)語句）（賦值語句）（讀語句） （寫語句）A) if語句（if-stmt）而if語句有兩種形式：a)if 表達式 then 語句序列 end 例如：if x0 then y:=1 endb)if 表達式 then 語句序列 else 語句序列 end例如：if x if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence endB) 循環(huán)語句（repeat-stmt）循環(huán)語句語句的形式為：repeat 語句序列 until 表達式 例如：repeat fact:=fact*x; x:=x-1until x=0;由此可得循環(huán)語句語句的文法為：repeat-stmt - repeat stmt-sequence until expC）賦值語句（assign-stm）由3可知賦值語句的左邊為變量（標識符），右部為表達式。形式為：變量：= 表達式|值例如：x:=x-1由此可得賦值語句的文法為：assign-stmt - identifier := expD）讀寫語句（read-stmt和write-stmt）讀寫語句形式為：讀出 變量 | 寫入 變量 例如：read x;input an integer write fact output factorial of x由此可得讀寫語句的文法為：read-stmt - read identifierwrite-stmt - write expE）布爾表達式和整型算術(shù)表達式表達式的要求：表達式滿足優(yōu)先順序，優(yōu)先順序從低到高為：比較運算符 simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-依此類推，我們可以得到表達式的文法如下所示：exp - simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-term - term mulop factor |factormulop - *|/factor - (exp)|number | identifier其中，exp表示表達式，simple-exp表示算術(shù)表達式 term表示加法項，mulop表示乘除項，factor表示其他因子（數(shù)字或標示符）綜上所述，可以得到下圖TINY的文法如圖21所示：program - stmt-sequencestmt-sequence- stmt-sequence;statement|statementstatement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmtif-stmt - if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence endrepeat-stmt - repeat stmt-sequence until expassign-stmt - identifier := expread-stmt - read identifierwrite-stmt - write expexp - simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-term - term mulop factor |factormulop - *|/factor - (exp)|number | identifier粗體表示終結(jié)符，如if then +等等。圖2-1 TINY的BNF的文法3.3 TINY語法分析器算法的選擇 選擇： 自上而下文法的遞歸下降分析程序分析： 根據(jù)2.2節(jié)中TINY的文法生成，可以計算TINY文法的FIRST集合和Follow集合。AFIRST集合的定義FIRST(X)表示X所有可能推出的開始終結(jié)符,包括. 1,顯然，若X為終結(jié)符，則FIRST(X) = X。 2,如果X為非終結(jié)符，有兩種情況： (1)若有產(chǎn)生式 Xa,則把a加入FIRST(X)中; 若有產(chǎn)生式 X,則把加入FIRST(X)中. (2)若有產(chǎn)生式 XY , Y是非終結(jié)符, 如果Y不能推出,也就是說,不屬于FIRST(Y),那么X所能推出的開頭終結(jié)符也就是Y所能推出的開頭終結(jié)符.我們把FIRST(Y)加入FIRST(X)中. 如果Y能推出,即FIRST(Y)中包含,假設跟在Y后的符號為 Y2,那么當我們用匹配Y時,X所能推出的開頭終結(jié)符就為Y2所能推出的開頭終結(jié)符(不包括).也就是說在這種情況下, X所能推出的開頭終結(jié)符不但包括Y所能推出的除之外的開頭終結(jié)符也應包括Y2所能推出的除之外的開頭終結(jié)符.應把FIRST(Y)和FIRST(Y2)中所有非-元素加入FIRST(X)中.FIRST集合計算結(jié)果：PROGRAM 的 FIRST集： IF REPEAT ASSIGN READ WRITE STMT_SEQUENCE 的 FIRST集： IF REPEAT ASSIGN READ WRITE STATEMENT 的 FIRST集： IF REPEAT ASSIGN READ WRITE IF_STMT 的 FIRST集： IF PROGRAM REPEAT_STMT 的 FIRST集： REPEAT PROGRAM ASSIGN_STMT 的 FIRST集： IDENTIFIER PROGRAM READ_STMT 的 FIRST集： READ PROGRAM WRITE_STMT 的 FIRST集： WRITE PROGRAM EXP 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM SIMPLE_EXP 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM COMPARISON_OP 的 FIRST集： LESS EQUAL PROGRAM ADDOP 的 FIRST集： ADD SUBTRACT PROGRAM MULOP 的 FIRST集： MULTIPLY DIVIDE PROGRAM TERM 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM FACTOR 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM NUMBER 的 FIRST集： NUMBER PROGRAM PROGRAM IDENTIFIER 的 FIRST集： IDENTIFIER IF 的 FIRST集： IF THEN 的 FIRST集： THEN ELSE 的 FIRST集： ELSE END 的 FIRST集： END REPEAT 的 FIRST集： REPEAT UNTIL 的 FIRST集： UNTIL READ 的 FIRST集： READ WRITE 的 FIRST集： WRITE ADD 的 FIRST集： ADD SUBTRACT 的 FIRST集： SUBTRACT MULTIPLY 的 FIRST集： MULTIPLY DIVIDE 的 FIRST集： DIVIDE EQUAL 的 FIRST集： EQUAL LESS 的 FIRST集： LESS LPAR 的 FIRST集： LPAR RPAR 的 FIRST集： RPAR SEMICOLON 的 FIRST集： SEMICOLON ASSIGN 的 FIRST集： ASSIGN B Follow集合的定義A為非終結(jié)符,FOLLOW(A)表示緊跟A后的所有終結(jié)符,包括結(jié)束符#.(1) 若A為文法的開始符號S，置#于FOLLOW(A)中。(2) 若存在產(chǎn)生式BA,為符號串,那么緊跟A之后的終結(jié) 符應為的第一個終結(jié)符(不包括),因此將First()-加入Follow(A)中。(3) 若存在產(chǎn)生式BA, 那么緊跟B的終結(jié)符也可能是緊跟A的終結(jié)符,因此要將Follow(B)加入Follow(A)中.(4) 若存在產(chǎn)生式BA，而=,即FIRST().那么如果用匹配,就有以下推導: B=A,在這種情況下, 緊跟B的終結(jié)符也可能是緊跟A的終結(jié)符,因此要將Follow(B)加入Follow(A)中.注意:根據(jù)規(guī)則3和4,如果存在BA 或 BA，而=.那么當Follow(B)改變時, Follow(A)也會改變.因此計算文法G中所有非終結(jié)符的Follow集合時,一趟計算是不夠的.只有當文法中所有非終結(jié)符的Follow集合都不再發(fā)生變化時,我們才能結(jié)束對文法中非終結(jié)符的Follow集合的計算.FOLLOW集合的結(jié)果：PROGRAM 的 FOLLOW集： DOUBLE_CROSS STMT_SEQUENCE 的 FOLLOW集： DOUBLE_CROSS END ELSE UNTIL STATEMENT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL IF_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL REPEAT_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL ASSIGN_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL READ_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL WRITE_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL EXP 的 FOLLOW集： THEN SEMICOLON DOUBLE_CROSS RPAR PROGRAM END ELSE UNTIL SIMPLE_EXP 的 FOLLOW集： LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL COMPARISON_OP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM ADDOP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM MULOP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM TERM 的 FOLLOW集： ADD SUBTRACT LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL FACTOR 的 FOLLOW集： MULTIPLY DIVIDE ADD SUBTRACT LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL 首先判斷出文法的每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即：FIRST（）FIRST（）；它們不能推出空字; 其次是對于文法中的每個非終結(jié)符A，它存在的某個候選首符集包含。即：假若包含,那么,FIRST（） FOLLOW（A）.結(jié)論：由此可以確定是滿足LL(1)條件，我們就可以為它構(gòu)造一個不帶回溯的自上而下分析程序，而且TINY語句簡單只有5類，并且語句分析程序是由一組遞歸過程組成，所以選擇遞歸下降分析。3.4 TINY語言的遞歸下降分析程序編譯說穿了是對一個數(shù)據(jù)流進行逐字的分析， 把分析過程看做是不斷的讀取數(shù)據(jù)，是實現(xiàn)程序的一個基本思想。現(xiàn)在讓我們自頂而下地對表達式進行分析，自頂向下（top - down）的分析算法通過在最左推導中描述出各個步驟來分析記號串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號是一個前序編號，而且其順序是由根到葉遞歸下降分析的概念極為簡單：將一個非終結(jié)符A的文法規(guī)則看作將識別A的一個過程的定義。A的文法規(guī)則的右邊指出這個過程的代碼結(jié)構(gòu)：一個選擇中的終結(jié)符與非終結(jié)符序列與相匹配的輸入以及對其他過程的調(diào)用相對應，而選擇與在代碼中的替代情況（case語句和if語句）相對應。TINY遞歸下降程序中使用的是比BNF更加完善的EBNF-TINY語言的文法，如下：program - stmt-sequencestmt-sequence- stmt-sequence ;statementstatement - if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmtif-stmt - if exp then stmt- sequence else stmt-sequence endrepeat-stmt - repeat stmt-sequence until expassign-stmt - identifier := expread-stmt - read identifierwrite-stmt - write expexp - simple-exp comparison-op simple-exp comparison-op - term addop term addop - +|-term - factor mulop factor mulop - *|/factor - (exp)|number | identifier 分析程序構(gòu)造了語法樹，除此之外，它還將語法樹的表示打印到列表文件中。 TINY分析程序完全按照遞歸下降程序的要點，這個分析程序包括兩個代碼文件：parse.h和parse.c。parse . h文件。另外：它由一個聲明TreeNode * parse (void);組成，它定義了主分析例程parse，parse又返回一個指向由分析程序構(gòu)造的語法樹的指針。parse.c文件，它由11個相互遞歸的過程組成，這些過程與BNF文法直接對應：一個對應于stmt - sequence，一個對應于statement，5個分別對應于5種不同的語句，另有4個對應于表達式的不同優(yōu)先層次。操作符非終結(jié)符并未包括到過程之中，但卻作為與它們相關(guān)的表達式被識別。這里也沒有過程與program相對應，這是因為一個程序就是一個語句序列，所以parse例程僅調(diào)用stmt_sequ ence。分析程序代碼還包括了一個保存向前看記號的靜態(tài)變量token以及一個查找特殊記號的match過程，當它找到匹配時就調(diào)用getToken，否則就聲明出錯；此外代碼還包括將出錯信息打印到列表文件中的syntaxError過程。主要的parse程將token初始化到輸入的第1個記號中，同時調(diào)用stmt_sequence，接著再在返回由stmt_ sequence構(gòu)造的樹之前檢查源文件的末尾（如果在stmt_ sequence返回之后還有更多的記號，那么這就是一個錯誤）。每個遞歸過程的內(nèi)容應有相對的自身解釋性， stmt_sequence卻有可能是一個例外，它可寫在一個更為復雜的格式中以提高對出錯的處理能力；遞歸分析過程使用3種實用程序過程，為了方便已將它們都放在了文件util.c中，此外它還帶有接口util.h。這些過程是：1) newStmtNode，它取用一個指示語句種類的參數(shù)，它還在分配該類的新語句節(jié)點的同時返回一個指向新分配的節(jié)點的指針。2) newExpNode，它取用一個指示表達式種類的參數(shù)，它還在分配該類新表達式節(jié)點的同時返回一個指向新分配的節(jié)點的指針。3) copyString，它取用一個串參數(shù)，為拷貝分配足夠的空間，并拷貝串，同時返回一個指向新分配的拷貝的指針。