編譯原理第2章-文法和語言

1、Compiler Construction Principles第二章 文法和語言的基本知識 形式語言理論是編譯的重要理論基礎(chǔ)。本章主要介紹編譯理論中用到的有關(guān)形式語言理論的最基本概念最基本概念，重點介紹如何采用形式化的方法描述程序設(shè)計語言。Compiler Construction Principles第二章 文法和語言的基本知識q字母表和符號串字母表和符號串q文法和語言的形式定義文法和語言的形式定義q短語、直接短語和句柄短語、直接短語和句柄q語法樹和文法的二義性語法樹和文法的二義性q文法和語言的分類文法和語言的分類Compiler Construction Principles2.0 概

2、述 對程序設(shè)計語言的描述是從語法、語義和語用三個因素來考慮。語法是對語言結(jié)構(gòu)的定義。 語用則是從使用的角度去描述語言。語義是描述了語言的含義。Compiler Construction Principles2.0 概 述例如例如 賦值語句賦值語句s s2 2* *3.14163.1416* *r r* *(r+h)(r+h)的的 非形式化的描述為：非形式化的描述為：語法：賦值語句由一個變量，后隨一個賦 值號“”，再在其后面跟一個表達式構(gòu)成。語義：首先計算語句右部表達式的值，然后把所得結(jié)果送給左部變量中。語用：賦值語句可用來計算和保存表達式的值。Compiler Construction Pri

3、nciples2.0 概概 述述 這種非形式化的描述,不夠清晰和準(zhǔn)確,為了精確定義和描述程序設(shè)計語言,需采用形式化的方法。所謂形式化的方法,是用一整套帶有嚴(yán)格規(guī)定的符號體系來描述問題的方法。 形式語言理論是編譯的重要理論基礎(chǔ)。重點介紹如何采用形式化的方法描述程序設(shè)計語言。 Compiler Construction Principles2.1 字母表和符號串字母表和符號串元素的非空有窮集合。例如，= a, b, c 1. 字母表 根據(jù)字母表的定義，是字母表，它由a、b、c三個元素組成。Compiler Construction Principles2.1 字母表和符號串字母表和符號串 是一個字

4、母表，由0、1兩個元素組成。注意:例如， =0, 1 (2) 字母表中的元素, 可以是字母、數(shù)字或其他符號。(1) 字母表中至少包含一個元素。Compiler Construction Principles2.1 字母表和符號串字母表和符號串 字母表中的元素稱為符號或稱為字符。例如，前述例子中2. 符號（字符）a、b、c 是字母表中的符號；0、1 是字母表中的符號。Compiler Construction Principles2.1 字母表和符號串字母表和符號串 例如，設(shè)有字母表= a, b, c 符號的有窮序列稱為符號串。 符號串總是建立在某個特定字母表上的且只由字母表上的有窮多個符號組成

5、。 則有符號串 a，b，ab，ba， cba， abc 3. 符號串（字）Compiler Construction Principles2.1 字母表和符號串字母表和符號串說明說明: :不包含任何符號的符號串, 稱為空符號串，用表示。符號串中符號的順序是很重要的。ab和ba是字母表上的兩個不同的符號串?？辗柎?個符號組成，其長度| |=0|=0Compiler Construction Principles2.2 符號串的運算 設(shè)x和y是符號串，則串xy稱為它們的連結(jié)。則XYABC10A，YX10AABC。注意：對任意一個符號串x，1. 符號串的連結(jié)符號串的連結(jié)例如，設(shè)XABC，Y10A

6、我們有 xxx。Compiler Construction Principles2.2 符號串的運算2. 集合的乘積集合的乘積 設(shè)A和B是符號串的集合, 則A和B的乘積定義為： 集合的乘積是滿足于 xA, yB的所有符號串 xy 所構(gòu)成的集合。AB=xy | xA, yBCompiler Construction PrinciplesA=A=A2.2 符號串的運算例如：設(shè)A= a, b , B= c, d 則AB= ac, ad, bc, bd 由于對任意的符號串x，總有x=x=x所以, 對任意集合A, 我們有:Compiler Construction Principles2.2 符號串的運

7、算 特別指出的是， 是符號串, 不是集合，而表示由空符號串 所組成的集合, 但這樣的集合不是空集合= 。Compiler Construction Principles2.2 符號串的運算 3. 符號串的冪運算符號串的冪運算 設(shè)x是符號串, 則x的冪運算定義為： x0= x1= x x2= xx x3= xxx xn= xx x=x xn-1(n0)n注意：x0 1Compiler Construction Principles2.2 符號串的運算例如, 設(shè) xabc 則x0= x1=abcx2=xx=abcabc Compiler Construction Principles2.2 符號串

8、的運算 4. 集合的冪運算集合的冪運算 設(shè)A是符號串的集合，則集合A的冪運算定義為：A0=A1=AA2=AA An= AA A=AAn-1(n0)nCompiler Construction Principles2.2 符號串的運算例如，設(shè)A= a, b ，則A0=A1=A= a, b A2=AA= aa, ab, ba, bb A3=AAA=A2A= aaa, aab, aba, abb, baa, bab, bba, bbb Compiler Construction Principles2.2 符號串的運算5. 集合集合A的正閉包的正閉包A與閉包與閉包A* 設(shè)A是符號串的集合，則A的正閉

9、包A和A的閉包A*的定義為:A+=A1A2 An A*= A0 A1A2 An =A+Compiler Construction Principles2.2 符號串的運算 可見,集合A的正閉包表示A上元素a,b構(gòu)成的所有符號串的集合,集合A的閉包比集合A的正閉包多含一個空符號串。例如，設(shè)A= a, b , 則：A+= a, b, aa, ab, ba, bb, aaa, aab, A*= , a, b, aa, ab, ba, bb, aaa, aab, Compiler Construction Principles2.3 文法和語言的形式定義 每個形式語言都是某個字母表上按某種規(guī)則構(gòu)成的所

10、有符號串的集合。反之，任何一個字母表上符號串的集合均可定義為一個形式語言。形式語言形式語言序列的集合稱為形式語言。Compiler Construction Principles2.3 文法和語言的形式定義 對每個具體語言,都有語法和語義兩個方面，形式語言是指不考慮語言的具體意義，即不考慮語義。 Compiler Construction Principles2.3 文法和語言的形式定義形式語言的描述形式語言的描述 對形式語言的描述有兩種方法，一種方法是當(dāng)語言為有窮集合時，用枚舉法來表示語言。 Compiler Construction Principles2.3 文法和語言的形式定義 均表示

11、字母表A上的一個形式語言。由于這三個語言均是有限符號串的集合，因此，可枚舉出其全部句子來表示該語言。 例如，設(shè)有字母表A= a, b, c ，則L1= a, b, c L2= a, aa, ab, ac L3= c, cc Compiler Construction Principles2.3 文法和語言的形式定義例如，設(shè)字母表= 0, 1 , 則+=123= 0, 1, 00, 10, 11, 01, 000, 100, 當(dāng)語言為無窮集合時，用文法來描述語言。 Compiler Construction Principles2.3 文法和語言的形式定義 下面用A表示+，用式子A0表示符號串0

12、A或A生成符號串0，符號“”讀作“生成”或“由組成”。則集合A可表示成： A0A1AA0AA1+=123= 0, 1, 00, 10, 11, 01, 000, 100, Compiler Construction Principles2.3.1 文法的形式定義 規(guī)則是一個符號與一個符號串的有序?qū)Γˋ,），通常寫作： A（或A ) 1.1. 規(guī)則規(guī)則 也稱產(chǎn)生式也稱產(chǎn)生式 規(guī)則的作用是告訴我們?nèi)绾斡靡?guī)則中的符號串生成語言中的序列。Compiler Construction Principles2.3.1 文法的形式定義 例如，前述例中一組規(guī)則 描述的語言序列只可能是由0和1組成的符號串。A0A

13、1AA0AA1Compiler Construction Principles2.3.1 文法的形式定義 規(guī)則中出現(xiàn)的符號分為兩類，一類是終結(jié)符號，另一類是非終結(jié)符號。 非終結(jié)符號是出現(xiàn)在規(guī)則左部能派生出符號或符號串的那些符號，即每個非終結(jié)符號表示一定符號串的集合，用大寫字母表示或用尖括號把非終結(jié)符號括起來。例如，上例中的A。Compiler Construction Principles2.3.1 文法的形式定義 終結(jié)符號是不屬于非終結(jié)符號的那些符號, 它是組成語言的基本符號，是一個語言的不可再分的基本符號，通常用小寫字母表示。 例如，上例中的0和1。 Compiler Constructi

14、on Principles2.3.1 文法的形式定義 規(guī)則的非空有窮集合，通常表示成四元組VN是規(guī)則中非終結(jié)符號的集合。VT是規(guī)則中終結(jié)符號的集合。P 是文法規(guī)則的集合。 2. 文法文法G=VN,VT, P, S Compiler Construction Principles2.3.1 文法的形式定義 S 是一個非終結(jié)符號，稱為文法的開始符號或文法的識別符號，它至少要在一條規(guī)則中作為左部出現(xiàn)。由它開始，識別出我們所定義的語言。 由文法定義可知，文法是對語言結(jié)構(gòu)的定義和描述，文法四大要素中關(guān)鍵是規(guī)則的集合。 Compiler Construction Principles2.3.1 文法的形式

15、定義將它們縮寫為：A1 | 2 | | nA1A2An 其中每個i有時也稱為是A的一個候選式。 為了書寫方便，對于若干個左部相同的規(guī)則，如Compiler Construction Principles2.3.1 文法的形式定義我們約定： 第一條規(guī)則的左部是識別符號。 對文法G不用四元式顯示表示，僅 只將規(guī)則寫出。 Compiler Construction Principles2.3.1 文法的形式定義 G=(VN，VT，P，S )VN=AVT=0，1P: A 0 | 1 | A0 | A1S=A前例中描述+的文法是:Compiler Construction Principles2.3.1

16、 文法的形式定義 例1 設(shè)字母表=a, b，試設(shè)計一個文法，描述語言 L= a2n, b2n | n1 分析 設(shè)計一個文法來描述一個語言, 關(guān)鍵是設(shè)計一組規(guī)則生成語言中的符號串。因此，為設(shè)計該語言文法，必須分析這個語言是由怎樣一些符號串組成的，即首先分析語言中串的結(jié)構(gòu)特征： Compiler Construction Principles2.3.1 文法的形式定義當(dāng)n1 L=aa, bb L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, 即語言L是由偶數(shù)個a，偶數(shù)個b這樣的符號串組成的集合。 L=a2n, b2n | n1當(dāng)n2 L=aaaa, bbbb當(dāng)n3 L=a

17、aaaaa, bbbbbbCompiler Construction Principles2.3.1 文法的形式定義因此，定義語言L的文法 G=( VN，VT，P，S )其中： VN=A, B, DVT=a, bP= Aaa S=ABaa Dbb | bbD | bb | bbD注意:VTaa,bb | aaB| aaBCompiler Construction Principles2.3.1 文法的形式定義 提出問題: 描述該語言的文法是否唯一呢？ 顯然，G不同于G。由此可見，對于一個給定的語言，描述該語言的文法是不唯一的。 P : AB | DBaa | aBaDbb | bDbCompi

18、ler Construction Principles 若G和G是兩個不同的文法，如果它們描述的語言相同，那么，稱G和G 為等價文法。2.3.1 文法的形式定義Compiler Construction Principles描述該語言的文法是否G？2.3.1 文法的形式定義 對此例，我們提出下面這樣一個問題： G=( A, a, b, P, A )P= Aaa | bb | Aaa | Abb Compiler Construction Principles 對于文法G來說，它所產(chǎn)生的有些符號串，如aabb，bbaa， 不屬于語言L，即設(shè)計的文法超出了所定義語言的范圍。 2.3.1 文法的形式

19、定義P= Aaa | bb | Aaa | Abb Compiler Construction Principles2.3.1 文法的形式定義 例2 試設(shè)計一個表示所有標(biāo)識符的文法 分析 題意是用文法定義標(biāo)識符，必須確定P中規(guī)則。為了設(shè)計出一組規(guī)則，首先應(yīng)搞清楚集合中串的結(jié)首先應(yīng)搞清楚集合中串的結(jié)構(gòu)特征構(gòu)特征。Compiler Construction Principles2.3.1 文法的形式定義 用I代表標(biāo)識符；L代表字母；D代表數(shù)字; 則定義標(biāo)識符的文法為： 字母 字母或數(shù)字串標(biāo)識符的結(jié)構(gòu)可用下圖表示:Compiler Construction Principles2.3.1 文法的形式

20、定義 G=(VN，VT，P，S)其中： VN=I, L, DVT=a,b,c, x,y,z,0,1,2, ,9P= IL S=ILa | b | c | | x | y | zD0 | 1 | 2 | 3 | | 9 | I L| I DCompiler Construction Principles2.3.1 文法的形式定義 若將定義標(biāo)識符的文法設(shè)計成： 其中 VN，VT ，S 同上 G=(VN，VT，P，S )P= IL | I DLa | b | c | |x|y|zD0 | 1 | 2 | 3 | |9 Compiler Construction Principles2.3.1 文法的

21、形式定義 該文法不能定義ab，abc 僅由字母串組成的標(biāo)識符，縮小了所定義語言的范圍。 P= IL | I DLa | b | c | |x|y|zD0 | 1 | 2 | 3 | |9 Compiler Construction Principles2.3.1 文法的形式定義 用I代表標(biāo)識符；L代表字母；D代表數(shù)字；T代表字母數(shù)字串；則定義標(biāo)識符的文法還可寫為： 字母 字母或數(shù)字串Compiler Construction Principles2.3.1 文法的形式定義P: IL | LT TL | D | LT | DT La | b | c | |x|y|z D0 | 1 | 2 | 3

22、 | | 9 字母 字母或數(shù)字串Compiler Construction Principles2.3.1 文法的形式定義 例3 用文法定義一個含、*的算術(shù)表達式，定義用下述自然語言描述： 變量是一個表達式； 若 E1和 E2是算術(shù)表達式, 則 E1E2、E1*E2、(E1) 也是算術(shù)表達式。 Compiler Construction Principles2.3.1 文法的形式定義 分析 算術(shù)表達式的定義用自然語言描述，這是對算術(shù)表達式的非形式定義，題意用文法來定義算術(shù)表達式，即是用形式化的方法定義表達式。定義算術(shù)表達式的文法為： G=(E, i, +, *, (, ) , P, E )其中

23、P為：Ei | E+E | E*E | (E)Compiler Construction Principles2.3.1 文法的形式定義P為：Ei | E+E | E*E | (E) i, i+i, i*i, i+i*i, (i+i), 注意：是符號串的集合Compiler Construction Principles2.3.1 文法的形式定義 例4 設(shè)字母表 = a, b , 試設(shè)計一個文法，描述語言 L= abna | n0 分析 該語言中串的結(jié)構(gòu)特征是 當(dāng)n1 L= aba L= aa, aba, abba, 當(dāng)n2 L= abba 當(dāng)n0 L= aa (b0=)Compiler Co

24、nstruction Principles2.3.1 文法的形式定義所以定義語言的文法為： G=( A, B, a, b, P, A )P= AaBa BBb | L= aa, aba, abba, Compiler Construction Principles2.3.1 文法的形式定義 例5 設(shè)字母表= (, ) ,試設(shè)計一個文法描述語言 L= (n )n | n0分析 該語言中串的結(jié)構(gòu)特征是 當(dāng)n=0 L= 注: (0 )0= 當(dāng)n=1 L= ( ) 當(dāng)n=2 L= ( ) L= , ( ), ( ), ( ), Compiler Construction Principles2.3.1

25、 文法的形式定義P: S | ( S )所以定義語言的文法為： L= (n )n | n0Compiler Construction Principles2.3.2 語言的形式定義 1. 直接推導(dǎo) 令G是一文法，我們稱 xAy直接推導(dǎo)出 xy ，即 xAyxy 僅 A 是 G 的一條規(guī)則, 且 x, y(VNVT)*。也就是說從符號串 xAy 直接推導(dǎo)出 xy 僅使用一次規(guī)則。 Compiler Construction Principles2.3.2 語言的形式定義例如，設(shè)有文法GS: S01 使用規(guī)則 S01 此時 x， yP為：S 0 1 | 0 S 1 有如下直接推導(dǎo)：S0S1 使用規(guī)

26、則 S0S1 此時 x， yCompiler Construction Principles2.3.2 語言的形式定義 0S10011 使用規(guī)則 S01 此時 x0， y1 00S11000S111 使用規(guī)則 S0S1 此時 x00 , y11 000S11100001111 使用規(guī)則 S01 此時 x000 y111S 0 1 | 0 S 1Compiler Construction Principles2.3.2 語言的形式定義 (1) 形式上的區(qū)別，推導(dǎo)用“”表示，規(guī)則用“”表示 。 (2) 對文法G中任何規(guī)則A，我們有A，即推導(dǎo)的依據(jù)是規(guī)則。 注意推導(dǎo)和規(guī)則的區(qū)別：Compiler C

27、onstruction Principles即表示從0 出發(fā)，經(jīng) 一步或若干步 或者說 使用若干次規(guī)則可推導(dǎo)出 n。 2.3.2 語言的形式定義 如果存在一個直接推導(dǎo)序列： 則我們稱這個序列是一個從0至n的長度為n的推導(dǎo)，記為 2推導(dǎo)0 1 2 n+0 nCompiler Construction Principles2.3.2 語言的形式定義 例如 設(shè)有文法GE=(E,T,F,i,+,*,(,),P,E)對 i+i*i 有如下直接推導(dǎo)序列: 我們可記為 其中P為：EE+T | TTT*F | FF(E) | iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEi+i*i+C

28、ompiler Construction Principles2.3.2 語言的形式定義 3廣義推導(dǎo) 我們有： 0n表示從0出發(fā)，經(jīng)0步或若干步， 可推導(dǎo)出n。* 也就是說0n意味著0n或者0=n。*+EE*Ei+i*i*對上例 EE+T | T TT*F | F F(E) | iCompiler Construction Principles2.3.2 語言的形式定義 區(qū)別：直接推導(dǎo)的長度為1，推導(dǎo)的長度大于等于1，而廣義推導(dǎo)的長度大于等于0。 Compiler Construction Principles2.3.2 語言的形式定義 4. 句型和句子 設(shè)有文法GS（S是文法G的開始符號）

29、如果S x, x (VNVT)* 則稱符號串x 為文法GS的句型。* 如果S x, x VT* 則稱符號串x為文法 GS的句子。*Compiler Construction Principles2.3.2 語言的形式定義 例1 設(shè)有文法GS： 我們有: 顯然，符號串01、0S1、00S11和000111 都是文法GS的句型，而01和000111又是文法GS的句子。 S01 | 0S1S 01*S 0S1*S 00S11*S 000111*Compiler Construction Principles2.3.2 語言的形式定義 例2 設(shè)有文法GE： 試證明符號串 (i*i+i) 是文法GE的一

30、個句子。 分析 只要證明符號串 (i*i+i) 對文法 G存在一個推導(dǎo)，就可證明符號串 (i*i+i) 是文法GE的一個句子。 EE+E | E*E | (E) | iCompiler Construction Principles2.3.2 語言的形式定義 EE+E | E*E | (E) | iE(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i) 即有 E(i*i+i), 所以符號串(i+i*i)是文法 GE的一個句子。 *Compiler Construction Principles（2）L(G)是VT* 的子集。即屬于VT* 的符 號串 x 不一定屬于L(G)。

31、2.3.2 語言的形式定義 5語言 文法GS產(chǎn)生的所有句子的集合稱為文 法G所定義的語言,記為L(GS)： 由語言定義可知：（1）一當(dāng)文法給定，語言也就確定。L(GS)=x|Sx且xVT*Compiler Construction Principles2.3.2 語言的形式定義 例3 設(shè)有文法GS ：S01 | 0S1求該文法所描述的語言是什么？ 分析 由識別符號S出發(fā)，將推出一些什么樣的句子，也就是說，L(GS)將由什么樣的一些符號串所組成的集合，找出其中的規(guī)律，用式子或自然語言描述出來。 Compiler Construction Principles2.3.2 語言的形式定義 我們應(yīng)用第

32、二個規(guī)則n1次，然后再應(yīng)用第一個規(guī)則1次，有： S0S100S110n-1S1n-10n1n即S0n1n*可見，此文法定義的語言為L(GS)= 0n1n | n1S01 | 0S1Compiler Construction Principles2.3.2 語言的形式定義 例4 設(shè)有文法GS：S0S | 1S |該文法所定義的語言是什么？ 由該文法所確定的語言為 L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* Compiler Construction Principles2.3.2 語言的形式定義 例5 設(shè)有文法GA： 該文法所定義的語言是什么？ 分析 從文

33、法開始符號A出發(fā)可推導(dǎo)出以y開頭后面跟一個或多個x結(jié)尾的符號串，所以該文法定義的語言為AyBB xB | xL(GA)= yxn | n1Compiler Construction Principles2.3.2 語言的形式定義 由此可見，從已知文法確定語言的中心思想是：從文法的開始符號出發(fā)，反復(fù)連續(xù)地使用規(guī)則替換、展開非終結(jié)符，找出句子的規(guī)律，用式子或自然語言描述出來。 Compiler Construction Principles2.3.2 語言的形式定義 形式語言理論可以證明如下兩點：(1) 給定一種語言，能確定其文法，但這種文法不是唯一的，即：LG1或G2或(2) 給定一個文法，就能

34、從結(jié)構(gòu)上唯一確定其語言，即：GL(G)；Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約 文法和語言是密切相關(guān)的，文法所定義的任一句型和句子, 都可以根據(jù)文法推導(dǎo)出來。我們提出一個問題：這種推導(dǎo)過程是否唯一？這種推導(dǎo)過程是否唯一？Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約 同一個句型(句子)可以通過不同的推導(dǎo)序列推導(dǎo)出來，這是因為在推導(dǎo)過程中與所選擇非終結(jié)符的次序無關(guān)。Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約例如，設(shè)有文法GN1 N1NNND

35、| DD0 | 1 | 2 N1NNDN2D212 N1NNDDD1D12 N1NNDDDD212句子12有下列三種不同的推導(dǎo)序列:Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約 最左(最右)推導(dǎo)，是指對于一個推導(dǎo)序列中的每一步直接推導(dǎo) , 都是對 中的最左(最右)非終結(jié)符進行替換。 最右推導(dǎo)也稱為規(guī)范推導(dǎo)，用規(guī)范推導(dǎo)推導(dǎo)出的句型稱為規(guī)范句型。 Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約 例 設(shè)有文法GS: 請給出句子101001的最右、最左推導(dǎo)。 分析 最右推導(dǎo)是指在推導(dǎo)過程中任何一步 (和是

36、句型)，都是對中的最右非終結(jié)符進行替換。SABAA0 | 1BB0 | S1Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約SABAS1AAB1AA01A1B01A10011B1001101001句子101001的最右推導(dǎo)為: SABAA0 | 1BB0 | S1Compiler Construction Principles2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約 最左推導(dǎo)是指在推導(dǎo)過程中任何一步 (和是句型), 都是對的最左非終結(jié)符進行替換。句子101001的最左推導(dǎo)為： SABAA0 | 1BB0 | S1SAB1BB10B10S110AB1101BB

37、11010B1101001Compiler Construction Principles2.3.3 2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約歸約是與推導(dǎo)相對的概念，推導(dǎo)是把句型中的非終結(jié)符用規(guī)則的一個右部來替換的過程，而歸約則是把句型中的某個子串用一個非終結(jié)符來替換的過程。 若用表示歸約，設(shè)A是文法G中的 一個規(guī)則，則我們有： .xAyxyxyxAy.Compiler Construction Principles2.3.3 2.3.3 規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約例如，例文法GN1中有規(guī)范推導(dǎo)： 則有規(guī)范歸約： 規(guī)范推導(dǎo)的逆過程，稱為最左歸約，也稱為規(guī)范歸約。 N1NNDN

38、2D21212D2.N2.ND.N.N1.Compiler Construction Principles2.3.4 遞歸規(guī)則與文法的遞歸性遞歸規(guī)則 如果文法中有規(guī)則 AA 稱為規(guī)則左遞歸。 如果文法中有規(guī)則 A A 稱為規(guī)則右遞歸。 如果文法中有規(guī)則 A A 稱為規(guī)則遞歸。Compiler Construction Principles2.3.4 遞歸規(guī)則與文法的遞歸性文法的遞歸性若文法中有推導(dǎo)AA 稱文法左遞歸。+若文法中有推導(dǎo)A A稱文法右遞歸。+若文法中有推導(dǎo)A A 稱文法遞歸。+Compiler Construction Principles2.3.4 遞歸規(guī)則與文法的遞歸性例如 文

39、法中有如下規(guī)則： 這三條規(guī)則都不是遞歸規(guī)則，但有 在文法中使用遞歸規(guī)則，使得我們能用有限的規(guī)則去定義無窮集合的語言。 UVxVUy | zUVx Uyx , 則該文法是左遞歸的。Compiler Construction Principles2.3.4 遞歸規(guī)則與文法的遞歸性 例2 考慮文法GA： 由于該文法無遞歸性，由它所描述的語言是有窮的。該文法描述的語言為: AaB | bBBa | bL(GA)= aa, ab, ba, bb Compiler Construction Principles 2.3.4 遞歸規(guī)則與文法的遞歸性例3 考慮文法GN1 該文法有直接左遞歸規(guī)則 NND, 則稱

40、該文法為左遞歸文法或說文法左遞歸，其定義的語言為0,1,2+。 N1NNND | DD0 | 1 | 2Compiler Construction Principles 2.3.4 遞歸規(guī)則與文法的遞歸性 也就是說，當(dāng)一個語言是無窮集合時，則定義該語言的文法一定是遞歸的。 若不用遞歸規(guī)則，則 NND 需要用 ND | DD | DDD | 即無窮多條規(guī)則來定義由數(shù)字0,1,2 組成的所有無符號整數(shù)。 Compiler Construction Principles2.4 文法的類型 著名的語言學(xué)家喬姆斯基(Chomsky) 將文法和語言分為四大類，即0型、1型、 2型、3型。劃分的依據(jù)是對文法

41、中的規(guī) 則施加不同的限制。 Compiler Construction Principles2.4 文法和語言的分類 0型文法（無限制文法） 若文法G=(VN,VT, P, S)中的每條規(guī)則 是這樣一種結(jié)構(gòu)： 而且中至少含一個非終結(jié)符, 則稱G 是0型文法。(VNVT)+ , (VNVT)*0型文法描述的語言是0型語言。0型文法沒有加任何限制條件，又稱為 無限制性文法，相應(yīng)的語言稱為無限制 性語言。0型語言由圖靈機識別。Compiler Construction Principles2.4 文法和語言的分類 例如，有0型文法G=(VN,VT, P, S) 其中：VN=A,B,S , VT=0,

42、1 其描述的 0 型語言為 L0(GS)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0BCompiler Construction Principles2.4 文法和語言的分類 1型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法， 相應(yīng) 的語言又稱為上下文有關(guān)語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： , (VNVT)* ,AVN ,則稱G是1型文法。1型文法描述的語言是1型語言。1型語言由線性界限自動機識別。 (VNVT)+Compiler Construction Principles2.4 文法和語言的分類 例

43、如，有1型文法G=(VN,VT, P, S) 其中：VN=S,A,B , VT=a,b,c P: S aSAB | abB BA BA BA AA AA AB bA bb bB bc cB cc其描述的1型語言為L1(GS)=anbncn | n1 Compiler Construction Principles2.4 文法和語言的分類 2型文法（上下文無關(guān)文法） 2型文法又稱上下文無關(guān)文法，其產(chǎn)生的 語言又稱為上下文無關(guān)的語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： AVN ,(VNVT)*則稱G是2型文法。2型文法描述的語言是2型語言。2型語言由下推

44、自動機識別。Compiler Construction Principles例如前面描述算術(shù)表達式的文法GE:EE+E | E*E | (E) | i2.4 文法和語言的分類 Compiler Construction Principles 其描述的語言為 L2(GS)=x | x a, b+ 且x中a和b的個數(shù)相同 例如，有2型文法G=(VN,VT, P, S) 其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.4 文法和語言的分類 Compiler Construction Principles2.4

45、文法和語言的分類 3型文法（正規(guī)文法） 右線性文法和左線性文法都稱為3型文法。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的形式 為A aB 或 A a , 其中： A , BVN, a VT*, 則稱G是右線性文法。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的形式 為A Ba 或 A a , 其中： A , BVN , a VT*, 則稱G是左線性文法。3型文法描述的語言是3型語言。3型語言由有窮自動機識別。 3型文法也稱正規(guī)文法。正規(guī)文法產(chǎn)生的語言 稱為正規(guī)語言。Compiler Construction Principles 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義標(biāo)

46、識符 2.4 文法和語言的分類 用I代表標(biāo)識符; l代表任意一個字母; d代表任意一個數(shù)字; 則定義標(biāo)識符的文法為：左線性文法: P: I l | Il | Id右線性文法: P: I l | lT Tl | d | lT| dTCompiler Construction Principles 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義無符號整數(shù)2.4 文法和語言的分類 用N代表無符號整數(shù); d代表任意一個數(shù)字；則定義的無符號整數(shù)文法為：左線性文法: P: N Nd | d右線性文法: P: N dN | dCompiler Construction Principles2.4 文法和語言的分

47、類 由上述四類文法的定義可知, 從0型文法到3型文法, 是逐漸增加對規(guī)則的限制條件而得到的，因此每一種正規(guī)文法都是上下文無關(guān)的文法，每一種上下文無關(guān)的文法都是上下文有關(guān)的文法，而每一種上下文有關(guān)的文法都是0型文法, 而由它們所定義的語言類是依次縮小的，有 L0 L1 L2 L3 。 Compiler Construction Principles2.4 文法和語言的分類2型文法型文法1型文法型文法0型文法型文法四種四種文法文法之間之間的的逐級逐級“包含包含”關(guān)系關(guān)系3型文法型文法Compiler Construction Principles2.5 上下文無關(guān)文法與語法樹上下文無關(guān)文法有足夠的

48、能力描述程序設(shè)計語言的語法結(jié)構(gòu)上下文無關(guān)文法有足夠的能力描述程序設(shè)計語言的語法結(jié)構(gòu)描述簡單算術(shù)表達式的文法G=(E,+,*,i,(,),P,E)其中P為：Ei , EE+E , EE*E , E(E) 描述一種簡單賦值語句的產(chǎn)生式：賦值語句i =E描述條件語句的產(chǎn)生式：條件語句if條件then語句 if條件then語句else語句Compiler Construction Principles2.5 上下文無關(guān)文法與語法樹1.規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約Gs: SaAS ASbA ASS Sa Aba構(gòu)造句子構(gòu)造句子aabbaa推導(dǎo)過程推導(dǎo)過程推導(dǎo)過程一：推導(dǎo)過程一：S aAS aAa

49、 aSbAa aSbbaa aabbaa推導(dǎo)過程二：推導(dǎo)過程二：S aAS aSbAS aabAS aabbaS aabbaa推導(dǎo)過程三：推導(dǎo)過程三：S aAS aSbAS aSbAa aabAa aabbaaCompiler Construction Principles2.5 上下文無關(guān)文法與語法樹1.規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約最左（最右）推導(dǎo)：最左（最右）推導(dǎo)：在推導(dǎo)的任何一步在推導(dǎo)的任何一步，其中，其中、是句型，都是對是句型，都是對中中的最左（右）非終結(jié)符進行替換的最左（右）非終結(jié)符進行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型由規(guī)范

50、推導(dǎo)所得的句型稱為規(guī)范句型練習(xí)：設(shè)有文法練習(xí)：設(shè)有文法GE： EE+T|T TT*F|F F(E)|i給出句子給出句子i*i+i的最左和最右推導(dǎo)的最左和最右推導(dǎo)Compiler Construction Principles2.5 上下文無關(guān)文法與語法樹推導(dǎo)和語法樹推導(dǎo)和語法樹 2. 語法樹語法樹 對句型的推導(dǎo)過程給出一種圖形表示, 這種表示稱為語法樹，也稱推導(dǎo)樹。 Compiler Construction Principles 2.5.1 推導(dǎo)和語法樹例如 設(shè)有文法GE:構(gòu)造句型i*i+i的語法樹。首先給出句型的推導(dǎo)過程 (最左推導(dǎo)) ：EE+T | ET | TTT*F | T/F |

51、FF(E) | iEE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+iCompiler Construction Principles2.5.1 推導(dǎo)和語法樹根據(jù)推導(dǎo)過程構(gòu)造句型i*i+i的語法樹如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+T ii*i+Tii*i+FFi*i+iiCompiler Construction Principles2.5.1 推導(dǎo)和語法樹 由例可知，語法樹的構(gòu)造過程是從文法的開始符號出發(fā)，構(gòu)造一個推導(dǎo)的過程。 因為文法的每一個句型 (句子) 都存在一 個推導(dǎo)，所以文法的每個句型(句子) 都存在一棵對應(yīng)的語法樹。Comp

52、iler Construction PrinciplesEE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i2.5.1 推導(dǎo)和語法樹 對句型i*i+i，還可給出最右推導(dǎo)： EE+TTT*FFiiFiCompiler Construction Principles2.5.1 推導(dǎo)和語法樹 這也就是說，一棵語法樹表示了 一個句型的種種可能的(但未必是所 有的)不同推導(dǎo)過程, 包括最左(最右) 推導(dǎo)。Compiler Construction Principles3.5.1 推導(dǎo)和語法樹 子樹語法樹的子樹是由某一結(jié)點連同所有分枝組成的部分。EE+TTT*FFiiFiCom

53、piler Construction Principles3.5.1 推導(dǎo)和語法樹 簡單子樹 語法樹的簡單子樹是指只有單層分枝的子樹。EE+TTT*FFiiFiCompiler Construction Principles2.5.2 文法的二義性從前面的討論可以看出，對于文法G中 任一句型的推導(dǎo)序列, 我們總能為它構(gòu)造 一棵語法樹，現(xiàn)在我們提出一個問題： 文法的某個句型是否只對應(yīng)唯一的一棵語法樹呢？也就是，它是否只有唯一的一個最左(最右)推導(dǎo)呢？ Compiler Construction Principles2.5.2 文法的二義性 例如 設(shè)有文法GE： 句子 i*i+i 有兩個不同的最左

54、推導(dǎo)，對應(yīng)兩棵不同的語法樹。E E+E | E*E | (E) | iCompiler Construction Principles2.5.2 文法的二義性 最左推導(dǎo)1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推導(dǎo)2 EE*Ei*E i*E+Ei*i+E i*i+i EE*EE+EiiiEE+EE*EiiiCompiler Construction Principles2.5.2 文法的二義性 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則說這個文法是二義性的。 或者說，若一個文法中存在某個句子，它有兩個不同的最左 (最右) 推導(dǎo)，則這個文法是二義性的。 E E+E |

55、E*E | (E) | iCompiler Construction Principles文法的二義性和語言的二義性是兩個不同的文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法概念。因為可能有兩個不同的文法G和和G，其中其中G是二義的，但是卻有是二義的，但是卻有L(G)=L(G)，也，也就是說，這兩個文法所產(chǎn)生的語言是相同的。就是說，這兩個文法所產(chǎn)生的語言是相同的。如果產(chǎn)生上下文無關(guān)語言的每一個文法都是如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說此語言是先天二義的。對于一二義的，則說此語言是先天二義的。對于一個程序設(shè)計語言來說，常常希望它的文法是個程序設(shè)計語言來說，常

56、常希望它的文法是無二義的，因為希望對它的每個語句的分析無二義的，因為希望對它的每個語句的分析是唯一的。是唯一的。Compiler Construction Principles2.6 句型分析l句型分析句型分析就是識別一個符號串是否為某文法的句就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。型，是某個推導(dǎo)的構(gòu)造過程。l在語言的編譯實現(xiàn)中，把完成句型分析的程序稱在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為為分析程序分析程序或或識別程序識別程序。分析算法又稱。分析算法又稱識別算法識別算法。l從左到右的分析算法從左到右的分析算法，即總是從左到右地識別輸，即總是從左到右地識別輸入符號串，首

57、先識別符號串中的最左符號，進而入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。依次識別右邊的一個符號，直到分析結(jié)束。Compiler Construction Principles句型的分析算法分類l分析算法可分為：分析算法可分為：l自上而下分析法自上而下分析法：從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。尋找與輸入符號串匹配的推導(dǎo)。l自下而上分析法自下而上分析法：從輸入符號串開始，逐步進行歸約，直至歸約到從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。文法的開始符號。 Compi

58、ler Construction Principles1.自上而下的語法分析例：文法例：文法G：S cAd A ab A a識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導(dǎo)過程：推導(dǎo)過程：S cAd cAd cabdCompiler Construction Principles2.自下而上的語法分析例：文法例：文法G： S cAd A ab A a識別輸入串識別輸入串w=cabd是否該文法的是否該文法的句子句子SAA c a b d c a b d c a b d 規(guī)約規(guī)約過程構(gòu)造的推導(dǎo)：過程構(gòu)造的推導(dǎo)： cAd cabd S cAdComp

59、iler Construction Principles句型分析中的關(guān)鍵問題1）在自上而下的分析方法中）在自上而下的分析方法中如何如何選擇選擇使用使用哪個哪個產(chǎn)生式產(chǎn)生式進行推導(dǎo)進行推導(dǎo)？假定要被代換的最左非終結(jié)符號是假定要被代換的最左非終結(jié)符號是B，且有，且有n條規(guī)則：條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代，那么如何確定用哪個右部去替代B？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何識別可歸約的串識別可歸約的串？在分析程序工作的每一步，都是從當(dāng)前串中在分析程序工作的每一步，都是從當(dāng)前串中選擇一個選擇一個子串子串，將它，將它歸約歸約到到某個非終結(jié)符號某個非終結(jié)符

60、號，該子串稱為，該子串稱為“可可歸約串歸約串”Compiler Construction Principles2.6短語、直接短語和句柄短語短語 令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 則稱 是相對于非終結(jié)符A的, 句型的短語。SA*+且 A Compiler Construction Principles2.6 短語、直接短語和句柄則稱是直接短語。 直接短語直接短語 SA*且 A 令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 Compiler Construction Principles2.6 短語、直接短語和句柄 注意：短語和直接短語的區(qū)