編譯原理第二講

1、形式形式語言及其文法語言及其文法本節(jié)主要本節(jié)主要內(nèi)容內(nèi)容2.1 2.1 語言概述語言概述什么是語言？什么是語言？2.1 2.1 語言概述語言概述 自然語言自然語言( (Natural Language)Natural Language) 是人與人的通訊工具是人與人的通訊工具 是人類概念形成和進(jìn)行思維的工具，是人之是人類概念形成和進(jìn)行思維的工具，是人之所以為人的主要特征所以為人的主要特征 復(fù)雜，多歧義復(fù)雜，多歧義難以形式化難以形式化 計(jì)算機(jī)語言計(jì)算機(jī)語言( (Computer Language)Computer Language) 計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具 嚴(yán)格的

2、語法嚴(yán)格的語法( (Grammar)Grammar)、語義語義、易于形式化易于形式化形式語言與自動(dòng)機(jī)理論的關(guān)系形式語言與自動(dòng)機(jī)理論的關(guān)系Noam Chomsky （1928）形式語言與自動(dòng)機(jī)理論的關(guān)系形式語言與自動(dòng)機(jī)理論的關(guān)系 語言學(xué)家語言學(xué)家ChomskyChomsky最初從產(chǎn)生語言的角度研究語言。最初從產(chǎn)生語言的角度研究語言。 19561956年，通過抽象，他將語言形式地定義為是由一個(gè)字母表年，通過抽象，他將語言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合?？梢栽谧帜副砩习凑找欢ǖ闹械淖帜附M成的一些串的集合。可以在字母表上按照一定的規(guī)則定義一個(gè)文法（規(guī)則定義一個(gè)文法（Grammar

3、Grammar），該文法所能產(chǎn)生的所有句），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。子組成的集合就是該文法產(chǎn)生的語言。 19591959年，年，ChomskyChomsky通過深入研究通過深入研究，不僅，不僅確定了文法和自動(dòng)機(jī)分別確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語言，而且證明了文法與自動(dòng)機(jī)的從生成和識(shí)別的角度去表達(dá)語言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性等價(jià)性。 形式語言與自動(dòng)機(jī)理論的關(guān)系形式語言與自動(dòng)機(jī)理論的關(guān)系 2020世紀(jì)世紀(jì)5050年代，人們用巴科斯范式（年代，人們用巴科斯范式（Backus Nour Backus Nour Form Form 或或 Back

4、us Normal FormBackus Normal Form，簡(jiǎn)記為，簡(jiǎn)記為BNFBNF）成功地對(duì)）成功地對(duì)高級(jí)語言高級(jí)語言ALGOL-60ALGOL-60進(jìn)行了描述。實(shí)際上，巴科斯范式進(jìn)行了描述。實(shí)際上，巴科斯范式就是上下文無關(guān)文法（就是上下文無關(guān)文法（Context Free GrammarContext Free Grammar）的一）的一種表示形式。這一成功，使得形式語言在種表示形式。這一成功，使得形式語言在2020世紀(jì)世紀(jì)6060年年代得到了大力的發(fā)展。代得到了大力的發(fā)展。 2.12.1語言概述語言概述 形式語言的描述方法形式語言的描述方法 文法文法數(shù)學(xué)語言（符號(hào)）數(shù)學(xué)語言（符號(hào)

5、） 嚴(yán)格、準(zhǔn)確、形式化嚴(yán)格、準(zhǔn)確、形式化 高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。表示。2.1 2.1 語言概述語言概述 形式語言的組成要素形式語言的組成要素語言語言( (Language)Language)：滿足一定條件的句子集合滿足一定條件的句子集合句子句子( (Sentence)Sentence)：滿足一定規(guī)則的單詞序列滿足一定規(guī)則的單詞序列單詞單詞( (Token)Token)：滿足一定規(guī)則的字符串滿足一定規(guī)則的字符串2.1 2.1 語言概述語言概述 程序設(shè)計(jì)語言的組成要素程序設(shè)計(jì)語言的組成要素 程序設(shè)計(jì)語言程序設(shè)計(jì)語言( (Program

6、ming Language)Programming Language)：組成程序組成程序的所有語句的集合。的所有語句的集合。 程序程序( (Program)Program)：滿足語法規(guī)則的語句序列。滿足語法規(guī)則的語句序列。 語句語句( (Sentence) Sentence) ：滿足語法規(guī)則的單詞序列。滿足語法規(guī)則的單詞序列。 單詞單詞( (Token) Token) ：滿足詞法規(guī)則的字符串。滿足詞法規(guī)則的字符串。 例：變量例：變量:=:=表達(dá)式表達(dá)式 if if 條件條件 then then 語句語句 whilewhile條件條件 do do 語句語句2.2 2.2 基本定義基本定義 字母表

7、字母表（AlphabetAlphabet）是一個(gè)非空有窮集合，是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母字母表中的元素稱為該字母表的一個(gè)字母（LetterLetter），），也叫字符（也叫字符（CharacterCharacter）。）。 例例 以下是不同的字母表：以下是不同的字母表： aa，b b，c c，dd a a，b b，c c，zz 0 0，11 (4) ASCII(4) ASCII字母表字母表2.2 2.2 基本定義基本定義 符號(hào)串符號(hào)串的定義的定義 由字母表中的符號(hào)所組成的任何有窮序列被由字母表中的符號(hào)所組成的任何有窮序列被稱之為該字母表上的符號(hào)串稱之為該字母表上的

8、符號(hào)串, ,也稱作也稱作 字字 。(1) (1) 是是上的一個(gè)符號(hào)串。上的一個(gè)符號(hào)串。(2) (2) 若若x x是是上的符號(hào)串，而上的符號(hào)串，而a a是是的元素的元素, , 則則xaxa是是上的符號(hào)串。上的符號(hào)串。(3) (3) y y是是上的符號(hào)串上的符號(hào)串, ,當(dāng)且僅當(dāng)它由當(dāng)且僅當(dāng)它由(1)(1)和和(2)(2)導(dǎo)出。導(dǎo)出。2.2 2.2 基本定義基本定義設(shè)設(shè)s s是是符號(hào)串，則符號(hào)串，則s s的的前綴前綴：移走：移走s s的尾部的零個(gè)或多于零個(gè)符號(hào)的尾部的零個(gè)或多于零個(gè)符號(hào)后綴后綴：刪去：刪去s s的頭部的零個(gè)或多于零個(gè)符號(hào)的頭部的零個(gè)或多于零個(gè)符號(hào)子串子串: : 從從s s中刪去一個(gè)前

9、綴和一個(gè)后綴中刪去一個(gè)前綴和一個(gè)后綴逆轉(zhuǎn)逆轉(zhuǎn)：將：將S S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串長(zhǎng)度長(zhǎng)度：是該符號(hào)串中的符號(hào)的數(shù)目。例如：是該符號(hào)串中的符號(hào)的數(shù)目。例如| |aab|=3,|=0aab|=3,|=0。2.2 2.2 基本定義基本定義符號(hào)串的連接和方冪符號(hào)串的連接和方冪1.1.連接：設(shè)連接：設(shè)x x和和y y是符號(hào)串，它們的連接是符號(hào)串，它們的連接xyxy是把是把y y的符號(hào)的符號(hào)寫在寫在x x的符號(hào)之后得到的符號(hào)串。例如，的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=banana.x=ba,y=nana,xy=banana.2.2

10、.方冪：方冪：x x0 0= = ; ; x x1 1=x; x=x; x2 2=xx; =xx; ； x xn n=x=xn-1n-1x;x; 例如例如, , 設(shè)設(shè)x=ba, x=ba, 則則 x x1 1= ba, x= ba, x2 2=baba, x=baba, x3 3=bababa, =bababa, 2.2 2.2 基本定義基本定義 定義定義1 1 設(shè)設(shè)1 1、2 2是兩個(gè)字母表，是兩個(gè)字母表，1 1與與2 2 的的乘積乘積( (Product)Product)定義為定義為1 12 2=ab|a=ab|a1 1，bb2 2 例例:1 1=0,1, =0,1, 2 2=a,b, a

11、,b, 1 12 2 =0a,0b,1a,1b =0a,0b,1a,1b 定義定義2 2 設(shè)設(shè)是一個(gè)字母表，是一個(gè)字母表，的的n n次冪次冪( (Power)Power)遞歸遞歸地定義為：地定義為： 0 0= n n=n-1n-1 n1 n1 例：例： 1 13 3 =000,001,010,011,100,101,110,111 =000,001,010,011,100,101,110,1112.2 2.2 基本定義基本定義 定義定義3 3 設(shè)設(shè)是一個(gè)字母表，是一個(gè)字母表，的的正閉包正閉包定定義為：義為： + +=2 23 34 4 的的閉包閉包為：為： * *=0 0+ + = =0 02

12、 23 3 2.2 2.2 基本定義基本定義例例0,10,1+ + = = 00，1 1，0000，0101，10,10,1111，000000，001001，010010，011011，100100， 0,10,1* * = = ，0 0，1 1，0000，0101，10,1110,11，000000，001001，010010，011011，100100， 2.2 2.2 基本定義基本定義定義定義5 5 設(shè)設(shè)是一個(gè)字母表，是一個(gè)字母表， L L * *，L L稱為字稱為字母表母表上的上的語言語言（LanguageLanguage），），xLxL，x x叫做叫做L L的一個(gè)的一個(gè)句子句子。例

13、：例： 字母表字母表00，11上的語言上的語言00，110000，111100，1 1，0000，111100，1 1，0000，1111，0101，10100000，1111* *0101，1010* *2.3 2.3 文法文法如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？考慮一個(gè)句子考慮一個(gè)句子文法要素的提取文法要素的提取分析分析：The grey wolf will eat the goat謂語謂語主語主語形容詞形容詞名詞名詞動(dòng)詞動(dòng)詞直接賓語直接賓語情態(tài)情態(tài)動(dòng)動(dòng)詞詞句子句子動(dòng)原動(dòng)原冠詞冠詞名詞名詞The grey wolf will eat the goat冠詞冠詞 句子句

14、子 主語主語 謂語謂語 （1 1） 主語主語 冠詞冠詞 形容詞形容詞 名詞名詞 （2 2） 冠詞冠詞 thethe （3 3） 形容詞形容詞 greygrey （4 4） 謂語謂語 動(dòng)詞動(dòng)詞 直接賓語直接賓語 （5 5） 動(dòng)詞動(dòng)詞 情態(tài)動(dòng)詞情態(tài)動(dòng)詞 動(dòng)詞原動(dòng)詞原形形 （6 6） 情態(tài)動(dòng)詞情態(tài)動(dòng)詞 willwill （7 7） 動(dòng)詞原動(dòng)詞原形形 eateat （8 8） 直接賓語直接賓語 冠詞冠詞 名詞名詞 （9 9） 名詞名詞 wolfwolf （1010） 名詞名詞 goatgoat （1111）句子的組成規(guī)則句子的組成規(guī)則問題：如何用符號(hào)來描問題：如何用符號(hào)來描述？即如何形式化？述？即如何

15、形式化？終結(jié)符號(hào)集終結(jié)符號(hào)集V VT T = = thethe，grey, wolf,will, eat, goatgrey, wolf,will, eat, goat非終結(jié)符號(hào)集非終結(jié)符號(hào)集V VN N = = 句子句子 ， 主語主語 ， 謂語謂語 ， 冠詞冠詞 ， 形容詞形容詞 ， 名詞名詞 ， 動(dòng)詞動(dòng)詞 ， 直接賓語直接賓語 ， 助動(dòng)詞助動(dòng)詞 ， 動(dòng)詞原動(dòng)詞原形形 語法規(guī)則集語法規(guī)則集P P = = 句子句子 主語主語 謂語謂語 ， 開始符號(hào)開始符號(hào)S S = = 句子句子 定義句子的規(guī)則的語法定義句子的規(guī)則的語法組成組成問題：有了定義句子的規(guī)則，問題：有了定義句子的規(guī)則，如何如何推導(dǎo)出

16、推導(dǎo)出語語言言？ 句子句子 主語主語 謂語謂語 冠詞冠詞 形容詞形容詞 名詞名詞 謂語謂語 thethe 形容詞形容詞 名詞名詞 謂語謂語 the the greygrey 名詞名詞 謂語謂語 the grey the grey wolfwolf 謂語謂語 the grey wolf the grey wolf 動(dòng)詞動(dòng)詞 直接賓語直接賓語 . the grey wolf the grey wolf will eat the goatwill eat the goat句子的推導(dǎo)句子的推導(dǎo) 句子句子 the grey wolf will eat the goat the grey wolf wil

17、l eat the wolf the grey goat will eat the wolf the grey goat will eat the grey符合語法且符合語義的句子僅是：符合語法且符合語義的句子僅是： the grey wolf will eat the goat句子句子的的語義語義約束約束文法文法G G 的形式定義的形式定義文法文法G G為一個(gè)四元組為一個(gè)四元組: : = ( = (T T，N N，) ) T T：終結(jié)符終結(jié)符( (Terminal)Terminal)集集 N N：非終結(jié)符非終結(jié)符( (Variable)Variable)集，集，T TN N= 語法成分語法成

18、分代表某個(gè)語言的各種子結(jié)構(gòu)代表某個(gè)語言的各種子結(jié)構(gòu) ：開始符號(hào)：開始符號(hào)( (Start Symbol)Start Symbol)，SSN N 代表文法所定義的語言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次代表文法所定義的語言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次文法文法G G 的形式定義的形式定義：產(chǎn)生式：產(chǎn)生式( (Product)Product)集合集合，被稱為產(chǎn)生式（定義式），讀作：被稱為產(chǎn)生式（定義式），讀作：定義為定義為。其中其中(T TN N) )+ +，且且中至少有中至少有N N中元素中元素的一個(gè)出現(xiàn)。的一個(gè)出現(xiàn)。(T TN N) )* *。稱為產(chǎn)生式稱為產(chǎn)生式的的左部左部( (Left Part)Lef

19、t Part)，稱為產(chǎn)生式稱為產(chǎn)生式的的右部右部( (Right Part)Right Part)。產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu)（組成規(guī)則）產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu)（組成規(guī)則） 產(chǎn)生式的簡(jiǎn)寫產(chǎn)生式的簡(jiǎn)寫對(duì)一組有相同左部的產(chǎn)生式對(duì)一組有相同左部的產(chǎn)生式1 1，2 2，n n可以簡(jiǎn)單地記為：可以簡(jiǎn)單地記為：1 1|2 2| |n n讀作：讀作：定義為或者定義為或者1 1，或者或者2 2，或者或者n n。并且稱它們?yōu)椴⑶曳Q它們?yōu)楫a(chǎn)生式。產(chǎn)生式。1 1，2 2，n n稱為稱為候選式候選式( (Candidate)Candidate)。 例例2-1 2-1 算術(shù)表達(dá)式的文法算術(shù)表達(dá)式的文法 考慮簡(jiǎn)單

20、算術(shù)表達(dá)式組成的語言考慮簡(jiǎn)單算術(shù)表達(dá)式組成的語言 G =(idG =(id，+ +，* *，( (，)，EE，P P，E)E)P: EE + E P: EE + E EE EE * * E E E( E ) E( E ) Eid Eid 簡(jiǎn)寫簡(jiǎn)寫 E E + E | E E E + E | E * * E | ( E ) | id E | ( E ) | id 推導(dǎo)舉例推導(dǎo)舉例E E E + E E + E （1 1） 串中含有變量串中含有變量 id + E id + E （4 4） 串中含有變量串中含有變量 id + E id + E * * E E （2 2） 串中含有變量串中含有變量 i

21、d + id id + id * * E E（4 4） 串中含有變量串中含有變量 id + id id + id * * id id（4 4） 串中沒有變量串中沒有變量 到此串中已經(jīng)沒有（語法）變量了，不能再推導(dǎo)了到此串中已經(jīng)沒有（語法）變量了，不能再推導(dǎo)了最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)最左推導(dǎo)( (Left-most Derivation)Left-most Derivation)每次推導(dǎo)都施加在句型的最左邊的語法每次推導(dǎo)都施加在句型的最左邊的語法變量上。變量上。最右推導(dǎo)最右推導(dǎo)( (Right-most Derivation)Right-most Derivation)每次推

22、導(dǎo)都施加在句型的最右邊的語法每次推導(dǎo)都施加在句型的最右邊的語法變量上。變量上。id+idid+id* *idid的不同推導(dǎo)的不同推導(dǎo)P: EP: EE+E|EE+E|E* *E|(E)|idE|(E)|id直接推導(dǎo)直接推導(dǎo) 設(shè)有文法設(shè)有文法G G 是文法的一個(gè)產(chǎn)生式，是文法的一個(gè)產(chǎn)生式， 且且、（T TN N）* *， 且且有有v,v, ,滿足滿足v=v=, , = =, , 則則是是v v的直接推導(dǎo)，記做的直接推導(dǎo)，記做v=v= （多步）推導(dǎo)（多步）推導(dǎo) 0 01 12 2 n n記為記為 0 0n n n n ( (恰用恰用n n步步) ) 0 0+ + n n （至少一步）至少一步） 0

23、 0* * n n （若干步若干步: :零步或多步）零步或多步）遞歸遞歸 設(shè)有文法設(shè)有文法G G A A是文法的一個(gè)產(chǎn)生式，是文法的一個(gè)產(chǎn)生式， 若若具有具有v vA A的形式，其中的形式，其中v,v,不同時(shí)為空，則不同時(shí)為空，則A A是直接遞歸的是直接遞歸的 若存在推導(dǎo)若存在推導(dǎo)A A * * vAvA, ,則則A A是遞歸的是遞歸的 特別的，當(dāng)特別的，當(dāng)v v為空，為空，不為空時(shí)，分別稱上述兩種不為空時(shí)，分別稱上述兩種情況的產(chǎn)生式為直接左遞歸和左遞歸情況的產(chǎn)生式為直接左遞歸和左遞歸 若文法中至少含有一個(gè)遞歸的產(chǎn)生式，則稱為遞若文法中至少含有一個(gè)遞歸的產(chǎn)生式，則稱為遞歸文法歸文法句型與句子句

24、型與句子 句型句型: :如果如果S S* *，(T TN N) )* *則稱則稱是是G G產(chǎn)生的一個(gè)產(chǎn)生的一個(gè)句型句型( (Sentential Form)Sentential Form) E E E + E E + E E E + E + E * * E E E E 4 4 id + id id + id * * E E 句子句子: :如果如果S S * * x x，且且xxT T* * ，則稱則稱x x是是G G產(chǎn)生的一個(gè)產(chǎn)生的一個(gè)句子句子( (SentenceSentence) )E E id + id id + id * * id id文法文法G G產(chǎn)生的語言產(chǎn)生的語言定義定義 ( (

25、) ) x x* * x and xx and xT T* * 文法文法G G的作用的作用語言的有窮描述語言的有窮描述 以有限的規(guī)則描述無限的語言現(xiàn)象以有限的規(guī)則描述無限的語言現(xiàn)象有限：有限： 產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限：無限： 可以導(dǎo)出無窮多個(gè)句子（可以導(dǎo)出無窮多個(gè)句子（L L也可是有窮）也可是有窮）2.2. 文法的分類文法的分類( (ChomskyChomsky體系體系) ) 根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言）根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言） 涉及文法的復(fù)雜程度、分析方法的選擇涉及文法的復(fù)雜程度、分析方法的選擇 反映文法描述語言的能力反映

26、文法描述語言的能力 如果如果G G滿足文法定義的要求，則是型文滿足文法定義的要求，則是型文法（短語結(jié)構(gòu)文法法（短語結(jié)構(gòu)文法PSG: Phrase Structure PSG: Phrase Structure Grammar Grammar ）。）。 L(G)L(G)為為PSLPSL。 上下文有關(guān)文法上下文有關(guān)文法( (CSG)CSG) 若產(chǎn)生式集合中所有若產(chǎn)生式集合中所有， 除除 外，則是型文法外，則是型文法 即：上下文有關(guān)文法（即：上下文有關(guān)文法（CSGCSGContext Context Sensitive GrammarSensitive Grammar） L(G)L(G)為為1 1型

27、型/ /上下文有關(guān)上下文有關(guān)/ /敏感語言敏感語言( (CSL)CSL)上下文無關(guān)文法上下文無關(guān)文法( (CFG)CFG) 若若 N N，(N NT T) )* *，則則 是型文法是型文法 即：上下文無關(guān)文法即：上下文無關(guān)文法( (CFG: Context Free CFG: Context Free Grammar)Grammar) L(G)L(G)為為2 2型型/ /上下文無關(guān)語言（上下文無關(guān)語言（CFLCFL） CFGCFG能描述程序設(shè)計(jì)語言的多數(shù)語法成分能描述程序設(shè)計(jì)語言的多數(shù)語法成分例例2-3 2-3 標(biāo)識(shí)符的文法標(biāo)識(shí)符的文法2 2 S L|LTS L|LTT L|N|TL|TN T

28、 L|N|TL|TN L a|b|c|dL a|b|c|dN 0|1|2|3|4|5N 0|1|2|3|4|5正則文法正則文法( (RG)RG) 設(shè)、設(shè)、N N，T T或?yàn)榛驗(yàn)?右線性右線性( (Right Linear)Right Linear)文法：文法：或或 左線性左線性( (Left Linear)Left Linear)文法：文法：或或 都是型文法都是型文法( (正規(guī)文法正規(guī)文法 Regular Grammar -RG)Regular Grammar -RG) L(G)L(G)為為3 3型型/ /正規(guī)集正規(guī)集/ /正則集正則集/ /正則語言（正則語言（RLRL）能描述程序設(shè)計(jì)語言的多

29、數(shù)單詞能描述程序設(shè)計(jì)語言的多數(shù)單詞左、右線性文法不可混用左、右線性文法不可混用例例 非非CFLCFL的文法的文法L=aL=an nb bn nc cn n|n0|n0的文法的文法S SaBC|aSBCaBC|aSBCCBCBBCBCaBaBababbBbBbbbbbCbCbc bc 在我們使用的程序設(shè)計(jì)語言中在我們使用的程序設(shè)計(jì)語言中, ,有些語言結(jié)有些語言結(jié)構(gòu)不能用上下文無關(guān)文法來描述。構(gòu)不能用上下文無關(guān)文法來描述。 例例2.2.4 L4 L1 1=wcw|wa,b=wcw|wa,b+ + 。例例, ,aabcaabaabcaab就就是是L L1 1的一個(gè)句子。這個(gè)語言是檢查程序中標(biāo)的一個(gè)句

30、子。這個(gè)語言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。識(shí)符的聲明應(yīng)先于引用的抽象。 例例2.2.5 L5 L2 2=a=an nb bm mc cn nd dm m|n,m0|n,m0，它是檢查過，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。否一致問題的抽象。非上下文無關(guān)的語言結(jié)構(gòu)非上下文無關(guān)的語言結(jié)構(gòu)ChomskyChomsky體系體系總結(jié)總結(jié) = ( = (T T，N N，) )是一個(gè)文法是一個(gè)文法, , P P* * G G是是0 0型文法，型文法，L(G)L(G)是是0 0型語言；型語言； -其能力相當(dāng)于圖靈機(jī)其能力相當(dāng)于圖靈

31、機(jī)* * | |:G|:G是是1 1型文法，型文法，L(G)L(G)是是1 1型語言型語言( (除除);); -其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)* * N N : G : G是是2 2型文法，型文法，L(G)L(G)是是2 2型語言型語言; ; -其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)* * AaBAaB或或Aa: Aa: G G是右線性文法，是右線性文法，L(G)L(G)是是3 3型語言型語言ABaABa或或AA: : G G是左線性文法，是左線性文法，L(G)L(G)是是3 3型語言型語言 -其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī)其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī)文法的類型文

32、法的類型四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。四種文法之間的逐級(jí)四種文法之間的逐級(jí)“包含包含”關(guān)系如下：關(guān)系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法范式范式Backus-Naur FormBackus-Naur FormBackus-Normal FormBackus-Normal Form 表示為表示為 非終結(jié)符用非終結(jié)符用“ ”括起來括起來 終結(jié)符：基本符號(hào)集終結(jié)符：基本符號(hào)集 其他其他 (1 1|2 2|n n)1 1|2 2|n n | | 范式范式Backus Normal FormBackus No

33、rmal Form 例例 簡(jiǎn)單算術(shù)表達(dá)式簡(jiǎn)單算術(shù)表達(dá)式( (只寫產(chǎn)生式只寫產(chǎn)生式) ) + * * () idid 即： +| * * |(|()|)|idid 哪些是終結(jié)符？哪些是變量？哪些是終結(jié)符？哪些是變量？例例2-2-6 6 句子結(jié)構(gòu)的表示句子結(jié)構(gòu)的表示 ( (文法文法EE+E|EEE+E|E* *E|(E)|idE|(E)|id ）2.5 2.5 CFGCFG的分析樹的分析樹Parse TreeParse Tree 用樹的形式表示句型的生成用樹的形式表示句型的生成 樹根：樹根： 開始符號(hào)開始符號(hào) 中間結(jié)點(diǎn)：中間結(jié)點(diǎn)： 非終結(jié)符非終結(jié)符 葉結(jié)點(diǎn)：葉結(jié)點(diǎn)： 終結(jié)符或者非終結(jié)符終結(jié)符或者非

34、終結(jié)符 每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子一個(gè)二級(jí)子樹一個(gè)二級(jí)子樹- -直接短語直接短語 又稱為語法分析樹又稱為語法分析樹EE+TT+TF+T a1+T a1+T*F a1+F * F a1+a2 *FE+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*Fa1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a3EE+TTFa1T*FFa2a3a1+a2 *a3短語短語 二義性文法與先天二義性語言二義性文法與先天二義性語言 對(duì)同一句子存在兩棵語法分析樹對(duì)

35、同一句子存在兩棵語法分析樹 在理論上不可判定在理論上不可判定 1. 描述一個(gè)句子的文法不是唯一的；描述一個(gè)句子的文法不是唯一的； 2. 對(duì)于一個(gè)句子的分析應(yīng)是唯一的。對(duì)于一個(gè)句子的分析應(yīng)是唯一的?？紤]表達(dá)式下面的文法考慮表達(dá)式下面的文法 GE,其產(chǎn)生式如下：其產(chǎn)生式如下： EE+E E*E (E) a 對(duì)于句子對(duì)于句子a+a*a, 有如下兩個(gè)最左推導(dǎo)：有如下兩個(gè)最左推導(dǎo)： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a文法的二義性文法的二義性 EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*E

36、a+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推導(dǎo)最左推導(dǎo) EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推導(dǎo)最右推導(dǎo)如果一個(gè)文法的句子存在兩棵分析樹如果一個(gè)文法的句子存在兩棵分析樹,那么那么,該句子該句子是二義性的。如果一個(gè)文法包含二義性的句子是二義性的。如果一個(gè)文法包含二義性的句子,則則稱這個(gè)文法是二義性的稱這個(gè)文法是二義性的; 否則，該否則，該文法是無二義性文法是無二義性的。幾點(diǎn)說明：的。幾點(diǎn)說明：1 . 一般來說，程序語言存在無二義性文法，一般來說，程序語言存在

37、無二義性文法， 對(duì)于對(duì)于表達(dá)式來說，文法（表達(dá)式來說，文法（2 .1）是二義性的。對(duì)于條件）是二義性的。對(duì)于條件語句，經(jīng)常使用二義性文法描述它：語句，經(jīng)常使用二義性文法描述它：S if expr then S if expr then S else S other二義性的句子二義性的句子: if e1 then if e2 then s1 else s2 二義性（歧義性，二義性（歧義性，ambiquity)ambiquity)的定義的定義 下面是下面是 Smatched_s unmatched_s matched_s if expr then matched_s else matched_s other unmatched