編譯原理形式語言基礎(chǔ)

1、（優(yōu)選）編譯原理第章形式語言基礎(chǔ)第一頁，共一百五十二頁。1一、語言的定義 任何一種語言都是在某個特定字母表上定義的、按照一定的規(guī)則構(gòu)成的字符串的集合。第二頁，共一百五十二頁。2二、形式語言提出 形式語言是研究符號的語言，它僅考慮符號間的關(guān)系，不考慮含義，即用數(shù)學(xué)方法（主要是代數(shù)方法）對語言進行形式化描述。 1956年N.Chomsky(喬姆斯基）在研究自然語言過程中提出一種文法數(shù)學(xué)模型，為形式語言理論打下了基礎(chǔ)，成為計算機科學(xué)理論一個重要分支，即形式語言與自動機。第三頁，共一百五十二頁。3三、語言描述方法枚舉法文法生成法：就是用有限個規(guī)則來產(chǎn)生出語言中無限個句子，這種規(guī)則集合稱文法。自動機識別

2、法：用自動機對語言中的句子進行識別第四頁，共一百五十二頁。4四、與語言有關(guān)的幾個概念元語言：可用來描述其它語言的一種語言語法：是在字母表上構(gòu)造句子的一組規(guī)則語義：是按照語法規(guī)則所構(gòu)成結(jié)構(gòu)的含義語用：是表示語言符號與使用者關(guān)系第五頁，共一百五十二頁。52.2 符號和符號串 一、字母表 二、符號串 三、符號串集合第六頁，共一百五十二頁。6一、字母表 有限個元素的非空集合稱字母表，也稱符號集。它是組成一個語言最基本的成分。字母表中元素稱符號。 習(xí)慣上用V、或其它大寫字母表示。例如V=a,b,c，V=, | V|表示字母表中符號的個數(shù)。 對于不同程序設(shè)計語言有不同字母表。例如，機器語言字母表=0,1，

3、PASCAL語言的字母表由字母、數(shù)字以及一些特殊符號，如+，-，*，/，(，)，=，等組成。 注意：在一個語言中不能出現(xiàn)字母表以外的符號。第七頁，共一百五十二頁。7二、符號串 1、定義 符號串是字母表中的符號所組成的任何有窮序列(有時也稱為符號行或字) 例如： 設(shè)V=a,b,c,則符號串有 a, b, c, aa, ab, ac, ba, abc 又如： 設(shè)V=0,1,則符號串有 0，1，00，01，10，11，000 由上例可以看出，符號串與符號組成順序有關(guān)，如符號串a(chǎn)b不同于ba， 符號串01不同于10，今后我們常用t,u,v,x,y,z等小寫字母表示符號串。第八頁，共一百五十二頁。82、

4、空符號串 不包含任何符號的符號串稱為空符號串，記為。 3、符號串長度 符號串中所含符號個數(shù)稱為該符號串的長度，設(shè)符號串為x，則用|x|來表示x的長度。例如：x=abc，則|x|=3,顯然,|=0。第九頁，共一百五十二頁。94、關(guān)于符號串的幾種運算 （1）符號串的聯(lián)結(jié) 設(shè)有符號串x和y，則它們的聯(lián)結(jié)xy是將符號串y直接拼接在符號串x之后，即 x=x1x2x3xm, y=y1y2y3yn 則 x y = x1x2x3xmy1y2y3yn 顯然x = x， x= x 第十頁，共一百五十二頁。10（2）符號串的方冪 若x是符號串 則x0=， x1=x，x2=xx，x3=xxx，xn=xxx(n個） 如

5、x=abc 則x0= , x1 = abc, x2= abcabc X3= abcabcabc第十一頁，共一百五十二頁。11三、符號串集合 舉例：字母表V=a,b，問用V中的符號，可以組成哪些符號串？ 解：,a,b,aa,ab,ba,bb,aaa,bbb,1、定義：若集合A中的一切元素都是字母表V上的符號串，則稱A為字母表V上的符號串集合第十二頁，共一百五十二頁。12V*定義：字母表V上各種長度符號串構(gòu)成串集合，記為V*，不包括空行的集合記為V+ 即 V*=x|x是V上符號串且包括空符號串 V+=x|x是V上符號串且不包括空符號串 V+=V*- 如：V=a,b，則 V*=,a,b,aa,ab,

6、ba,bb,aaa,bbb, V+=a,b,aa,ab,ba,bb,aaa,bbb,第十三頁，共一百五十二頁。132、關(guān)于串集合的運算（1）串集合乘積設(shè)A和B為兩個符號串集合，并包含于V*，則A和B的乘積定義為：AB= xy | xA 且 yB 由此定義，乘積AB是滿足xA且yB的所有符號串xy所組成的集合。如：V=0，1 V* =,0,1,00,01,10,11,000,001，010，011，100,101如果 A=0，101 B=10，11，110則 AB=010，011，0110，10110，10111，101110符號表示空集 第十四頁，共一百五十二頁。14（2）符號串集合的方冪設(shè)符

7、號串集合A 則A的方冪運算定義為：A0=, A1= A, A2= AA, A3= AAA, An = AAAA (n個）如：設(shè)A=a,b，則A0=,A1=a,bA2=a,ba,b=aa,ab,ba,bbA3=aaa,aab,aba,abb,baa,bab,bba,bbb第十五頁，共一百五十二頁。15(3)符號串集合的閉包和正閉包 設(shè)A為符號串集合，則A的正閉包定義為 A+=A1A2An 符號串集合A的閉包定義為 A*=A0A+=A+ 如 A = a,b 則A+=a,baa,ab,ba,bb=a,b,aa,ab,ba,bb,aaa,bbb, A*=, a, b, aa, ab, ba, bb,

8、aaa, bbb, 我們可以證明： A+= AA* = A*A AA* =A（A0A1A2 An ） = A1A2 An = A+第十六頁，共一百五十二頁。16作業(yè)： P.38：習(xí)題2、3第十七頁，共一百五十二頁。172.3 文法與語言 一、巴科斯范式BNF(Backus Normal Form) 二、語法樹 三、產(chǎn)生式（規(guī)則） 四、文法 五、推導(dǎo)和歸約 六、句型和句子 七、語言 八、遞歸文法 九、短語和簡單短語 十、最左推導(dǎo)和最右推導(dǎo) 十一、文法二義性 第十八頁，共一百五十二頁。18一、巴科斯范式BNF例子：The man has a dog.(這人有一條狗）我們以“=”符號(或“”符號)表

9、示”定義為”，以“|”符號表示“或”，以“”符號表示語法實體(語法單位)，這些符號是元語言符號，第十九頁，共一百五十二頁。19=the | a=man | book | dog= =has= 我們把這種描述語法規(guī)則方法稱巴科斯范式，也稱為巴科斯-瑙爾范式(Backus Normal Form)，簡稱BNF。那么上面敘述的語法規(guī)則可寫為：第二十頁，共一百五十二頁。20例如, 在高級語言中大家所熟知的這種語法成分,它用巴科斯范式描述為:=|=A|B|C|D|Z|a|b|z=0|1|2|9 這樣便刻畫出了是以字母開始的一串字母和數(shù)字任意組合這種特點。第二十一頁，共一百五十二頁。21如果定義的巴科斯范

10、式改為：句子=主語=We | He | I謂語=ran | ate | sat則下面9個句子都是正確的：We ran He ran I ran We ate He ate I ateWe sat He sat I sat 可見，如果一個語言有無窮多個句子，那么用上述規(guī)則來描述更有實際意義.它用一組規(guī)則來代替枚舉法，用有窮來描述無限。第二十二頁，共一百五十二頁。22二、語法樹 除了上面可以根據(jù)語言語法規(guī)則來推導(dǎo)出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結(jié)構(gòu)關(guān)系，稱語法樹。 第二十三頁，共一百五十二頁。23（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）第二

11、十四頁，共一百五十二頁。24（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹） =第二十五頁，共一百五十二頁。25（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹） =第二十六頁，共一百五十二頁。26（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）the =the | a第二十七頁，共一百五十二頁。27（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manthe =the =man 第二十八頁，共一百五十二頁。28（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manthe =the =man =第

12、二十九頁，共一百五十二頁。29（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manhasthe =the =has第三十頁，共一百五十二頁。30（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manhasthe =the =第三十一頁，共一百五十二頁。31（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manhasathe =the =第三十二頁，共一百五十二頁。32（句子the man has a book的推導(dǎo)過程及對應(yīng)的語法樹）manhasabookthe =the =第三十三頁，共一百五十二頁。33（句子the man ha

13、s a book的推導(dǎo)過程及對應(yīng)的語法樹）manhasabookthe第三十四頁，共一百五十二頁。34其中：稱為語法樹根 帶和不帶的都稱為語法樹的結(jié)點 一個結(jié)點以及向下射出部分稱為子樹 沒有向下射出部分的結(jié)點稱為末端結(jié)點第三十五頁，共一百五十二頁。35三、產(chǎn)生式（規(guī)則） 1. 定義 產(chǎn)生式(規(guī)則)就是一個符號與另一個符號串的有序偶(U,x),通常記為 Ux或U=x 其中：U是符號,x是有限非空符號串。 U稱為規(guī)則的左部, x稱為規(guī)則的右部 如果 Ux1， Ux2， Ux3， Uxn 可以寫成Ux1|x2|xn ,并稱xi是U的一個候選式。第三十六頁，共一百五十二頁。362. 字匯表(符號表)

14、（1）定義 用于規(guī)則左部和右部中所有符號形成集合為字匯表，記為V。 第三十七頁，共一百五十二頁。37（2）分類 1）非終結(jié)符號 出現(xiàn)在規(guī)則左部,且能派生出符號或符號串的那些符號稱為非終結(jié)符,也稱語法實體或語法單位,它們的全體構(gòu)成一個非終結(jié)符的集合,記為VN 2）終結(jié)符 規(guī)則中不屬于VN的那些符號,稱為終結(jié)符,它們的全體組成終結(jié)符的集合,記為VT 。終結(jié)符一般出現(xiàn)在規(guī)則的右部。 顯然,V= VN VT, VN VT =第三十八頁，共一百五十二頁。38如：在PASCAL中，對標識符的定義規(guī)則為：=|=a|b|z|A|B|Z=0|1|9 由此得： VN =, VT=a,b,z,A,B,Z,0,1,9

15、第三十九頁，共一百五十二頁。39例如：有產(chǎn)生式: S=0S1 S=01 則 VN =S VT=0,1 V=S,0,1第四十頁，共一百五十二頁。40四、文法為研究方便，下面給出文法的形式定義定義：文法是規(guī)則的有窮集合,形式定義為四元組形式為 G=(VN,VT,P,Z)其中：VN是非終結(jié)符集合,VT是終結(jié)符集合, P代表產(chǎn)生式集, ZVN是文法G開始符號,也稱識別符號,它至少要在一 條產(chǎn)生式左部出現(xiàn)。 文法G通常記為GZ 。第四十一頁，共一百五十二頁。41對于前面英語句子的例子中用7條文法規(guī)則來描述英語句子,其文法可表示為 G=(VN,VT,P,Z)其中:VN=， ，VT=the, a, man,

16、 book, dog P是前述7條規(guī)則Z=第四十二頁，共一百五十二頁。42又例如：標識符文法可定義如下: GZ=(VN,VT,P,Z) VN=, VT=a,b,z,A,B,Z,0,1,9 Z= P由下列規(guī)則組成: =| =a|b|z|A|B|Z =0|1|9第四十三頁，共一百五十二頁。43五、推導(dǎo)和歸約 定義1 設(shè)G為一個文法，U=u是G中一個規(guī)則，x和y是V*上符號串，使得 v=xUy 與 w=xuy 則稱符號串v直接推導(dǎo)出符號串w，或稱w直接歸約到v，并把w叫做v直接派生式，記作 v w 若x=y=，則v=xUy =U， w=xuy=u 可見v w即U u 說明一個規(guī)則就是一個直接推導(dǎo) 例

17、如直接推導(dǎo)到，而 直接歸約到。 第四十四頁，共一百五十二頁。44例如: G =(VN,VT,P,S) VN =S, VT =0,1 P: S =0S1 S =01 令 v=xSy ,w=x01y, 因 S =01 (U=u) 即 v w xSy x01y 若 x=y= 則 S 01(一個規(guī)則就是一個直接推導(dǎo)) 同樣 S =0S1 v=00S11， w=000S111 U u 即 v w 00S11 000S111第四十五頁，共一百五十二頁。45又如：標識符文法定義如下: GZ=(VN,VT,P,Z) VN=, VT=a,b,z,A,B,Z,0,1,9 P由下列規(guī)則組成: =| =a|b|z|A

18、|B|Z =0|1|9 Z=則有： a 第四十六頁，共一百五十二頁。46定義2 設(shè)u0,u1,u2,un均為V*上符號串,若w是v經(jīng)過一系列直接推導(dǎo)得到的,即 v= u0 u1 u2 un-1 un =w (n0) 則稱v推導(dǎo)到w,或稱w歸約到v,記作 v +w 稱這個直接推導(dǎo)序列為長度為n的推導(dǎo)。如果v +w或者v=w(表示0步推導(dǎo)),則記作 v *w 稱v廣義推導(dǎo)到w或稱w廣義歸約到v。 顯然,直接推導(dǎo) 的長度為1,推導(dǎo) +的長度1,而廣義推導(dǎo) *的長度0 例如在前面的例子中,因 S =0S1 S =01 0S1 00S11 000S111 00001111 所以 0S1 +0000111

19、1 (n=3)第四十七頁，共一百五十二頁。47例 設(shè)有文法G:(1)= (2)=(3)= (4)=0 (5)=1(6)=2 (7)=3 (8)=4 (9)=5 (10)=6 (11)=7 (12)=8 (13)=9整數(shù)23的推導(dǎo)過程: 2 23因此,+23,其推導(dǎo)長度為5。顯而易見,在推導(dǎo)時,任意地選取規(guī)則(4)到(13),就可以推導(dǎo)得到任意整數(shù)。第四十八頁，共一百五十二頁。48六、句型和句子定義：設(shè)GZ是一文法,若符號串x是由識別符Z推導(dǎo)而得,即Z *x xV* 則稱符號串x為該文法G的一個句型。如果一個句型x僅由終結(jié)符組成,即Z*x xVT* 則稱句型x為該文法一個句子。 例如： 在書中的

20、例2.16中, 2,23等都是文法G的句型,其中僅23是句子。 可見：句子一定是句型，而句型未必是句子。一個正確的源程序是句子。第四十九頁，共一百五十二頁。49七、語言定義：設(shè)GZ為一文法,由該文法所產(chǎn)生的一切句子的集合稱為由該文法所定義的語言,記為L(G)(或記為L(G),即 L(G)=x|Z *x且xVT*有時我們稱這樣定義的語言為形式語言，以區(qū)別于自然語言。上述公式包含兩層意思：語言是句子集合，是VT*一個子集合，即VT中行集合子集。句子必須由該語言文法識別符推導(dǎo)出。第五十頁，共一百五十二頁。50例如：GS=(VN,VT,P,S) VN=S VT=0,1 P:S=01,S=0S1 S:識

21、別符很容易推出：L（G）=0n1n|n1第五十一頁，共一百五十二頁。51又如：寫一個文法，使其語言為偶整數(shù)集合。首先分析以下偶整數(shù) （1）偶整數(shù)最后一個數(shù)字應(yīng)該是偶數(shù)字0，2，4，6，8 （2）偶整數(shù)前面符號可以是+，-或不帶符號由此得其文法應(yīng)由下列規(guī)則組成：= | |=0|2|4|6|8=1|3|5|7|9|=|=+|-所以文法可表示為：G=(VN,VT,P,)其中：VN =， ， ， VT =0，1，2，3，4，5，6，7，8，9，+，-第五十二頁，共一百五十二頁。52對于通常的程序設(shè)計語言其文法為: G程序=(VN,VT,P,)其中 VN=, VT=0,1,9,a,z,-,(,), P=

22、, =, =, L(G)=w| *w且wVT* 由此可知,每一個w就是一個源程序，所謂PASCAL語言也就是所有PASCAL程序的集合。第五十三頁，共一百五十二頁。53作業(yè)：P.38 習(xí)題6、7第五十四頁，共一百五十二頁。54八、遞歸文法 構(gòu)成一個語言的句子集合可以是有窮的，也可以是無窮的，例如文法G所描述的語言L(G)是有窮的。但文法G所描述的語言L(G)是無窮的，它包含無窮多個句子。 第五十五頁，共一百五十二頁。55例如：文法G()包含的下列規(guī)則如下：句子=主語=We | He | I謂語=ran | ate | sat所描述的語言為：We ran He ran I ran We ate

23、He ate I ateWe sat He sat I sat第五十六頁，共一百五十二頁。56例 如文法G的規(guī)則如下：(1)= (2)=(3)= (4)=0 (5)=1(6)=2 (7)=3 (8)=4 (9)=5 (10)=6 (11)=7 (12)=8 (13)=9所描述的語言包括無窮多個句子。第五十七頁，共一百五十二頁。57不難發(fā)現(xiàn)，兩個文法其根本差別在于文法G有形如=的規(guī)則。 在這個規(guī)則中左部和右部皆出現(xiàn)非終結(jié)符。這種借助于自己來定義自己的規(guī)則，即在規(guī)則左部和右部具有相同的非終結(jié)符規(guī)則稱為遞歸規(guī)則。 第五十八頁，共一百五十二頁。58八、遞歸文法 1. 定義 對于一個文法,若有一個規(guī)則U

24、=U,則稱直接遞歸,若有規(guī)則U=U,則稱直接左遞歸,若有規(guī)則U=U,則稱直接右遞歸。若有推導(dǎo)式U+U,則稱間接遞歸,若有推導(dǎo)式U+U,則稱間接左遞歸,若有推導(dǎo)式U+U,則稱間接右遞歸。非終結(jié)符U稱遞歸非終結(jié)符。如果一個文法中至少含有一個遞歸非終結(jié)符,則將此文法稱為遞歸文法。第五十九頁，共一百五十二頁。59例如：規(guī)則 S =0S1 是直接遞歸 規(guī)則 A=Aa 是直接左遞歸 規(guī)則 B=aBB 是直接右遞歸 第六十頁，共一百五十二頁。60例如：設(shè)有文法G的規(guī)則P為 S=Qc|c Q=Rb|b R=Sa|a在這些條規(guī)則中,無直接遞歸規(guī)則,但有如下推導(dǎo): Q Rb Sab Qcab所以 Q +Qcab因

25、此是間接左遞歸。文法G為遞歸文法顯然，直接遞歸是間接遞歸一種特殊情況。 第六十一頁，共一百五十二頁。61八、遞歸文法 2.說明 如果一個語言是無窮的，則描述該語言的文法必定是遞歸的。一般說，程序設(shè)計語言是無窮的，因此描述它們的文法必定是遞歸的。應(yīng)當指出，從語法定義的角度來看，遞歸定義使文法的形式比較簡練，給無限的語言有限的表示提供了一種可用的方法。然而在后面我們將會看到，文法的左遞歸性將會給某些語法分析方法的實現(xiàn)帶來很大的麻煩。 第六十二頁，共一百五十二頁。62九、短語和簡單短語 1.短語和簡單短語 2.句柄(柄短語) 3.再談?wù)Z法樹第六十三頁，共一百五十二頁。631. 短語和簡單短語定義：設(shè)

26、GZ是一文法，w=xuy是其中一句型，若有 Z * xUy,UVN 且 U + u,uV+ 則稱u是一個相對于非終結(jié)符U、句型w的短語。 若 Z * xUy 且U u 則稱u是一個相對于非終結(jié)符U、句型w的簡單短語。 第六十四頁，共一百五十二頁。64例 設(shè)有文法GS=(S,A,B,a,b,P,S),其中P為 S=AB A=Aa|bB B=a|Sb找出句型baSb的全部短語，簡單短語.第六十五頁，共一百五十二頁。65根據(jù)句型推導(dǎo)過程有 S AB bBB baB baSb由上可見，下式成立： S *baB 且 B Sb所以子串Sb是相對于非終結(jié)符B，句型baSb的簡單短語。同樣有 S AB ASb

27、 bBSb baSb即 S * bBSb 且 B a子串a(chǎn)是相對于B，句型baSb的簡單短語。還有 S * ASb 且 A + ba即子串ba是相對于非終結(jié)符A，句型baSb的短語。對于句型baSb，再沒有其它能產(chǎn)生新的短語推導(dǎo)了，所以句型baSb有短語ba簡單短語a和Sb第六十六頁，共一百五十二頁。662、句柄(柄短語) 定義 一個句型最左邊的簡單短語稱為該句型 的句柄(或柄短語)，而且句柄最左邊的符號 稱句柄的頭，句柄最右邊的符號稱句柄的尾。 如上例句型baSb簡單短語為a和Sb ，由于a是 最左簡單短語，所以a又是句柄。 第六十七頁，共一百五十二頁。67例如：設(shè)文法GS S=A A=B|

28、A+B B=C|B*C C=|(A)現(xiàn)在我們看w=C+B*C句型 SAA+BB+BC+BC+B*C S* C+B BB*C B*C是相對于B和句型C+B*C的簡單短語同樣 SAA+BB+BB+B*CC+B*C S* B+B*C BC C是相對于B，句型C+B*C的簡單短語。由于C在左邊，所以C是句柄，柄頭和柄尾都是C第六十八頁，共一百五十二頁。683. 再談?wù)Z法樹 前面我們曾利用語法樹直觀地描述句子語法結(jié)構(gòu)關(guān)系，現(xiàn)在我們?nèi)匀唤柚谡Z法樹進行句型和句子的推導(dǎo)，同時，利用它尋找短語和簡單短語也是十分直觀和方便的。（1）語法樹形式定義 設(shè)有文法G=（VN，VT，P，Z），滿足下列條件的樹即為一個語法

29、樹 a. 樹中每一個結(jié)點都有標記，且該標記是VNVT中某一符號 b. 樹根標記是識別符號 c. 若有一個結(jié)點至少有一個后繼結(jié)點，則該結(jié)點標記必為非終結(jié)符 d. 若一個標記為U的結(jié)點，它有標記依次為X1，X2, X3，Xn的直接后繼結(jié)點，則U=X1X2Xn必定是G的一條規(guī)則。第六十九頁，共一百五十二頁。69SABbBSba我們以書中的例2.22的文法GS為例，句型baSb的推導(dǎo),設(shè)有文法GS=(S,A,B,a,b,P,S),其中P為 S=AB A=Aa|bB B=a|SbS AB bBB baB baSb畫出語法樹如下圖所示 第七十頁，共一百五十二頁。70語法樹中的幾個術(shù)語： 結(jié)點：每個符號(終

30、結(jié)符或非終結(jié)符)對應(yīng)于一個結(jié)點，以符號名為結(jié)點名稱； 邊：兩個結(jié)點間的連線稱為邊； 根結(jié)點：由文法識別符號標記，如S； 分支：從某結(jié)點向下射出的邊連同邊上的結(jié)點稱為分支，分支的深度為1。分支的名字是射出該分支結(jié)點的名字，分支的各個結(jié)點稱為分支結(jié)點； 子樹：語法樹的某結(jié)點連同從它向下射出的部分稱為該語法樹的子樹，該結(jié)點稱為子樹根結(jié)點； 末端結(jié)點/葉結(jié)點。第七十一頁，共一百五十二頁。71（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB, 規(guī)則S=AB)。SAB第七十二頁，共一百五十二頁。72（2）語法樹構(gòu)造過程句型baSb的語法

31、樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。SAB第七十三頁，共一百五十二頁。73（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。SABbB第七十四頁，共一百五十二頁。74（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支

32、,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB), (規(guī)則B=a)。SABbB第七十五頁，共一百五十二頁。75（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB), (規(guī)則B

33、=a)。SABbBa第七十六頁，共一百五十二頁。76（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB), (規(guī)則B=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb), (規(guī)則B=Sb)。SABbBa第七十七頁，共一百五十二頁。77（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S

34、開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB), (規(guī)則A=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB), (規(guī)則B=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb), (規(guī)則B=Sb)。SABbBSba第七十八頁，共一百五十二頁。78（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB), (規(guī)則S=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直

35、接推導(dǎo)(ABbBB), (規(guī)則A=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB), (規(guī)則B=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb), (規(guī)則B=Sb)。SABbBSba這時末端結(jié)點自左至右排列起來就是句型baSb。這棵語法樹形象地表示了句型baSb上述推導(dǎo)過程。第七十九頁，共一百五十二頁。79結(jié)論：對于每一個語法樹（或者子樹）至少對應(yīng)一個推導(dǎo)（可能是直接推導(dǎo)?？赡苁莕步推導(dǎo)）對于每個推導(dǎo)必存在有一個語法樹，畫語法樹過程中，每個分支對應(yīng)于一個直接推導(dǎo) 。不同推導(dǎo)可能有相同的語法樹。 如： S AB bBB b

36、aB baSb S AB ASb bBSb baSb 同一句型的兩個不同的推導(dǎo)對應(yīng)的語法樹確是相同的。樹的末端結(jié)點標記從左到右連接起來就是要推導(dǎo)的句型或句子第八十頁，共一百五十二頁。80作業(yè)P.38：習(xí)題8；P.39：習(xí)題11(1)、(2)第八十一頁，共一百五十二頁。81（3）語法樹的作用 1）利用語法樹可以構(gòu)造文法的句型；（前面我們已經(jīng)講了句型baSb的語法樹構(gòu)造過程） 2）根據(jù)語法樹可以確定短語、簡單短語和句柄；樹末端結(jié)點的符號串是相對于子樹根的短語，分支結(jié)點的符號串是相對于分支名字的簡單短語，最左簡單子樹(只有父子兩代)的末端結(jié)點的符號串是句柄。從右圖語法樹可直觀看出：ba是句型baSb

37、，相對于A的短語，Sb是句型baSb相對于B的簡單短語，a是句型baSb相對于B簡單短語，也是句柄。 3）當給定文法G后，我們可借助于推導(dǎo)語法樹的逆過程把句型推導(dǎo)構(gòu)造出來 （見下頁舉例）SABbBSba第八十二頁，共一百五十二頁。82對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSbSABbBSba第八十三頁，共一百五十二頁。83對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為

38、bBSb baSbSABbBSb第八十四頁，共一百五十二頁。84對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSbSABSbbB第八十五頁，共一百五十二頁。85對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSb此時該語

39、法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSbSABSb第八十六頁，共一百五十二頁。86對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbba

40、SbSABSb第八十七頁，共一百五十二頁。87對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSbSAB第八十八頁，共一百五十二頁。88對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，

41、則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為 bBSb baSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSb最后剪去分支AB(將AB歸約為S)，得到樹根S，建立了句型baSb推導(dǎo)為SABASbbBSbbaSbSAB第八十九頁，共一百五十二頁。89對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)

42、造了一個直接推導(dǎo)為 bBSb baSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為 ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSb最后剪去分支AB(將AB歸約為S)，得到樹根S，建立了句型baSb推導(dǎo)為SABASbbBSbbaSbS第九十頁，共一百五十二頁。90結(jié)論： 從語法樹構(gòu)造推導(dǎo)也就是不斷地重復(fù)構(gòu)造最后直接推導(dǎo)和剪去相應(yīng)分支直到無分支可剪過程。對于每個語法樹至少存在一個推導(dǎo)。上例我們選用了最左歸約，即每次剪去最左末端分支，實際

43、上每次歸約是句柄。如果改變剪去相應(yīng)分支順序便將得到不同推導(dǎo)。第九十一頁，共一百五十二頁。91十、最左推導(dǎo)和最右推導(dǎo) 對于一給定的文法來說，從其開始符號到某一句型，或從某一句型到另一句型間的推導(dǎo)序列可能不唯一。為了使句型或句子能按照一確定的推導(dǎo)序列來產(chǎn)生，通常我們僅考慮最左推導(dǎo)或最右推導(dǎo)。第九十二頁，共一百五十二頁。92定義1：在任何一步推導(dǎo)vw中，都是對符號串v的最左(右)的非終結(jié)符進行替換，則稱最左(右)推導(dǎo)。 例如：GS S=AB A=Aa|Bb B=a|S SABbBBbaB - 最左推導(dǎo)SABASbAABbAAabAbBab -最右推導(dǎo)SABASbbBSbbaSb - 非左非右推導(dǎo)第九

44、十三頁，共一百五十二頁。93定義2：最右推導(dǎo)叫規(guī)范推導(dǎo)，即在規(guī)范推導(dǎo)過程中，每步直接推導(dǎo)xUyxuy中，符號串y只含有終結(jié)符。如果推導(dǎo)v+w中每一步直接推導(dǎo)是規(guī)范的，則稱推導(dǎo)v+w為規(guī)范推導(dǎo)。第九十四頁，共一百五十二頁。94相關(guān)概念：規(guī)范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。規(guī)范歸約：我們把最左推導(dǎo)的逆過程稱最右歸約 最右推導(dǎo)的逆過程稱最左歸約 最左歸約也稱為規(guī)范歸約 第九十五頁，共一百五十二頁。95應(yīng)當指出，對于文法中的每一句子都必定有最左和最右推導(dǎo)，但對于一句型來說則不盡然。例如，對于文法GE E=E+T|T T=T*F|F F=(E)|i中句型T*i+T，僅有唯一的推導(dǎo)E E+TT+T

45、T*F+TT*i+T顯然，推導(dǎo)E+ T*i+T既非最左推導(dǎo)亦非最右推導(dǎo)。 第九十六頁，共一百五十二頁。96十一、文法二義性 1.定義 2.文法二義性消除 3.幾點說明第九十七頁，共一百五十二頁。971. 定義 如果一個文法中某個句型對應(yīng)兩棵不同的語法樹，則稱這個文法是二義性的。也就是說，若一個文法中的某句型對應(yīng)兩個不同的最左推導(dǎo)或最右推導(dǎo)，則這個文法是二義性的。 第九十八頁，共一百五十二頁。98例如：文法GE E=E+E|E*E|(E)|i符號串i+i*i是L(G)中一個句子,有兩個不同的最右推導(dǎo) EE+EE+E*EE+E*iE+i*ii+i*i (1) EE*EE*iE+E*iE+i*ii+

46、i*i (2)對應(yīng)兩棵不同的語法樹推導(dǎo)序列(1)和(2)分別對應(yīng)兩棵不同的語法樹, 所以文法GE是二義性的。若將+，*看成算術(shù)運算符，則出現(xiàn)對表達式i+i*i 是先做+還是先做*的不確定問題。EE+EiEEii*EE*EiEEii+第九十九頁，共一百五十二頁。99對于不少高級語言中，例如PASCAL語言，在描述條件語句(IF語句)時，使用文法GC，其規(guī)則P為 C=if B then C C=if B then C else C C=S B= B1 | B2 S= S1 | S2其中C是開始符號，B代表布爾表達式，S代表語句，顯然，句子 if B1 then if B2 then S1 else

47、 S2存在兩種不同最右推導(dǎo)。第一百頁，共一百五十二頁。100 C if B then C if B1 then if B2 then C else C if B1then if B2 then S1 else S2 CifBCthenifBCthenelseCSSB1B2S1S2第一百零一頁，共一百五十二頁。101 C if B then C else C if B1 then C else S2 if B1 then if B2 then C else S2 if B1 then if B2 then S1 else S2 CifBCthenelseCifBCthenSSB1S2S1B2第一

48、百零二頁，共一百五十二頁。1022. 文法二義性消除 由于二義性文法的存在，使得在語法分析時帶來了麻煩，為此，們可以具體采用兩種途徑來解決文法二義性問題。 （1）在語義上加些限制，或者說加一些語法非形式規(guī)定 。 例如對于上例中GE文法，我們可以通過規(guī)定運算符之間的優(yōu)先級來避免文法的二義性。又例如對于條件語句文法GC，我們可以規(guī)定else永遠與最靠近它前面一個尚未匹配then配對，這樣就避免文法二義性 。（2）對原二義性文法加上一定條件，將其改造成一個等價的無二義性文法。第一百零三頁，共一百五十二頁。103例如對于上述GE文法可以構(gòu)造出一個無二義性文法GE。即E=T|E+T T=F|T*F F=

49、(E)|iEE+TTFiTFFii*第一百零四頁，共一百五十二頁。1043.幾點說明（1）業(yè)已證明，文法的二義性是不可判定的。（2）文法的二義性和語言的二義性是兩個不同的概念。 產(chǎn)生該語言的文法都是二義性文法，稱該語言為二義性語言，也稱先天二義性。 至少有一個非二義文法產(chǎn)生該語言稱此語言為非二義性語言。 對于由二義性文法描述的語言，有時可以找到等價的無二義性文法描述它，如上例文法GE和GE，因此，我們只說文法二義性，而不說語言的二義性 。第一百零五頁，共一百五十二頁。105作業(yè)P.39：習(xí)題15P.41：習(xí)題22第一百零六頁，共一百五十二頁。106 2.4 語法分析初步若已有文法G，如果給定一

50、個符號串w，如何來確定該符號串是否是文法的句子呢? 第一百零七頁，共一百五十二頁。107一、自頂向下語法分析 1.分析基本思想 2.分析方法二、自底向上語法分析 1.分析基本思想 2.分析方法第一百零八頁，共一百五十二頁。108一、自頂向下語法分析（導(dǎo)出法） 1.分析基本思想 自頂向下分析就是從文法的開始符號出發(fā)，利用其中產(chǎn)生式，逐步推導(dǎo)出要分析的符號串。換言之，對于任何給定的輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下、從左到右地為輸入串建立語法樹。這種分析過程本質(zhì)上是一個試探過程，是反復(fù)使用不同規(guī)則謀求匹配輸入串的過程。 第一百零九頁，共一百五十二頁。1092. 分析方法例如

51、： 設(shè)有文法G=(VN，VT,P,S),其中 VN=S,A VT=a,b,c,d P: S=cAd A=ab|a試分析符號串x=cad是否是文法G的句子.根據(jù)推導(dǎo)ScAdcad容易判斷出x=cad是該文法的句子。若用畫語法樹的方法我們同樣可以判斷出cad是文法的句子。SAdca第一百一十頁，共一百五十二頁。110（1）為了自上而下為符號串x建立語法樹，首先將文法的開始符號S作為樹的根結(jié)點，并設(shè)輸入串指針i指向其第一個符號c，然后用S為左部的產(chǎn)生式來擴展這棵樹.若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcScAdcadi第一百一十一頁，共一百五

52、十二頁。111（2） 此時該樹最左邊末結(jié)點c與x的第一個符號c相匹配，于是調(diào)整指針i使其指向輸入串下一符號a。我們再試圖讓樹的中間端末結(jié)點A去匹配a，顯然，由于A是非終結(jié)符，它不可能直接與終結(jié)符a匹配，我們只得在文法中選擇以A為左部的產(chǎn)生式，這里以A為左部的產(chǎn)生式有兩個，我們試著用第一個選擇來匹配輸入串 ,并擴展語法樹。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcScAd cabdcadiab第一百一十二頁，共一百五十二頁。112（3）此時子樹A最左端末結(jié)點a與i所指的符號a匹配。于是再調(diào)整i使其指向下一輸入符號d，并試圖用A的最右端末結(jié)點b

53、與之匹配。 但它們不匹配，因此，子樹A的匹配失敗，這意味著選用A的第一個候選式對此時的情況不適合，不能構(gòu)造出輸入串x的語法樹，在這種情況下，我們應(yīng)該回頭看看(回溯)是否還有其它的候選式可供利用.若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcScAd cabdcadiabERROR!第一百一十三頁，共一百五十二頁。113（4） 我們應(yīng)把A的第一個候選式所擴展的子樹剪掉，還應(yīng)把指針i恢復(fù)到進入A時所指的輸入符號a，再選用A第二個候選式來構(gòu)造語法樹 .若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcSc

54、Adcadi第一百一十四頁，共一百五十二頁。114（5） 此時子樹A的唯一端末結(jié)點a與i所指的輸入符號a匹配，因此A匹配成功，調(diào)整指針i，使其指向下一個輸入符號d。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcScAd cadcadia第一百一十五頁，共一百五十二頁。115（6） 最后考慮S的第三個端末結(jié)點d，它與i所指的最后一個輸入符號匹配，因此完成了構(gòu)造輸入串x的語法樹的任務(wù)，從而證明了x是所給文法推導(dǎo)出一個句子。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S=cAd A=ab|aSAdcScAd cadcadiaSUC

55、CESS!第一百一十六頁，共一百五十二頁。116下面我們將上述分析過程總結(jié)一下：（1）自根開始建樹 試圖生成一個和所給的符號串相一致的終結(jié)符號串 （2）選擇不同的規(guī)則反復(fù)試探 在建樹過程中，反復(fù)選擇不同的規(guī)則，每一步試圖將語法樹最左的葉子與所給的符號串進行匹配 （3）匹配失敗退回出錯點 當匹配失敗時，必須回到出錯點，然后再選擇其他規(guī)則進行試探 這種方法稱為回溯采用自頂向下分析時，不僅可能遇到回溯問題，而且還可能由于文法中有左遞歸規(guī)則而陷入無限循環(huán)。我們將在第四章中要介紹這兩方面問題及其解決辦法。 第一百一十七頁，共一百五十二頁。117二、自底向上語法分析 1.分析基本思想 自底向上分析是從所給

56、的符號串w開始，在其中尋找與文法規(guī)則右部相匹配的子串，并用該規(guī)則的左部取代此子串(即歸約)，重復(fù)此過程，步步向上歸約，最后試圖將符號串w歸約到文法識別符號，如歸約成功，則符號串w是文法的句子。 第一百一十八頁，共一百五十二頁。118二、自底向上語法分析 2.分析方法例2.24 設(shè)有文法G=(VN,VT,P,S),其中 VN=A,B,S VT=a,b,c,d,e P: S=aAcBe A=Ab|b B=d 試分析w=abbcde是否為此文法的句子。 第一百一十九頁，共一百五十二頁。119歸約過程描述: 先設(shè)立一個符號棧，即將輸入串中符號逐個移進棧，當棧頂符號串形成一個句柄時，就進行一次歸約，把棧

57、頂句柄那個符號串用相應(yīng)規(guī)則左部的非終結(jié)符號來代替，接著再檢查在棧頂是否形成新的句柄，若出現(xiàn)新的句柄，那么再進行歸約；若沒有形成新句柄，則再從輸入符號串中移進新符號，如此繼續(xù)到整個輸入符號串處理完畢。 最終，如棧底為開始符號，則輸入符號串是該文法的句子，報告成功，否則，是不合法的符號串，報告錯誤。第一百二十頁，共一百五十二頁。120為了具體實現(xiàn)方便，我們統(tǒng)一以符號“#”作為待分析符號串左右分界符，作為初始狀態(tài)，先將符號串的左分界符壓入符號棧，作為棧底符號。對符號串a(chǎn)bbcde分析過程如下所示。步驟 符號棧 輸入符號串 動作 # abbcde# 左界符進棧 #a bbcde# a進棧 #ab bc

58、de# b進棧 #aA bcde# 用Ab歸約 # aAb cde# b進棧 #aA cde# 用AAb歸約 #aAc de# c進棧 #aAcd e# d進棧 #aAcB e# 用Bd歸約 #aAcBe # e進棧 #S # 用SAcBe歸約 # S # 接受 P: S=aAcBe A=Ab|b B=d第一百二十一頁，共一百五十二頁。121歸約過程描述: 先設(shè)立一個符號棧，即將輸入串中符號逐個移進棧，當棧頂符號串形成一個句柄時，就進行一次歸約，把棧頂句柄那個符號串用相應(yīng)規(guī)則左部的非終結(jié)符號來代替，接著再檢查在棧頂是否形成新的句柄，若出現(xiàn)新的句柄，那么再進行歸約；若沒有形成新句柄，則再從輸入符

59、號串中移進新符號，如此繼續(xù)到整個輸入符號串處理完畢。 最終，如棧底為開始符號，則輸入符號串是該文法的句子，報告成功，否則，是不合法的符號串，報告錯誤。第一百二十二頁，共一百五十二頁。1222.5 文法和語言分類一、文法分類二、文法和自動機三、壓縮過文法第一百二十三頁，共一百五十二頁。123如前所述，文法G形式定義為G=(VN,VT,P,Z)其規(guī)則P呈如下形式:U=w其中,UVN,wV*但僅有這種文法,還不足以描述許多語言,例如語言L(G)=anbncn|n1便不能完全用上述形式規(guī)則來描述,因此還得定義其它類型的文法。根據(jù)對P中規(guī)則施加不同限制,Chomsky將文法和語言分為四類。一、文法分類第

60、一百二十四頁，共一百五十二頁。124一、文法分類 1.0型文法 2.1型文法 3.2型文法 4.3型文法第一百二十五頁，共一百五十二頁。1251.0型文法若在文法G中，P中規(guī)則具有如下形式：=其中V+，且至少含一個非終結(jié)符，*,則文法G稱為0型文法或稱短語結(jié)構(gòu)文法，簡記為PSG(Phrase Structure Grammar)。由0型文法所描述和定義的語言稱為0型語言,記PSL,即L0 第一百二十六頁，共一百五十二頁。126例2.25 設(shè)文法G=(VN,VT,P,S),其中 VN=S,A,B,C,D,E VT=a P: S=ACaB, Ca=aaC CB=DB, CB=E aD=Da AD=