《《形式語(yǔ)言理論》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《形式語(yǔ)言理論》PPT課件.ppt（49頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第二章 形式語(yǔ)言理論,形式語(yǔ)言,Chomsky于1956年提出了一種用來(lái)描述語(yǔ)言的數(shù)學(xué)系統(tǒng)。人們把用一組數(shù)學(xué)符號(hào)和規(guī)則來(lái)描述語(yǔ)言的方式稱為形式描述，而把所用的數(shù)學(xué)符號(hào)和規(guī)則稱為形式語(yǔ)言。 形式語(yǔ)言，只是從語(yǔ)法上研究語(yǔ)言。它是抽象的數(shù)學(xué)系統(tǒng)，用于模擬程序設(shè)計(jì)語(yǔ)言的語(yǔ)法，或者是并不很成功地模擬自然語(yǔ)言如英語(yǔ)的語(yǔ)法。 形式語(yǔ)言理論是編譯理論的重要基礎(chǔ)，它主要研究組成符號(hào)語(yǔ)言的符號(hào)串的集合及它們的表示法、結(jié)構(gòu)與特性。,形式語(yǔ)言和編譯理論中的 最基本概念 符號(hào)串和符號(hào)串集合,2.1字母表和符號(hào)串,字母表 定義:元素的非空有窮集合，記為。 例：=01 =ab,c 元素也稱為符號(hào)，字母表也稱符號(hào)集。 程序語(yǔ)
2、言的字母表由字母數(shù)字和若干專用符號(hào)組成。,符號(hào)串 定義:由字母表中的符號(hào)組成的任何有窮序列 例：0,00,10是字母表=01上的符號(hào)串 a,ab,aaca是=ab,c上的符號(hào)串 在符號(hào)串中，符號(hào)是有順序的，順序不同,代表不同的符號(hào)串，如:ab和ba不同 不含任何符號(hào)的符號(hào)串稱為空串，用表示 注意:并不等于空集合 符號(hào)串長(zhǎng)度: 符號(hào)串中含有符號(hào)的個(gè)數(shù) 如: |abc|=3| |=0,符號(hào)串的運(yùn)算 符號(hào)串的連接：設(shè)x、y是符號(hào)串,它們的連接 是把y的符號(hào)寫(xiě)在 x的符號(hào)之后得到的符號(hào)串xy 例如 x=ST，y=abu ，則 xy=STabu 顯然x = x=x 符號(hào)串的方冪：把符號(hào)串a(chǎn)自身連接n
3、次得到的符號(hào)串a(chǎn)n = aaaa 例如 a1=a a2=aa a0=,符號(hào)串集合： 定義: 若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。 符號(hào)串集合的乘積：符號(hào)串集合A和B的乘積定義為:AB =xy|xA且yB，即AB是由A中的串x和B中的串y連接而成的串xy組成的集合。 若集合A = ab,cde B = 0,1 則 AB = ab0,ab1,cde0,cde1 顯然 A = A = A,符號(hào)串集合的方冪: 設(shè)A是符號(hào)串的集合，則稱Ai為符號(hào)串集A的方冪，其中i是非負(fù)整數(shù)。具體定義如下: A0 = A1 = A , A2 = A A AK = AA......A
4、(k個(gè)),集合的閉包 閉包 集合的閉包 *定義如下： * = 0 1 2 3 例：設(shè)有字母表=0，1 則*=012 =,0,1,00,01,10,11,000, 即*表示上所有有窮長(zhǎng)的串的集合。,正閉包 + = 123稱為的正閉包。 + 表示上的除外的所有有窮長(zhǎng)串的集合 自反閉包* = 0+ + = * = * ,2.2文法和語(yǔ)言,1、文法定義: 文法G(Grammar)定義為四元組（VN，VT，P，S） VN (Nonternimal)：非終結(jié)符集 VT (Terminal)：終結(jié)符集 P (Production)：產(chǎn)生式（規(guī)則）集合 S：開(kāi)始符號(hào)或識(shí)別符號(hào),說(shuō)明: V=VNVT，V稱為文法
5、G的字母表 P中產(chǎn)生式形如：,其中V+且至少含一個(gè)非終結(jié)符，V* VN,VT和P是非空有窮集 VNVT= S是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn) 非終結(jié)符代表一個(gè)語(yǔ)言中的語(yǔ)法成分，如，它是構(gòu)成程序的一個(gè)語(yǔ)法成分，這個(gè)符號(hào)本身不會(huì)在程序中出現(xiàn)，而終結(jié)符是組成程序的具體的符號(hào)。,2. 推導(dǎo)和規(guī)范推導(dǎo)： 是文法G的產(chǎn)生式，若有v，w滿足：v=,w=, 其中,V* 則稱v直接推導(dǎo)出w,也稱w直接歸約到v, 記作 v w 直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過(guò)程 直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程,2、直接推導(dǎo)序列： 或 + 若存在v =u0 u1 ... un=w,
6、(n0) 則稱v + w，v推導(dǎo)出w，或w歸約到v（至少有1步推導(dǎo)），這個(gè)直接推導(dǎo)序列的長(zhǎng)度為n。 3、廣義推導(dǎo)： 或 * 若有v + w 或 v=w， 則記為v * w，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）,+ ,* ,三種推導(dǎo)的比較,直接推導(dǎo)（）的長(zhǎng)度為1 直接推導(dǎo)序列（ +）的長(zhǎng)度n1 廣義推導(dǎo)（ *）的長(zhǎng)度0,規(guī)范推導(dǎo)與規(guī)范規(guī)約,考慮兩種特殊推導(dǎo)：最左推導(dǎo)和最右推導(dǎo)，即 對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)，都是對(duì)最左（最右）非終結(jié)符進(jìn)行替換。 最右推導(dǎo)也稱規(guī)范推導(dǎo)，它的逆過(guò)程稱為最左規(guī)約，也稱規(guī)范規(guī)約。,2.3 文法的分類,Chomsky對(duì)文法中的規(guī)則施加不同限
7、制，將文法和語(yǔ)言分為四大類： 0型文法（PSG） 0型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言 1型文法（CSG） 1型語(yǔ)言或上下文有關(guān)語(yǔ)言 2型文法（CFG） 2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言 3型文法（RG）3型語(yǔ)言或正則（正規(guī)）語(yǔ)言,如果對(duì)于某文法G，P中每個(gè)規(guī)則具有下列形式： 其中V+ ， V*，則該文法G為（Chomsky）0型文法或短語(yǔ)結(jié)構(gòu)文法。相應(yīng)的語(yǔ)言 稱為0型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言。 如文法G，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B ,0型文法,1型文法(上下文有關(guān)) 它是0型文法的特例,對(duì)P中的任一產(chǎn)生式，都有|||| 1， 僅僅 S除外,但S
8、不得出現(xiàn)在任何產(chǎn)生式的右部。 例 文法GS： SaSBE SaBEEBBE aBab bBbb bEbe eEee 1型文法產(chǎn)生式的一般形式是 A， , V* ，AVN , V ，它表示當(dāng)A的上文為且下文為時(shí)可把A替換成，因此稱1型文法為上下文有關(guān)文法。,2型文法（上下文無(wú)關(guān)文法） 它是1型文法的特例，對(duì)任一產(chǎn)生式，都有VN ， (VNVT)* 例 文法GS：SAB ABS|0 BSA|1 2型文法產(chǎn)生式的一般形式是: A，它表示不管A的上下文如何都可把A替換成，因此被稱為上下文無(wú)關(guān)文法。 通常程序設(shè)計(jì)語(yǔ)言的文法，可用2型文法來(lái)描述，因此我們重點(diǎn)研究2型文法。,3型文法(右線性文法和正規(guī)文法
9、) 它是2型文法的特例，任一產(chǎn)生式的形式都為 AaB或Aa，其中A ，BVN ，aVT * 在正規(guī)文法中，任一產(chǎn)生式的形式都為 AaB或Aa，其中A ，BVN ，aVT 例如 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|0 在程序設(shè)計(jì)語(yǔ)言中，正規(guī)文法通常用來(lái)描述單詞的結(jié)構(gòu)。,四種文法之間的逐級(jí)“包含”關(guān)系,2.4語(yǔ)言和語(yǔ)法,1、句型和句子 設(shè)有文法GS，若符號(hào)串是從開(kāi)始符推導(dǎo)出來(lái)的,即 S =* ，則稱是文法G的句型。若僅由終結(jié)符組成,即 S =* ，且VT*，則稱是文法G的句子。 例 文法GS： S0S1， S01 因?yàn)镾 0S1 00S11 000S111 00001111
10、 所以S,0S1 ,00S11 ,000S111,00001111都是G的句型,00001111是G的句子 由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型,2、語(yǔ)言的定義 由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01 S0S1 00S11 03S13 0n-1S1n-1 0n1n L(G)=0n1n|n1 3、文法和語(yǔ)言的關(guān)系： 文法G生成的每個(gè)終結(jié)符號(hào)串都在L(G)中 L(G)中的每個(gè)串確實(shí)能被G生成,2. 語(yǔ)法樹(shù),1、定義：語(yǔ)法樹(shù)是這樣的一個(gè)語(yǔ)法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于開(kāi)始符號(hào)。
11、只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。 2、引入語(yǔ)法樹(shù)的意義：作為識(shí)別句子的輔助工具，語(yǔ)法樹(shù)可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。,3、作用:直觀地描述上下文無(wú)關(guān)文法的句型推導(dǎo) 過(guò)程。給定文法G=(VN,VT,P,S)，對(duì)于G的任何句 型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù),語(yǔ)法樹(shù)的相關(guān)概念,結(jié)點(diǎn)：每個(gè)樹(shù)的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。 邊：兩個(gè)結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹(shù)：語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分 末端結(jié)點(diǎn)：
12、沒(méi)有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹(shù)中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)。,語(yǔ)法樹(shù)的特征,給定文法G，G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）。這棵樹(shù)具有下列特征： 1、根結(jié)點(diǎn)的標(biāo)記是開(kāi)始符號(hào)S； 2、每個(gè)結(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號(hào)； 3、若一棵子樹(shù)的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2AR，那么 A A1A2..AR一定是P中的一條規(guī)則； 4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則AVN 5、若樹(shù)的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)生的句子。,
13、構(gòu)造語(yǔ)法樹(shù),方法：把開(kāi)始符號(hào)做為根結(jié)點(diǎn)，對(duì)每一個(gè)直接推導(dǎo)畫(huà)一個(gè)分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無(wú)分支可畫(huà)結(jié)束。,例如：推導(dǎo) S AB AcBd Accdd abccdd,S,B,B,d,b,a,A,c,d,c,,,,,,,,,,語(yǔ)法樹(shù)的構(gòu)造過(guò)程,S AB AcBd Accdd abccdd,S,S,B,A,,,S,B,B,d,A,c,,,,,,S,B,B,d,A,c,d,c,,,,,,,,S,B,B,d,b,a,A,c,d,c,,,,,,,,,,（1）,（2）,（3）,（5）,（4）,例：文法G：EE+T|TTTF|F F（E）|i 句型T+TF的推導(dǎo)過(guò)程與語(yǔ)法樹(shù),E=E
14、+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,從語(yǔ)法樹(shù)中看不出句型中的符號(hào)被替代的順序,從左到右讀出葉子結(jié)點(diǎn)得到的符號(hào)串，為文法的句型。也把該語(yǔ)法樹(shù)稱為該句型的語(yǔ)法樹(shù)。,2.5 文法和語(yǔ)言的一些特性,1、無(wú)用非終結(jié)符：某個(gè)非終結(jié)符不出現(xiàn)在文法的任何一個(gè)句型中，并且不能從它推出終結(jié)符號(hào)串。含有該非終結(jié)符的規(guī)則即不可終止。 2、不可達(dá)文法符號(hào)：如果一個(gè)非終結(jié)符不出現(xiàn)在該文法的任何其他的產(chǎn)生式的右部。該非終結(jié)符為不可達(dá)文法符號(hào)，含有該非終結(jié)符的規(guī)則即不可達(dá)規(guī)則 3、有害規(guī)則：UU ,無(wú)用且引起文法的二義 4、可空非終結(jié)符： 2型文法允許以下產(chǎn)生式 S，該產(chǎn)生式稱為空產(chǎn)生式，S稱為可
15、空非終結(jié)符。在消除左遞歸方法中用到空產(chǎn)生式。,例：文法GS： （1）SBe （2）BCe （3）BAf （4）AAe （5）Ae（6）CCf （7）Df 多余規(guī)則為：（6）不可終止 （7）不可到達(dá),文法G：EE+E|EE|（E）|i 句子 ii+i 對(duì)應(yīng)的語(yǔ)法樹(shù),兩個(gè)不同的最左推導(dǎo)： 推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i 推導(dǎo)2：E EE iE iE+E ii+E ii+i,2.5文法的二義性(Ambiguity),如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。二義性文法存在某個(gè)句子,它有兩個(gè)不同的最左（右）推導(dǎo)。,為什么要避免文法產(chǎn)生二義性？
16、,二義性的文法將給編譯程序的執(zhí)行帶來(lái)問(wèn)題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的理解。語(yǔ)法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語(yǔ)義處理上的不確定性。因此，希望描述語(yǔ)言的文法是無(wú)二義性的。,如何消除文法的二義性？(1),方法一：不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。 如1：對(duì)于文法 GE: E i E E+E E E*E E (E) 規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即*優(yōu)先于+，+、*服從左結(jié)合。,如何消除文法的二義性？(2),方法二：構(gòu)造一個(gè)等價(jià)的無(wú)二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫(xiě)原有的文法。 如文法 GE: E i E
17、E+E E E*E E (E) 將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無(wú)二義性的文法 GE: E T|E+T T F|T*F F （E）|i,2.6 分析方法簡(jiǎn)介,對(duì)于2型文法,如何識(shí)別一個(gè)符號(hào)串是否為某文法的句型或句子，有兩種分析方法： 自頂向下分析法 (Top-Down parsing) 自底向上分析法 (Bottom-Up parsing),2.6.1 自頂向下的分析方法,1、定義:從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。 2、語(yǔ)法樹(shù)的構(gòu)造：將文法的開(kāi)始符號(hào)作為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。,
18、例 文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子,S,推導(dǎo)過(guò)程：,=cabd,S,=cAd,3、自頂向下方法的主要問(wèn)題 對(duì)輸入串cabd自上而下構(gòu)造語(yǔ)法樹(shù)的另一過(guò)程,不成功，不成功的原因是選錯(cuò)產(chǎn)生式Aa,自頂向下分析的主要問(wèn)題是選擇產(chǎn)生式 : 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：BA1|A2||An，那么如何確定用哪個(gè)右部去替代B？只能試探性地構(gòu)造，如果選錯(cuò)了產(chǎn)生式，必須退回原來(lái)的狀態(tài)，往前回退稱為回溯。,S,2.6.2 確定的自頂向下的分析方法,當(dāng)文法的某一個(gè)非終結(jié)符有幾條產(chǎn)生式、而且每條產(chǎn)生式右部都是終結(jié)符時(shí)，應(yīng)保證它們是互不相同的終結(jié)符
19、。,2.6.3 自底向上的分析方法,1、定義:從輸入符號(hào)串開(kāi)始，在其中尋找句柄，此句柄如果與某一產(chǎn)生式右部相匹配，就用產(chǎn)生式左部去替換句柄，替換之后得一新符號(hào)串，繼續(xù)進(jìn)行同樣的句柄替換處理。這種處理過(guò)程是一種歸約過(guò)程，直至歸約到文法的開(kāi)始符號(hào)。 2、語(yǔ)法樹(shù)的構(gòu)造：從輸入符號(hào)串開(kāi)始，以它作為語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上的構(gòu)造語(yǔ)法樹(shù),例 文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子,歸約過(guò)程：,用“|-”表示歸約，下劃線部分為被歸約符號(hào),cabd,|-cAd,|-S,3、自底向上分析的主要問(wèn)題 對(duì)輸入串cabd的兩種歸約過(guò)程 （1）cabd|-cAd|-
20、S 歸約到開(kāi)始符 （2）cabd|-cAbd 不能歸約到開(kāi)始符 在自下而上的分析方法中，每一步都是從當(dāng)前串中選擇一個(gè)子串加以歸約，該子串暫稱“可歸約串”。 如何確定“可歸約串”是自下而上分析的主要問(wèn)題。,為了刻劃“可歸約串”,引入下面的概念,1、短語(yǔ)，直接短語(yǔ)和句柄 定義:設(shè)是文法GS中的一個(gè)句型，如果有S=*A且A=+，則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ) 特別的如有A=，則稱是句型相對(duì)于規(guī)則A的簡(jiǎn)單短語(yǔ)。 一個(gè)句型的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄(Handle)。句柄就是“可歸約串”,2.6.4文法在內(nèi)存中的表示,在計(jì)算機(jī)中，可以為相關(guān)文法建立一個(gè)產(chǎn)生式表，把文法的所有產(chǎn)生式都放在這個(gè)產(chǎn)生式表中。為了在自下而上分析過(guò)程中迅速找到可規(guī)約子串相匹配的產(chǎn)生式右部，可以為產(chǎn)生式建立一個(gè)目錄表。在目錄表的每一項(xiàng)中，都存放著一個(gè)產(chǎn)生式右部的尾符號(hào)和一個(gè)指針，這個(gè)指針指示該產(chǎn)生式在產(chǎn)生式表中的位置。具有相同產(chǎn)生式右部尾符號(hào)的產(chǎn)生式被連接成一個(gè)產(chǎn)生式鏈。,
《形式語(yǔ)言理論》PPT課件.ppt
