1、2022-3-20西北工業大學軟件與微電子學院 machunyan1o 課程內容課程內容 第第1 1章章 概論概論 第第2 2章章 詞法分析詞法分析 第第3 3章上下文無關文法章上下文無關文法 第第4 4章語法分析章語法分析n 第第5 5章語義分析章語義分析n 第第6 6章運行時環境章運行時環境n 第第7 7章代碼生成章代碼生成machunyan西北工業大學軟件與微電子學院2o 語法分析程序的任務語法分析程序的任務：n 語法分析以詞法分析程序輸出的單詞序列為輸入，分析源程序的語法結構，判斷它是否為相應程序設計語言的合法程序。o語法分析階段可以確定單詞流中違反源語言語法結構規則的錯誤。n 通常語

2、法分析的結果是構造出表示該語法結構的分析樹（parse tree）或語法樹(syntax tree)。第四章第四章 自上而下的語法分析自上而下的語法分析machunyan西北工業大學軟件與微電子學院3 4.1 4.1 自上而下的語法分析算法概述自上而下的語法分析算法概述 4.2 4.2 遞歸下降分析（遞歸下降分析（Recursive-Descent Recursive-Descent Top-Down ParsingTop-Down Parsing） 4.3 4.3 LL(1)LL(1)分析分析 4.4 4.4 自上而下的語法分析器自動生成工具自上而下的語法分析器自動生成工具JavaCCJav

3、aCC 4.5 4.5 項目：編譯器實現（語法分析模塊）項目：編譯器實現（語法分析模塊）第四章第四章 自上而下的語法分析自上而下的語法分析machunyan西北工業大學軟件與微電子學院4o 自上而下的語法分析算法自上而下的語法分析算法：n 已知文法GS，對任意輸入串w，若從文法的開始符號S出發, 能為w構造一個最左推導，則w是一個合法的句子，即w L(G)，否則w有語法錯誤。n 該算法自上而下為w的分析結果建立一棵語法樹。4.1自上而下的語法分析算法概述自上而下的語法分析算法概述machunyan西北工業大學軟件與微電子學院5例4.1：文法G：S aAS cAdA aA ab識別輸入串w=ca

4、bd是否為該文法所定義的句子？運用自上而下的語法分析方法：4.1自上而下的語法分析算法概述自上而下的語法分析算法概述(續續)machunyan西北工業大學軟件與微電子學院6cAd cabdcAd cadS cAd從文法開始符號S出發試圖為w=cabd構造一個最左推導:S cAd cabdcSdAba成功machunyan西北工業大學軟件與微電子學院74.1自上而下的語法分析算法概述自上而下的語法分析算法概述(續續)o 自上而下的語法分析方法：自上而下的語法分析方法：n 從文法開始符號S出發試圖為輸入符號串構造一個最左推導；n 構造最左推導的過程就是選擇產生式和匹配符號串的過程；n 有時需要重復

5、掃描詞法分析輸出的單詞序列。machunyan西北工業大學軟件與微電子學院8 4.1 4.1 自上而下的語法分析算法概述自上而下的語法分析算法概述 4.2 4.2 遞歸下降分析（遞歸下降分析（Recursive-Recursive-Descent Top-Down ParsingDescent Top-Down Parsing） 4.3 4.3 LL(1)LL(1)分析分析 4.4 4.4 自上而下的語法分析器自動生成自上而下的語法分析器自動生成工具工具JavaCCJavaCC 4.5 4.5 項目：編譯器實現（語法分析模項目：編譯器實現（語法分析模塊）塊）第四章第四章 自上而下的語法分析自上

6、而下的語法分析machunyan西北工業大學軟件與微電子學院94.2 遞歸下降語法分析 4.2.1 遞歸下降分析的基本方法 4.2.2 文法規則使用EBNF表示法4.2.3 其它應注意的問題 4.2.4 分析樹與抽象語法樹 4.2.5 案例：Tiny語法分析machunyan西北工業大學軟件與微電子學院10例4.2：文法G：S cAd A ab識別輸入串w=cabd是否為該文法定義的句子？4.2.1 遞歸下降分析的基本方法(續)machunyan西北工業大學軟件與微電子學院11void match(TokenType tokenExpected) if (currentToken.tokent

7、ype = tokenExpected) currentToken = scanner.getToken(); else error: tokenExpected expectedbut currentToken found4.2.1 遞歸下降分析的基本方法(續)match函數：全局變量currentToken存儲即將掃描的下一個單詞machunyan西北工業大學軟件與微電子學院12void S(void) match(c); A(); match(d);void A(void) match(a); match(b); 4.2.1 遞歸下降分析的基本方法(續)識別S的遞歸下降函數的偽代碼：ma

8、chunyan西北工業大學軟件與微電子學院13 遞歸下降分析方法是一種自上而下的語法分析方法，該方法執行一組遞歸函數判斷輸入的單詞序列是否符合語法規則。 遞歸函數如何寫？ 為每個產生式規則撰寫一個函數，以產生式左部的非終結符作為函數的名子，根據產生式規則的右部撰寫函數體。 遇到終結符，匹配并讀取下一個單詞； 遇到非終結符，調用該非終結符所在產生式對應的函數；4. 4.2.1 2.1 遞歸下降分析的基本方法遞歸下降分析的基本方法machunyan西北工業大學軟件與微電子學院14例4.3：文法G：S cAd A a A ab識別輸入串w=cabd是否為該文法定義的句子？4.2.1 遞歸下降分析的基

9、本方法(續)machunyan西北工業大學軟件與微電子學院15識別S的遞歸下降函數的偽代碼：void S(void) match(c); A1(); match(d); if(調用A1()失敗) A2(); match(d); void A1(void) match(a); void A2(void) match(a); match(b); /記住當前的token位置machunyan西北工業大學軟件與微電子學院16o 如果語法分析方法使用遞歸下降分析程序,為了避免重復掃描詞法分析輸出的單詞序列(提高效率)，需要先將文法G采用EBNF表示法，然后寫出遞歸下降分析程序。4.2.1 遞歸下降分析的

10、基本方法(續)machunyan西北工業大學軟件與微電子學院174.2 遞歸下降語法分析 4.2.1 遞歸下降分析的基本方法 4.2.2 文法規則使用EBNF表示法 4.2.3 其它應注意的問題 4.2.4 分析樹與抽象語法樹 4.2.5 案例：Tiny語法分析machunyan西北工業大學軟件與微電子學院181.選擇的情況選擇的情況EBNF使用使用 表示選擇表示選擇： 文法文法G： S cAd A a A ab文法G的EBNF表示法如下：S cAdA ab4.2.2 文法規則使用文法規則使用EBNF表示法表示法machunyan西北工業大學軟件與微電子學院19 識別S的遞歸下降函數的偽代碼：

11、 ScAd A abvoid S(void) match(c); A(); match(d);void A(void) match(a); if token=b then match(b);避免了重復掃描詞法分析輸出的單詞序列1.選擇的情況(續)machunyan西北工業大學軟件與微電子學院20例4.4：一個簡化了的if語句的文法規則：if-stmtif (exp) statement |if (exp) statement else statement寫出識別if-stmt的遞歸下降函數的偽代碼1.選擇的情況(續)p首先給出if文法規則的EBNF表示法：pif-stmtif(exp)stat

12、ementelse statementmachunyan西北工業大學軟件與微電子學院21viod ifStmt(void) match(if); match(); exp(); match(); statement(); if token = else then match(else); statement(); 1.選擇的情況(續)nif-stmt if(exp)statementelse statementmachunyan西北工業大學軟件與微電子學院22簡單整型算術表達式文法：expexp addop term|termaddop+|-termterm mulop factor|fact

13、ormulop*factor(exp)|number寫出識別表達式exp的遞歸下降函數的偽代碼4.2.2 文法規則使用文法規則使用EBNF表示法表示法machunyan西北工業大學軟件與微電子學院23現在考慮簡單算術表達式文法中exp對應的遞歸下降函數： expexp addop term|termo 存在無限遞歸循環的問題；存在無限遞歸循環的問題；o 由于從由于從exp和和term出發都可以首先推導出終出發都可以首先推導出終結符結符number或或（，所以存在選用，所以存在選用 產生式產生式expexp addop term還是還是產生式產生式expterm進進行推導的問題；行推導的問題；

14、重復情況machunyan西北工業大學軟件與微電子學院24解決問題的辦法是使用EBNF規則：EBNF使用 表示重復： A 重復的一般規則：AA|(左遞歸) 表示其中的內容重復n次(n=0)寫遞歸下降語法分析程序時可將花括號表示的重復部分翻譯成循環代碼；重復情況（續）：AA|(右遞歸)Amachunyan西北工業大學軟件與微電子學院25將花括號表示的重復部分addop term翻譯成循環代碼， 語法結構exp對應的函數定義如下：上述產生式規則expexp addop term|term用EBNF表示成重復情況（續）：exp termaddop termmachunyan西北工業大學軟件與微電子學

15、院26viod exp(void) term( ); while token=+ or token=- match(token); term( ); 重復情況（續）：exp termaddop termmachunyan西北工業大學軟件與微電子學院27簡單整型算術表達式文法：expexp addop term|termaddop+|-termterm mulop factor|factormulop*factor(exp)|number寫出識別表達式exp的完整的遞歸下降函數的偽代碼？重復情況（續）：machunyan西北工業大學軟件與微電子學院284.2遞歸下降語法分析 4.2.1 遞歸下降

16、分析的基本方法 4.2.2 文法規則使用EBNF表示法 4.2.3 其它應注意的問題 4.2.4 分析樹與抽象語法樹 4.2.5 案例：Tiny語法分析machunyan西北工業大學軟件與微電子學院294.2.3 其它應注意的問題o 遞歸下降分析方法簡單、功能強大，但它仍遞歸下降分析方法簡單、功能強大，但它仍有特殊性。若使用的是一個設計精巧的小型有特殊性。若使用的是一個設計精巧的小型語言（例如語言（例如TINY），），那么對于構造一個完那么對于構造一個完整的語法分析程序，遞歸下降分析是適合的，整的語法分析程序，遞歸下降分析是適合的，但可能會出現一些問題（例如，下頁的但可能會出現一些問題（例如，

17、下頁的1），），2）兩點）。）兩點）。machunyan西北工業大學軟件與微電子學院30間接遞歸的文法(會導致死循環，要將文法進行相應處理): n例如：文法GS:SAb|c ASa，試寫出它的遞歸下降分析程序。n避免分析程序死循環的解決辦法：n可將間接遞歸的文法進行等價改造為SSab|c，進而改造為：S cab4.2.3 其它應注意的問題(續)machunyan西北工業大學軟件與微電子學院314.2.3 其它應注意的問題其它應注意的問題(續續)o對于兩個或多個文法規則的選項對于兩個或多個文法規則的選項A| ， 如果如果和和均以非終結符開始，那么就很難決均以非終結符開始，那么就很難決定何時使用定

18、何時使用A選項，何時又使用選項，何時又使用A選選項，這樣撰寫的遞歸下降分析程序就存在回項，這樣撰寫的遞歸下降分析程序就存在回溯。溯。p解決辦法：計算和的First集合（LL(1)分析方法給出定義和求解方法）。2022-3-20西北工業大學軟件與微電子學院 machunyan324.2.3 其它應注意的問題其它應注意的問題(續續)o GSo 寫出上述文法的遞歸下降語法分析程序寫出上述文法的遞歸下降語法分析程序2022-3-20西北工業大學軟件與微電子學院 machunyan334.2.3 其它應注意的問題其它應注意的問題(續續)machunyan西北工業大學軟件與微電子學院34在遞歸下降分析程序

19、中，應該增加代碼以實現保存語法分析結果的功能：p（1）構造相應的語法樹節點p（2）保持運算的結合性p（3）計算表達式值p（4）4.2.3 其它應注意的問題(續)machunyan西北工業大學軟件與微電子學院354.2遞歸下降語法分析 4.2.1 遞歸下降分析的基本方法 4.2.2 文法規則使用EBNF表示法 4.2.3 其它應注意的問題 4.2.4 分析樹與抽象語法樹 4.2.5 案例：Tiny語法分析2022-3-20西北工業大學軟件與微電子學院 machunyan36簡單整型算術表達式文法：exp exp op exp|(exp)|numberop +|-|*簡單算術表達式對應的抽象語法樹

20、結構4.2.4 分析樹 與抽象語法樹2022-3-20西北工業大學軟件與微電子學院 machunyan37o 分析樹對于顯示程序的各語法單位或程序的單詞序列分析樹對于顯示程序的各語法單位或程序的單詞序列很有幫助，但是相比純粹為編譯生成可執行代碼所需很有幫助，但是相比純粹為編譯生成可執行代碼所需的信息而言，分析樹卻包括了冗余的信息。的信息而言，分析樹卻包括了冗余的信息。o 所以語法分析程序更趨向于生成抽象語法樹，抽象語所以語法分析程序更趨向于生成抽象語法樹，抽象語法樹是分析樹中所含信息的濃縮，包含了進一步分析法樹是分析樹中所含信息的濃縮，包含了進一步分析所需的所有信息，比分析樹效率高。所需的所有

21、信息，比分析樹效率高。o 例如：見下頁例如：見下頁4.2.4 分析樹 與抽象語法樹(續)2022-3-20西北工業大學軟件與微電子學院 machunyan38o exp exp op expo exp (exp)| Numbero op +|-|*opl_expr_expExpl_expr_expop抽象語法樹結構分析樹結構4.2.4 分析樹 與抽象語法樹(續)2022-3-20西北工業大學軟件與微電子學院 machunyan39+343+4的抽象語法樹（34-3）+42 的抽象語法樹+-423434.2.4 分析樹 與抽象語法樹(續)o 抽象語法樹設計抽象語法樹設計n 各語法單位對應的抽象語

22、法樹的結構可以規定，沒有標準，但可以參考現有編譯器的做法。例如：o工具：Pyc parser，可以打印C語言程序的抽象語法樹2022-3-20西北工業大學軟件與微電子學院 machunyan404.2.4 分析樹 與抽象語法樹(續)o 設計抽象語法樹（續）設計抽象語法樹（續）n 畫出產生式規則的語法分析樹n 在保證語義信息不丟失保證語義信息不丟失的情況下，除掉語法分析樹的冗余節點形成抽象語法樹；2022-3-20西北工業大學軟件與微電子學院 machunyan414.2.4 分析樹 與抽象語法樹(續)machunyan西北工業大學軟件與微電子學院42EBNF文法表示的tiny語言的語法.doc

23、用遞歸下降分析算法寫出TINY語言的語法分析程序？4.2.5 案例：Tiny語法分析machunyan西北工業大學軟件與微電子學院43語法分析的基本步驟語法分析的基本步驟o 對程序設計語言的語法規則進行形式化描述對程序設計語言的語法規則進行形式化描述（用（用2型文法）；型文法）；o 根據語言的語法描述形式，定義各種基本語根據語言的語法描述形式，定義各種基本語法結構的法結構的抽象語法樹抽象語法樹；o 選擇一種合適的選擇一種合適的語法分析算法語法分析算法，并在分析程，并在分析程序中插入動作序中插入動作() -語法分析程序。語法分析程序。machunyan西北工業大學軟件與微電子學院44語句序列st

24、mt-sequence statement;statementTINY語言的各基本語法范疇的抽象語法樹結構形式如下：每個語句對應子樹的右兄弟指向下一個語句對應的子樹machunyan西北工業大學軟件與微電子學院45if-stmt if exp then stmt-sequenceelse stmt-sequenceendif語句的抽象語法樹結構：machunyan西北工業大學軟件與微電子學院46repeat 語句repeat-stmtrepeat stmt-sequence until expmachunyan西北工業大學軟件與微電子學院47assign 語句assign_stmtidenti

25、fier := expmachunyan西北工業大學軟件與微電子學院48write語句 write_stmt write expread語句 read_stmtread identifiermachunyan西北工業大學軟件與微電子學院49算符表達式machunyan西北工業大學軟件與微電子學院50typedef enumStmtK, ExpKNodeKind;typedef enumIfK, RepeatK, AssignK, ReadK, WriteKStmtKind;typedef enumOpK, ConstK, IdKExpKind;typedef enumVoid, Integer

26、, BooleanExpType;#define MAXCHILDREN 3抽象語法樹的定義抽象語法樹的定義machunyan西北工業大學軟件與微電子學院51typedef struct treeNodestruct treeNode* childMAXCHILDREN; struct treeNode* sibling; int lineno; NodeKind nodekind; union StmtKind stmt;ExpKind exp; kind; union TokenType op;int val;char * name; attr; ExpType type; TreeNod

27、e;抽象語法樹的定義(續)machunyan西北工業大學軟件與微電子學院52o statementif-stmt|repeat-stmt|assign-stmt| read-stmt|write-stmtTiny語法分析程序：語法分析程序：PARSE.Cmachunyan西北工業大學軟件與微電子學院53Tiny語法分析程序：語法分析程序：PARSE.Co if-stmtif exp then stmt-sequence else stmt-squence end machunyan西北工業大學軟件與微電子學院54Tiny語法分析程序：語法分析程序：PARSE.Co產生式：產生式：repeat-

28、stmt-repeat stmt-sequence until expmachunyan西北工業大學軟件與微電子學院55一個輸出其輸入階乘的TINY語言程序read x;if x0 then fact:=1; repeat fact:=fact* x; x:=x-1 until x=0; write fact end4.2.4 案例：Tiny語法分析(續)machunyan西北工業大學軟件與微電子學院56Read(x)IFop()id(x)Assign(fact)const(0)const(1)repeatwrite4.2.4 案例：Tiny語法分析(續)PARSE.Cmachunyan西北工

29、業大學軟件與微電子學院57 4.1 自上而下的語法分析算法概述 4.2 遞歸下降分析 4.3 LL(1)分析 4.4 4.4 自上而下的語法分析器自動生成工自上而下的語法分析器自動生成工具具JavaCCJavaCC 4.5 4.5 項目：編譯器實現（語法分析模塊）項目：編譯器實現（語法分析模塊）第四章第四章 自上而下的語法分析自上而下的語法分析machunyan西北工業大學軟件與微電子學院584.3 LL( 1 )分析4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析與算法 4.3.3 消除左遞歸和提取左因子machunyan西北工業大學軟件與微電子學院594.3.1 LL(1)

30、分析的基本方法o LL (1)分析方法是一種自上而下的語法分析分析方法是一種自上而下的語法分析方法：方法：n 第1個“L”指的是由左向右地處理輸入；n 第2個“L”指的是它為輸入串找出一個最左推導；n 括號中的數字1意味著它使用輸入單詞序列中的一個單詞預測分析的動作。machunyan西北工業大學軟件與微電子學院60例如：假設有簡單文法：S(S)S|a 判斷輸入串(a)a是否是符合該文法規則的句子？4.3.1 LL(1)分析的基本方法(續)S(S)S (a)S (a)a(a)a的最左推導S（）SS a amachunyan西北工業大學軟件與微電子學院614.3.1 LL(1)分析的基本方法分析

31、的基本方法(續續)o 針對每一步推導，構造最左推導的語法分析針對每一步推導，構造最左推導的語法分析程序要解決的問題：程序要解決的問題：n 定位當前句型進行下一步推導的非終結符：每一步推導是針對當前句型中最左一個非終結符進行推導；n 選擇產生式：用該非終結符對應的哪一個產生式進行推導最有可能成功？1. 符號串的替換：用選擇產生式的左部替換右部。machunyan西北工業大學軟件與微電子學院62LL (1)分析方法如下：o通過棧來通過棧來“記憶記憶”針對當前句型中的哪一個非針對當前句型中的哪一個非終結符進行推導，首先將文法的開始符號終結符進行推導，首先將文法的開始符號S入棧；入棧；n如果棧的頂部是

32、非終結符A,則利用A對應的某個文法規則A將棧頂部的非終結符A(出棧)替換成串(將串自左至右還是自右至左入棧？)。1. 如果棧的頂部是終結符a,則將其與當前輸入單詞匹配(出棧)。4.3.1 LL(1)分析的基本方法(續)machunyan西北工業大學軟件與微電子學院63o構造一個構造一個非終結符非終結符和和終結符索引終結符索引的二維表格的二維表格MN，T，通過表格指出用哪一個產生式進，通過表格指出用哪一個產生式進行進行下一步推導，其中行進行下一步推導，其中N是非終結符的集是非終結符的集合，合，T是終結符的集合。是終結符的集合。p即構造一個LL(1)分析表，通過該表格引導用哪一個產生式進行推導。

33、例如：例如：4.3.1 LL(1)分析的基本方法(續)machunyan西北工業大學軟件與微電子學院64MN,TS()$S (S)SS a文法S(S)S|a的LL(1)分析表4.3.1 LL(1)分析的基本方法(續)o MS,(表示表示當前分析棧的棧頂符號為當前分析棧的棧頂符號為S，而當前，而當前詞法分析的輸入單詞為詞法分析的輸入單詞為(時，按產生式時，按產生式S(S)S進行推導；進行推導；o MS,a表示表示當前分析棧的棧頂符號為當前分析棧的棧頂符號為S，而當前，而當前詞法分析的輸入單詞為詞法分析的輸入單詞為a時，按產生式時，按產生式Sa進行推導。進行推導。amachunyan西北工業大學軟

34、件與微電子學院65步驟分析棧輸入動作$S1(a)a$S （S）S$S)S(2(a)a$匹配$S)S3a)a$S a$S)a4a)a$匹配$S6a$S a$a7a$匹配引入$作為輸入符號串的限界符；句型自右至左入棧LL (1)分析方法示例$S)5)a$匹配$8$接受machunyan西北工業大學軟件與微電子學院66LL(1)分析程序通過將分析棧頂部的非終結符替換成文法規則中該非終結符的一個選擇來做出分析。在分析過程中有兩個基本動作： 如果棧的頂部是終結符a,則將其與當前輸入單詞匹配。p 如果不能匹配，出現什么情況？ 如果棧的頂部是非終結符A,則利用文法規則A將棧頂部的非終結符A替換成串(保證自右

35、至左入棧)。4.3.1 LL(1)分析的基本方法(續)machunyan西北工業大學軟件與微電子學院67問題：如何構造LL(1)分析表？構造分析表的步驟：求First集合求Follow集合1) 構造LL(1)分析表4.3.1 LL(1)分析的基本方法(續)2022-3-20西北工業大學軟件與微電子學院 machunyan681)求求First集合集合machunyan西北工業大學軟件與微電子學院69 若X是終結符或，則First(X) =X1)求求First集合（續）集合（續）o 文法符號文法符號X的的First(X)集合集合：o 若X可推導出以終結符a為首的字符串，則a在First(X)中；

36、 o 令令X為一個為一個文法符號文法符號（一個終結符或非終結符）（一個終結符或非終結符）或或，則，則First(X)是是終結符的集合終結符的集合，此外可能還，此外可能還有有，它的定義如下：，它的定義如下：machunyan西北工業大學軟件與微電子學院70若X是非終結符，則對于X對應的每個產生式XX1X2.Xn ，First(X)包括 First(X1)-。若對于某個i TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 先求其First( )集包含的非終結符：例：考慮下述文法，求各非終結符的First()集合；文法G E:

37、E,Tmachunyan西北工業大學軟件與微電子學院74First(E)First(E)First(T)First(T)First(F)(a+* 從文法的開始符號E,將求First()集的算法過程表示成下列圖示；machunyan西北工業大學軟件與微電子學院75求得上述文法各非終結符的First集合如下：First(E)=(,aFirst(E)=+,First(T)=(,aFirst(T)=*,First(F)=(,amachunyan西北工業大學軟件與微電子學院76文法符號串的First()集合：設任意串a=X1X2.Xn（終結符和非終結符組成的符號串），則First(a)的定義如下： Fi

38、rst(a)包括First(X1)- 。 對于每個i = 2,.,n，如果對于所有的k=1,.,i-1，First(Xk)包括了，則First(a)也包括First(Xi)-。 如果對于所有的i =1,.,n，First(Xi)包括了，則First(a)也包括。1)求First集合(續)machunyan西北工業大學軟件與微電子學院77Follow集合的定義：給出一個非終結符A，集合Follow(A)是由終結符組成，此外可能還有$。集合Follow(A)的定義如下：2)求Follow集合1. 若A是開始符號,則Follow(A)包含$2. 若存在產生式BA,則Follow(A)包含 First

39、()-3. 若存在產生式BA，且在First()中，則 Follow(A)包含Follow(B)注：求解Follow(A) ，考慮A出現在哪些產生式右部。Follow 集僅針對非終結符，并且不包含machunyan西北工業大學軟件與微電子學院78o 例如：例如：a Follow(B)n 若有句型Ba出現，由于BA，且在First()中，所以有：o Ba Aa * A a = Aao aFollow(A)2)求Follow集合（續）machunyan西北工業大學軟件與微電子學院79例：考慮下述簡單整型表達式文法，求各非終結符的Follow()集合； expexp addop term (2) e

40、xpterm(3) addop+ (4) addop-(5) termterm mulop factor(6) term factor(7) mulop* (8) factor(exp)(9) factornumbermachunyan西北工業大學軟件與微電子學院80Follow(exp)=Follow(addop)=Follow(term)=Follow(mulop)=Follow(factor)=$,+,-,)(,number$,+,-,*,)(,number$,+,-,*,)2)求Follow集合(續)machunyan西北工業大學軟件與微電子學院81例2：考慮下述文法，求各非終結符的F

41、ollow()集合； 先求其First集包含的非終結符為：E， T(1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a文法G E:machunyan西北工業大學軟件與微電子學院82Follow(E)$Follow(E)Follow(E)Follow(T)First(E)Follow(E) 從文法的開始符號E,將求Follow()集的算法過程表示成下列圖示；machunyan西北工業大學軟件與微電子學院83Follow(T)Follow(T)Follow(F)First(T)Follow(T)machunyan西北

42、工業大學軟件與微電子學院84各非終結符的Follow集合如下：Follow(E)=) , $Follow(E)=), $Follow(T)=+, ), $Follow(T)=+, ), $ Follow(F)=*, +, ), $machunyan西北工業大學軟件與微電子學院85 構造LL(1)分析表對于First()中的每個終結符a，都將A添加到MA,a元素位置，置MA,a =“A”。 即當當前分析棧的棧頂符號為A時，而當前詞法分析的輸入單詞為a時，按產生式A進行推導；LL(1)分析表的構造方法：分析表以非終結符作為行索引，以終結符作為列索引，分析表的元素位置存儲產生式，為每個非終結符A和它

43、對應的產生式A重復以下兩步驟：machunyan西北工業大學軟件與微電子學院86定義：如果文法G相關的LL(1)分析表的每個項目中至多只有一個產生式，則該文法就是LL(1)文法。3)所有沒有定義的元素位置A,a標上“出錯”標志。若在First()中，則對于Follow(A)的每個元素a(或是$)，都將A添加到 MA,a中。即在此情況下按產生式A進行推導。 LL(1)分析表的構造方法(續)：例如：bAa. b a * b a bamachunyan西北工業大學軟件與微電子學院87例：考慮簡化了的C變量聲明的文法：declarationtype var-listtypeint|floatvar-l

44、istidentifier listlist ,var-list| 求該文法各非終結符的First()集合和Follow()集合。構造該文法的LL(1)分析表。說明該文法是LL(1)文法。a.假設有輸入串 int x,y,z 寫出相對應的LL(1)分析程序的動作。machunyan西北工業大學軟件與微電子學院88First(declaration)=int,floatFirst(type) =int,floatFirst(var-list) =identifierFirst(list) =, 所求得的各非終結符的First集合和Follow集合如下：machunyan西北工業大學軟件與微電子學

45、院89Follow(declaration)=$Follow(type)=identifierFollow(var-list)=$Follow(list) =$machunyan西北工業大學軟件與微電子學院90r1: declarationtype var-listr2: typeintr3: type floatr4: var-listidentifier listr5: list ,var-listr6: list 對各產生式進行編號： 構造該文法的LL(1)分析表。machunyan西北工業大學軟件與微電子學院91MN,Tdeclarationintidentifier$ ,typeva

46、r-listlistfloatr1r1r2r3r4r5r6 由于文法G相關的LL(1)分析表的每個項目中至多只有一個產生式，故該文法是LL(1)文法。machunyan西北工業大學軟件與微電子學院92 輸入串 int x,y,z 相對應的LL(1)分析程序的分析過程如下表所示：步驟分析棧輸入動作1$ declarationint x,y,z$r14 $ var-listx,y,z$r42$ var-list typer2int x,y,z$3int x,y,z$匹配$ var-list intmachunyan西北工業大學軟件與微電子學院935$ list identifierx,y,z$匹配

47、6$ list,y,z$r5$var-list,y,z$7匹配$var-list8r4y,z$步驟分析棧輸入動作$成功$machunyan西北工業大學軟件與微電子學院944.3 LL( 1 )分析 4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析與算法 4.3.3 消除左遞歸和提取左因子machunyan西北工業大學軟件與微電子學院95Input$總控程序LL(1)預測分析表stack$machunyan西北工業大學軟件與微電子學院964.3.2 LL(1)分析與算法o 基于表的基于表的LL(1)分析算法流程分析算法流程：n LL(1)分析表的構造是LL(1)分析算法的關鍵技術

48、。machunyan西北工業大學軟件與微電子學院974.3 LL( 1 )分析 4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析與算法 4.3.3 消除左遞歸和提取左因子machunyan西北工業大學軟件與微電子學院98o 簡單直接左遞歸文法是否是簡單直接左遞歸文法是否是LL(1)文法？例如：文法？例如：n AAan Abo 若文法若文法G有產生式有產生式Uxy |xw | xz則該文法是則該文法是否是否是LL(1)文法？文法？4.3.3 消除左遞歸和提取左因子machunyan西北工業大學軟件與微電子學院994.3.3 消除左遞歸和提取左因子(續)o由于含有左遞歸和左公共因子

49、的文法由于含有左遞歸和左公共因子的文法不不是是LL(1)文法，如果要使用文法，如果要使用LL(1)語法分析算語法分析算法對該文法定義的語言進行語法分析，那么法對該文法定義的語言進行語法分析，那么必須通過必須通過消除左遞歸和提取左公共因子，消除左遞歸和提取左公共因子，將文法進行等價改造。將文法進行等價改造。machunyan西北工業大學軟件與微電子學院100簡單直接左遞歸的消除AAA4.3.3 消除左遞歸和提取左因子(續)消除直接左遞歸將文法重寫為：AAAA|machunyan西北工業大學軟件與微電子學院101例：消除下面文法的左遞歸規則：exp exp addop term|termexp t

50、erm exp消除左遞歸后將上述文法重寫為：exp addop term exp|machunyan西北工業大學軟件與微電子學院102多項直接左遞歸的消除AA1|A2| An|1|2 | |m消除左遞歸后將上述文法重寫為：A 1A|2A|mAA1A|2A|nA|machunyan西北工業大學軟件與微電子學院103例：消除下面文法的左遞歸規則：exp exp+term| exp-term| termexp term exp消除左遞歸后將上述文法重寫為：exp +term exp| -term exp| machunyan西北工業大學軟件與微電子學院104若在y,w,z中仍然有左公共因子，可以再次提取。注意，若有：Uxy|x 則提取后：Ux(y|)若有產生式Uxy|xw|xz ，則提取左公共因子并用EBNF表示為： Ux(y|w|z) 再引入另一個非終結符號V，將產生式變為：UxVV y|w|z提取左因子：machunyan西北工業大學軟件與微電子