程序語言的基本知識.ppt

《程序語言的基本知識.ppt》由會員分享，可在線閱讀，更多相關(guān)《程序語言的基本知識.ppt（70頁珍藏版）》請在裝配圖網(wǎng)上搜索。

編譯原理,杭州電子科技大學(xué),2019/12/16,2,第2章程序語言的基本知識,符號串的集合文法和語言分析樹和二義性形式語言概觀,2019/12/16,3,2.1符號串的集合,字母表,字母表是符號的非空有窮集合，用∑表示,符號：可以相互區(qū)別的記號（元素）,不同的語言有不同的字母表英語——26個英文字母Pascal語言——{A?Z,a?z,0?9,+,-,*,/,,:,?,?,；,.,?,(,),{,},[,]},2019/12/16,4,2.1符號串的集合,符號串,符號串是由字母表中的符號所組成的有窮序列,例如：Σ={a,b}則a,b,aa,ab,aabba…都是Σ上的符號串ε是任何Σ上的符號串,在語言理論中，符號串又稱為:句子、字,2019/12/16,5,2.1符號串的集合,符號串的長度符號串中包含符號的個數(shù)符號串s的長度記為|s|,例，對于字母表{a,b,c}，aab是其上的一個符號串，|aab|=3注意：空符號串ε，|ε|=0,2019/12/16,6,2.1符號串的集合,符號串的前綴、后綴、子串,后綴：刪去符號串s頭部的零個或多于零個符號得到的符號串,前綴：移走符號串s尾部的零個或多于零個符號得到的符號串,2019/12/16,7,2.1符號串的集合,符號串的真前綴、真后綴和真子串——非空,子串：從s中刪去一個前綴和一個后綴得到的符號串,**對于每個符號串s，s和ε兩者都是符號串s的前綴、后綴和子串,2019/12/16,8,2.1符號串的集合,符號串的運算：連接：符號串α、β的連接，是把β的符號寫在α的符號之后得到的符號串αβ,如α=ab,β=cd則αβ=abcd注：εα=αε=α,方冪：符號串自身連接n次得到的符號串,αn定義為αα…ααn個αα1=α,α2=αα，注：α0=ε,2019/12/16,9,2.1符號串的集合,例:漢語—所有符合漢語語法的句子構(gòu)成的集合PASCAL語言——所有合法的PASCAL程序構(gòu)成的集合,注意：空集{}、?和{ε}的不同,語言,某個字母表上的符號串的集合,2019/12/16,10,2.1符號串的集合,語言的運算：,語言是符號串的集合，集合的運算有并、交、差等,并運算—等同于集合的并運算,2019/12/16,11,2.1符號串的集合,連接兩個符號串集合L和M的乘積定義為：LM={st|s?L且t?M},例如：集合A={ab,cde}?B={0,1}?則AB={ab1,ab0,cde0,cde1},{ε}L=L{ε}=LLL…L=LnL0={ε},2019/12/16,12,2.1符號串的集合,*閉包（Kleene閉包）L*=L0∪L1∪L2∪L3∪…,+閉包（正閉包）L+=L1∪L2∪L3∪…L*=L+∪?ε?,2019/12/16,13,2.1符號串的集合,注意:后面通常是考慮字母表∑的*閉包和+閉包,例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…},2019/12/16,14,2.1符號串的集合,綜合性的例子：P10例2.1L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9},把L和D兩個字母表看作長度為1的符號串集合，即語言,1.L∪D2.LD3.L44.L*5.L(L∪D)*6.D+,2019/12/16,15,2.2文法和語言,如何來描述一種語言？,如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示,如果語言是無窮的，找出語言的有窮表示。,2019/12/16,16,2.2文法和語言,語言有窮表示的兩個途經(jīng),**文法即是以生成方式描述語言的,生成方式,語言中的每個句子可以用嚴格定義的規(guī)則來構(gòu)造,2019/12/16,17,2.2文法和語言,**自動機即是以識別方式描述語言的,識別方式,用一個過程，當(dāng)輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”，（要么永遠運行下去）,2019/12/16,18,2.2文法和語言,一個自然語言的例子,規(guī)則（文法）,?句子???主語??謂語?（1）?主語???冠詞??形容詞??名詞?（2）?冠詞??the?形容詞??grey?謂語???動詞??直接賓語?（5）?動詞???助動詞??動詞原形?（6）?助動詞??will?動詞原形??eat?直接賓語???冠詞??名詞?（9）?名詞??wolf?名詞??goat,2019/12/16,19,?句子???主語??謂語???冠詞??形容詞??名詞??謂語??the?形容詞??名詞??謂語??thegrey?名詞??謂語??thegreywolf?謂語??thegreywolf?動詞??直接賓語??…...?thegreywolfwilleatthegoat,句子可根據(jù)規(guī)則推導(dǎo)（生成）出來：,Thegreywolfwilleatthegoat,分析句子,2019/12/16,20,〈謂語〉,〈主語〉,〈冠詞〉,〈形容詞〉,〈名詞〉,〈動詞〉,〈直接賓語〉,,〈句子〉,,,,,,,,,,,,,,,Thegreywolfwilleatthegoat,,,,,,,,2019/12/16,21,2.2文法和語言,文法G,VT,VN,S,P,終結(jié)符號集,非終結(jié)符號集,開始符號,產(chǎn)生式集合,文法的形式定義,2019/12/16,22,終結(jié)符號集VT,代表語言中不可再分的基本符號，如漢語中的漢字、PASCAL語言中的基本字,其中的元素一般用小寫字母或數(shù)字表示（a,b,c,…,0,1…),2.2文法和語言,2019/12/16,23,非終結(jié)符號集VN,代表語法單位，如漢語中的語句、段落，PASCAL語言中的語句、表達式、子程序等，其中的元素一般用大寫字母表示（A,B,C…），或者用尖括號括起一個串來表示,2.2文法和語言,2019/12/16,24,開始符號S,是一個特殊的非終結(jié)符號，代表最高級的語法單位，S至少要在一條產(chǎn)生式中作為左部出現(xiàn),2.2文法和語言,2019/12/16,25,產(chǎn)生式集合P,2.2文法和語言,產(chǎn)生式（重寫規(guī)則、生成式），是形如α→β或α∷=β的（α，β）有序?qū)Γ姚痢蔞+，β∈V*，其中V=（VT∪VN）α稱為產(chǎn)生式的左部，不能為空εβ稱為產(chǎn)生式的右部，可以為空ε（如：A→ε）,2019/12/16,26,2.2文法和語言,例1：文法G=（VT，VN，S，P）VN={S}VT={0,1}P={S→0S1,S→01},可以只寫出產(chǎn)生式，通過產(chǎn)生式可以得到文法的其它部分,左部相同的產(chǎn)生式可以寫在一起，如:S→0S1|01,2019/12/16,27,2.2文法和語言,例2：文法G=（VT，VN，S，P）VN={，，}VT={a,b,c,…x,y,z,0,1,…,9}P={→→→→a,…,→z→0,…,→9}S=,2019/12/16,28,2.2文法和語言,推導(dǎo),直接推導(dǎo),直接歸約,歸約,如果A→γ是G的一條產(chǎn)生式，則稱用αγβ代替αAβ為一步直接推導(dǎo)，記為αAβ?αγβ,2019/12/16,29,2.2文法和語言,推導(dǎo)是用產(chǎn)生式的右部代替左部，歸約是用產(chǎn)生式的左部代替右部，歸約是推導(dǎo)的逆過程,直接推導(dǎo),直接歸約,用αAβ代替αγβ為一步直接歸約，記為αγβ<=αAβ,2019/12/16,30,2.2文法和語言,推導(dǎo)的長度直接推導(dǎo)的次數(shù)αβ，長度大于等于1的推導(dǎo)αβ，長度大于等于0的推導(dǎo),推導(dǎo)的例子：S?0S1?00S11?000111，長度為3記為：S000111SS,2019/12/16,31,2.2文法和語言,最左推導(dǎo),最右推導(dǎo),對α中的最左非終結(jié)符進行展開,對α中的最右非終結(jié)符進行展開,2019/12/16,32,2.2文法和語言,例子：表達式文法E→E+TE→TT→T*FT→FF→（E）F→a,最左推導(dǎo)：ETT*FF*Fa*Fa*a,**最右推導(dǎo)又稱為規(guī)范推導(dǎo),最右推導(dǎo)：ETT*FT*aF*aa*a,2019/12/16,33,2.2文法和語言,最右歸約,最左歸約,最左推導(dǎo)的逆過程是最右歸約，即對最右邊的可歸約串進行歸約,最右推導(dǎo)的逆過程是最左歸約，即對最左邊的可歸約串進行歸約,a*a<=a*F<=F*F<=T*F<=T<=E,a*a<=F*a<=T*a<=T*F<=T<=E,**最左歸約稱為規(guī)范歸約,2019/12/16,34,2.2文法和語言,句型,句子,只包含終結(jié)符號的句型稱為句子。句子是一種特殊的句型。,從文法的開始符號出發(fā)進行零步或多于零步的推導(dǎo)得到的文法符號串（Sα）。句型可以既包含終結(jié)符號又包含非終結(jié)符號。,2019/12/16,35,2.2文法和語言,例：在推導(dǎo)E?T?T*F?F*F?a*F?a*a中，,句型有：E、T、T*F、F*F、a*F、a*a,句子是：a*a,E→E+TE→TT→T*FT→FF→（E）F→a,2019/12/16,36,2.2文法和語言,語言的形式定義,文法G推導(dǎo)出的所有句子組成的集合，稱為語言，記為L（G）,L（G）={α|Sα，α∈VT*},2019/12/16,37,2.2文法和語言,例子：G1：S→AA→0A1A→01,是由一個或多個0開頭，后跟同樣數(shù)目的1的符號串構(gòu)成的集合（語言），,可記為：L(G)={0n1n|n≥1},2019/12/16,38,2.2文法和語言,G2：E→idE→E+EE→E*EE→（E）,產(chǎn)生的是表達式的集合,2019/12/16,39,2.2文法和語言,G3：E→E+TE→TT→T*FT→FF→（E）F→id,產(chǎn)生的也是表達式的集合,2019/12/16,40,2.2文法和語言,一個文法對應(yīng)一個語言，但一個語言可能有若干個文法產(chǎn)生它，這若干個文法是等價的，稱為等價文法,例G2與G3,2019/12/16,41,2.2文法和語言,上下文無關(guān)文法能夠描述現(xiàn)今程序設(shè)計語言的大部分語法結(jié)構(gòu),算術(shù)表達式賦值語句條件語句等,2019/12/16,42,2.2文法和語言,表達式文法：G=({+,*,id,(,)},{E},E,P)P:E→idE→E+EE→E*EE→(E),E表示算術(shù)表達式，id表示程序的“變量”，該文法定義了由變量，+，*，(和)組成的算術(shù)表達式的語法結(jié)構(gòu)，即：變量是算術(shù)表達式；若E1和E2是算術(shù)表達式，則E1+E2，E1*E2和(E1)也是算術(shù)表達式。,2019/12/16,43,2.2文法和語言,描述一種簡單賦值語句的產(chǎn)生式：〈賦值語句〉→id∶=E,描述條件語句的產(chǎn)生式：〈條件語句〉→if〈條件〉then〈語句〉｜if〈條件〉then〈語句〉else〈語句〉,2019/12/16,44,2.3分析樹和二義性,分析樹是描述上下文無關(guān)文法句型推導(dǎo)的一種直觀方法，也稱為推導(dǎo)樹,分析樹,句型推導(dǎo),,對應(yīng)關(guān)系,2019/12/16,45,,2.3分析樹和二義性,為句型推導(dǎo)構(gòu)造分析樹例子：,E?T,E→E+TE→TT→T*FT→FF→（E）F→a,?T*F,?F*F,?a*F,T,T,*,F,F,a,a,,,,,,,E,,?a*a,2019/12/16,46,,2.3分析樹和二義性,分析樹的特性：,根標(biāo)識為開始符號,內(nèi)部結(jié)點標(biāo)識為非終結(jié)符號,每一內(nèi)部結(jié)點及其子結(jié)點對應(yīng)一條產(chǎn)生式，該結(jié)點是產(chǎn)生式的左部，子結(jié)點從左至右排列構(gòu)成產(chǎn)生式的右部,葉結(jié)點從左至右排列構(gòu)成句型,T,T,*,F,F,a,a,,,,,,,E,,2019/12/16,47,,2.3分析樹和二義性,分析樹與句型推導(dǎo)的關(guān)系,一次推導(dǎo)（不是一個句型）對應(yīng)一棵分析樹,一棵分析樹可能對應(yīng)若干個推導(dǎo),例如下面的推導(dǎo)對應(yīng)的也是上面那棵分析樹E?T?T*F?T*a?F*a?a*a,T,T,*,F,F,a,a,,,,,,,E,,2019/12/16,48,,2.3分析樹和二義性,說明分析樹沒有嚴格反映推導(dǎo)的順序,但是一棵分析樹對應(yīng)一個最左推導(dǎo)，也只能對應(yīng)一個最右推導(dǎo),T,T,*,F,F,a,a,,,,,,,E,,2019/12/16,49,2.3分析樹和二義性,對應(yīng)最左推導(dǎo),分析樹,,,對應(yīng)最右推導(dǎo),分析樹,,2019/12/16,50,,2.3分析樹和二義性,分析句型：短語、直接短語、句柄,如果SαAδ和Aβ，則稱β是關(guān)于A的，句型αβδ的一個短語（子樹的葉子）,S,α,A,δ,β,,,,,2019/12/16,51,,2.3分析樹和二義性,例：句型F*a的短語,T,T,*,F,F,a,,,,,,E,,F*a,E→E+TE→TT→T*FT→FF→（E）F→a,F,a,2019/12/16,52,,2.3分析樹和二義性,如果SαAδ和A?β，則稱β是關(guān)于A的，句型αβδ的一個直接短語（只有父子兩代的子樹的葉子）,S,α,A,δ,β,,,,,2019/12/16,53,,2.3分析樹和二義性,例：句型F*a的直接短語,T,T,*,F,F,a,,,,,,E,,F,a,2019/12/16,54,,2.3分析樹和二義性,最左直接短語稱為句柄最左性體現(xiàn)在分析樹和句型中,S,α,A,δ,β,,,,,2019/12/16,55,,2.3分析樹和二義性,例：句型F*a的句柄,T,T,*,F,F,a,,,,,,E,,F,2019/12/16,56,2.3分析樹和二義性,句型的素短語、最左素短語,1、β是關(guān)于A的，句型αβδ的一個短語,2、β至少含有一個終結(jié)符,3、β除自身外不含更小的帶終結(jié)符的短語,稱β是關(guān)于A的，句型αβδ的一個素短語,句型最左邊的素短語稱為最左素短語,2019/12/16,57,,例：,E,E,+,T,E,+,T,F,T,T,*,F,a,,,,,,,,,,,,,句型：T+T*F+a,短語：T+T*F+a、T+T*F、T*F、T（左邊）、a,直接短語：T、T*F、a,句柄：T,素短語：T*F、a,最左素短語：T*F,E→E+TE→TT→T*FT→FF→（E）F→a,2019/12/16,58,2.3分析樹和二義性,句子、文法和語言的二義性,如果一個文法的句子有兩棵或兩棵以上的分析樹，稱此句子是二義的,最左（右）推導(dǎo)與分析樹一一對應(yīng)，句子二義說明它有兩個或以上最左（右）推導(dǎo),2019/12/16,59,,,2.3分析樹和二義性,E?E+E?id+E?id+E*E?id+id*E?id+id*id,E?E*E?E+E*E?id+E*E?id+id*E?id+id*id,E,E,+,E,id,*,,,,,,E,E,,,id,,id,,E,E,*,E,id,+,,,,,,E,E,,,id,,id,,例：,E→idE→E+EE→E*EE→（E）,2019/12/16,60,2.3分析樹和二義性,如果一個文法有一個句子是二義的，此文法稱為二義文法,E→idE→E+EE→E*EE→（E）,2019/12/16,61,2.3分析樹和二義性,如果一個語言的所有文法都是二義的，稱此語言是二義的,希望文法是無二義的，因為希望對于每一個句子進行唯一確定的分析,2019/12/16,62,2.4形式語言概觀,喬姆斯基（Chomsky）在1956年提出形式語言理論，他將形式文法分為四類(0,1,2,3)，對應(yīng)四類形式語言(0,1,2,3),分類的方法是對文法的產(chǎn)生式進行不同的限制,2019/12/16,63,2.4形式語言概觀,0型文法—|α|≠0，即α≠ε（α→β）,1型（上下文有關(guān)）文法—|α|≤|β|（α→β）,2型（上下文無關(guān)）文法—A∈VN，β∈（VT∪VN）*（A→β）,3型（正規(guī)）文法A→a或A→aB（右線性）A→a或A→Ba（左線性）,2019/12/16,64,2.4形式語言概觀,例：1型（上下文有關(guān)）文法文法G：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→εBD→bDD→εAa→bDL(G)={ww|w∈{a,b}*},2019/12/16,65,2.4形式語言概觀,例：2型（上下文無關(guān)）文法文法G1：S→aB|bAA→a|aS|bAAB→b|bS|aBB文法G2：S→0A|1B|0A→0A|1B|0SB→1B|1|0,2019/12/16,66,2.4形式語言概觀,例：3型（正規(guī)）文法文法G：S→0A|1B|0A→0A|1B|0SB→1B|1|0,2019/12/16,67,2.4形式語言概觀,0型文法產(chǎn)生的語言稱為0型語言,1型文法或上下文有關(guān)文法產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言,2型文法或上下文無關(guān)文法產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言,3型文法或正則（正規(guī)）文法產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言,2019/12/16,68,2.4形式語言概觀,四種文法（語言）之間的逐級“包含”關(guān)系,,,,,2型文法（語言）,1型文法（語言）,0型文法（語言）,3型文法（語言）,2019/12/16,69,2.4形式語言概觀,識別各類語言的數(shù)學(xué)模型（自動機）,圖靈機（0型語言）,有界圖靈機、線性有界自動機（1型語言）,下推自動機（2型語言）,有限自動機（3型語言）,2019/12/16,70,TheEnd!,