《程序語(yǔ)言的基本知識(shí).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《程序語(yǔ)言的基本知識(shí).ppt（70頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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