高級(jí)語(yǔ)言及其語(yǔ)法描述-有限自動(dòng)機(jī)理論

1、1形式化的方法 用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)題的方法。 Noan Chomsky 1956 形式語(yǔ)言理論 形式語(yǔ)言理論是編譯的理論基礎(chǔ) 編譯理論中用到的有關(guān)形式語(yǔ)言理論的最基本概念 字母表和符號(hào)串 文法和語(yǔ)言的形式定義 語(yǔ)法樹(shù)和文法的二義性 文法和語(yǔ)言的分類(lèi)22.3 2.3 程序語(yǔ)言的語(yǔ)法描述程序語(yǔ)言的語(yǔ)法描述1. 1. 相關(guān)概念相關(guān)概念 考慮一個(gè)考慮一個(gè)有窮有窮 字母表字母表 字符集字符集 其中每一個(gè)元素稱(chēng)為一個(gè)其中每一個(gè)元素稱(chēng)為一個(gè)符號(hào)符號(hào) 上的上的符號(hào)串符號(hào)串 (也叫也叫字字) 是指由是指由中的中的符號(hào)符號(hào)所構(gòu)成所構(gòu)成的一個(gè)有窮序列的一個(gè)有窮序列空字，不包含任何符號(hào)的序列空字，

2、不包含任何符號(hào)的序列 * 上所有符號(hào)串的全體，包括上所有符號(hào)串的全體，包括例：若例：若 =a, b，則，則 *=, a, b, aa, ab, ba, bb, aaa, 3 ：空集，不包含任何元素的集合：空集，不包含任何元素的集合 * 的子集的子集U和和V的積定義為：的積定義為：(連接連接)UV= |U& V 注意，一般注意，一般UV VU, 但但(UV)W=U(VW) V自身的自身的n次次(連接連接)積積 Vn = VVVn V0 = 令令V* = V0V1 V2 V3 ，則令，則令V*是是V的閉包的閉包 V+ = VV* ，稱(chēng)，稱(chēng)V+是是V的正則閉包的正則閉包如如、分別表示符號(hào)串分

3、別表示符號(hào)串01和和110，則則表示符號(hào)串表示符號(hào)串01110，表示符表示符號(hào)串號(hào)串11001。空串是連接運(yùn)算的恒等元素，空串是連接運(yùn)算的恒等元素，s = s=s 4 例例 令令LA, B, , Z, a, b, , z，表示，表示L是由大、小寫(xiě)是由大、小寫(xiě)字母組成的字母表，字母組成的字母表，D0, 1, , 9，表示，表示D是由是由10個(gè)個(gè)數(shù)字組成的字母表。數(shù)字組成的字母表。L和和D可以分別看成是有窮的語(yǔ)言可以分別看成是有窮的語(yǔ)言集。用集合的運(yùn)算作用于集。用集合的運(yùn)算作用于L和和D所得到的所得到的6種新語(yǔ)言：種新語(yǔ)言： （1）LD是字母和數(shù)字的集合；是字母和數(shù)字的集合； （2）LD是所有一個(gè)

4、字母后隨一個(gè)數(shù)字的符號(hào)串的集合；是所有一個(gè)字母后隨一個(gè)數(shù)字的符號(hào)串的集合； （3）L6是由是由6個(gè)字母構(gòu)成的符號(hào)串的集合；個(gè)字母構(gòu)成的符號(hào)串的集合； （4）L*是所有字母串（包括是所有字母串（包括 ）的集合；）的集合； （5）L(LD )*是以字母開(kāi)頭的所有字母數(shù)字串的集合；是以字母開(kāi)頭的所有字母數(shù)字串的集合； （6）D+是不含空串的數(shù)字串的集合。是不含空串的數(shù)字串的集合。 從這個(gè)例子可以看出，從基本集合開(kāi)始，利用集合上的從這個(gè)例子可以看出，從基本集合開(kāi)始，利用集合上的運(yùn)算，可以定義新的語(yǔ)言。運(yùn)算，可以定義新的語(yǔ)言。52. 2. 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法文法：描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的文法：描述

5、語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則形式規(guī)則 (語(yǔ)法語(yǔ)法規(guī)則規(guī)則)。必須是必須是準(zhǔn)確、易理解的，準(zhǔn)確、易理解的，且應(yīng)且應(yīng)有強(qiáng)描述力有強(qiáng)描述力 應(yīng)應(yīng)有利于句子分析和翻有利于句子分析和翻譯譯 最好能夠最好能夠自動(dòng)產(chǎn)生語(yǔ)法分析程序。自動(dòng)產(chǎn)生語(yǔ)法分析程序。通常用符號(hào)通常用符號(hào)G表示表示(Grammar)。上下文無(wú)關(guān)文法：所定義的語(yǔ)法范疇是完全獨(dú)上下文無(wú)關(guān)文法：所定義的語(yǔ)法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的，即是和立于這種范疇可能出現(xiàn)的環(huán)境的，即是和其上下文無(wú)關(guān)的，不同于自然語(yǔ)言。其上下文無(wú)關(guān)的，不同于自然語(yǔ)言。6例：英文例句分析例：英文例句分析 He gave me a book.設(shè)“” 為“由組成”或“定

6、義為”，則有語(yǔ)法規(guī)則： He me a gave book7推導(dǎo)He gave me a book 的語(yǔ)法的合法性。 He He He gave He gave He gave me He gave me He gave me a He gave me a book語(yǔ)法正確8得到語(yǔ)法分析樹(shù): Hegavemeabook9 上下文無(wú)關(guān)文法的定義：上下文無(wú)關(guān)文法的定義： 一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式是一個(gè)四元式 G=(VT，VN，S，P)，其中，其中VT：終結(jié)符集合：終結(jié)符集合(非空非空)VN：非終結(jié)符集合：非終結(jié)符集合(非空非空)，且，且VT VN=S：文法的開(kāi)始符號(hào)：文法

7、的開(kāi)始符號(hào)，S VNP：產(chǎn)生式集合：產(chǎn)生式集合(有限有限)，每個(gè)產(chǎn)生式形式為每個(gè)產(chǎn)生式形式為P， P VN， (VT VN)*開(kāi)始符開(kāi)始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。一次。10上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法G包括四個(gè)組成部分：包括四個(gè)組成部分：一組一組終結(jié)符號(hào)終結(jié)符號(hào)：組成語(yǔ)言的基本符號(hào)，不可再：組成語(yǔ)言的基本符號(hào)，不可再分，如基本字、標(biāo)識(shí)符、常數(shù)等。分，如基本字、標(biāo)識(shí)符、常數(shù)等。一組一組非終結(jié)符號(hào)非終結(jié)符號(hào)：規(guī)則中用尖括號(hào)括起來(lái)的符：規(guī)則中用尖括號(hào)括起來(lái)的符號(hào)，表示一些語(yǔ)法成分，可以推導(dǎo)出其他號(hào)，表示一些語(yǔ)法成分，可以推導(dǎo)出其他的語(yǔ)法成分的語(yǔ)法成分,表示

8、一定符號(hào)串的集合表示一定符號(hào)串的集合11一個(gè)一個(gè)開(kāi)始符號(hào)開(kāi)始符號(hào)：特殊的非終結(jié)符，程序語(yǔ)言中，：特殊的非終結(jié)符，程序語(yǔ)言中，最終感興趣的是最終感興趣的是“程序程序”。一組一組產(chǎn)生式產(chǎn)生式：定義語(yǔ)法范疇的書(shū)寫(xiě)規(guī)則，：定義語(yǔ)法范疇的書(shū)寫(xiě)規(guī)則，A，A是一個(gè)非終結(jié)符，稱(chēng)左部符號(hào)，是一個(gè)非終結(jié)符，稱(chēng)左部符號(hào)， 稱(chēng)為稱(chēng)為產(chǎn)生式的右部，是由終結(jié)符號(hào)或產(chǎn)生式的右部，是由終結(jié)符號(hào)或|與非終結(jié)與非終結(jié)符號(hào)組成的一個(gè)符號(hào)串。產(chǎn)生式符號(hào)組成的一個(gè)符號(hào)串。產(chǎn)生式A稱(chēng)為稱(chēng)為關(guān)于關(guān)于A的一條產(chǎn)生規(guī)則。的一條產(chǎn)生規(guī)則。這種表示法稱(chēng)這種表示法稱(chēng)巴科斯范式巴科斯范式，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)BNF范式范式。有的書(shū)用。有的書(shū)用“:=”代替代替“

9、”。12對(duì)于一個(gè)語(yǔ)法范疇，有時(shí)需幾個(gè)產(chǎn)生式，特對(duì)于一個(gè)語(yǔ)法范疇，有時(shí)需幾個(gè)產(chǎn)生式，特別需含遞歸的產(chǎn)生式。別需含遞歸的產(chǎn)生式。 例，定義只含+，*的算術(shù)表達(dá)式的文法 G=， 其中，P由下列產(chǎn)生式組成：E iE E+EE E*EE (E)13 幾點(diǎn)規(guī)定：幾點(diǎn)規(guī)定： P 1 P 2 可縮寫(xiě)為可縮寫(xiě)為 P 1| 2| n P n 其中，其中，“|”讀成讀成“或或”，稱(chēng)為，稱(chēng)為P的一個(gè)候選式。的一個(gè)候選式。 表示一個(gè)文法時(shí)，通常只給出開(kāi)始符號(hào)和產(chǎn)生式，表示一個(gè)文法時(shí)，通常只給出開(kāi)始符號(hào)和產(chǎn)生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)合并：E i | E

10、AE | (E)A +|14 上下文無(wú)關(guān)文法如何定義語(yǔ)言上下文無(wú)關(guān)文法如何定義語(yǔ)言: :從文法的開(kāi)始符從文法的開(kāi)始符號(hào)出發(fā)號(hào)出發(fā), ,反復(fù)連續(xù)使用產(chǎn)生式反復(fù)連續(xù)使用產(chǎn)生式, ,對(duì)左邊的非終結(jié)對(duì)左邊的非終結(jié)符進(jìn)行替換和展開(kāi)符進(jìn)行替換和展開(kāi) 直接推導(dǎo)直接推導(dǎo)：又稱(chēng)一步推導(dǎo)：又稱(chēng)一步推導(dǎo)( (用用 符號(hào)符號(hào)=表示表示),),就是就是用某條規(guī)則的右部去替換該規(guī)則的左部用某條規(guī)則的右部去替換該規(guī)則的左部 連續(xù)使用某個(gè)產(chǎn)生式右部去替換左部某個(gè)非終連續(xù)使用某個(gè)產(chǎn)生式右部去替換左部某個(gè)非終結(jié)符的過(guò)程結(jié)符的過(guò)程, ,得到的連續(xù)序列稱(chēng)為推導(dǎo)得到的連續(xù)序列稱(chēng)為推導(dǎo), ,從從 到我是大學(xué)生是一個(gè)到我是大學(xué)生是一個(gè)推導(dǎo)

11、推導(dǎo). .15約約 定定大寫(xiě)字母大寫(xiě)字母A, B, C, 或漢語(yǔ)詞組代表非終結(jié)符號(hào)；或漢語(yǔ)詞組代表非終結(jié)符號(hào)；小寫(xiě)字母小寫(xiě)字母a, b, c, 代表終結(jié)符；代表終結(jié)符； , , 等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。16 定義：稱(chēng)定義：稱(chēng) A 直接推出直接推出，即，即 A 僅當(dāng)僅當(dāng)A 是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， 且且 ， (VT VN)* 。例：例：S-01, 0S-01, 0S S0=00=001010(0(直接推導(dǎo)直接推導(dǎo) , , ) ) v v直接推導(dǎo)直接推導(dǎo)出出w,w,也稱(chēng)也稱(chēng)w w直接歸約直接歸約到到v,v, 記作記作 v v w w 。直接推

12、導(dǎo)直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過(guò)程的過(guò)程直接歸約直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程的過(guò)程17 如果如果 1 2 n，則我們稱(chēng)這個(gè)序列，則我們稱(chēng)這個(gè)序列是從是從 1到到 n的一個(gè)的一個(gè)推導(dǎo)推導(dǎo)。若存在一個(gè)從。若存在一個(gè)從 1到到 n的推導(dǎo)，則稱(chēng)的推導(dǎo)，則稱(chēng) 1可以可以推導(dǎo)推導(dǎo)出出 n 。 例：對(duì)文法例：對(duì)文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)18 1n，從，從 1出發(fā)，經(jīng)一步或若干步，可出發(fā)，經(jīng)一步或若干步，可推導(dǎo)出推導(dǎo)出 n， 1+

13、 1n，從，從 1出發(fā)，經(jīng)出發(fā)，經(jīng)0步或若干步，可推步或若干步，可推導(dǎo)出導(dǎo)出 n ， 0 故故 1n，相當(dāng)于，相當(dāng)于 = 或或 +19三種推導(dǎo)的比較 直接推導(dǎo)（直接推導(dǎo)（）的長(zhǎng)度為）的長(zhǎng)度為1 直接推導(dǎo)序列（直接推導(dǎo)序列（ +）的長(zhǎng)度）的長(zhǎng)度n1 廣義推導(dǎo)（廣義推導(dǎo)（ *）的長(zhǎng)度）的長(zhǎng)度020 例例 : G = (E, i, +, *, (, ) , P , E) (1.1) P： E E + E | E * E | ( E ) | i 表達(dá)式表達(dá)式(i)和和(i+i)*i的推導(dǎo)：的推導(dǎo)：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i

14、 + i)*i E E 0步推導(dǎo)步推導(dǎo) E (i + i)*i 6步推導(dǎo)步推導(dǎo) E (i + i)*i 6步推導(dǎo)步推導(dǎo) E (E) 直接推導(dǎo)直接推導(dǎo)*21句型、句子、語(yǔ)言的定義q句型和句子句型和句子設(shè)有文法設(shè)有文法GSGS，若符號(hào)串，若符號(hào)串是從開(kāi)始符推導(dǎo)是從開(kāi)始符推導(dǎo)出來(lái)的出來(lái)的, ,即即 S S =* * ，則稱(chēng)，則稱(chēng)是文法是文法G G的的句型句型。 若若僅由終結(jié)符組成僅由終結(jié)符組成, ,即即 S S =* * ，且，且VVT T* *，則稱(chēng)則稱(chēng)是文法是文法G G的的句子句子。例例 文法文法GSGS： S0S1S0S1， S01S01因?yàn)橐驗(yàn)镾 S 0 0S S1 1 00 00S S11

15、 11 000 000S S111 111 0000111100001111所以所以S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句型的句型0000111100001111是是G G的句子的句子22q語(yǔ)言的定義語(yǔ)言的定義由文法由文法G G生成的語(yǔ)言記為生成的語(yǔ)言記為L(zhǎng)(G),L(G),它是文法它是文法G G的一切句的一切句子的集合子的集合, ,即即 L(G)=x|S L(G)=x|S =+ +x x，且，且 xVxVT T* * 例例 文法文法G G： S0S1S0S1， S01S01S0S1 00S11

16、 03S13 0n-1S1n-1 0n1nL(G)=0L(G)=0n n1 1n n|n1|n1q文法和語(yǔ)言的關(guān)系：文法和語(yǔ)言的關(guān)系：文法文法G G生成的每個(gè)串都在生成的每個(gè)串都在L(G)L(G)中中L(G)L(G)中的每個(gè)串確實(shí)能被中的每個(gè)串確實(shí)能被G G生成生成23根據(jù)文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言；根據(jù)文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言；例：例：GE E：EE+T|TEE+T|TTTTTF|FF|F F(E)|aF(E)|aE E E+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符號(hào)表示一切能用符號(hào)a，+，(，)構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)

17、式有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法例：若語(yǔ)言由例：若語(yǔ)言由0、1符號(hào)串組成，串中符號(hào)串組成，串中0和和1的個(gè)數(shù)相同，的個(gè)數(shù)相同，構(gòu)造其文法為：構(gòu)造其文法為：A 0B|1CB 1|1A|0BBC 0|0A|1CC24 例：文法例：文法(A,B,S,a,b,c,P,S) S-Ac|aB A-ab B-bc寫(xiě)出寫(xiě)出(G)的全部元素的全部元素 L(G) = abc25例例1：考慮文法：考慮文法G1：SbA AaA|a定義了一個(gè)什么語(yǔ)言定義了一個(gè)什么語(yǔ)言分析：分析：SbAbaSbAbaAbaaSbAbaA.baa.所以：所以：L(G1)=ban | n1l得到

18、一個(gè)語(yǔ)言，是通過(guò)利用所有的侯選式推導(dǎo)出所得到一個(gè)語(yǔ)言，是通過(guò)利用所有的侯選式推導(dǎo)出所有句子，構(gòu)成一個(gè)集合。有句子，構(gòu)成一個(gè)集合。L(G1) = 以以b開(kāi)頭后跟一個(gè)或多個(gè)開(kāi)頭后跟一個(gè)或多個(gè)a的串的串26推導(dǎo)例題2e.g. 文法產(chǎn)生的語(yǔ)言文法產(chǎn)生的語(yǔ)言L(G2)=ambn|m,n 1L(G3) = anbn|n 1G2: S A B A a A | a B b B | bG3: S a S b | ab27e.g. 文法產(chǎn)生的語(yǔ)言文法文法G2對(duì)句子對(duì)句子aaabb的推導(dǎo)：的推導(dǎo)：S = A B A B S A B = a A B a A B A a A = a a A B a a A B A a

19、A = a a a B a a a B A a = a a a b B a a a b B B b B = a a a b b a a a b b B bA= aB = abA= Ab = ab S A B A a A | a B b B | b28e.g. 文法產(chǎn)生的語(yǔ)言文法文法G3對(duì)句子對(duì)句子aaaabbbb的推導(dǎo)：的推導(dǎo)：S = a S b a S b S a S b = a a S b b a a S b b S a S b = a a a S b b b a a a S b b b S a S b = a a a a b b b b a a a a b b b b S a bS a

20、S b | ab29例例4：文法：文法G3(A)：A c|AbG3(A)的語(yǔ)言的語(yǔ)言?L(G3)=c，cb，cbb，以以c開(kāi)頭，后繼若干個(gè)開(kāi)頭，后繼若干個(gè)b30 從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯一。一。 E+Ei+Ei+i E+EE+ii+i 最左推導(dǎo)最左推導(dǎo)：任何一步：任何一步 都是對(duì)都是對(duì) 中的最中的最左非終結(jié)符進(jìn)行替換。左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)最右推導(dǎo)：任何一步：任何一步 都是對(duì)都是對(duì) 中的最中的最右非終結(jié)符進(jìn)行替換。右非終結(jié)符進(jìn)行替換。31舉例 例例: 文法文法GS: SAB AA0|1B B0|S1 請(qǐng)給出句子請(qǐng)給出句子101001的最左

21、和最右推導(dǎo)。的最左和最右推導(dǎo)。 最左推導(dǎo)：最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推導(dǎo)：最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001323. 3. 語(yǔ)法分析樹(shù)與二義性語(yǔ)法分析樹(shù)與二義性語(yǔ)法樹(shù)語(yǔ)法樹(shù)(推導(dǎo)樹(shù)推導(dǎo)樹(shù)Parse Tree)作用作用:直觀地描述上下文無(wú)關(guān)文法的句型直觀地描述上下文無(wú)關(guān)文法的句型推導(dǎo)過(guò)程。給定文法推導(dǎo)過(guò)程。給定文法G=(VN,VT,P,S)，對(duì)，對(duì)于于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)樹(shù)33語(yǔ)法樹(shù)的相關(guān)概念 結(jié)點(diǎn)：每個(gè)樹(shù)

22、的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就結(jié)點(diǎn)：每個(gè)樹(shù)的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。是該符號(hào)。 邊：兩個(gè)結(jié)點(diǎn)之間的連線。邊：兩個(gè)結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。根結(jié)點(diǎn)：沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱(chēng)為分支。分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱(chēng)為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹(shù)：語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分子樹(shù)：語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分 末端結(jié)點(diǎn)：沒(méi)有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。末端結(jié)點(diǎn)：沒(méi)有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹(shù)中，末端結(jié)點(diǎn)可能是非終結(jié)符在相對(duì)于句型的語(yǔ)法樹(shù)中，末端結(jié)點(diǎn)可能是非

23、終結(jié)符號(hào)。號(hào)。34語(yǔ)法樹(shù)的概念 定義：語(yǔ)法樹(shù)的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)定義：語(yǔ)法樹(shù)的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于識(shí)別符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)應(yīng)于識(shí)別符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。 引入語(yǔ)法樹(shù)的意義：作為識(shí)別句子的輔助工引入語(yǔ)法樹(shù)的意義：作為識(shí)別句子的輔助工具，語(yǔ)法樹(shù)可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)具，語(yǔ)法樹(shù)可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。于其后的語(yǔ)義分析有非常重要的意義。35語(yǔ)法樹(shù)的特征 給定文法給定文法G，G=

24、(VN,VT,P,S)，對(duì)于，對(duì)于G的任何句型都能構(gòu)造與之關(guān)的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）。這棵樹(shù)具有下列特征：聯(lián)的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）。這棵樹(shù)具有下列特征：1、根結(jié)點(diǎn)的標(biāo)記是、根結(jié)點(diǎn)的標(biāo)記是開(kāi)始符號(hào)開(kāi)始符號(hào)S；2、每個(gè)結(jié)點(diǎn)的標(biāo)記都是、每個(gè)結(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號(hào)；中的一個(gè)符號(hào)；3、若一棵子樹(shù)的根結(jié)點(diǎn)為、若一棵子樹(shù)的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)橛业呐帕写涡驗(yàn)锳1A2AR，那么，那么 A A1A2.AR一定是一定是P中的一中的一條規(guī)則；條規(guī)則；4、若一標(biāo)記為、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則的結(jié)點(diǎn)至少有一個(gè)除它以

25、外的子孫，則AVN5、若樹(shù)的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串、若樹(shù)的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則，則w是是文法文法G的的句型句型；若；若w中僅含中僅含終結(jié)符號(hào)終結(jié)符號(hào)，則，則w為文法為文法G所產(chǎn)生的所產(chǎn)生的句句子子。36從推導(dǎo)構(gòu)造語(yǔ)法樹(shù) 方法：把識(shí)別符號(hào)做方法：把識(shí)別符號(hào)做為根結(jié)點(diǎn)，對(duì)每一個(gè)為根結(jié)點(diǎn)，對(duì)每一個(gè)直接推導(dǎo)畫(huà)一個(gè)分支，直接推導(dǎo)畫(huà)一個(gè)分支，分支的名字是直接推分支的名字是直接推導(dǎo)中被替換的非終結(jié)導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無(wú)分支符號(hào)，直到再無(wú)分支可畫(huà)結(jié)束?？僧?huà)結(jié)束。 例如：推導(dǎo)S AB AcBd Accdd abccddSBBdbaAcdc37語(yǔ)法樹(shù)的構(gòu)造過(guò)程S

26、AB AcBd Accdd abccddSSBASBB dAcSBB dAcdcSBB dbaAcdc（1）（2）（3）（5）（4）38從語(yǔ)法樹(shù)構(gòu)造推導(dǎo) 方法：從分支建立直接推導(dǎo)，然后從語(yǔ)法方法：從分支建立直接推導(dǎo)，然后從語(yǔ)法樹(shù)中剪去之這個(gè)分支，直到無(wú)分支可剪。樹(shù)中剪去之這個(gè)分支，直到無(wú)分支可剪。 語(yǔ)法樹(shù)表明了在推導(dǎo)過(guò)程中使用了哪條規(guī)語(yǔ)法樹(shù)表明了在推導(dǎo)過(guò)程中使用了哪條規(guī)則和使用在哪個(gè)非終結(jié)符號(hào)上，但它并沒(méi)則和使用在哪個(gè)非終結(jié)符號(hào)上，但它并沒(méi)有表明使用規(guī)則的順序。有表明使用規(guī)則的順序。 一棵語(yǔ)法樹(shù)可能對(duì)應(yīng)不止一種推導(dǎo)。一棵語(yǔ)法樹(shù)可能對(duì)應(yīng)不止一種推導(dǎo)。一棵語(yǔ)法樹(shù)是不同推導(dǎo)過(guò)程的共性抽象。一棵語(yǔ)法樹(shù)

27、是不同推導(dǎo)過(guò)程的共性抽象。39從語(yǔ)法樹(shù)構(gòu)造推導(dǎo)的過(guò)程 例如文法GS： S AB A aAb|ab B cBd|cd 存在下面的推導(dǎo)可能： S AB AcBd (4) (3) Accdd abccdd (2) (1) S AB abB abcBd abccdd（從后往前看）SBBdbaAcdc(1)(2)(3)(4)40文法G：EE+E|EE|（E）|i句子 ii+i 對(duì)應(yīng)的語(yǔ)法樹(shù)兩個(gè)不同的最左推導(dǎo)：兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i推導(dǎo)推導(dǎo)2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii文法的二義性文法的二義性

28、(Ambiguity)41定義定義 如果一個(gè)文法存在如果一個(gè)文法存在某個(gè)句子某個(gè)句子對(duì)應(yīng)兩棵不對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。 二義性文法存在某個(gè)句子二義性文法存在某個(gè)句子, ,它它有兩個(gè)不有兩個(gè)不同的最左（右）推導(dǎo)同的最左（右）推導(dǎo)42 例例 設(shè)設(shè)if語(yǔ)句語(yǔ)句S的文法的文法G=(E，A，S，if，then，else，S，P)，其中，其中P為：為： Sif E then S （1） S if E then S else S （2） SA （3） 證明該文法是二義的。證明該文法是二義的。 由文法有推導(dǎo)：由文法有推導(dǎo)：S if E then S if

29、E then if E then S else S 同樣也有推導(dǎo)：同樣也有推導(dǎo)：S if E then S else S if E then if E then S else S 對(duì)于同一個(gè)句型對(duì)于同一個(gè)句型if E then if E then S else S，由于應(yīng)用規(guī)則的順序不同，得到了兩個(gè)不同的推由于應(yīng)用規(guī)則的順序不同，得到了兩個(gè)不同的推導(dǎo)，所以該文法是二義文法。導(dǎo)，所以該文法是二義文法。43為什么要避免文法產(chǎn)生二義性？ 二義性的文法將給編譯程序的執(zhí)行帶來(lái)問(wèn)二義性的文法將給編譯程序的執(zhí)行帶來(lái)問(wèn)題。當(dāng)編譯程序?qū)Χx性文法生成的句子題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，

30、就會(huì)產(chǎn)生兩種甚至結(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的理解。語(yǔ)法結(jié)構(gòu)上的不確定更多種不同的理解。語(yǔ)法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語(yǔ)義處理上的不確定性。因性，必將導(dǎo)致語(yǔ)義處理上的不確定性。因此，希望描述語(yǔ)言的文法是無(wú)二義性的。此，希望描述語(yǔ)言的文法是無(wú)二義性的。44如何消除文法的二義性？(1) 方法一：不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一方法一：不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。些語(yǔ)法的非形式規(guī)定。 如如1：對(duì)于文法對(duì)于文法 GE: E i E E+E E E*E E (E) 規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即*優(yōu)先于優(yōu)先于+，+、*服從左

31、結(jié)合。服從左結(jié)合。 如如2：Pascal中二義性的消除是通過(guò)約定，如在符中二義性的消除是通過(guò)約定，如在符合合if 語(yǔ)句中，語(yǔ)句中，else子句總是屬于最近的尚無(wú)子句總是屬于最近的尚無(wú)else子句子句的那個(gè)的那個(gè)if語(yǔ)句。語(yǔ)句。45如何消除文法的二義性？(2) 方法二：構(gòu)造一個(gè)等價(jià)的無(wú)二義性的文法，方法二：構(gòu)造一個(gè)等價(jià)的無(wú)二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，即把排除二義性的規(guī)則合并到原有文法中，改寫(xiě)原有的文法。改寫(xiě)原有的文法。 如文法如文法 G(E)： E i|E+E|E*E|(E) 將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無(wú)二義

32、性的文法法中，則可構(gòu)造無(wú)二義性的文法 46二義文法：G(E)： E i|E+E|E*E|(E)表達(dá)式表達(dá)式 項(xiàng)項(xiàng)|表達(dá)式表達(dá)式+項(xiàng)項(xiàng)項(xiàng)項(xiàng) 因子因子 | 項(xiàng)項(xiàng)*因子因子因子因子 (表達(dá)式表達(dá)式) | i無(wú)二義文法：無(wú)二義文法： G(E)：E T | E+T T F | T*F F (E) | i47)EEEFFTTTTi+*(EFiiE T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i)考慮句子考慮句子(i*i+i)48上下文無(wú)關(guān)文法限制：上下文無(wú)關(guān)文法限制：(化簡(jiǎn)后化簡(jiǎn)后) 不存在任何形如不存在任何形如PP的產(chǎn)

33、生式的產(chǎn)生式(多余多余) 每個(gè)非終結(jié)符每個(gè)非終結(jié)符P必須都有用處必須都有用處b. 必須存在終結(jié)符串必須存在終結(jié)符串 ，使，使P，即，即P不不存在永不終結(jié)的回路。存在永不終結(jié)的回路。*TVa. 從從S出發(fā)，存在出發(fā)，存在SP *+49 文法G（S）: S Bd A Ad|d B Cd |Ae C Ce D e 文法G（S）: S Bd A Ad|d B Ae504.4.形式語(yǔ)言概述形式語(yǔ)言概述喬姆斯基將其分為四類(lèi)，喬姆斯基將其分為四類(lèi)，0, 1, 2, 3，與上下文無(wú)關(guān)，與上下文無(wú)關(guān)文法一樣，它們都由四部分組成，差別在于對(duì)產(chǎn)生式施文法一樣，它們都由四部分組成，差別在于對(duì)產(chǎn)生式施加不同的限制。加不

34、同的限制。v0型文法（型文法（PSG） 0型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言v1型文法（型文法（CSG） 1型語(yǔ)言或上下文有關(guān)語(yǔ)言型語(yǔ)言或上下文有關(guān)語(yǔ)言v2型文法（型文法（CFG） 2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言v3型文法（型文法（RG）3型語(yǔ)言或正則（正規(guī)）語(yǔ)言型語(yǔ)言或正則（正規(guī)）語(yǔ)言510型文法型文法(短語(yǔ)文法，圖靈機(jī)短語(yǔ)文法，圖靈機(jī)) ：對(duì)文法對(duì)文法G，如果它的，如果它的每個(gè)產(chǎn)生式每個(gè)產(chǎn)生式 是這樣的一種結(jié)構(gòu)：是這樣的一種結(jié)構(gòu)：(VNVT)* 且至少含有一個(gè)非終結(jié)符且至少含有一個(gè)非終結(jié)符(VN VT)*0型文法相應(yīng)的語(yǔ)言為型文法相應(yīng)的語(yǔ)言為0型語(yǔ)言，或稱(chēng)遞歸可枚舉型

35、語(yǔ)言，或稱(chēng)遞歸可枚舉集，它的識(shí)別系統(tǒng)是圖靈（集，它的識(shí)別系統(tǒng)是圖靈（Turing）機(jī)。）機(jī)。如文法如文法G，其中，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B 52q1型文法型文法(上下文有關(guān)上下文有關(guān))：它是它是0型文法的特例，對(duì)型文法的特例，對(duì)P中的任一產(chǎn)生式中的任一產(chǎn)生式，都，都|， 僅僅僅僅 S除除外外,但但S不得出現(xiàn)在任何產(chǎn)生式的右部。不得出現(xiàn)在任何產(chǎn)生式的右部。q1型文法相應(yīng)的語(yǔ)言稱(chēng)為型文法相應(yīng)的語(yǔ)言稱(chēng)為1型語(yǔ)言或上下文有關(guān)型語(yǔ)言或上下文有關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)是線性有界自動(dòng)機(jī)。語(yǔ)言，它的識(shí)別系統(tǒng)是線性有界自動(dòng)機(jī)。q例例 文法文法G

36、SGS： SaSBE SaSBE SaBESaBEEBBEEBBEaBab aBab bBbb bBbb bEbe bEbe eEeeeEee53 文法文法G的每一個(gè)產(chǎn)生式均為下列形式：的每一個(gè)產(chǎn)生式均為下列形式：A其中其中，V*，A Vn, V+ 它表示當(dāng)它表示當(dāng)A的上文為的上文為 且下文為且下文為時(shí)可把時(shí)可把A替替換成換成 ，因此稱(chēng)，因此稱(chēng)1型文法為上下文有關(guān)文法。型文法為上下文有關(guān)文法。 滿(mǎn)足前頁(yè)定義的長(zhǎng)度限制，但它更明確地表滿(mǎn)足前頁(yè)定義的長(zhǎng)度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即達(dá)了上下文有關(guān)的特性，即A必須在的上下必須在的上下文環(huán)境中才能被替換。文環(huán)境中才能被替換。54q2型文

37、法（上下文無(wú)關(guān)文法）型文法（上下文無(wú)關(guān)文法） ：它是：它是1型文法的特型文法的特例，對(duì)任一產(chǎn)生式例，對(duì)任一產(chǎn)生式，都有，都有VN N ， (VN NVT T)*q2型文法相應(yīng)的語(yǔ)言稱(chēng)為型文法相應(yīng)的語(yǔ)言稱(chēng)為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言。型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言。它的識(shí)別系統(tǒng)是下推自動(dòng)機(jī)。它的識(shí)別系統(tǒng)是下推自動(dòng)機(jī)。q例例 文法文法GS： SAB ABS|0 BSA|12型文法產(chǎn)生式的一般形式是型文法產(chǎn)生式的一般形式是: A ，它表示不管，它表示不管A的上下文如何都可把的上下文如何都可把A替換成替換成 ，因此被稱(chēng)為上，因此被稱(chēng)為上下文無(wú)關(guān)文法。下文無(wú)關(guān)文法。通常程序設(shè)計(jì)語(yǔ)言的文法，可用通常程序設(shè)計(jì)語(yǔ)言的文法，可用2型文法來(lái)描述，型文法來(lái)描述，因此我們重點(diǎn)研究因此我們重點(diǎn)研究2型文法。如型文法。如C，Pascal 55q3型文法型文法(正規(guī)文法正規(guī)文法)：它是它是2型文法的特例，型文法的特例，任一產(chǎn)生任一產(chǎn)生式式的形式都為的形式都為 AaB或或Aa，其中，其中A ，BVN N ，aVT Tq這種形式的這種形式的3型文法也叫型文法也叫右線性文法右線性文法。3型文法還有一種型文法還有一種形式，限定形式，限定P