編譯原理-第四章

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

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

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

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

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

6、e girl是不是一個語法上正確的句子？是不是一個語法上正確的句子？思想：是否可以利用我們定義的這些語法規(guī)則推思想：是否可以利用我們定義的這些語法規(guī)則推導(dǎo)出這個句子導(dǎo)出這個句子方法：從方法：從出發(fā)，反復(fù)把上述規(guī)則中的出發(fā)，反復(fù)把上述規(guī)則中的“”左邊成分替換成右邊成分左邊成分替換成右邊成分TJNU-COCIE-WJW102022-5-26推導(dǎo)過程推導(dǎo)過程：=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也可以用語法分析樹來表示這種推導(dǎo)也可以用語法分析樹來表示這種推導(dǎo) The boy sees the girlTJNU-COCIE-WJW122022-5-262. 引出幾個概念引出幾個概念(1)終結(jié)符號終結(jié)符號不帶尖括號的部分，就是單詞符號，語法分析角不帶尖括號的部分，就是單詞符號，語法分析角度是不可再分的基本符號度是不可再分的基本符號： the、 boy、 sees、 girl等等：基本字、標(biāo)識符、常數(shù)、算符和界符等：基本字、標(biāo)識符、常數(shù)、算符和界符等TJNU-COCIE-WJW132022-5-26(2)非終結(jié)符號非終結(jié)符號帶尖括號的部分，代表一類語法成分帶尖括號的部分，代

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

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

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

11、，是一個開始符號，也稱為是識別符號，是一個非終結(jié)符，至少在一個產(chǎn)生式作為左部出現(xiàn)一個非終結(jié)符，至少在一個產(chǎn)生式作為左部出現(xiàn)P P是一個產(chǎn)生式的集合是一個產(chǎn)生式的集合( (有限有限) )，它的每個元素稱為，它的每個元素稱為一條產(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代表變量代表變量描述了一類由變量和描述了一類由變量和+*運(yùn)算組成的算數(shù)表達(dá)式文法運(yùn)算組成的算數(shù)表達(dá)式文法TJNU-COCIE-WJW182022-5-26：(1)文法的核心是一組產(chǎn)生式，而開始符號文法的核心是一組產(chǎn)生式，而開始符號S是文法所要識別的語法范疇（語法單位）是文法所要識別的語法范疇（語法單位）(2)若有這樣一些左部相同的產(chǎn)生式：若有這樣一些左部相同的產(chǎn)生式：P1P2Pn可以合并為一個，縮寫成可以合并為一個，縮寫成P1 | 2 | | n其中每個其中每個i 稱為稱為P的一個候選式，的一個候選式，|讀作讀作“或或”：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è)一個文法設(shè)一個文法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é)符組成的任意符號串成的任意符號串)且，且， A是是G的一個產(chǎn)生式，如果有的一個產(chǎn)生式，如果有 A = 就稱就稱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則稱這個序列是從則稱這個序列是從1 到到n的一個推導(dǎo)的一個推導(dǎo) 1 n從從1 出發(fā)經(jīng)過出發(fā)經(jīng)過1步或若干步推出步或若干步推出n1 n從從1 出發(fā)經(jīng)過出發(fā)經(jīng)過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)任何一步任何一步 = 都對都對最左邊最左邊的那個的那個非終結(jié)符號非終結(jié)符號進(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、對都對最右邊最右邊的那個的那個非終結(jié)符號非終結(jié)符號進(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是一個文法，是一個文法，S S是它的開始符號，如果是它的開始符號，如果S S ，且，且(V VN NV VT T)* 則稱則稱是是G的一個句型的一個句型6.句子句子設(shè)設(shè)G G是一個文法，是一個文法，S S是它的開始符號，如果是它的開始符號，如果S S ，且，且 V VT T* 則稱則稱是是G的一個句子的一個句子：(1)句子實(shí)際上是僅含有終結(jié)符號的句型句子實(shí)際上是僅含有終結(jié)符

17、號的句型(2)從一個句型到另一個句型的推導(dǎo)過程不唯一從一個句型到另一個句型的推導(dǎo)過程不唯一*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.語言語言文法文法G G所產(chǎn)生的句子的全體就是一個語言，記為所產(chǎn)生的句子的全體就是一個語言，記為L(G)L(G)L(G)=L(G)= | S & V VT T* 8.8.文法和語言的關(guān)系文法和語言的關(guān)系(1)(1)給定一個文法，就能從結(jié)構(gòu)上唯一確定其語言給定一個文法，就能從結(jié)構(gòu)上唯一確定其語言G-G-L(G)L(G)( (唯一的唯一的) )(2)(2)給定一種語言，能找到其文法，但該文法不是唯一給定一種語言，能找到其文法，但該文法不是唯一的，即的，即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)造其語言試構(gòu)造其語言解解：因?yàn)橐驗(yàn)閆 = aZb = a2Zb2 = a3Zb3 = = an-1Zbn-1 = anbn所以所以L(G) = anbn | n1TJNU-COCIE-WJW282022-5-26：已知語言：已知語言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.語法分析樹語法分析樹用一棵樹來表示句型的推導(dǎo)，簡稱語法樹用一棵樹來表示句型的推導(dǎo)，簡稱語法樹三、三、語法分析樹與二義性語法分析樹與二義性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、性句子的二義性若一個文法的一個句子對應(yīng)兩棵不同的語法樹，若一個文法的一個句子對應(yīng)兩棵不同的語法樹，則稱該句子是二義性句子則稱該句子是二義性句子：有個句子：手提包：有個句子：手提包 手手 提提 包包TJNU-COCIE-WJW322022-5-263.文法的二義性文法的二義性如果一個文法含有二義性的句子，則稱該文法是如果一個文法含有二義性的句子，則稱該文法是二義性文法二義性文法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對于上例，規(guī)定對于上例，規(guī)定*比比+優(yōu)先級高，且都服從左結(jié)合優(yōu)先級高，且都服從左結(jié)合構(gòu)造無二義性的文法構(gòu)造無二義性的文法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喬姆斯基形式語言理論：喬姆斯基形式語言理論：19561956年建立，發(fā)展至今，年建立，發(fā)展至今，對產(chǎn)生式加以不同限制得到對產(chǎn)生式加以不同限制得到4 4種類型的文法：種類型的文法：0 0型型1 1型型2 2型型3 3型型四、四、文法分類文法分類TJNU-COCIE-WJW362022-5-260 0型文法型文法也稱為短語結(jié)構(gòu)文法也稱為短語結(jié)構(gòu)文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每個產(chǎn)生式，如果它的每個產(chǎn)生式是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)：(V(VN NVVT T)

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

25、它的每個產(chǎn)生式有如下形式：下形式：x xAyxyAyxy，AVAVN N，(V(VN NVVT T) )+ +， x x、y(Vy(VN NVVT T) )* *，則，則G G是一個是一個1 1型文法型文法l對非終結(jié)符進(jìn)行替換時必須考慮上下文，對非終結(jié)符進(jìn)行替換時必須考慮上下文，A A只有在只有在x x和和y y這樣的上下文環(huán)境中才能替換為這樣的上下文環(huán)境中才能替換為l另一種定義：設(shè)另一種定義：設(shè)G=(VG=(VN N,V,Vt t,P,S),P,S)，如果它的每個產(chǎn)生，如果它的每個產(chǎn)生式式滿足滿足|=|=|，則，則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型文法對程序設(shè)計(jì)語言的應(yīng)用來說一般太復(fù)雜了，型文法對程序設(shè)計(jì)語言的應(yīng)用來說一般太復(fù)雜了，難于應(yīng)用難于應(yīng)用TJNU-COCIE-WJW382022-5-262 2型文法型文法也稱為上下文無關(guān)文法也稱為上下文無關(guān)文法l定義：設(shè)定義：設(shè)G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每個產(chǎn)生式，如果它的每個產(chǎn)生式有如下形式：有如下形式：A A，AVAVN N，(V(VN NVVT T) )* *，則，則G G是一個是一個2 2型文法型文法l2 2型文

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

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

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

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

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

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

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

34、不帶回溯的自上而下分析算法要求要求：(1)消除文法的左遞歸性消除文法的左遞歸性(自上而下分析方法不允許文法含有左遞歸自上而下分析方法不允許文法含有左遞歸)(2)找出克服回溯的充分必要條件找出克服回溯的充分必要條件(不要回溯不要回溯)TJNU-COCIE-WJW482022-5-261.直接左遞歸直接左遞歸直接見于產(chǎn)生式的左遞歸稱為直接左遞歸直接見于產(chǎn)生式的左遞歸稱為直接左遞歸. .：產(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開頭，開頭，不為不為。那么，我們可以把。那么，我們可以把P的規(guī)則改為如下的非直接左遞歸形式：的規(guī)則改為如下的非直接左遞歸形式：PPPP|(2)(1)式和式和(2)式是等價的式是等價的TJNU-COCIE-WJW502022-5-26(續(xù)續(xù))PP|(1)PPPP|(2)對于對于(1)式：式：P=P=P=P=對于對于(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)生式的直接左遞歸解：對于解：對于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其中每個其中每個i不以不以P開頭，每個開頭，每個i不為不為消除消除P的直接左遞歸性就是把這些規(guī)則改寫成：的直接左遞歸性就是把這些規(guī)則改寫成：P1P|2P|nPP1P| 2P|mP| TJNU-COCIE-WJW542022-5-26：消除直接左遞歸的代價是引進(jìn)了若干非終結(jié)符和消除直接左遞歸的代價是引進(jìn)了若干非終結(jié)符和產(chǎn)生式產(chǎn)生式用上述辦法實(shí)際上把直接左遞歸變成直接右遞歸用上述辦法實(shí)際上把直接左遞歸變成直接右遞歸PP|PPPP|上述辦法不意味著可以消除整個文法的左遞歸性上述辦法不意味著可以消除整個文法的左遞歸性：有文法：有文法 SQc | cQRb

38、| bRSa | a已經(jīng)不具有直接左遞歸，但卻是間接左遞歸的已經(jīng)不具有直接左遞歸，但卻是間接左遞歸的因?yàn)椋阂驗(yàn)椋篠=Qc =Rbc =SabcTJNU-COCIE-WJW552022-5-264.消除整個文法的左遞歸的算法消除整個文法的左遞歸的算法如果文法不含回路（形如如果文法不含回路（形如 的推導(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ī)則改寫成的規(guī)則改寫成: :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)化簡由化簡由(2)(2)得到的文法：除去從開始符號無法達(dá)到的得到的文法：除去從開始符號無法達(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)對于對于R，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除對于對于Q，把，把R代入到代入到Q的有關(guān)候選式后，把的有關(guān)候選式后，把Q的產(chǎn)生式改寫為的產(chǎn)生式改寫為QSab| ab | b現(xiàn)在現(xiàn)在Q不存在直接左遞歸，不用消除不存在直接左遞歸，不用消除對于對于S，把，把Q代讀到代讀到S的有關(guān)候選式后，把的有關(guān)候選式后，把S的產(chǎn)生式改寫為的產(chǎn)生式改寫為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)サ艋喓蟮奈姆ㄊ牵夯喓蟮奈姆ㄊ牵篠abcS | bcS | cSSabcS | ：由于對非終結(jié)符排序的不同，最后所得的文法在形式：由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣，但它們都是等價

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

43、改寫為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.消除回溯的要求消除回溯的要求對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)該非終結(jié)符所面臨的輸入符號準(zhǔn)確地指派能夠根據(jù)該非終

44、結(jié)符所面臨的輸入符號準(zhǔn)確地指派它的一個候選式去匹配，并且此候選式匹配后得到它的一個候選式去匹配，并且此候選式匹配后得到的工作結(jié)果應(yīng)該是確信無疑的，即：的工作結(jié)果應(yīng)該是確信無疑的，即：(1)若該候選式匹配成功，那么該匹配不是虛假匹配若該候選式匹配成功，那么該匹配不是虛假匹配(2)若該候選式無法完成最終的匹配任務(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、個輸入符號為所面臨的第一個輸入符號為a，如果，如果A指派指派i去匹去匹配，那么就肯定沒有回溯。配，那么就肯定沒有回溯。：這里這里A不再是讓某個不再是讓某個i去試探匹配，而是根據(jù)所面去試探匹配，而是根據(jù)所面臨的輸入符號的不同準(zhǔn)確制定一個臨的輸入符號的不同準(zhǔn)確制定一個i去匹配，若匹去匹配，若匹配到最后沒能識別整個字串，則該字串一定不是該配到最后沒能識別整個字串，則該字串一定不是該文法中的句子。文法中的句子。TJNU-COCIE-WJW622022-5-262.消除回溯的條件消除回溯的條件定義定義FIRSTFIRST集集令文法令文法G G是不含左遞歸的文法，對是不含左遞歸的文法，對G G的非終結(jié)符的

46、候的非終結(jié)符的候選選，定義它的開始符號（終結(jié)首符）集合：，定義它的開始符號（終結(jié)首符）集合：特別地，如果特別地，如果 ，則，則FIRST()FIRST()如果非終結(jié)符如果非終結(jié)符A A的任意兩個候選式的任意兩個候選式i i和和j j的開的開始符號集滿足始符號集滿足FIRST(FIRST(i i)FIRST()FIRST(j j)=)=，則，則A A可以根據(jù)所面臨的第一個輸入符號，準(zhǔn)確地可以根據(jù)所面臨的第一個輸入符號，準(zhǔn)確地指派一個候選式指派一個候選式去執(zhí)行任務(wù)，去執(zhí)行任務(wù)，是那個是那個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)前輸入符號為當(dāng)前輸入符號為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、 問題問題：對于許多程序設(shè)計(jì)語言的文法，都有產(chǎn)生式對于許多程序設(shè)計(jì)語言的文法，都有產(chǎn)生式語句語句if 條件條件 then 語句語句 else 語句語句| if 條件條件 then 語句語句這兩個候選式的這兩個候選式的FIRSTFIRST集合相交不為集合相交不為 TJNU-COCIE-WJW652022-5-263.改造文法改造文法(續(xù)續(xù))改造方法改造方法：提取公共左因子：提取公共左因子假設(shè)假設(shè)A的產(chǎn)生式為的產(chǎn)生式為A1|2|n|1| | 2|m其中每個其中每個不以不以開頭開頭那么把這些產(chǎn)生式改寫為那么把這些產(chǎn)生式改寫為: :AA |1| | 2|mA1|2|n反復(fù)提取左因子反復(fù)提取左因子( (

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

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

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

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

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

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

55、且aFOLLOW(A)FOLLOW(A)，則讓則讓A A與與自動匹配；自動匹配；否則，否則，a的出現(xiàn)是一種語法錯誤的出現(xiàn)是一種語法錯誤TJNU-COCIE-WJW722022-5-264.4 遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造文法滿足文法滿足LL(1)條件（是條件（是LL(1)文法）文法）對文法的每個非終結(jié)符號編寫一個遞歸子程序?qū)ξ姆ǖ拿總€非終結(jié)符號編寫一個遞歸子程序一、構(gòu)造條件一、構(gòu)造條件二、構(gòu)造方法二、構(gòu)造方法TJNU-COCIE-WJW732022-5-26：對于：對于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指向下一指向下一個輸入符號個輸入符號SYM是指是指IP當(dāng)前所指的那個輸入符號當(dāng)前所指的那個輸入符號ERROR為出錯處理程序?yàn)槌鲥e處理程序TJNU-COCIE-WJW752022-5-26第第2次上機(jī)作業(yè)次上機(jī)作業(yè)根據(jù)根據(jù)編譯原理編譯原理P69頁文法頁文法4.2，構(gòu)造其遞歸下，構(gòu)造其遞歸下降分析程序降分析程序n參考參考P74偽代碼偽代碼n要求加入輸入輸出，用要求加入輸入輸出，用C編寫編寫n輸入使用前面詞法分析程序的結(jié)果，其中輸入使用前面詞法分析程序的結(jié)果，其中i代代表標(biāo)識符或常數(shù)表標(biāo)識符或常數(shù)n輸入符號串，輸出遞歸過程輸入符號串，輸出遞歸過程(非終結(jié)符號序非終結(jié)符號序列

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

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

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