工科專業(yè)下編譯原理第二章

1、編譯原理電子教案第二章高級(jí)語言及其語法描述2本章的主要內(nèi)容高級(jí)語言的一般特性語法、文法和語義上下文無關(guān)的文法分析樹與二義性形式語言的概況及分類3本章要求 知識(shí)點(diǎn)：文法和語言的形式定義，分析樹和二義性，形式語言概觀。深刻理解：上下文無關(guān)文法，推導(dǎo)，語言，最左推導(dǎo)，最右推導(dǎo)，分析樹和二義性。熟練掌握：（1）已知上下文無關(guān)文法G和句型w，構(gòu)造出w的推導(dǎo)，最左推導(dǎo)，最右推導(dǎo)，分析樹； （2）判定上下文無關(guān)文法G是二義性的。（3）已知上下文無關(guān)文法G，求出L，使得L=L（G）； 已知上下文無關(guān)語言 L，求出 G，使得 L（G）=L。4本章教學(xué)線索1高級(jí)語言的一般特性 1.1 程序語言的定義 1.2 程序

2、語言的分類 1.3 數(shù)據(jù)類型與操作 1.4 高級(jí)語言常見的語句2 字符串3 文法和語言 4 語法分析樹與二義性問題 5 文法的分類（逐漸對(duì)產(chǎn)生式施加限制）51.1 程序語言的定義高級(jí)程序語言都可看成是一個(gè)字符集上的字符串。程序語言主要是由語法和語義兩方面定義。語言的語法是用來形成一個(gè)合法程序的一組規(guī)則，這些規(guī)則一部分稱為詞法規(guī)則，另一部分稱為語法規(guī)則。詞法規(guī)則定義了單詞符號(hào)的形成規(guī)則，而語法規(guī)則定義了語法單位的形成規(guī)則。語法單位：表達(dá)式、語句、函數(shù)、過程和程序等。語義規(guī)則定義了語言的意義，語義規(guī)則定義語言的單詞符號(hào)和語法單位的意義。程序語言的語法規(guī)則是用文法來描述的，目前的程序語言一般用上下文

3、無關(guān)的文法來描述。61.2 程序語言的分類（1）強(qiáng)制式語言（過程式語言）：命令驅(qū)動(dòng)，面向語句，一個(gè)強(qiáng)制式語言程序由一系列語句組成，如：FORTRAN、C、PASCAL等；（2）應(yīng)用式語言（函數(shù)式語言）：注重程序的表示功能，程序的開發(fā)過程就是從前面已有的函數(shù)出發(fā)構(gòu)造更復(fù)雜的函數(shù)，如：LISP。（3）基于規(guī)則的語言（邏輯設(shè)計(jì)語言）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)牟僮?，如：Prolog。（4）面向?qū)ο蟮恼Z言：封裝性、繼承性、多態(tài)性，如：C+，Java，Smalltalk。71.3 數(shù)據(jù)類型與操作一個(gè)數(shù)據(jù)類型通常包括3種要素：（1）用于區(qū)別這種類型數(shù)據(jù)對(duì)象的屬性（2）這種類型的數(shù)據(jù)對(duì)象可以具

4、有的值（3）可以作用于這種類型的數(shù)據(jù)對(duì)象的操作常見的數(shù)據(jù)類型：（1）數(shù)值數(shù)據(jù)（2）邏輯數(shù)據(jù)（3）字符數(shù)據(jù)（4）指針類型（5）數(shù)組（6）記錄（7）字符串、棧、隊(duì)列（8）抽象數(shù)據(jù)類型（類）81.4 高級(jí)語言常見的語句說明語句賦值語句控制語句（無條件轉(zhuǎn)移語句、條件語句、循環(huán)語句、過程調(diào)用語句、返回語句）9本章教學(xué)線索1高級(jí)語言的一般特性2 字符串 2.1 字母表 2.2 符號(hào)串定義、術(shù)語及運(yùn)算3 文法和語言 4 語法分析樹與二義性問題5 文法的分類（逐漸對(duì)產(chǎn)生式施加限制） 102.1 字母表 字母表是符號(hào)的非空有窮集合。任何程序語言都有自己的字母表，一個(gè)程序語言只使用一個(gè)有限字符集作為字母表。用表示

5、。例如:計(jì)算機(jī)語言：由符號(hào)“0”和“1”組成的字母表，=0，1 ASCII字符集；Pascal字母表為： = AZ, az, 09, +, -, *, /, , :, , ; ，.， , (, ), , , , 112.2 符號(hào)串定義、術(shù)語及運(yùn)算符號(hào)串的定義 設(shè)是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號(hào)。上的一個(gè)符號(hào)串是指由中的符號(hào)所構(gòu)成的一個(gè)有窮序列。(1) 空字是上的一個(gè)符號(hào)串。空字是不包含任何符號(hào)的序列。(2) 若x是上的符號(hào)串，而a是的元素, 則xa是上的符號(hào)串。(3) y是上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。 由字母表中的符號(hào)所組成的任何有窮序列稱之為該字母表上的符號(hào)串,也稱

6、作“字”。*(Kleene閉包)：表示上的所有字符串的全體，也在其中。表示不含任何元素的空集。例如：若=a，b，則*=，a，b ，aa，ab，ba，bb，aaa， 12符號(hào)串的術(shù)語設(shè)s是符號(hào)串前綴：移走s的尾部的零個(gè)或多于零個(gè)符號(hào)后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號(hào)子串：從s中刪去一個(gè)前綴和一個(gè)后綴子序列：從s中刪去零個(gè)或多于零個(gè)符號(hào)(這些符號(hào)不要求是連續(xù)的）逆轉(zhuǎn)：將S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串。長度：是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|=0。真前綴，真后綴，真子串: xsx 例子：符號(hào)串s=banana前綴：,b,ba,ban,bana,banan,banana后綴：

7、banana,anana,nana,ana,na,a, 子串：banana,anana,banan,anan, 子序列: baa(這些符號(hào)不要求是連續(xù)的）逆轉(zhuǎn)（用SR表示）：ananab長度：banana=613符號(hào)串的運(yùn)算（1）連接：設(shè)x和y是符號(hào)串，它們的連接 xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。例如：x = ba，y = nana，xy = banana。（2）方冪：x0 = ；x1 = x；x2 = xx ；xn=xn-1x ； 例如： x = ba，x1= ba， x2=baba，x3=bababa，14符號(hào)串集合(語言）的運(yùn)算設(shè)*的子集U和V是兩個(gè)符號(hào)串集合，則合并：UV

8、 |U orV（或表示為：U+V）連接：UV |U and V方冪： V0=， V1V，V2VV，VnVn-1V 語言V的閉包，記作V*： V*Vi（i=0） = V0V1V2V3 語言V的正則閉包，記作V+（V+V V*） V+Vi（i =1） = V1V2V3 15本章教學(xué)線索1高級(jí)語言的一般特性2 字符串3 文法和語言 3.1 文法的定義（上下文無關(guān)的文法） 3.2 直接推導(dǎo)和推導(dǎo)的定義 3.3 最左推導(dǎo)與最右推導(dǎo) 3.4 語言的定義4 語法分析樹與二義性問題 5 文法的分類（逐漸對(duì)產(chǎn)生式施加限制）163 文法和語言例子：He gave me a book Hegavemebooka語法

9、樹17語法規(guī)則 He me a gave book18注意：其中He,me,book,gave,a等稱為終結(jié)符；、等稱為非終結(jié)符號(hào)；這種書寫形式稱為產(chǎn)生式。產(chǎn)生式（規(guī)則，重寫規(guī)則或生成式）： Uu （或U:=u） 且UV+，uV* ，U是符號(hào),稱為規(guī)則左部，u是有窮非空符號(hào)串，為規(guī)則右部。非終結(jié)符號(hào)：需要進(jìn)一步定義的符號(hào)，不會(huì)出現(xiàn)在程序中。終結(jié)符號(hào)：不需要再定義，會(huì)出現(xiàn)在程序中。193.1 文法的定義（上下文無關(guān)的文法）一個(gè)上下文無關(guān)的文法G可以表示成一個(gè)四元式(VT，VN，S，P)，其中：VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符；VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符，且有VTV

10、N=S是一個(gè)非終結(jié)符，稱為開始符號(hào)； P是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是A，其中AVN，（VTVN）*。S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次?？梢詫⒆蟛肯嗤漠a(chǎn)生式縮寫成：A1|2|3|n 20（注意：終結(jié)符號(hào)是組成語言的基本符號(hào)，比如關(guān)鍵字、標(biāo)志符、常數(shù)、算符和界符等；非終結(jié)符用來代表語法范疇，比如算術(shù)表達(dá)式、賦值語句、程序等；開始符號(hào)是一個(gè)特殊的非終結(jié)符，代表了我們最終有用的語法范疇。） 例2.1：一個(gè)簡單的算術(shù)表達(dá)式的文法：G = ( i，+，*，(，)，P )P： * （） i可以簡單表示為：E E+TTT T*F FF ( E ) i 21巴科斯范式（BNF：Backus

11、-Naur Form）： “”：表示定義為，“”：表示或另一種表示法： := i := +* 將非終結(jié)符用括起來表示，用“:=”表示“定義為”，用“”表示“或”，這種方法不夠簡潔。 22令G=（VT，VN，S，P），若AP，且，（VTVN）*，則稱A直接推出，表示成A ，我們稱：A直接推出 ，反之稱直接歸約到A； 如果存在一個(gè)直接推導(dǎo)序列： 1 2 3 n（n0），我們稱這個(gè)序列是從 1到n 的一個(gè)推導(dǎo)。 1 n：表示從1經(jīng)過一步或若干步可以推導(dǎo)出n。 1 n：表示從1經(jīng)過0步或若干步可以推導(dǎo)出n。（ 意味著=，或者 ）。3.2 直接推導(dǎo)和推導(dǎo)的定義+*23例：E E+T T+T F+Ti+T

12、 i+F i+i A產(chǎn)生式E E+TE E+TE+T T+TE T+TT+T F+TT F+TF+Ti+TF i+Ti+Ti+FT Fi+i+Fi+iF ii+243.3 最左推導(dǎo)與最右推導(dǎo) 對(duì)于推導(dǎo)，如果每一步都是對(duì)中的最左非終結(jié)符進(jìn)行替換的，則我們稱這種推導(dǎo)為最左推導(dǎo)，如果每一步都是對(duì)中的最右非終結(jié)符進(jìn)行替換的，則我們稱這種替換為最右推導(dǎo)。 例2-2：對(duì)于文法：EE+ E|E*E|(E)|i 我們看對(duì)于（i*i+i）的推導(dǎo)最左推導(dǎo)：E （E） （E+E） （E*E+E） （i*E+E） (i*i+E) (i*i+i)最右推導(dǎo)：E （E） （E+E） （E+i） （E*E+i） (E*i+i

13、) (i*i+i) 25 例2-3:文法GS: SAB AA0|1B B0|S1 請(qǐng)給出句子101001的最左和最右推導(dǎo)。 最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001 結(jié)論：對(duì)某文法的同一句型存在不同的推導(dǎo)序列26 假定G是一個(gè)文法，S是它的開始符號(hào)。如果S ，則稱是一個(gè)句型。僅含終結(jié)符的句型是一個(gè)句子。文法G所產(chǎn)生句子的全體是一個(gè)語言，將它記為：L（G）， 則L（G）=|S & VT* 例2-4：考慮文法 G(a,b,S,S，P）其中P

14、：SaSb abSaSb aaSbb a3Sb3 an-1Sbn-1 anbn這里文法可以表示為：L(G) = anbn|n1注意：1)句型與句子的區(qū)別和聯(lián)系 2)文法和語言之間并不存在一一對(duì)應(yīng)關(guān)系，對(duì)于一給定的文法，唯一地確定它所產(chǎn)生的語言；但對(duì)于一個(gè)給定的語言往往可用若干個(gè)不同的文法來產(chǎn)生。3.4 語言的定義+*27本章教學(xué)線索1高級(jí)語言的一般特性2 字符串3 文法和語言4 語法分析樹與二義性問題 4.1 語法分析樹的定義 4.2 文法的二義性問題 4.3 壓縮過的文法（化簡了的文法）5 文法的分類（逐漸對(duì)產(chǎn)生式施加限制）284.1 語法分析樹的定義設(shè)G=（VT，VN，S，P），G的一棵分

15、析樹滿足如下條件：每一結(jié)點(diǎn)有一標(biāo)記，此標(biāo)記是VTVN中的符號(hào)。根的標(biāo)記是S。如果一個(gè)結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)，且標(biāo)記A，那么A必在VN中。如果編號(hào)為n的結(jié)點(diǎn)有標(biāo)記A，結(jié)點(diǎn)n1，n2，nk是點(diǎn)n的從左到右的兒子，并分別有標(biāo)記X1，X2，Xk，則AX1X2Xk必須是P中的產(chǎn)生式。若結(jié)點(diǎn)n有標(biāo)記，那么結(jié)點(diǎn)n是葉子，且是它父親唯一的兒子。 29畫語法樹的兩種方法：自頂向下：根據(jù)推導(dǎo)序列，對(duì)每步推導(dǎo)畫相應(yīng)分枝自底向上：根據(jù)歸約序列，對(duì)每步歸約畫相應(yīng)分枝 有關(guān)分析樹要注意的幾點(diǎn)：一個(gè)句型推導(dǎo)或分析用一棵樹結(jié)構(gòu)圖示出來，它反應(yīng)了一個(gè)句子的語法結(jié)構(gòu)層次。對(duì)于一個(gè)句子的多種推導(dǎo)（若文法是無二義性的），采用各種推導(dǎo)過程，畫

16、出的分析樹是一樣的。分析樹并未描述推導(dǎo)過程。在書中，用畫分析樹的過程解釋語法分析過程，用分析樹圖解語法結(jié)構(gòu)。分析樹是推導(dǎo)的圖形表示。30E（樹根）（E）E+EE*Eiii12345E（E）（E+E）（E*E+E）（i*E+E）（i*i+E）（i*i+i）對(duì)于（i*i+i）的語法分析樹314.2 文法的二義性問題描述一個(gè)句子的文法不是唯一的；對(duì)于一個(gè)句子的分析應(yīng)是唯一的。 考慮文法：EE+ E|E*E|（E）|i， 句子 （i*i+i）推導(dǎo)一：E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)推導(dǎo)二：E (E) (E*E) (i*E) (i*E+E) (i*i

17、+E) (i*i+i)32推導(dǎo)一對(duì)應(yīng)的語法樹推導(dǎo)二對(duì)應(yīng)的語法樹E（樹根）（E）E*EE+Eiii12345E（樹根）（E）E+EE*Eiii1234533 如果一個(gè)文法的句子存在兩棵不同的分析樹，那么該句子是二義性的。如果一個(gè)文法包含二義性的句子，則稱這個(gè)文法是二義性的；否則，該文法是無二義性的。 34幾點(diǎn)說明：1）一般來說，程序語言要求無二義性文法，對(duì)于條件語句，經(jīng)常使用二義性文法描述它：S if 條件 then 語句 if 條件 then 語句 else 語句 其它語句二義性的句子：if e1 then if e2 then s1 else s2 2）在能駕馭的情況下，使用二義性文法。3）

18、對(duì)于任意一個(gè)上下文無關(guān)文法，不存在一個(gè)算法，能夠在有限的步驟內(nèi)判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。354.3 壓縮過的文法（化簡了的文法）1）文法中不含有任何形如PP的產(chǎn)生式；2）每個(gè)非終結(jié)符號(hào)P必須都有用處。即：S P 且P ，VT*（兩層含義：一方面意味著，必須存在含P的句型，另一方面方面意味著對(duì)于P不存在永不終結(jié)的回路）*+36本章教學(xué)線索1高級(jí)語言的一般特性2 字符串3 文法和語言4 語法分析樹與二義性問題 5 文法的分類（逐漸對(duì)產(chǎn)生式施加限制） 5.1 喬姆斯基文法（Chomsky） 5.2 上下文有關(guān)的語法結(jié)構(gòu) 5.3 自嵌套的文法 5.4

19、 文法的遞歸性 5.5 文法與語言的典型題目375.1 喬姆斯基文法（Chomsky）喬姆斯基文法（Chomsky）：四種類型：0型，1型，2型，3型0型：G =（VT，VN，S，P） 規(guī)則形式： ， (VTVN)*， 推導(dǎo)： 例如：GS = （S，A，B，C，D，E，a，P，S），其中P由如下產(chǎn)生式組成：SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 381型（上下文有關(guān)）：對(duì)于產(chǎn)生式均滿足，僅僅S除外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。例如：GS = （S，A，B，C，A ，a，b，c，P，S） 其中P： SaSBA SabB BABA BA AA AA AB

20、bAbb bBbc cBcc L（G）=aibici|i1 392型（上下文無關(guān)）：G的任何產(chǎn)生式為A A VN， (VN VT)* 例如：GS = （S，a，b，SaSb，Sab，S） L（G）= aibi|i13型（右線性）：G的任何產(chǎn)生式為A B或A ， VT*，A、BVN （左線性）：G的任何產(chǎn)生式為A B或A ， VT*，A、BVN3型文法等價(jià)于正規(guī)式，因此又稱為正規(guī)文法。40四種文法之間的關(guān)系 由于四種文法是按照將產(chǎn)生式做進(jìn)一步限制而定義的，所以它們之間是逐級(jí)“包含”的關(guān)系，由四種文法產(chǎn)生的語言也是逐級(jí)“包含”的關(guān)系。 即： 3型語言類 2型語言類 1型語言類 0型語言類注：0型語

21、言除外，從其中刪去或往其中添加一個(gè)空串并不改變其語言類。語言層正規(guī)語言3上下文無關(guān)語言2上下文有關(guān)語言1遞歸可枚舉語言0圖靈機(jī)TM線性界限自動(dòng)機(jī)LBA下推自動(dòng)機(jī)PDA有窮自動(dòng)機(jī)FA415.2 上下文有關(guān)的語法結(jié)構(gòu) 現(xiàn)在使用的程序語言中,有些語言結(jié)構(gòu)并不是總能用上下文無關(guān)文法描述的。 例2.9 L1=wcw|wa,b+。例如,aabcaab就是L1的一個(gè)句子。這個(gè)語言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。例2.10 L2=anbmcndm|n,m0，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)一致問題的抽象。 語言中過程定義和引用的語法并不涉及到參數(shù)個(gè)數(shù)，例如，Pascal的過程語句可描述為 s