編譯原理文法和語言

1、編譯原理文法和語言1第1頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二第2章文法和語言【學(xué)習(xí)目標(biāo)】本章是為語言的語法描述尋求工具 掌握對程序設(shè)計(jì)語言給出精確、無二義（嚴(yán)謹(jǐn)、易讀）的語法描述的手段之一文法。 對形式語言的理論有一個(gè)初步基礎(chǔ) 根據(jù)文法的特點(diǎn)指導(dǎo)語法分析過程2第2頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.1 文法的直觀表示文法：闡明語法的一個(gè)工具，也可以說是以有窮的集合刻畫無窮的集合的一個(gè)工具。語言：程序設(shè)計(jì)語言。一、語言概述語言是由符合語法的句子組成的集合。漢語-所有符合漢語語法的句子的全體英語-所有符合英語語法的句子的全體程序設(shè)計(jì)語言-所有該語言的

2、程序的全體 每個(gè)句子構(gòu)成的規(guī)律語法研究語言 每個(gè)句子的含義 語義 每個(gè)句子和使用者的關(guān)系語用3第3頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二形式語言：只考慮語法而不考慮語義的符號(hào)語言。每種語言具有兩個(gè)可識(shí)別的特性語言的形式與該形式相關(guān)聯(lián)的意義“形式”指語言的所有規(guī)則，描述出現(xiàn)什么符號(hào)串語言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的基本符號(hào)串組成的所有集合。形式語言理論是對符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。4第4頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二表達(dá)語言時(shí)，一般無法窮盡語言的所有句子，常用規(guī)則加以描述 例：漢

3、語句子的構(gòu)成規(guī)則：句子=主語謂語主語=代詞|名詞代詞= 我 | 你 | 他名詞= 王明 | 大學(xué)生 | 工人 | 英語謂語=動(dòng)詞直接賓語動(dòng)詞= 是 | 學(xué)習(xí)直接賓語=代詞|名詞二、文法的直觀概念5第5頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二推導(dǎo)：“我是大學(xué)生” 是漢語的一個(gè)句子句子 主語 謂語 代詞謂語 我謂語 我動(dòng)詞直接賓語 我是直接賓語 我是名詞 我是大學(xué)生 6第6頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.2 符號(hào)與符號(hào)串一、相關(guān)概念程序設(shè)計(jì)語言是由程序構(gòu)成的集合，程序是由基本符號(hào)按照一定的規(guī)則構(gòu)成的集合。1. 符號(hào)、字母表和符號(hào)串基本符號(hào)：可以相互區(qū)

4、別的基本元素，如字母，數(shù)字，標(biāo)點(diǎn)符號(hào)。字母表：基本符號(hào)的非空有窮集合，常用表示。例： =0,1， =a, b, c, , x,y, z7第7頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二符號(hào)串：由字母表中的符號(hào)構(gòu)成的任何有窮序列稱為符號(hào)串。符號(hào)串中的符號(hào)是有順序的。例如 =0,1上的符號(hào)串0, 1, 00, 01, 11, 10 注意：表示空符號(hào)串,它表示不包含任何符號(hào)串，不是空格符。符號(hào)串集合：字母表上若干個(gè)符號(hào)串組成的集合.例：字母表=0,1 的符號(hào)串集合A=1, 00, 01;約定：小寫字母 a,b,r表示符號(hào). 小寫字母 s,t,z表示符號(hào)串;8第8頁，共59頁，2022年

5、，5月20日，20點(diǎn)32分，星期二符號(hào)串s的頭（前綴）和尾（后綴） ：如果s=xy是一符號(hào)串，那么x是s的頭，y是s的尾。若x是非空，則y是固有尾；若y非空，則x是固有頭。前綴：移走符號(hào)串s尾部的零個(gè)或多個(gè)符號(hào)得到的串。 如：設(shè)s=abc,那么s的前綴是，a，ab，abc 后綴：移走符號(hào)串s頭部的零個(gè)或多個(gè)符號(hào)得到的串。 如：s =abc的后綴是，c，bc，abc，s的固有尾是，c，bc。 9第9頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二符號(hào)串s的子串： 從s中刪去任何前綴或后綴得到的串. 如:bc是符號(hào)串a(chǎn)bc的一個(gè)子串.對符號(hào)串s， s和兩者都是符號(hào)串s的前綴、后綴和子串。

6、符號(hào)串s的真前綴，真后綴，真子串：任何非空符號(hào)串 x，是s的前綴，后綴或子串，并且 s x10第10頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.符號(hào)串的運(yùn)算(1)符號(hào)串相等： 符號(hào)串x，y，如果兩者諸符號(hào)依次相等，則兩符號(hào)串相等。(2)符號(hào)串的長度：符號(hào)串中包含符號(hào)的個(gè)數(shù)。|abc|=3；| |=0；(3)符號(hào)串的連結(jié)：x=abc，y=def 則xy=abcdef；yx=defabc；xy yx x=x =x；11第11頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二(4)符號(hào)串集合的乘積： 設(shè)A、B為兩個(gè)符號(hào)串集合，其乘積為AB=xy|x A，yB；例：A=aa，

7、bb，B=cc，dd，則AB=aacc，aadd，bbcc，bbdd A=A =A；(5)空集：不含任何元素的集合稱為空集。記為；對任何集合A：A = A= ; 注意： 12第12頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二(6)符號(hào)串的方冪： x是字母表上的符號(hào)串，則x的冪運(yùn)算為：x0= ; x1= x; x2= xx; xn= xn-1x=x xn-1 (n0) xn表示n個(gè)x相連結(jié)。eg：x=ok；則 x0= ; x1= ok; x2= okok; (7)符號(hào)串集合的方冪：A為符號(hào)串集合，則A的冪運(yùn)算為：A0=; A1=A; A2=AA;. An= An-1A=AAn-1;

8、(n0) A=aa，bb，則A0=； A1=aa，bb； A2=AA=aaaa，aabb，bbaa，bbbb;.13第13頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二(8)符號(hào)串集合的閉包和正閉包集合A的閉包表示為A*（亦稱為自反閉包或星閉包）定義為：A*=A0 A1 A2 A3 =Ak， k0正閉包表示為A+具體定義為A+=A1 A2 A3 =Ak， k1由定義可以看到A*= A0 A+例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,14第14頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二3、

9、語言(1)由一組符號(hào)所構(gòu)成的集合。即： 字母表上的每個(gè)語言是*的一個(gè)子集。例如：字母表=a,b，*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示為w|w*且w=anbn,n1為字母表上的一個(gè)語言。集合a,aa,aaa, 或表示為w|w*，且w=an，n1 為字母表上的一個(gè)語言。(2) 是一個(gè)語言。(3) 即 是一個(gè)語言。15第15頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.3 文法和語言的形式定義如何來描述一種語言？如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言

10、的有窮表示有兩個(gè)途徑：生成方式 （文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。 識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一個(gè)任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要么能停止并回答“不是”，（要么永遠(yuǎn)繼續(xù)下去。）16第16頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二一、規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）規(guī)則是形如或=的(，)有序?qū)Γ?其中 V+， V*中的一個(gè)符號(hào)稱為規(guī)則的左部稱作規(guī)則的右部。例： 文法可利用規(guī)則來描述。17第17頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二二、文法的定義1、文法G定義為四元組(VN，VT，P，S

11、)其中VN ：非終結(jié)符號(hào)；VT：終結(jié)符號(hào)集；P：規(guī)則集合；VN，VT和P是非空有窮集。 S：開始符或識(shí)別符，是一個(gè)非終結(jié)符，至少要在一條規(guī)則的左部出現(xiàn)。VN VT = ，V=VN VT ，V稱為文法G的字母表例1：文法G = (VN，VT，P，S)， 其中 VN=S， VT=0，1， P=S0S1，S01。18第18頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二文法G習(xí)慣上只將規(guī)則寫出。如例1還可以寫成：G：S0S1 S01或GS：S0S1S01 或GS：S0S1 | S0119第19頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二總結(jié)一個(gè)文法的幾種寫法 G=(S,A，a

12、,b，P，S) 其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS： S aAb Aab AaAb A GS： SaAb Aab |aAb |20第20頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二三、推導(dǎo)的定義用文法定義語言的中心思想是：從文法的開始符號(hào)出發(fā)，反復(fù)使用合適規(guī)則，對非終結(jié)符施行替換和展開。1、直接推導(dǎo)： 是文法G的產(chǎn)生式，若有v，w滿足：v =，w = , 其中V*,V*。則稱v直接推導(dǎo)到w,或w直接歸約到v記作 vw，2、推導(dǎo)：如果存在直接推導(dǎo)的序列：v=W0 W1 W2 Wn=w,(n0)；稱v推導(dǎo)出w(推導(dǎo)長度為n)，或稱w歸約到

13、v。 記作v w。若有v w，或v=w，則記作v w ，(n=0)*21第21頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例3：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11+*22第22頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二3、規(guī)范推導(dǎo)最左(最右)推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對中的最左（右）非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。例4：GE： EE+T|T TT*F|F F

14、(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a（最左推導(dǎo)） EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a （最右推導(dǎo)）23第23頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二四、句型、句子和語言的定義1.句型:文法GS，若S x，則稱x是G的句型。2.句子:文法GS，若S x，且xVT*，則稱x是G的句子。句子是句型的特殊，只包含終結(jié)符。例5：G：S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S, 0S1 ,00S11 ,000S111,0000111

15、1 G的句子000011113.語言:文法G的一切句子的集合, 記為L(G)，*24第24頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例 6 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee SanBnEn anbnen 則 L（G）= anbnen | n1 因?yàn)镾an-1S（BE）n-1 an（BE）n ，繼續(xù)推導(dǎo)時(shí)，將用規(guī)則(3)(7)替換*25第25頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBE

16、E ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee)G生成的每個(gè)串都在L(G)中L(G)中的每個(gè)串確實(shí)能被G生成26第26頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二五、語言和文法給定一個(gè)文法，能從結(jié)構(gòu)上唯一確定其語言給定一個(gè)語言，不能唯一確定其文法，即一個(gè)語言可有多個(gè)文法與之對應(yīng)已知語言描述，寫出文法，應(yīng)滿足：所描述的語言的任何句子都能由該文法產(chǎn)生該文法推導(dǎo)不出不是已知語言的任何句子已知文法，寫出語言描述，應(yīng)滿足：該文法能推導(dǎo)出的任何句子都包含在所描述的語言中描述的語言中不包含該文法推導(dǎo)不出的句子27第27頁，共59頁，202

17、2年，5月20日，20點(diǎn)32分，星期二六、文法的等價(jià)若L（G1）=L（G2），稱文法G1和G2是等價(jià)的如文法G1A：A0R 與G2S：S0S1 等價(jià) A01 S01 RA1作業(yè)：P47:1，4，528第28頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.4 文 法 的 類 型一、文法分類 通過對產(chǎn)生式施加不同的限制，將文法分為四類 設(shè)有文法G=(VN，VT，P，S);0型文法：（短語結(jié)構(gòu)文法）圖靈機(jī)對任一產(chǎn)生式，都有(VNVT)+，且至少包含一個(gè)非終結(jié)符，(VNVT)*1型文法：（上下文有關(guān)文法）對任一產(chǎn)生式，都有|， 僅僅 S除外。29第29頁，共59頁，2022年，5月20日

18、，20點(diǎn)32分，星期二文法GS是1型文法 SaSBC| aBC CB DB DB DC DCBC aBab bBbb bCbc cCccSaSBC aaBCBC aabCBC aabbcc*30第30頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2型文法：（上下文無關(guān)文法）對任一產(chǎn)生式，都有VN ，(VNVT)*設(shè)文法G(VN,VT,P,S)是一個(gè)2型文法， VN S,A,B, VT a,b 其中P為: (0) S aB (1) S bA (2) A a (3) A aS | bAA (4) B b (5) B bS | aBB31第31頁，共59頁，2022年，5月20日，20點(diǎn)

19、32分，星期二3型文法：（正規(guī)文法）右線性文法任一產(chǎn)生式的形式都為AaB或Aa，其中AVN ，BVN ，aVT(a可為)左線性文法任一產(chǎn)生式的形式都為ABa或Aa，其中AVN ，BVN ，aVT(a可為)32第32頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例：GE： EE+T|T TT*F|F F(E)|a G是上下文無關(guān)文法。例文法G=(S,A,B,0,1,P,S)，其中P由下列產(chǎn)生式組成：S0A A1BS1B B1BS0 B1A0A B0A0SG是正規(guī)文法。33第33頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二二、四類文法之間的關(guān)系四種文法之間的逐級(jí)“包含”關(guān)

20、系2型文法1型文法0型文法3型文法34第34頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.5 上下文無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)例:文法GE：Ea|E+E|E*E|(E) E表示算術(shù)表達(dá)式, a表示程序的“變量”， 該文法定義了由變量，+，*,(和)組成的算術(shù)表達(dá)式的語法結(jié)構(gòu)句型推導(dǎo)的直觀表示-語法樹35第35頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二設(shè)G為一上下文無關(guān)文法，若一棵樹滿足下列4個(gè)條件，則稱作G的語法樹(推導(dǎo)樹，派生樹）1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2. 根的標(biāo)記是 文法開始符號(hào)S3. 如

21、果結(jié)點(diǎn)n至少有一個(gè)除自己外的子孫并有標(biāo)記A，則肯定AVN4. 如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式語法樹的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的行一、語法樹36第36頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+TEE+TTEE+TTFEE+TTFaT*FFaa給定文法G=(VN, VT, P, S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)

22、樹)37第37頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號(hào)串，為GS的句型。該推導(dǎo)樹稱為該句型的語法樹。用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法 例: GS:SaASASbAASSSaAba用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法句型aabbaa的語法樹（推導(dǎo)樹） S a A S S b A a a b a38第38頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:SaASASbA

23、ASSSaAbaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa S a A S S b A a a b a39第39頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例：GE： EE+T|T TT*F|F F(E)|a 試給出表達(dá)式a+a*a的推導(dǎo)，并畫出語法樹。左: EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a右: EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a 混合: EE+T T+T T+T*F

24、F+T*F F+F*F a+F*F a+F*a a+a*a40第40頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例如，有一個(gè)2型文法 G= (S,A,B,a,b,P,S),其中P: (0) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 采用最左推導(dǎo)產(chǎn)生句子aabbab: S aB aaBB aabSB aabbAB aabbaB aabbab一棵語法樹表示了一個(gè)句型的種種可能的不同推導(dǎo)過程，一個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢? 是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?41第41頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二語法樹其中P: (0

25、) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB分析句子aabbab SaBaBBbSbbAa42第42頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例：GE:E aE E+EE E*EE (E) E E + E E * E a a a E E * E a E + E a a句型 a*a+a 的兩個(gè)不同的最左推導(dǎo)：(1)EE+EE*E+E a*E+E a*a+E a*a+a(2)E E*E a*E a*E+E a*a+E a*a+a43第43頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二 若一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法

26、是二義的。 或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的文法的二義性和語言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G，其中G是二義的，但是卻有L(G)=L(G)，也就是說，這兩個(gè)文法所產(chǎn)生的語言是相同的。 44第44頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法都是二義的，則說此語言是先天二義的。對于一個(gè)程序設(shè)計(jì)語言來說，常常希望它的文法是無二義的，因?yàn)橄Ｍ麑λ拿總€(gè)語句的分析是唯一的。二義文法改造為無二義文法GE: E a GE：E T|E+T E E+E T F|T*F E E*E F （E）|a

27、E (E) 規(guī)定優(yōu)先順序和結(jié)合律45第45頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2.6 句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。在語言的編譯實(shí)現(xiàn)中，完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。46第46頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二一、句型的分析算法分類分析算法可分為：自上而下分析法：從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。自下而上分析法：

28、從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。兩種方法反映了兩種不同的語法樹的構(gòu)造過程。 47第47頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二1、自上而下的語法分析例：文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子S S S c Adc Ad a b推導(dǎo)過程：S cAd cAd cabd48第48頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二2、自下而上的語法分析例：文法G： S cAd A ab A a識(shí)別輸入串w=cabd是否該文法的句子SAA c a b d c a b d c a b d 規(guī)約過程構(gòu)造的推導(dǎo)： cAd

29、 cabd S cAd49第49頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二3、句型分析的有關(guān)問題1）在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？假定要被代換的最左非終結(jié)符是B，且有n條規(guī)則：BA1|A2|An，如何確定用哪個(gè)右部去替代B？2）自下而上分析法中，分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符，該子串稱為“可歸約串”,如何識(shí)別可歸約串？3）存在確定和不確定分析，本課只討論確定分析50第50頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二4、短語、直接短語、句柄的定義對于文法GS（1）句型的短語: S = A且 A =，則稱是句型相對于非終結(jié)符A的短語。（2）句型的直接短語：若有A ，則稱是句型相對于非終結(jié)符A 的直接短語。（3）句型的句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。*+51第51頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二語法樹子樹分析法：短語：任意一顆子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串（按給定句型排除）。直接短語：只有父子兩層的子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串。句柄：最左最下的只有父子兩層的子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串。52第52頁，共59頁，2022年，5月20日，20點(diǎn)32分，星期二例1：考慮文法GE: ET