編譯原理-第四章

1、編譯原理編譯原理第四章第四章 語(yǔ)法分析語(yǔ)法分析(自上而下分析自上而下分析)王金偉計(jì)算機(jī)與信息工程學(xué)院天津師范大學(xué)TJNU-COCIE-WJW22022-5-26第四章第四章 語(yǔ)法分析語(yǔ)法分析(自上而下分析自上而下分析)n4.1 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法n4.2 帶回溯的自上而下語(yǔ)法分析帶回溯的自上而下語(yǔ)法分析n4.3 LL(1)分析法分析法n4.4 遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造n4.5 預(yù)測(cè)分析程序預(yù)測(cè)分析程序TJNU-COCIE-WJW32022-5-26n語(yǔ)法分析的任務(wù)語(yǔ)法分析的任務(wù)在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序

2、的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。n語(yǔ)法分析器語(yǔ)法分析器執(zhí)行語(yǔ)法分析的程序稱(chēng)為語(yǔ)法分析器執(zhí)行語(yǔ)法分析的程序稱(chēng)為語(yǔ)法分析器其功能是其功能是n輸入：由單詞符號(hào)組成的有限序列輸入：由單詞符號(hào)組成的有限序列n輸出：語(yǔ)法范疇輸出：語(yǔ)法范疇(語(yǔ)法單位語(yǔ)法單位)TJNU-COCIE-WJW42022-5-26n語(yǔ)法分析的方法語(yǔ)法分析的方法自上而下分析法自上而下分析法(由文法開(kāi)始符號(hào)推出句子由文法開(kāi)始符號(hào)推出句子)n一般分析方法一般分析方法(窮舉，帶回溯窮舉，帶回溯)n遞歸下降分析法遞歸下降分析法(消除左遞歸，不帶回溯消除左遞歸，不帶回溯)n預(yù)測(cè)方法預(yù)測(cè)方法(LL(1)方法，一張

3、分析表和一個(gè)棧方法，一張分析表和一個(gè)棧)自下而上分析法自下而上分析法(由輸入串開(kāi)始逐步歸約到文法由輸入串開(kāi)始逐步歸約到文法開(kāi)始符號(hào)開(kāi)始符號(hào))n算符優(yōu)先分析法算符優(yōu)先分析法nLR分析法分析法TJNU-COCIE-WJW52022-5-26語(yǔ)法分析器在編譯程序中的核心地位語(yǔ)法分析器在編譯程序中的核心地位語(yǔ)法分析器語(yǔ)法分析器詞法分析器詞法分析器編譯程序編譯程序后續(xù)部分后續(xù)部分符號(hào)表符號(hào)表單詞符號(hào)單詞符號(hào)取下一個(gè)取下一個(gè)單詞符號(hào)單詞符號(hào)語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù) 源程序源程序TJNU-COCIE-WJW62022-5-264.1 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法1.文法文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（語(yǔ)法規(guī)

4、則）是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（語(yǔ)法規(guī)則）：自然語(yǔ)言句子的主謂賓結(jié)構(gòu)自然語(yǔ)言句子的主謂賓結(jié)構(gòu)一、一、文法概述文法概述TJNU-COCIE-WJW72022-5-262.上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法(1)它所定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)它所定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的（與它所在的上立于這種范疇可能出現(xiàn)的環(huán)境的（與它所在的上下文無(wú)關(guān)）下文無(wú)關(guān)）：程序設(shè)計(jì)語(yǔ)言中的一個(gè)算術(shù)表達(dá)式：程序設(shè)計(jì)語(yǔ)言中的一個(gè)算術(shù)表達(dá)式A*B(2)自然語(yǔ)言中不適合于上下文無(wú)關(guān)文法自然語(yǔ)言中不適合于上下文無(wú)關(guān)文法：漢語(yǔ)中的：漢語(yǔ)中的“打打”字是一個(gè)泛義動(dòng)詞字是一個(gè)泛義動(dòng)詞“打毛衣打

5、毛衣” “編織編織”“打籃球打籃球” “玩玩”“打水打水” “取得取得”(3)對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)用上下文無(wú)關(guān)的文法來(lái)對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)用上下文無(wú)關(guān)的文法來(lái)描述就足夠了描述就足夠了TJNU-COCIE-WJW82022-5-261.：有一個(gè)由英語(yǔ)單詞組成的一個(gè)單詞串：有一個(gè)由英語(yǔ)單詞組成的一個(gè)單詞串The boy sees the girl 用用表示表示“由由組成組成”或或“定義為定義為”，定義一些，定義一些語(yǔ)法規(guī)則語(yǔ)法規(guī)則theboygirlsees二、二、文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義TJNU-COCIE-WJW92022-5-261.問(wèn)題：?jiǎn)栴}：The boy sees th

6、e girl是不是一個(gè)語(yǔ)法上正確的句子？是不是一個(gè)語(yǔ)法上正確的句子？思想：是否可以利用我們定義的這些語(yǔ)法規(guī)則推思想：是否可以利用我們定義的這些語(yǔ)法規(guī)則推導(dǎo)出這個(gè)句子導(dǎo)出這個(gè)句子方法：從方法：從出發(fā)，反復(fù)把上述規(guī)則中的出發(fā)，反復(fù)把上述規(guī)則中的“”左邊成分替換成右邊成分左邊成分替換成右邊成分TJNU-COCIE-WJW102022-5-26推導(dǎo)過(guò)程推導(dǎo)過(guò)程：=The =The boy =The boy =The boy sees =The boy sees =The boy sees the=The boy sees the girltheboygirlseesTJNU-COCIE-WJW1120

7、22-5-26n也可以用語(yǔ)法分析樹(shù)來(lái)表示這種推導(dǎo)也可以用語(yǔ)法分析樹(shù)來(lái)表示這種推導(dǎo) The boy sees the girlTJNU-COCIE-WJW122022-5-262. 引出幾個(gè)概念引出幾個(gè)概念(1)終結(jié)符號(hào)終結(jié)符號(hào)不帶尖括號(hào)的部分，就是單詞符號(hào)，語(yǔ)法分析角不帶尖括號(hào)的部分，就是單詞符號(hào)，語(yǔ)法分析角度是不可再分的基本符號(hào)度是不可再分的基本符號(hào)： the、 boy、 sees、 girl等等：基本字、標(biāo)識(shí)符、常數(shù)、算符和界符等：基本字、標(biāo)識(shí)符、常數(shù)、算符和界符等TJNU-COCIE-WJW132022-5-26(2)非終結(jié)符號(hào)非終結(jié)符號(hào)帶尖括號(hào)的部分，代表一類(lèi)語(yǔ)法成分帶尖括號(hào)的部分，代

8、表一類(lèi)語(yǔ)法成分(語(yǔ)法范疇語(yǔ)法范疇)：、 、 、等等：算數(shù)表達(dá)式、布爾表達(dá)式、賦值語(yǔ)句、：算數(shù)表達(dá)式、布爾表達(dá)式、賦值語(yǔ)句、分程序、過(guò)程等分程序、過(guò)程等TJNU-COCIE-WJW142022-5-26(3)開(kāi)始符號(hào)開(kāi)始符號(hào)(識(shí)別符號(hào)，綱符號(hào)識(shí)別符號(hào)，綱符號(hào))A.指定一個(gè)非終結(jié)符號(hào)為開(kāi)始符號(hào)，表示推導(dǎo)從它指定一個(gè)非終結(jié)符號(hào)為開(kāi)始符號(hào)，表示推導(dǎo)從它開(kāi)始開(kāi)始B.代表所定義語(yǔ)言中我們最感興趣的語(yǔ)法范疇代表所定義語(yǔ)言中我們最感興趣的語(yǔ)法范疇C.是由其他語(yǔ)法范疇構(gòu)造起來(lái)的是由其他語(yǔ)法范疇構(gòu)造起來(lái)的： 句子句子句子是由主語(yǔ)、謂語(yǔ)、賓語(yǔ)這些語(yǔ)法范疇構(gòu)成的句子是由主語(yǔ)、謂語(yǔ)、賓語(yǔ)這些語(yǔ)法范疇構(gòu)成的前面說(shuō)的前面說(shuō)

9、的：程序：程序程序是由分程序、過(guò)程這些語(yǔ)法范疇構(gòu)成的程序是由分程序、過(guò)程這些語(yǔ)法范疇構(gòu)成的TJNU-COCIE-WJW152022-5-26(4)產(chǎn)生式產(chǎn)生式(產(chǎn)生規(guī)則、規(guī)則產(chǎn)生規(guī)則、規(guī)則)是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則，是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則，形式為：形式為： AA是某個(gè)非終結(jié)符號(hào)是某個(gè)非終結(jié)符號(hào), 稱(chēng)為稱(chēng)為產(chǎn)生式的左部產(chǎn)生式的左部，可以是終結(jié)符號(hào)可以是終結(jié)符號(hào),也可以是非終結(jié)符號(hào)，還可以是也可以是非終結(jié)符號(hào)，還可以是終結(jié)符號(hào)和非終結(jié)符號(hào)組成的任意符號(hào)串，稱(chēng)為終結(jié)符號(hào)和非終結(jié)符號(hào)組成的任意符號(hào)串，稱(chēng)為產(chǎn)生式的右部產(chǎn)生式的右部： the boy girl seesTJNU-COCIE-WJ

10、W162022-5-263.上下文無(wú)關(guān)文法的形式定義上下文無(wú)關(guān)文法的形式定義上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法G G定義為定義為四元式四元式( (V VT T，V VN N，S S，P P) )V VT T是非空有限集，是終結(jié)符號(hào)集合，它的每個(gè)元素是非空有限集，是終結(jié)符號(hào)集合，它的每個(gè)元素稱(chēng)為終結(jié)符號(hào)，用小寫(xiě)字母表示。稱(chēng)為終結(jié)符號(hào)，用小寫(xiě)字母表示。V VN N是非空有限集，是非終結(jié)符號(hào)集合，它的每個(gè)元是非空有限集，是非終結(jié)符號(hào)集合，它的每個(gè)元素稱(chēng)為非終結(jié)符號(hào)，用大寫(xiě)字母表示，并且素稱(chēng)為非終結(jié)符號(hào)，用大寫(xiě)字母表示，并且V VN NVVT T=S S V VN N ，是一個(gè)開(kāi)始符號(hào)，也稱(chēng)為是識(shí)別符號(hào)，是

11、，是一個(gè)開(kāi)始符號(hào)，也稱(chēng)為是識(shí)別符號(hào)，是一個(gè)非終結(jié)符，至少在一個(gè)產(chǎn)生式作為左部出現(xiàn)一個(gè)非終結(jié)符，至少在一個(gè)產(chǎn)生式作為左部出現(xiàn)P P是一個(gè)產(chǎn)生式的集合是一個(gè)產(chǎn)生式的集合( (有限有限) )，它的每個(gè)元素稱(chēng)為，它的每個(gè)元素稱(chēng)為一條產(chǎn)生式一條產(chǎn)生式( (一條規(guī)則一條規(guī)則) )，形式：，形式：P其中其中P V VN N ， (V VN NV VT T)*TJNU-COCIE-WJW172022-5-26：設(shè)有文法：設(shè)有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=i=i，+ +，* *，（，），（，） V VN N=E=ES = ES = EP P：E i E E +

12、E E E * E E (E)其中其中i代表變量代表變量描述了一類(lèi)由變量和描述了一類(lèi)由變量和+*運(yùn)算組成的算數(shù)表達(dá)式文法運(yùn)算組成的算數(shù)表達(dá)式文法TJNU-COCIE-WJW182022-5-26：(1)文法的核心是一組產(chǎn)生式，而開(kāi)始符號(hào)文法的核心是一組產(chǎn)生式，而開(kāi)始符號(hào)S是文法所要識(shí)別的語(yǔ)法范疇（語(yǔ)法單位）是文法所要識(shí)別的語(yǔ)法范疇（語(yǔ)法單位）(2)若有這樣一些左部相同的產(chǎn)生式：若有這樣一些左部相同的產(chǎn)生式：P1P2Pn可以合并為一個(gè)，縮寫(xiě)成可以合并為一個(gè)，縮寫(xiě)成P1 | 2 | | n其中每個(gè)其中每個(gè)i 稱(chēng)為稱(chēng)為P的一個(gè)候選式，的一個(gè)候選式，|讀作讀作“或或”：P P：E i | E+E |

13、E*E | (E)TJNU-COCIE-WJW192022-5-26：設(shè)有文法設(shè)有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=i=i，+ +，* * V VN N=E=E，AAS = ES = EP P：E i | EAE A + | + | * *：這里：這里P P有有4 4條產(chǎn)生式規(guī)則。條產(chǎn)生式規(guī)則。TJNU-COCIE-WJW202022-5-264.推導(dǎo)推導(dǎo)(1)(1)直接直接( (一次一次) )推導(dǎo)推導(dǎo) =設(shè)一個(gè)文法設(shè)一個(gè)文法G(V(VT T，V VN N，S S，P)P),(V VN NV VT T)* (,是終結(jié)符或是終結(jié)符或非終結(jié)符或終結(jié)符和

14、非終結(jié)符組非終結(jié)符或終結(jié)符和非終結(jié)符組成的任意符號(hào)串成的任意符號(hào)串)且，且， A是是G的一個(gè)產(chǎn)生式，如果有的一個(gè)產(chǎn)生式，如果有 A = 就稱(chēng)就稱(chēng)A直接推導(dǎo)出直接推導(dǎo)出：推導(dǎo)是用產(chǎn)生式的右部替換產(chǎn)生式的左部：推導(dǎo)是用產(chǎn)生式的右部替換產(chǎn)生式的左部TJNU-COCIE-WJW212022-5-26(2) (2) 1 到到n的推導(dǎo)的推導(dǎo)如果如果1 = 2 = = n則稱(chēng)這個(gè)序列是從則稱(chēng)這個(gè)序列是從1 到到n的一個(gè)推導(dǎo)的一個(gè)推導(dǎo) 1 n從從1 出發(fā)經(jīng)過(guò)出發(fā)經(jīng)過(guò)1步或若干步推出步或若干步推出n1 n從從1 出發(fā)經(jīng)過(guò)出發(fā)經(jīng)過(guò)0步或若干步推出步或若干步推出n：1 n1 = n1 n*TJNU-COCIE-WJ

15、W222022-5-26：設(shè)有文法：設(shè)有文法G P P：E i | E+E | E*E | (E)求從求從E到到( i * i + i )的推導(dǎo)的推導(dǎo)解：解：E = (E) = (E+E) = (E*E+E) = (i*E+E) = (i*i+E) = (i*i+i)TJNU-COCIE-WJW232022-5-26：常用的推導(dǎo)有兩種：常用的推導(dǎo)有兩種(1)最左推導(dǎo)最左推導(dǎo)任何一步任何一步 = 都對(duì)都對(duì)最左邊最左邊的那個(gè)的那個(gè)非終結(jié)符號(hào)非終結(jié)符號(hào)進(jìn)行替換進(jìn)行替換：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)(2)最右推導(dǎo)最右推導(dǎo)任何一步任何一步 = 都

16、對(duì)都對(duì)最右邊最右邊的那個(gè)的那個(gè)非終結(jié)符號(hào)非終結(jié)符號(hào)進(jìn)行替換進(jìn)行替換： E=(E)=(E+E)=(E+i)=(E*E+i)=(E*i+i)=(i*i+i)TJNU-COCIE-WJW242022-5-265.句型句型設(shè)設(shè)G G是一個(gè)文法，是一個(gè)文法，S S是它的開(kāi)始符號(hào)，如果是它的開(kāi)始符號(hào)，如果S S ，且，且(V VN NV VT T)* 則稱(chēng)則稱(chēng)是是G的一個(gè)句型的一個(gè)句型6.句子句子設(shè)設(shè)G G是一個(gè)文法，是一個(gè)文法，S S是它的開(kāi)始符號(hào)，如果是它的開(kāi)始符號(hào)，如果S S ，且，且 V VT T* 則稱(chēng)則稱(chēng)是是G的一個(gè)句子的一個(gè)句子：(1)句子實(shí)際上是僅含有終結(jié)符號(hào)的句型句子實(shí)際上是僅含有終結(jié)符

17、號(hào)的句型(2)從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程不唯一從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程不唯一*TJNU-COCIE-WJW252022-5-26：設(shè)有文法：設(shè)有文法G (V(VT T，V VN N，S S，P)P)，其中，其中P P：E i | E+E | E*E | (E)V VT T=i=i，+ +，* *，（，），（，） ； V VN N=E=E； S = ES = E推導(dǎo)推導(dǎo)( i * i + i )解解：E = (E) = (E+E) = (E*E+E) = (i*E+E) = (i*i+E) = (i*i+i)(句型句型)(句型句型)(句型句型)(句型句型)(句型句型)(句型句型)(

18、句型句型,句子句子)TJNU-COCIE-WJW262022-5-267.語(yǔ)言語(yǔ)言文法文法G G所產(chǎn)生的句子的全體就是一個(gè)語(yǔ)言，記為所產(chǎn)生的句子的全體就是一個(gè)語(yǔ)言，記為L(zhǎng)(G)L(G)L(G)=L(G)= | S & V VT T* 8.8.文法和語(yǔ)言的關(guān)系文法和語(yǔ)言的關(guān)系(1)(1)給定一個(gè)文法，就能從結(jié)構(gòu)上唯一確定其語(yǔ)言給定一個(gè)文法，就能從結(jié)構(gòu)上唯一確定其語(yǔ)言G-G-L(G)L(G)( (唯一的唯一的) )(2)(2)給定一種語(yǔ)言，能找到其文法，但該文法不是唯一給定一種語(yǔ)言，能找到其文法，但該文法不是唯一的，即的，即L-L-G1 G1 或或 G2 G2 或或 TJNU-COCIE-WJW2

19、72022-5-26：設(shè)有文法：設(shè)有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=a ,b=a ,b； V VN N=Z=Z； S = ZS = ZP P：Z aZb Z ab試構(gòu)造其語(yǔ)言試構(gòu)造其語(yǔ)言解解：因?yàn)橐驗(yàn)閆 = aZb = a2Zb2 = a3Zb3 = = an-1Zbn-1 = anbn所以所以L(G) = anbn | n1TJNU-COCIE-WJW282022-5-26：已知語(yǔ)言：已知語(yǔ)言L(G) = abna | n1可構(gòu)造文法可構(gòu)造文法G1：P P：S aBa B bB | b還可構(gòu)造文法還可構(gòu)造文法G2：P P：S aBa B Bb

20、| bTJNU-COCIE-WJW292022-5-261.語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)用一棵樹(shù)來(lái)表示句型的推導(dǎo)，簡(jiǎn)稱(chēng)語(yǔ)法樹(shù)用一棵樹(shù)來(lái)表示句型的推導(dǎo)，簡(jiǎn)稱(chēng)語(yǔ)法樹(shù)三、三、語(yǔ)法分析樹(shù)與二義性語(yǔ)法分析樹(shù)與二義性TJNU-COCIE-WJW302022-5-26：設(shè)有文法：設(shè)有文法G 為為E i | E+E | E*E | (E)推導(dǎo)推導(dǎo)： (i*i+i)解：解： E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) E第第1代代 ( E )第第2代代 E + E第第3代代 E * E第第4代代第第5代代iiiTJNU-COCIE-WJW312022-5-262. 句子的二義

21、性句子的二義性若一個(gè)文法的一個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，若一個(gè)文法的一個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)該句子是二義性句子則稱(chēng)該句子是二義性句子：有個(gè)句子：手提包：有個(gè)句子：手提包 手手 提提 包包TJNU-COCIE-WJW322022-5-263.文法的二義性文法的二義性如果一個(gè)文法含有二義性的句子，則稱(chēng)該文法是如果一個(gè)文法含有二義性的句子，則稱(chēng)該文法是二義性文法二義性文法TJNU-COCIE-WJW332022-5-26E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) E ( E ) E + EE * Eiii：設(shè)有文法：設(shè)有文法G 為為E i | E

22、+E | E*E | (E)推導(dǎo)推導(dǎo)： (i*i+i)E=(E)=(E*E)=(i*E)=(i*E+E)=(i*i+E)= (i*i+i)E ( E ) E * E E + EiiiTJNU-COCIE-WJW342022-5-26對(duì)于上例，規(guī)定對(duì)于上例，規(guī)定*比比+優(yōu)先級(jí)高，且都服從左結(jié)合優(yōu)先級(jí)高，且都服從左結(jié)合構(gòu)造無(wú)二義性的文法構(gòu)造無(wú)二義性的文法G 為為E T | E + T，T F | T * F ，F(xiàn) (E) | i，推導(dǎo)，推導(dǎo)： (i*i+i)E=T=F=(E)=(E+T)=(T*F+T)=(F*F+T)=(i*F+T)=(i*i+T)=(i*i+F)=(i*i+i)ETF( E )

23、E + TT * FFiiiFTJNU-COCIE-WJW352022-5-26n喬姆斯基形式語(yǔ)言理論：?jiǎn)棠匪够问秸Z(yǔ)言理論：19561956年建立，發(fā)展至今，年建立，發(fā)展至今，對(duì)產(chǎn)生式加以不同限制得到對(duì)產(chǎn)生式加以不同限制得到4 4種類(lèi)型的文法：種類(lèi)型的文法：0 0型型1 1型型2 2型型3 3型型四、四、文法分類(lèi)文法分類(lèi)TJNU-COCIE-WJW362022-5-260 0型文法型文法也稱(chēng)為短語(yǔ)結(jié)構(gòu)文法也稱(chēng)為短語(yǔ)結(jié)構(gòu)文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)：(V(VN NVVT T)

24、 )* *且至少含有且至少含有一個(gè)非終結(jié)符，而一個(gè)非終結(jié)符，而(V(VN NVVT T) )* * ，則，則G G是一個(gè)是一個(gè)0 0型型文法文法l任何任何0 0型語(yǔ)言都是遞歸可枚舉的，而遞歸可枚舉集型語(yǔ)言都是遞歸可枚舉的，而遞歸可枚舉集必定是一個(gè)必定是一個(gè)0 0型語(yǔ)言型語(yǔ)言l其它三類(lèi)文法都是對(duì)其它三類(lèi)文法都是對(duì)0 0型文法產(chǎn)生式的形式作某些型文法產(chǎn)生式的形式作某些限制得到的限制得到的TJNU-COCIE-WJW372022-5-261 1型文法型文法：也稱(chēng)為上下文有關(guān)文法也稱(chēng)為上下文有關(guān)文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每個(gè)產(chǎn)生式有如，如果

25、它的每個(gè)產(chǎn)生式有如下形式：下形式：x xAyxyAyxy，AVAVN N，(V(VN NVVT T) )+ +， x x、y(Vy(VN NVVT T) )* *，則，則G G是一個(gè)是一個(gè)1 1型文法型文法l對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文，對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文，A A只有在只有在x x和和y y這樣的上下文環(huán)境中才能替換為這樣的上下文環(huán)境中才能替換為l另一種定義：設(shè)另一種定義：設(shè)G=(VG=(VN N,V,Vt t,P,S),P,S)，如果它的每個(gè)產(chǎn)生，如果它的每個(gè)產(chǎn)生式式滿足滿足|=|=|，則，則G G是一個(gè)是一個(gè)1 1型文法；把型文法；把產(chǎn)生式產(chǎn)生式SS作為產(chǎn)生式的特例加

26、入作為產(chǎn)生式的特例加入1 1型文法的產(chǎn)生型文法的產(chǎn)生式集合中，但式集合中，但S S不能出現(xiàn)在產(chǎn)生式的右部不能出現(xiàn)在產(chǎn)生式的右部l1 1型文法對(duì)程序設(shè)計(jì)語(yǔ)言的應(yīng)用來(lái)說(shuō)一般太復(fù)雜了，型文法對(duì)程序設(shè)計(jì)語(yǔ)言的應(yīng)用來(lái)說(shuō)一般太復(fù)雜了，難于應(yīng)用難于應(yīng)用TJNU-COCIE-WJW382022-5-262 2型文法型文法也稱(chēng)為上下文無(wú)關(guān)文法也稱(chēng)為上下文無(wú)關(guān)文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式有如下形式：有如下形式：A A，AVAVN N，(V(VN NVVT T) )* *，則，則G G是一個(gè)是一個(gè)2 2型文法型文法l2 2型文

27、法等價(jià)于下推自動(dòng)機(jī)（語(yǔ)法分析）型文法等價(jià)于下推自動(dòng)機(jī)（語(yǔ)法分析）l2 2型文法有足夠能力來(lái)描述現(xiàn)今的多數(shù)程序設(shè)計(jì)型文法有足夠能力來(lái)描述現(xiàn)今的多數(shù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)語(yǔ)言的語(yǔ)法結(jié)構(gòu)l我們今后主要討論我們今后主要討論2 2型文法，就是上下文無(wú)關(guān)的型文法，就是上下文無(wú)關(guān)的文法，今后所說(shuō)的文法，如無(wú)特別聲明，就是指文法，今后所說(shuō)的文法，如無(wú)特別聲明，就是指上下文無(wú)關(guān)的文法上下文無(wú)關(guān)的文法TJNU-COCIE-WJW392022-5-263 3型文法型文法也稱(chēng)為正規(guī)文法、正則文法、線性文法也稱(chēng)為正規(guī)文法、正則文法、線性文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果

28、它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式有如下形式：有如下形式：AaBAaB或或AaAa，其中，其中A A、BVBVN N，aVaVT T，則，則G G是一個(gè)是一個(gè)3 3型文法型文法l3 3型文法等價(jià)于有限自動(dòng)機(jī)型文法等價(jià)于有限自動(dòng)機(jī)l上述定義給出的定義是右線性文法，如果產(chǎn)生式上述定義給出的定義是右線性文法，如果產(chǎn)生式的形式是：的形式是： ABaABa或或AaAa，則稱(chēng)為左線性文法，則稱(chēng)為左線性文法l3 3型文法常用于編譯器的詞法分析程序的構(gòu)造型文法常用于編譯器的詞法分析程序的構(gòu)造TJNU-COCIE-WJW402022-5-264.2 帶回溯的自上而下語(yǔ)法分析帶回溯的自上而下語(yǔ)法分析就是從文法開(kāi)始

29、符號(hào)出發(fā)，向下推導(dǎo)，最后推導(dǎo)就是從文法開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，最后推導(dǎo)出句子出句子一、自上而下語(yǔ)法分析一、自上而下語(yǔ)法分析TJNU-COCIE-WJW412022-5-261.基本思想基本思想對(duì)任何一個(gè)輸入串，試圖用一切可能的辦法，從對(duì)任何一個(gè)輸入串，試圖用一切可能的辦法，從文法的開(kāi)始符號(hào)文法的開(kāi)始符號(hào)(根節(jié)點(diǎn)根節(jié)點(diǎn))出發(fā)，根據(jù)文法自上而出發(fā)，根據(jù)文法自上而下地為輸入串建立一棵語(yǔ)法樹(shù)，即為輸入串尋找下地為輸入串建立一棵語(yǔ)法樹(shù)，即為輸入串尋找一個(gè)最左推導(dǎo)。一個(gè)最左推導(dǎo)。思想本質(zhì)思想本質(zhì)：是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)：是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程。生式謀求匹配輸入串

30、的過(guò)程。二、帶回溯的自上而下語(yǔ)法分析二、帶回溯的自上而下語(yǔ)法分析TJNU-COCIE-WJW422022-5-262.設(shè)有文法設(shè)有文法(1) S xAy(2) A * | *分析輸入串分析輸入串x*y。分析過(guò)程如下：分析過(guò)程如下：利用規(guī)則利用規(guī)則輸入串輸入串語(yǔ)法樹(shù)語(yǔ)法樹(shù)TJNU-COCIE-WJW432022-5-263.構(gòu)造方法構(gòu)造方法讓每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)讓每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)遞歸子程序遞歸子程序。每個(gè)子。每個(gè)子程序可以作為一個(gè)程序可以作為一個(gè)布爾過(guò)程布爾過(guò)程(返回返回“真真”或或“假假”)：(1)一旦發(fā)現(xiàn)該非終結(jié)符的某個(gè)候選式與輸入串相一旦發(fā)現(xiàn)該非終結(jié)符的某個(gè)候選式與輸入串相匹配，就

31、用這個(gè)候選式去擴(kuò)展語(yǔ)法樹(shù)，并返回匹配，就用這個(gè)候選式去擴(kuò)展語(yǔ)法樹(shù)，并返回“真真”值；值；(2)該候選式和輸入串不匹配，則保持原來(lái)的語(yǔ)法該候選式和輸入串不匹配，則保持原來(lái)的語(yǔ)法樹(shù)和樹(shù)和IP值不變值不變(IP回溯回溯)，并返回，并返回“假假”值值TJNU-COCIE-WJW442022-5-261.文法左遞歸文法左遞歸一個(gè)文法存是含有左遞歸的，如果存在非終結(jié)符一個(gè)文法存是含有左遞歸的，如果存在非終結(jié)符P，有有PP當(dāng)試圖用當(dāng)試圖用P P去匹配輸入串時(shí)，在沒(méi)有識(shí)別任何輸入去匹配輸入串時(shí)，在沒(méi)有識(shí)別任何輸入符號(hào)的情況下，又得重新要求符號(hào)的情況下，又得重新要求P P去進(jìn)行新的匹配去進(jìn)行新的匹配，這樣一來(lái)，

32、這樣一來(lái)，使推導(dǎo)無(wú)限循環(huán)下去。使推導(dǎo)無(wú)限循環(huán)下去。2.回溯問(wèn)題回溯問(wèn)題匹配不成功，需要回溯。但已經(jīng)走了一大段錯(cuò)路，匹配不成功，需要回溯。但已經(jīng)走了一大段錯(cuò)路，最后又必須回頭，就需要把已經(jīng)做過(guò)的一大堆工最后又必須回頭，就需要把已經(jīng)做過(guò)的一大堆工作作( (各種表格工作、語(yǔ)義分析等各種表格工作、語(yǔ)義分析等) )推倒重來(lái)，既費(fèi)推倒重來(lái)，既費(fèi)時(shí)又費(fèi)力時(shí)又費(fèi)力三、存在的困難和問(wèn)題三、存在的困難和問(wèn)題TJNU-COCIE-WJW452022-5-263.虛假匹配虛假匹配設(shè)有文法設(shè)有文法(1) S xAy(2) A * | *分析輸入串分析輸入串x*y。分析過(guò)程如下：分析過(guò)程如下：利用規(guī)則利用規(guī)則輸入串輸入串

33、語(yǔ)法樹(shù)語(yǔ)法樹(shù)x*y不能被識(shí)別不能被識(shí)別TJNU-COCIE-WJW462022-5-264.不易知道錯(cuò)誤位置不易知道錯(cuò)誤位置當(dāng)最終報(bào)告分析不成功時(shí)，難于知道輸入串中出當(dāng)最終報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置錯(cuò)的確切位置5.效率極低效率極低由于帶回溯，實(shí)際上才用了一種窮盡一切可能的由于帶回溯，實(shí)際上才用了一種窮盡一切可能的試探法，因此，效率很低，代價(jià)極高。該方法只試探法，因此，效率很低，代價(jià)極高。該方法只有理論意義，在實(shí)踐上價(jià)值不大有理論意義，在實(shí)踐上價(jià)值不大TJNU-COCIE-WJW472022-5-264.3 LL(1)分析法分析法目的目的：構(gòu)造不帶回溯的自上而下分析算法構(gòu)造

34、不帶回溯的自上而下分析算法要求要求：(1)消除文法的左遞歸性消除文法的左遞歸性(自上而下分析方法不允許文法含有左遞歸自上而下分析方法不允許文法含有左遞歸)(2)找出克服回溯的充分必要條件找出克服回溯的充分必要條件(不要回溯不要回溯)TJNU-COCIE-WJW482022-5-261.直接左遞歸直接左遞歸直接見(jiàn)于產(chǎn)生式的左遞歸稱(chēng)為直接左遞歸直接見(jiàn)于產(chǎn)生式的左遞歸稱(chēng)為直接左遞歸. .：產(chǎn)生式：產(chǎn)生式UU2.間接左遞歸間接左遞歸若有若有UU: :文法文法SAa|bSAa|bAAc|Sd|AAc|Sd|S=Aa=SdaS=Aa=Sda一、消除文法的左遞歸一、消除文法的左遞歸TJNU-COCIE-WJ

35、W492022-5-263.消除直接左遞歸消除直接左遞歸：設(shè)有產(chǎn)生式設(shè)有產(chǎn)生式PP|(1)其中其中不以不以P開(kāi)頭，開(kāi)頭，不為不為。那么，我們可以把。那么，我們可以把P的規(guī)則改為如下的非直接左遞歸形式：的規(guī)則改為如下的非直接左遞歸形式：PPPP|(2)(1)式和式和(2)式是等價(jià)的式是等價(jià)的TJNU-COCIE-WJW502022-5-26(續(xù)續(xù))PP|(1)PPPP|(2)對(duì)于對(duì)于(1)式：式：P=P=P=P=對(duì)于對(duì)于(2)式：式：P=P=P=P=P= TJNU-COCIE-WJW512022-5-26：設(shè)有文法：設(shè)有文法GE E + T | T T T * F | F F (E) | i 消

36、除其產(chǎn)生式的直接左遞歸消除其產(chǎn)生式的直接左遞歸解：對(duì)于解：對(duì)于E E + T | T (P=E，=+T，=T)變成變成ETEE+TE|PP|-PP PP|同理：同理：ETEE+TE|TFTT*FT|F(E)|iTJNU-COCIE-WJW522022-5-26：設(shè)有文法：設(shè)有文法GE E + T | T T T * F | F F (E) | i E=E+T= E+T+T= E+T+T=T+T+TE=TE= T+TE= T+T+TE=T+T+TE =T+T+TETEE+TE|TFTT*FT|F(E)|iTJNU-COCIE-WJW532022-5-26消除直接左遞歸方法消除直接左遞歸方法：設(shè)有

37、產(chǎn)生式設(shè)有產(chǎn)生式PP1|P2|Pm|1|2|n其中每個(gè)其中每個(gè)i不以不以P開(kāi)頭，每個(gè)開(kāi)頭，每個(gè)i不為不為消除消除P的直接左遞歸性就是把這些規(guī)則改寫(xiě)成：的直接左遞歸性就是把這些規(guī)則改寫(xiě)成：P1P|2P|nPP1P| 2P|mP| TJNU-COCIE-WJW542022-5-26：消除直接左遞歸的代價(jià)是引進(jìn)了若干非終結(jié)符和消除直接左遞歸的代價(jià)是引進(jìn)了若干非終結(jié)符和產(chǎn)生式產(chǎn)生式用上述辦法實(shí)際上把直接左遞歸變成直接右遞歸用上述辦法實(shí)際上把直接左遞歸變成直接右遞歸PP|PPPP|上述辦法不意味著可以消除整個(gè)文法的左遞歸性上述辦法不意味著可以消除整個(gè)文法的左遞歸性：有文法：有文法 SQc | cQRb

38、| bRSa | a已經(jīng)不具有直接左遞歸，但卻是間接左遞歸的已經(jīng)不具有直接左遞歸，但卻是間接左遞歸的因?yàn)椋阂驗(yàn)椋篠=Qc =Rbc =SabcTJNU-COCIE-WJW552022-5-264.消除整個(gè)文法的左遞歸的算法消除整個(gè)文法的左遞歸的算法如果文法不含回路（形如如果文法不含回路（形如 的推導(dǎo)），也不含有以的推導(dǎo)），也不含有以為右部的產(chǎn)生式，則下面算法可以消除左遞歸為右部的產(chǎn)生式，則下面算法可以消除左遞歸(1)(1)把文法把文法G G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成P P1 1,P,P2 2, ,P,Pn n；按此順序執(zhí)行；按此順序執(zhí)行(2)for i =

39、 1 to n do(2)for i = 1 to n do for j = 1 to i-1 do for j = 1 to i-1 do把形如把形如P Pi iPPj j的規(guī)則改寫(xiě)成的規(guī)則改寫(xiě)成: :P Pi i 1 1|2 2|k k。其中其中P Pj j1 1|2 2| |k k是關(guān)于是關(guān)于P Pj j的所有產(chǎn)生式的所有產(chǎn)生式 EndforEndfor 消除關(guān)于消除關(guān)于P Pi i的直接左遞歸的直接左遞歸EndforEndfor(3)(3)化簡(jiǎn)由化簡(jiǎn)由(2)(2)得到的文法：除去從開(kāi)始符號(hào)無(wú)法達(dá)到的得到的文法：除去從開(kāi)始符號(hào)無(wú)法達(dá)到的非終結(jié)符的產(chǎn)生式非終結(jié)符的產(chǎn)生式PPTJNU-COC

40、IE-WJW562022-5-26：考慮以下文法，消除其左遞歸性：考慮以下文法，消除其左遞歸性SQc | cQRb | bRSa | a解解：(1)把該文法的非終結(jié)符排列為把該文法的非終結(jié)符排列為R、Q、S.(2)對(duì)于對(duì)于R，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除對(duì)于對(duì)于Q，把，把R代入到代入到Q的有關(guān)候選式后，把的有關(guān)候選式后，把Q的產(chǎn)生式改寫(xiě)為的產(chǎn)生式改寫(xiě)為QSab| ab | b現(xiàn)在現(xiàn)在Q不存在直接左遞歸，不用消除不存在直接左遞歸，不用消除對(duì)于對(duì)于S，把，把Q代讀到代讀到S的有關(guān)候選式后，把的有關(guān)候選式后，把S的產(chǎn)生式改寫(xiě)為的產(chǎn)生式改寫(xiě)為SSabc | abc | bc

41、| cS有直接左遞歸，消除有直接左遞歸，消除S的直接左遞歸為的直接左遞歸為SabcS | bcS | cSSabcS | TJNU-COCIE-WJW572022-5-26得到消除左遞歸性的文法為得到消除左遞歸性的文法為SabcS | bcS | cSSabcS | QSab| ab | bRSa | a(3)顯然，顯然，Q和和R的產(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ舻漠a(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ艋?jiǎn)后的文法是：化簡(jiǎn)后的文法是：SabcS | bcS | cSSabcS | ：由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式：由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣，但它們都是等價(jià)

42、的上可能不一樣，但它們都是等價(jià)的TJNU-COCIE-WJW582022-5-26：考慮剛才的文法，消除其左遞歸性：考慮剛才的文法，消除其左遞歸性SQc | cQRb | bRSa | a解解：(1)把該文法的非終結(jié)符排列為把該文法的非終結(jié)符排列為S、Q、R(2)對(duì)于對(duì)于S，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除對(duì)于對(duì)于Q，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除對(duì)于對(duì)于R，把，把S代入到代入到R的有關(guān)候選式后，把的有關(guān)候選式后，把R的產(chǎn)生式改寫(xiě)為的產(chǎn)生式改寫(xiě)為RQca| ca | a把把Q代入到代入到R的有關(guān)候選式后，把的有關(guān)候選式后，把R的產(chǎn)生式改寫(xiě)為的產(chǎn)生式

43、改寫(xiě)為RRbca| bca | ca | aTJNU-COCIE-WJW592022-5-26RRbca| bca | ca | aR有直接左遞歸，消除有直接左遞歸，消除S的直接左遞歸為的直接左遞歸為RbcaR | caR | aRRbcaR | 得到消除左遞歸性的文法為得到消除左遞歸性的文法為SQc | cQRb | bRbcaR | caR | aRRbcaR | TJNU-COCIE-WJW602022-5-261.消除回溯的要求消除回溯的要求對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)該非終結(jié)符所面臨的輸入符號(hào)準(zhǔn)確地指派能夠根據(jù)該非終

44、結(jié)符所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選式去匹配，并且此候選式匹配后得到它的一個(gè)候選式去匹配，并且此候選式匹配后得到的工作結(jié)果應(yīng)該是確信無(wú)疑的，即：的工作結(jié)果應(yīng)該是確信無(wú)疑的，即：(1)若該候選式匹配成功，那么該匹配不是虛假匹配若該候選式匹配成功，那么該匹配不是虛假匹配(2)若該候選式無(wú)法完成最終的匹配任務(wù)，則其他任若該候選式無(wú)法完成最終的匹配任務(wù)，則其他任何候選式肯定也無(wú)法完成何候選式肯定也無(wú)法完成二、消除回溯二、消除回溯TJNU-COCIE-WJW612022-5-26：假設(shè)當(dāng)前輪到非終結(jié)符假設(shè)當(dāng)前輪到非終結(jié)符A去匹配輸入串，去匹配輸入串，A的產(chǎn)生的產(chǎn)生式為式為A1|2|nA所面臨的第一

45、個(gè)輸入符號(hào)為所面臨的第一個(gè)輸入符號(hào)為a，如果，如果A指派指派i去匹去匹配，那么就肯定沒(méi)有回溯。配，那么就肯定沒(méi)有回溯。：這里這里A不再是讓某個(gè)不再是讓某個(gè)i去試探匹配，而是根據(jù)所面去試探匹配，而是根據(jù)所面臨的輸入符號(hào)的不同準(zhǔn)確制定一個(gè)臨的輸入符號(hào)的不同準(zhǔn)確制定一個(gè)i去匹配，若匹去匹配，若匹配到最后沒(méi)能識(shí)別整個(gè)字串，則該字串一定不是該配到最后沒(méi)能識(shí)別整個(gè)字串，則該字串一定不是該文法中的句子。文法中的句子。TJNU-COCIE-WJW622022-5-262.消除回溯的條件消除回溯的條件定義定義FIRSTFIRST集集令文法令文法G G是不含左遞歸的文法，對(duì)是不含左遞歸的文法，對(duì)G G的非終結(jié)符的

46、候的非終結(jié)符的候選選，定義它的開(kāi)始符號(hào)（終結(jié)首符）集合：，定義它的開(kāi)始符號(hào)（終結(jié)首符）集合：特別地，如果特別地，如果 ，則，則FIRST()FIRST()如果非終結(jié)符如果非終結(jié)符A A的任意兩個(gè)候選式的任意兩個(gè)候選式i i和和j j的開(kāi)的開(kāi)始符號(hào)集滿足始符號(hào)集滿足FIRST(FIRST(i i)FIRST()FIRST(j j)=)=，則，則A A可以根據(jù)所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確地可以根據(jù)所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確地指派一個(gè)候選式指派一個(gè)候選式去執(zhí)行任務(wù)，去執(zhí)行任務(wù)，是那個(gè)是那個(gè)FIRSTFIRST集含集含a a的候選式，即的候選式，即 a a FIRST()FIRST()Vaa., |

47、 a)FIRST(T*TJNU-COCIE-WJW632022-5-26：假設(shè)假設(shè)A的產(chǎn)生式為的產(chǎn)生式為A1|2|n當(dāng)前輸入符號(hào)為當(dāng)前輸入符號(hào)為b b，b bVT如果如果b b FIRST(FIRST(1 1) )，則用，則用1 1去匹配去匹配b b如果如果b b FIRST(FIRST(2 2) )，則用，則用2 2去匹配去匹配b b如果如果b b FIRST(FIRST(n n) )，則用，則用n n去匹配去匹配b bFIRST(FIRST(1 1)FIRST()FIRST(2 2)FIRST(FIRST(n n)=)=TJNU-COCIE-WJW642022-5-263.改造文法改造文法

48、 問(wèn)題問(wèn)題：對(duì)于許多程序設(shè)計(jì)語(yǔ)言的文法，都有產(chǎn)生式對(duì)于許多程序設(shè)計(jì)語(yǔ)言的文法，都有產(chǎn)生式語(yǔ)句語(yǔ)句if 條件條件 then 語(yǔ)句語(yǔ)句 else 語(yǔ)句語(yǔ)句| if 條件條件 then 語(yǔ)句語(yǔ)句這兩個(gè)候選式的這兩個(gè)候選式的FIRSTFIRST集合相交不為集合相交不為 TJNU-COCIE-WJW652022-5-263.改造文法改造文法(續(xù)續(xù))改造方法改造方法：提取公共左因子：提取公共左因子假設(shè)假設(shè)A的產(chǎn)生式為的產(chǎn)生式為A1|2|n|1| | 2|m其中每個(gè)其中每個(gè)不以不以開(kāi)頭開(kāi)頭那么把這些產(chǎn)生式改寫(xiě)為那么把這些產(chǎn)生式改寫(xiě)為: :AA |1| | 2|mA1|2|n反復(fù)提取左因子反復(fù)提取左因子( (

49、包括對(duì)新引進(jìn)的非終結(jié)符，例如包括對(duì)新引進(jìn)的非終結(jié)符，例如A A) )TJNU-COCIE-WJW662022-5-26問(wèn)題：?jiǎn)栴}：當(dāng)一個(gè)文法不含左遞歸，并且滿足每個(gè)非終結(jié)當(dāng)一個(gè)文法不含左遞歸，并且滿足每個(gè)非終結(jié)符的所有候選首符集兩兩不相交的條件，是不符的所有候選首符集兩兩不相交的條件，是不是一定能進(jìn)行有效的自上而下分析了呢？是一定能進(jìn)行有效的自上而下分析了呢？若空字若空字屬于某個(gè)非終結(jié)符的候選式的首符集，屬于某個(gè)非終結(jié)符的候選式的首符集，就會(huì)有問(wèn)題就會(huì)有問(wèn)題三、三、LL(1)分析條件分析條件TJNU-COCIE-WJW672022-5-261.引例引例對(duì)于消除左遞歸的文法對(duì)于消除左遞歸的文法E

50、TEE+TE|TFTT*FT|F(E)|i對(duì)輸入串對(duì)輸入串i+i進(jìn)行分析進(jìn)行分析FIRST(TE) = ( ，i FIRST(+TE) = + FIRST() = FIRST(FT) = ( ，i FIRST(*FT) = * FIRST() = FIRST(E) = ( FIRST(i) = i T自動(dòng)匹配自動(dòng)匹配 ，IP不動(dòng)不動(dòng)TJNU-COCIE-WJW682022-5-261.引例引例對(duì)于消除左遞歸的文法對(duì)于消除左遞歸的文法ETEE+TE|TFTT*FT|F(E)|i對(duì)輸入串對(duì)輸入串i ( 進(jìn)行分析進(jìn)行分析FIRST(TE) = ( ，i FIRST(+TE) = + FIRST()

51、= FIRST(FT) = ( ，i FIRST(*FT) = * FIRST() = FIRST(E) = ( FIRST(i) = i T自動(dòng)匹配自動(dòng)匹配 ，IP不動(dòng)不動(dòng)TJNU-COCIE-WJW692022-5-262.定義定義FOLLOW集集 對(duì)文法對(duì)文法G G的任何非終結(jié)符的任何非終結(jié)符A A，定義它的后繼符號(hào)集合：，定義它的后繼符號(hào)集合：特別地，如果特別地，如果S S A，則，則#FOLLOW(A)FOLLOW(A)FOLLOW(A)FOLLOW(A)集合是所有句型中出現(xiàn)在緊接集合是所有句型中出現(xiàn)在緊接A A之后之后的終結(jié)符號(hào)或的終結(jié)符號(hào)或# #所組成的集合所組成的集合當(dāng)非終結(jié)符

52、當(dāng)非終結(jié)符A A面臨輸入符號(hào)面臨輸入符號(hào)a a，且，且a a不屬于不屬于A A的任的任意候選式的意候選式的FIRSTFIRST集但集但A A的某個(gè)候選式的的某個(gè)候選式的FIRSTFIRST集集包含包含時(shí)，只有當(dāng)時(shí)，只有當(dāng)a FOLLOW(A)FOLLOW(A)，才可能允許，才可能允許A A自動(dòng)匹配自動(dòng)匹配Va.Aa.,S | aFOLLOW(A)T*TJNU-COCIE-WJW702022-5-263.不帶回溯的自上而下分析的文法條件（不帶回溯的自上而下分析的文法條件（LL(1)LL(1)文法）文法）(1)文法不含左遞歸文法不含左遞歸(2)對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各

53、個(gè)產(chǎn)生式的候選的各個(gè)產(chǎn)生式的候選式的式的FIRST集兩兩不相交。即，若集兩兩不相交。即，若A1|2|n則則FIRST(FIRST(i i)FIRST()FIRST(j j)=)= (i (ij) )(3)對(duì)于文法中的每個(gè)非終結(jié)符對(duì)于文法中的每個(gè)非終結(jié)符A，若它的某個(gè)候選首，若它的某個(gè)候選首符集包含符集包含,則則FIRST(A)FOLLOW(A)=FIRST(A)FOLLOW(A)=如果一個(gè)文法如果一個(gè)文法G G滿足以上條件，則稱(chēng)該文法滿足以上條件，則稱(chēng)該文法G G為為L(zhǎng)L(1)LL(1)文文法法( (第第1 1個(gè)個(gè)L L代表從左到右掃描輸入串，第代表從左到右掃描輸入串，第2 2個(gè)個(gè)L L代表最

54、左代表最左推導(dǎo)，推導(dǎo)，1 1表示分析時(shí)每一步只看表示分析時(shí)每一步只看1 1個(gè)符號(hào)個(gè)符號(hào)) )TJNU-COCIE-WJW712022-5-264.不帶回溯的自上而下分析的方法不帶回溯的自上而下分析的方法對(duì)于對(duì)于LL(1)LL(1)文法，假設(shè)要用非終結(jié)符文法，假設(shè)要用非終結(jié)符A A進(jìn)行匹配，進(jìn)行匹配，面臨輸入符號(hào)為面臨輸入符號(hào)為a a，A A的所有產(chǎn)生式為的所有產(chǎn)生式為A1|2|n(1)若若a FIRST(FIRST(i i) ) ，則指派，則指派i i去匹配去匹配(2)若若a不屬于任何一個(gè)候選首符集，則：不屬于任何一個(gè)候選首符集，則：若若屬于某個(gè)屬于某個(gè) FIRST(FIRST(i i) )且

55、且aFOLLOW(A)FOLLOW(A)，則讓則讓A A與與自動(dòng)匹配；自動(dòng)匹配；否則，否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤的出現(xiàn)是一種語(yǔ)法錯(cuò)誤TJNU-COCIE-WJW722022-5-264.4 遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造文法滿足文法滿足LL(1)條件（是條件（是LL(1)文法）文法）對(duì)文法的每個(gè)非終結(jié)符號(hào)編寫(xiě)一個(gè)遞歸子程序?qū)ξ姆ǖ拿總€(gè)非終結(jié)符號(hào)編寫(xiě)一個(gè)遞歸子程序一、構(gòu)造條件一、構(gòu)造條件二、構(gòu)造方法二、構(gòu)造方法TJNU-COCIE-WJW732022-5-26：對(duì)于：對(duì)于LL(1)文法文法ETEE+TE|TFTT*FT|F(E)|i構(gòu)造其遞歸下降分析程序構(gòu)造其遞歸下降分析程序TJNU

56、-COCIE-WJW742022-5-26ETEPROCEDURE E;BEGINT;EEND;E+TE|PROCEDURE E;IF SYM=+ THENBEGINADVANCE;T;EEND;TFTPROCEDURE T;BEGINF;TEND;T*FT|PROCEDURE T;IF SYM=* THENBEGINADVANCE;F;TEND;F(E)|IPROCEDURE F;IF SYM=i THEN ADVANCEELSEIF SYM=( THENBEGINADVANCE;E;IF SYM=) THEN ADVANCEELSE ERRORENDELSE ERRORADVANCE把輸入

57、串指示器把輸入串指示器IP指向下一指向下一個(gè)輸入符號(hào)個(gè)輸入符號(hào)SYM是指是指IP當(dāng)前所指的那個(gè)輸入符號(hào)當(dāng)前所指的那個(gè)輸入符號(hào)ERROR為出錯(cuò)處理程序?yàn)槌鲥e(cuò)處理程序TJNU-COCIE-WJW752022-5-26第第2次上機(jī)作業(yè)次上機(jī)作業(yè)根據(jù)根據(jù)編譯原理編譯原理P69頁(yè)文法頁(yè)文法4.2，構(gòu)造其遞歸下，構(gòu)造其遞歸下降分析程序降分析程序n參考參考P74偽代碼偽代碼n要求加入輸入輸出，用要求加入輸入輸出，用C編寫(xiě)編寫(xiě)n輸入使用前面詞法分析程序的結(jié)果，其中輸入使用前面詞法分析程序的結(jié)果，其中i代代表標(biāo)識(shí)符或常數(shù)表標(biāo)識(shí)符或常數(shù)n輸入符號(hào)串，輸出遞歸過(guò)程輸入符號(hào)串，輸出遞歸過(guò)程(非終結(jié)符號(hào)序非終結(jié)符號(hào)序列

58、列)和識(shí)別結(jié)果和識(shí)別結(jié)果(是否正確句子是否正確句子)TJNU-COCIE-WJW762022-5-264.5 預(yù)測(cè)分析程序預(yù)測(cè)分析程序用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器只有用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器只有當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)時(shí)才有意義當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)時(shí)才有意義實(shí)現(xiàn)實(shí)現(xiàn)LL(1)分析的另一種有效方法是使用分析的另一種有效方法是使用一張分析表一張分析表一個(gè)棧一個(gè)棧本節(jié)介紹預(yù)測(cè)分析程序本節(jié)介紹預(yù)測(cè)分析程序TJNU-COCIE-WJW772022-5-261.總體結(jié)構(gòu)總體結(jié)構(gòu) a #預(yù)測(cè)分析表預(yù)測(cè)分析表M總控程序總控程序輸出輸出X.#一、預(yù)測(cè)分析程序的結(jié)構(gòu)一、預(yù)測(cè)分析

59、程序的結(jié)構(gòu)TJNU-COCIE-WJW782022-5-261.總體結(jié)構(gòu)總體結(jié)構(gòu)( (續(xù)續(xù)1)1)總控程序總控程序控制分析表和分析棧的工作控制分析表和分析棧的工作分析棧分析棧用于存放文法符號(hào)。分析開(kāi)始時(shí)先放一個(gè)用于存放文法符號(hào)。分析開(kāi)始時(shí)先放一個(gè)#，然后放進(jìn)文法開(kāi)始符號(hào)。同時(shí)假定輸入串之后也然后放進(jìn)文法開(kāi)始符號(hào)。同時(shí)假定輸入串之后也總有一個(gè)總有一個(gè)#，標(biāo)志輸入串的結(jié)束，標(biāo)志輸入串的結(jié)束TJNU-COCIE-WJW792022-5-261.總體結(jié)構(gòu)總體結(jié)構(gòu)( (續(xù)續(xù)2)2)一張分析表一張分析表M用一個(gè)矩陣來(lái)表示，即用一個(gè)矩陣來(lái)表示，即MA , a(1)A為非終結(jié)符為非終結(jié)符(2)a是終結(jié)符或者是

60、終結(jié)符或者#(這里這里#不是文法的終結(jié)不是文法的終結(jié)符，我們把它作為輸入串的結(jié)束符號(hào)符，我們把它作為輸入串的結(jié)束符號(hào))(3)矩陣的元素矩陣的元素MA , a中存放著一條關(guān)于中存放著一條關(guān)于A的產(chǎn)的產(chǎn)生式，指出當(dāng)生式，指出當(dāng)A面臨輸入符號(hào)面臨輸入符號(hào)a時(shí)所應(yīng)采用的候選時(shí)所應(yīng)采用的候選式。也可能放一個(gè)式。也可能放一個(gè)“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，指出，指出A根本不根本不該面臨輸入符號(hào)該面臨輸入符號(hào)a。TJNU-COCIE-WJW802022-5-26：有文法：有文法ETEE+TE|TFTT*FT|F(E)|iE#i + i * i #IPTJNU-COCIE-WJW812022-5-261.分析開(kāi)始時(shí)，各