《形式語(yǔ)言的基礎(chǔ)知識(shí).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《形式語(yǔ)言的基礎(chǔ)知識(shí).ppt（56頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第2章 形式語(yǔ)言的基礎(chǔ)知識(shí),,內(nèi)容提要,形式語(yǔ)言 文法和語(yǔ)言 分析樹(shù),2.1 形式語(yǔ)言,符號(hào)和字符串 符號(hào)：抽象實(shí)體，不加以形式定義。就像幾何學(xué)中的“點(diǎn)”?；蛘呓性痈拍?，憑直覺(jué)去體會(huì)。 字母表：有限個(gè)符號(hào)的集合。字母表一般用記。例如,英語(yǔ)的字母表=a,b,,z,A,B,,Z；漢語(yǔ)的字母表由漢字構(gòu)成。,,字符串：字母表中符號(hào)的有窮序列。 字符串的長(zhǎng)度：組成該字符串的符號(hào)的個(gè)數(shù)。字符串的長(zhǎng)度記作||。 例如字符串banana的長(zhǎng)度為6。空字符串記作，由0個(gè)符號(hào)組成，故||=0。,,字符串的前綴：該字符串領(lǐng)頭的若干符號(hào)。 字符串的后綴：該字符串結(jié)尾的若干符號(hào)。 例如，字符串a(chǎn)bc具有前綴，a，ab

2、和abc；其后綴有，c，bc，abc。 若字符串的前綴（或后綴）不是字符串本身，則稱之為真前綴（或真后綴）。,,字符串的子串：去掉字符串的一個(gè)前綴和后綴后得到的字符串。例如，nan是banana的一個(gè)子串。 字符串的子序列：從字符串中刪除0個(gè)或多個(gè)符號(hào)后得到的串（這些被刪除的符號(hào)可以不相鄰）。例如，baaa是banana的子序列。,,字符串的運(yùn)算 字符串的連接：如果x和y是字符串，那么x和y的連接xy是把y接到x后面所形成的字符串。 例如，如果x=dog，y=house，則xy=doghouse。由的定義，顯然有==。,,字符串的方冪：設(shè)x是字符串，把x自身連接n次得到字符串z，即z=xxxx

3、，稱為字符串x的n次方冪，記作z=xn。我們規(guī)定x0=。 例如，設(shè)x=AB，則x0=，x1=AB，x2=ABAB，x3=ABABAB。對(duì)于，n0，有xn=xxn-1=xn-1x。,,字符串集合的連接：兩個(gè)字符串集合A和B的連接AB=xy|xA，yB，即AB是滿足x屬于A，y屬于B的所有字符串xy所組成的集合。 例如，若A=a,b，B=c,d，則AB=ac,ad,bc,bd。另外，我們有A=A=A。 對(duì)任意字符串集合A，An=AAAA，即n個(gè)A相連。A0定義為。,,Kleene閉包：一個(gè)固定的字母表上所有的字符串的集合稱為集合的Kleene閉包，記作*。根據(jù)定義，我們有*=012n。 正閉包：+

4、=123n稱為的正閉包。顯然有 *=0+ +=*=*,,形式語(yǔ)言 語(yǔ)言：給定字母表上的任意一個(gè)字符串集合，即*的子集（*本身也是自己的子集，所以*也是語(yǔ)言）?？占陀煽兆址M成的集合都是語(yǔ)言。,2.2 文法和語(yǔ)言,文法是程序語(yǔ)言的生成系統(tǒng)，而自動(dòng)機(jī)則是程序語(yǔ)言的識(shí)別系統(tǒng)。用文法可以精確地定義一個(gè)語(yǔ)言，并依據(jù)該文法構(gòu)造出識(shí)別這個(gè)語(yǔ)言的自動(dòng)機(jī)。因此，文法對(duì)程序語(yǔ)言和編譯程序的構(gòu)造具有重要意義，如程序語(yǔ)言的詞法可用正規(guī)文法描述，語(yǔ)法可用上下文無(wú)關(guān)文法描述，而語(yǔ)義則要借助于上下文有關(guān)文法描述。,2.2.1 基本概念 定義 文法 文法表示成四元組G=(VT, VN, S, P)，其中： (1)VT為終

5、結(jié)符號(hào)(terminal)集，是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； (2)VN為非終結(jié)符(non-terminal)集，也是一個(gè)非空有限集，其每個(gè)元素稱為非終結(jié)符號(hào)。 要求VTVN=； (3)S為一文法開(kāi)始符號(hào)，也稱作識(shí)別符號(hào)，是一個(gè)特殊的非終結(jié)符號(hào)，即SVN；,(4)P是產(chǎn)生式的非空有限集，其中每個(gè)產(chǎn)生式(或稱規(guī)則)是一序偶(, )，通常寫(xiě)作 讀作“是”或“定義為”。在此，為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結(jié)符和非終結(jié)符組成的符號(hào)串， (VTVN)+且至少有一個(gè)非終結(jié)符，而(VTVN)*。 終結(jié)符和非終結(jié)符的集合用符號(hào)V表示，即V=VTVN。,終結(jié)符代表了語(yǔ)法的最小元素。 非

6、終結(jié)符號(hào)也稱語(yǔ)法變量，它代表語(yǔ)法實(shí)體或語(yǔ)法范疇；非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，因此，一個(gè)非終結(jié)符是一個(gè)類、一個(gè)集合。 例如，在程序語(yǔ)言中，可以把變量、常數(shù)、“+”、“*”等看作是終結(jié)符，而像“算術(shù)表達(dá)式”這個(gè)非終結(jié)符則代表著一定算術(shù)表達(dá)式組成的類，如i*(i+i)、i+i+i等；也即每個(gè)非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號(hào)串組成的集合。,產(chǎn)生式是定義語(yǔ)法實(shí)體的一種書(shū)寫(xiě)規(guī)則。一個(gè)語(yǔ)法實(shí)體的相關(guān)規(guī)則可能不止一個(gè)。 P1，P2，，Pn 可將這些有相同左部的產(chǎn)生式合并為一個(gè)，即縮寫(xiě)成 P12n 其中，每個(gè)i(i=1,2,,n)稱為P的一個(gè)候選式，直豎“”讀為“或”，它與“”一樣是

7、用來(lái)描述文法的元語(yǔ)言符號(hào)(即不屬于的字符)。,例2.1 文法G=(VN, VT, P, S)，其中VN=S， VT=0,1，P=S0S1, S01。 例2.2 文法G=(VN, VT, P, S)，其中VN=,, ，VT=a,,z,0,,9， P= a||z 0||9 S=,,習(xí)慣上只將產(chǎn)生式寫(xiě)出。并有如下約定： 第一條產(chǎn)生式的左部是開(kāi)始符號(hào) 用尖括號(hào)括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮?xiě)字母表示非終結(jié)符，小寫(xiě)字母表示終結(jié)符 G可寫(xiě)成GS，其中S是開(kāi)始符號(hào),,定義 直接推導(dǎo)&直接規(guī)約 設(shè)文法G=(VT,VN,S,P)且、(VTVN)*，如果存在產(chǎn)生式A((VTVN)*)，則稱A可直接推導(dǎo)出

8、，或者說(shuō)是A的直接推導(dǎo)，記做 A 其中“”表示直接推導(dǎo)出，是應(yīng)用產(chǎn)生規(guī)則進(jìn)行推導(dǎo)的記號(hào)。反過(guò)來(lái)，則稱可直接規(guī)約到A，或者說(shuō)A是的直接規(guī)約。,注意“”與“”不同，“”是產(chǎn)生式中的定義記號(hào)。直接推導(dǎo)是對(duì)文法符號(hào)串A中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A的右部來(lái)替換，從而得到。 例如，對(duì)例2.1和例2.2的文法G，可以給出一些直接推導(dǎo)的例子： 0S10011, S0S1, 0S100S11 ,S0S1, S01, a||z 0||9,定義 推導(dǎo)&規(guī)約的傳遞閉包 如果存在一個(gè)自1至n的直接推導(dǎo)序列：123n(n1)，則我們稱1可推導(dǎo)出n，或稱n規(guī)約到1，記為1+n，它表示從1出發(fā)經(jīng)過(guò)一步或若干步可推導(dǎo)出n。

9、 定義 推導(dǎo)&規(guī)約的自反傳遞閉包 如果有1+n或1=n，則記1*n，表示從1出發(fā)，經(jīng)過(guò)0步或若干步可推導(dǎo)出n。,,例如， 對(duì)例2.1的文法，0S100+001100，當(dāng)然也可以是0S100*001100。 對(duì)2.2的文法，+x1，當(dāng)然也可以是*x1。,S0S1, S01, a||z 0||9,定義 句型&句子 設(shè)GS是一文法，S是它的開(kāi)始符號(hào)，如果S*，(VTVN)*，則稱是文法GS的一個(gè)句型；如果VT*，則稱是文法GS的一個(gè)句子。 例如，S，0S1，000111都是例2.1的文法G的句型，其中000111是G的句子。，，a1等都是例2.2的文法G的句型，其中a1是G的句子。,S0S1, S

10、01, a||z 0||9,定義 文法的語(yǔ)言 文法GS產(chǎn)生的句子的全體稱為由文法GS產(chǎn)生的語(yǔ)言，記為L(zhǎng)(G)，即有L(G)=S*且VT*。 例如，例2.1的文法產(chǎn)生的語(yǔ)言的句子具有0n1n的形式。 定義 文法等價(jià) 若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。 例如，文法GA: A0R，A01，RA1。和例2.1的文法等價(jià)。,S0S1, S01,2.1.2 Chomsky譜系 語(yǔ)言學(xué)家Noam Chomsky于1956年首先建立了形式語(yǔ)言的描述，定義了四類文法及相應(yīng)的形式語(yǔ)言，并分別與相應(yīng)的識(shí)別系統(tǒng)相聯(lián)系，它對(duì)程序語(yǔ)言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響。 Chomsk

11、y把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。,,0型文法與0型語(yǔ)言(對(duì)應(yīng)圖靈機(jī)) 如果文法G的每一個(gè)產(chǎn)生式具有下列形式： 其中，V*VNV*，即至少含有一個(gè)非終結(jié)符；V*；則稱文法G為0型文法或短語(yǔ)結(jié)構(gòu)文法，記為PSG(Phrase Structure Grammar)。0型文法相應(yīng)的語(yǔ)言稱為0型語(yǔ)言或稱遞歸可枚舉集，它的識(shí)別系統(tǒng)是圖靈(Turing)機(jī)。,,1型文法與1型語(yǔ)言(對(duì)應(yīng)線性界限自動(dòng)機(jī)) 文法G的產(chǎn)生式 在0型文法的基礎(chǔ)上增加了字符長(zhǎng)度上滿足||||的限制，則稱文法G為1型文法或上下文有關(guān)文法，記為CSG (Context-Sensi

12、tive Grammar)。1型文法相應(yīng)的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。,,1型文法的另一種定義方法是文法G的每一個(gè)產(chǎn)生式具有下列形式： A 其中，AV*，AVN，V+；顯然它滿足前述定義的長(zhǎng)度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。 自然語(yǔ)言的語(yǔ)法應(yīng)屬于上下文有關(guān)文法。,,2型文法與2型語(yǔ)言(對(duì)應(yīng)下推自動(dòng)機(jī)) 文法G的每一個(gè)產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無(wú)關(guān)文法，記為CFG (Context-Free Grammar)。2型文法相應(yīng)的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言，它的識(shí)

13、別系統(tǒng)是下推自動(dòng)機(jī)。 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法是上下文無(wú)關(guān)的。,3型文法與3型語(yǔ)言(對(duì)應(yīng)有限自動(dòng)機(jī)) 文法G的每個(gè)產(chǎn)生式具有下列形式： A或AB 其中，A、BVN， VT*，則文法G稱為右線性文法。若每個(gè)產(chǎn)生式具有下列形式： A或AB 則文法G稱為左線性文法。右線性和左線性文法都稱為3型文法、正規(guī)文法，記為RG (Regular Grammar)。3型文法相應(yīng)的語(yǔ)言為3型語(yǔ)言或正規(guī)語(yǔ)言，它的識(shí)別系統(tǒng)是有限自動(dòng)機(jī)。,,例2.1和例2.2中的文法都是上下文無(wú)關(guān)的。 例2.3 設(shè)G=(VN, VT, P, S)，VN=S, B, E，VT=a, b, e， P=SaSBE, SaBE, EBBE, aBa

14、b, bBbb, bEbe, eEee 文法G是上下文有關(guān)的，L(G)=anbnen|n1,S0S1, S01, a||z 0||9,,S aSBE (SaSBE) aaBEBE (SaBE) aabEBE (aBab ) aabBEE (EBBE ) aabbEE (bBbb) aabbeE (bEbe) aabbee (eEee) S aSBEaaSBEBEaaaBEBEBE,,四類文法的聯(lián)系與區(qū)別 聯(lián)系：從0型文法到3型文法逐漸增加限制。13型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。 區(qū)別：(1)1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則

15、允許形如“A”的產(chǎn)生式存在；(2)0、1型文法的產(chǎn)生式左部存在含有終結(jié)符號(hào)的符號(hào)串或兩個(gè)以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個(gè)的非終結(jié)符號(hào)。,,文法的應(yīng)用 在編譯方法中，通常用3型文法來(lái)描述高級(jí)程序語(yǔ)言的詞法部分，然后用有限自動(dòng)機(jī)FA來(lái)識(shí)別高級(jí)語(yǔ)言的單詞；利用2型文法來(lái)描述高級(jí)語(yǔ)言的語(yǔ)法部分，然后用下推自動(dòng)機(jī)PDA(Push-Down Automata)來(lái)識(shí)別高級(jí)語(yǔ)言的各種語(yǔ)法成分。,,貫穿詞法分析和語(yǔ)法分析始終如一的思想是：語(yǔ)言的描述和語(yǔ)言的識(shí)別是表示一個(gè)語(yǔ)言的兩個(gè)不同的側(cè)面，二者缺一不可。用正規(guī)文法和上下文無(wú)關(guān)文法描述語(yǔ)言時(shí)的識(shí)別方法(即自動(dòng)機(jī))不同。通常，正規(guī)文法適合于

16、描述線性結(jié)構(gòu)，如標(biāo)識(shí)符、關(guān)鍵字和注釋等；而上下文無(wú)關(guān)文法則適合于描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的語(yǔ)句if-else、while等。,2.2 推導(dǎo)與分析(語(yǔ)法)樹(shù),上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)，比如描述算術(shù)表達(dá)式和各種語(yǔ)句等。 例2.6 文法GE： EE+EE*E(E)i 非終結(jié)符E表示一類算術(shù)表達(dá)式。i表示程序設(shè)計(jì)語(yǔ)言中的變量，該文法定義了由變量、+、*、(和)組成的算術(shù)表達(dá)式的語(yǔ)法結(jié)構(gòu)。,,分析樹(shù) 對(duì)程序語(yǔ)言來(lái)說(shuō)，有兩個(gè)問(wèn)題需要解決：其一是判別程序在語(yǔ)法上是否正確；其二是句子的識(shí)別或分析。在編譯方法中，為了便于識(shí)別或分析句子而引入了分析樹(shù)這一重要

17、的輔助工具。分析樹(shù)以圖示化的形式把句子分解成各個(gè)組成部分來(lái)描述或分析句子的語(yǔ)法結(jié)構(gòu)，這種圖示化的表示與所定義的文法規(guī)則完全一致，但更為直觀和完整。,對(duì)文法G=(VT, VN, S, P) ，滿足下列條件的樹(shù)稱為GS的句型的分析樹(shù)： (1) 結(jié)點(diǎn)用GS的一個(gè)終結(jié)符或非終結(jié)符標(biāo)記； (2) 根結(jié)點(diǎn)用文法開(kāi)始符S標(biāo)記； (3) 內(nèi)部結(jié)點(diǎn)(指非葉結(jié)點(diǎn))一定是非終結(jié)符，如果某內(nèi)部結(jié)點(diǎn)A有n個(gè)分支，它的所有子結(jié)點(diǎn)從左至右依次標(biāo)記為x1、x2、、xn，則Ax1x2xn一定是文法GS的一條產(chǎn)生式； (4) 如果某結(jié)點(diǎn)標(biāo)記為，則它必為葉結(jié)點(diǎn)且是其父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。,,例2.7 例2.6的文法的一棵分析樹(shù) 句

18、子i+i*i的分析樹(shù),EE+EE*E(E)i,,在一棵分析樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒(méi)有后代的樹(shù)葉結(jié)點(diǎn)自左至右排列起來(lái)就是一個(gè)句型。 分析樹(shù)表示了在推導(dǎo)過(guò)程中施用了哪個(gè)產(chǎn)生式和施用在哪個(gè)非終結(jié)符上，它并沒(méi)有表明施用產(chǎn)生式的順序。 例如，上面的分析樹(shù)表示的句子i+i*i可以有不同的推導(dǎo)過(guò)程： EE+Ei+Ei+E*Ei+i*Ei+i*i EE+EE+E*EE+E*iE+i*ii+i*i,,最左（最右）推導(dǎo) 推導(dǎo)序列中的每一步推導(dǎo)都是對(duì)句型中的最左（最右）非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換，這樣的推導(dǎo)稱為最左（最右）推導(dǎo)。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。規(guī)范推導(dǎo)的

19、逆過(guò)程便是規(guī)范規(guī)約。 例如，前面的第一個(gè)推導(dǎo)就是最左推導(dǎo)，而第二個(gè)推導(dǎo)就是最右推導(dǎo)。,,因此，一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。如果我們堅(jiān)持使用最左(或最右)推導(dǎo)，那么一棵語(yǔ)法樹(shù)就完全等價(jià)于一個(gè)最左(或最右)推導(dǎo)，這種等價(jià)性也包括語(yǔ)法樹(shù)的每一步生長(zhǎng)和推導(dǎo)的每一步展開(kāi)的這種完全一致性。,,介詞短語(yǔ)附著歧義 He saw a boy with a telescope. 他通過(guò)望遠(yuǎn)鏡看到一個(gè)男孩。 他看到一個(gè)帶望遠(yuǎn)鏡的男孩。,,文法的二義性 一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)呢？非也。 例如，例2.6的文法G的句子i+

20、i*i就有兩個(gè)不同的最左推導(dǎo)： EE+Ei+Ei+E*Ei+i*Ei+i*i EE*EE+E*Ei+E*Ei+i*Ei+i*i 對(duì)應(yīng)有兩棵不同的語(yǔ)法樹(shù)：,,,,文法GS的一個(gè)句子如果能找到兩個(gè)不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)句子是二義性的。一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義文法，否則是無(wú)二義文法。,再如，條件語(yǔ)句的文法GS為： GS: Sif B S Sif B S else S SA /*A指其它語(yǔ)句*/ 其中，VN = B,S,A，VT = if , else。 句型if B if B S else S所對(duì)應(yīng)的兩棵不同語(yǔ)

21、法樹(shù)： 因此，文法GS是二義性文法。,,注意：一個(gè)文法是二義性的，并不說(shuō)明該文法所描述的語(yǔ)言也是二義性的。也即，對(duì)于一個(gè)二義性文法GS，如果能找到一個(gè)非二義性文法GS，使得L(G)=L(G)，則該二義性文法的二義性是可以消除的。如果找不到這樣的GS，則二義性文法描述的語(yǔ)言為先天二義性的。,文法二義性消除的方法 不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。 如對(duì)例子2.6的文法，不改變已有的四條規(guī)則，僅加進(jìn)運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則，即*優(yōu)先于+，且*、+都服從左結(jié)合。 構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法，即把排除二義性的規(guī)則合并到原有文法中，改寫(xiě)原有的文法。 例2.8 可以將例2.6的文

22、法改寫(xiě)為無(wú)二義性的文法GE如下：EE+TT TT*FF F(E)i,EE+EE*E(E)i,,注： 1）二義性會(huì)給語(yǔ)法分析帶來(lái)不確定性。 2）文法的二義性是不可判定的，即不存在算法，能夠在有限步數(shù)內(nèi)確切判定一個(gè)文法是否為二義文法。 3）若要證明是二義性，只要舉出一例，即給出文法的某個(gè)句子有兩個(gè)不同的最左（最右）推導(dǎo)，或兩棵不同的語(yǔ)法樹(shù)。 4）若能控制文法的二義性，即加入人為的附加條件，則二義文法的存在并非壞事。,,自頂向下的語(yǔ)法分析 例：文法G：ScAd Aab Aa識(shí)別輸入串 w = cabd是否該文法的句子 推導(dǎo)過(guò)程：S cAd cabd,S,,自底向上的語(yǔ)法分析

23、規(guī)約過(guò)程： S cAd cabd,,句法分析的有關(guān)問(wèn)題 1）如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是V，且有n條規(guī)則：VA1|A2||An，那么如何確定用哪個(gè)右部去替代V？ 2）如何識(shí)別可歸約串？ 在自底向上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”素短語(yǔ)和句柄。,,短語(yǔ) 設(shè)是文法GS的一個(gè)句型，如果有： S*A且A+ 則稱是句型關(guān)于非終結(jié)符A的一個(gè)短語(yǔ)，或稱是的一個(gè)短語(yǔ)。特別是有A產(chǎn)生式時(shí)，稱為句型的一個(gè)直接短語(yǔ)或簡(jiǎn)單短語(yǔ)。 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。 注意，一個(gè)句型的直接短語(yǔ)可能不

24、只一個(gè)，但最左直接短語(yǔ)則是唯一的。 含有終結(jié)符的短語(yǔ)，如果它不存在也具有同樣性質(zhì)的真子串，則該短語(yǔ)為素短語(yǔ)。,,子樹(shù)和短語(yǔ) 只含有單層分枝的子樹(shù)稱為簡(jiǎn)單子樹(shù)。 (1) 短語(yǔ)：子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于子樹(shù)根的短語(yǔ)； (2) 直接短語(yǔ)：簡(jiǎn)單子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹(shù)根的直接短語(yǔ)； (3) 句柄：最左簡(jiǎn)單子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串為句柄； (4) 素短語(yǔ)：子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串含終結(jié)符，且在該子樹(shù)中不再有包含有終結(jié)符的更小子樹(shù)。,,例2.9 例2.8的文法的句子i1+i2*i3 短語(yǔ)：i1+i2*i3，i1，i2*i3，i2，i3 直接短語(yǔ)：i1，i2，i3 句柄：i1 素短語(yǔ)：i1，i2，i3,,,,,,,,,EE+TT TT*FF F(E)i,