《文法和語(yǔ)言》PPT課件.ppt_第1頁(yè)
《文法和語(yǔ)言》PPT課件.ppt_第2頁(yè)
《文法和語(yǔ)言》PPT課件.ppt_第3頁(yè)
《文法和語(yǔ)言》PPT課件.ppt_第4頁(yè)
《文法和語(yǔ)言》PPT課件.ppt_第5頁(yè)
已閱讀5頁(yè),還剩71頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1,第三章 文法和語(yǔ)言,本章目的為語(yǔ)言的語(yǔ)法描述尋求工具,以便: 對(duì)源程序給出精確無(wú)二義的語(yǔ)法描述。(嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀) 根據(jù)語(yǔ)言文法的特點(diǎn)來(lái)指導(dǎo)語(yǔ)法分析的過(guò)程 從描述語(yǔ)言的文法可以自動(dòng)構(gòu)造出可用的分析程序 制導(dǎo)語(yǔ)義翻譯,2,文法和語(yǔ)言,預(yù)備知識(shí) 文法和語(yǔ)言的形式定義 文法的類(lèi)型 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 上下文無(wú)關(guān)文法的句型分析 有關(guān)文法實(shí)用中的一些說(shuō)明 有關(guān)文法的一些關(guān)系,3,預(yù)備知識(shí) -語(yǔ)言概述,語(yǔ)言是由句子組成的集合,是由一組記號(hào)所構(gòu)成的集合。 漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體 英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體 程序設(shè)計(jì)語(yǔ)言-所有該語(yǔ)言的程序的全體 每個(gè)句子構(gòu)成的規(guī)律 研究語(yǔ)言 每個(gè)句子的含義 每個(gè)句子和使用者的關(guān)系,4,預(yù)備知識(shí) -語(yǔ)言概述,研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系 語(yǔ)言研究的三個(gè)方面 語(yǔ)法 Syntax 語(yǔ)義 Semantics 語(yǔ)用 Pragmatics,5,預(yù)備知識(shí) -語(yǔ)言概述,語(yǔ)法 - 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律 語(yǔ)義 - 表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。(各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系) 語(yǔ)用 -表示在各個(gè)記號(hào)所出現(xiàn)的行為中,它們的來(lái)源、使用和影響。,6,預(yù)備知識(shí) -語(yǔ)言概述,每種語(yǔ)言具有兩個(gè)可識(shí)別的特性,即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。 語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的,其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看,其一是該句子的創(chuàng)立者所想要表示的意義,另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的,前者稱(chēng)為語(yǔ)言的語(yǔ)義,后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。,7,預(yù)備知識(shí) -形式語(yǔ)言,如果不考慮語(yǔ)義和語(yǔ)用,即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言,這種意義下的語(yǔ)言稱(chēng)作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。“形式”是指這樣的事實(shí):語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。,8,預(yù)備知識(shí) -有關(guān)定義和記號(hào),符號(hào):可以相互區(qū)別的記號(hào)(元素)。 字母表:符號(hào)(元素)的非空有窮集合。 符號(hào)串:由字母表中的符號(hào)組成的任何有窮序列稱(chēng)為該字母表上的符號(hào)串。1.空符號(hào)串(沒(méi)有符號(hào)的符號(hào)串)是上的符號(hào)串 2.若x是上的符號(hào)串,a是的元素,則xa是上的符號(hào)串 3. y是上的符號(hào)串,當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。 例如: =a,b ,a,b,aa,ab,aabba都是上的符號(hào)串,9,預(yù)備知識(shí) -有關(guān)定義和記號(hào),符號(hào)串s的前綴:移走符號(hào)串s尾部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串. 如: b是符號(hào)串banana的一個(gè)前綴. 符號(hào)串s的后綴:刪去符號(hào)串s頭部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串. 如:nana是符號(hào)串banana的一個(gè)后綴. 符號(hào)串s的子串:從s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串. 如:ana是符號(hào)串banana的一個(gè)子串.,10,對(duì)于每個(gè)符號(hào)串s, s和兩者都是符號(hào)串s的前綴,后綴和子串。 符號(hào)串s的真前綴,真后綴,真子串:任何非空符號(hào)串 x,相應(yīng)地,是s的前綴,后綴或子串,并且 s x 符號(hào)串的運(yùn)算 符號(hào)串的長(zhǎng)度:符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串s的長(zhǎng)度記為|s|。 的長(zhǎng)度為0 連接:符號(hào)串x、y的連接,是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串xy 如 x=ab,y=cd 則 xy=abcd 有a = a 方冪:符號(hào)串自身連接n次得到的符號(hào)串 an 定義為 aaaa n個(gè)a a1=a, a2=aa則a0=,11,符號(hào)串集合:若集合A中所有元素都是某字母表上的符號(hào)串,則稱(chēng)A為字母表上的符號(hào)串集合。 兩個(gè)符號(hào)串集合A和B的乘積定義為 AB =xy|xA且yB 若 集合A=ab,cde B = 0,1 則 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符號(hào)串(包括)組成的集合。*稱(chēng)為的閉包。 上的除外的所有符號(hào)串組成的集合記為+ 。 +稱(chēng)為的正閉包。,12,例:=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,13,語(yǔ)言:字母表上的一個(gè)語(yǔ)言是上的一些符號(hào)串的集合 (上的每個(gè)語(yǔ)言是*的一個(gè)子集)。 例如: =a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或w|w*且w=anbn,n1為字母表上的一個(gè)語(yǔ)言。 集合a,aa,aaa, 或w|w*且w=an,n1 為字母表上的一個(gè)語(yǔ)言。 是一個(gè)語(yǔ)言。 即 是一個(gè)語(yǔ)言。,14,語(yǔ)言上的運(yùn)算,設(shè)L是(上的)一個(gè)語(yǔ)言,M是(上的)一個(gè)語(yǔ)言, 語(yǔ)言L和M的并,交,差,補(bǔ)是一個(gè)語(yǔ)言。 如語(yǔ)言L和M的并為 LM,是一個(gè)語(yǔ)言: w|w is in L or is in M 如: L1 =a,b,y,z M1 =1,28,9 L1M1=a,b, y,z,1,28,9 語(yǔ)言L和M的連接是一個(gè)語(yǔ)言,記為 LM LM=st |sL且 tM 如: L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L。 L的n次連接Ln= LL.L,15,語(yǔ)言上的運(yùn)算,語(yǔ)言L的 閉包記為 L*, L*= L0 L1 L2 . L0= , Ln= L Ln-1= Ln-1 L,n1 語(yǔ)言L的正 閉包記為 L+, L+= L1 L2 L3 . L+= LL*= L*L L*= L+ 如: L1 =a,b,y,z M1 =1,28,9 (L1M1)=a,b, y,z,1,28,9 (L1M1)*=a,b, y,z,1,28,9 ,aa,1a,xyz,6789st L1(L1M1)*=所有字母打頭的字母和數(shù)字符號(hào)串,16,語(yǔ)言的描述,如何來(lái)描述一種語(yǔ)言? 如果語(yǔ)言是有窮的(只含有有窮多個(gè)句子),可以將句子逐一列出來(lái)表示 如果語(yǔ)言是無(wú)窮的,找出語(yǔ)言的有窮表示。兩個(gè)途經(jīng): 生成方式 (文法):語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。 識(shí)別方式(自動(dòng)機(jī)):用一個(gè)過(guò)程,當(dāng)輸入的一任意串屬于語(yǔ)言時(shí),該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”,若不屬于,要麼能停止并回答“不是”,(要麼永遠(yuǎn)繼續(xù)下去。),17,文法 數(shù)學(xué)系統(tǒng),一個(gè)形式數(shù)學(xué)系統(tǒng)可由下列基本成分來(lái)刻畫(huà):一組基本符號(hào),一組形成規(guī)則,一組公理,一組推理規(guī)則。,18,文法和語(yǔ)言的形式定義,文法的定義 推導(dǎo)的定義 句型、句子、語(yǔ)言的定義,19,文法的定義,文法G定義為四元組(VN,VT,P,S) VN :非終結(jié)符集 VT :終結(jié)符集 P:產(chǎn)生式(規(guī)則)集合 S:開(kāi)始符號(hào) VNVT= , SVN V=VNVT,稱(chēng)為文法G的文法符號(hào)集合,20,規(guī)則的定義,規(guī)則(重寫(xiě)規(guī)則、產(chǎn)生式或生成式),是形如或=的(,)有序?qū)?,且V+,V*。 稱(chēng)為規(guī)則的左部(或生成式的左部)。 稱(chēng)為規(guī)則的右部(或生成式的右部)。,21,文法的定義,例3.1 文法G=(VN,VT,P,S) VN = S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào),22,文法的定義,習(xí)慣上只將產(chǎn)生式寫(xiě)出。并有如下約定: 第一條產(chǎn)生式的左部是開(kāi)始符號(hào) 用尖括號(hào)括起的是非終結(jié)符,否則為終結(jié)符?;蛘叽髮?xiě)字母表示非終結(jié)符,小寫(xiě)字母表示終結(jié)符 G可寫(xiě)成GS,S是開(kāi)始符號(hào) G:SaAb Aab AaAb A GS: Aab AaAb A SaSb 縮寫(xiě)形式 GS: Aab |aAb | SaSb 注意:元符號(hào)和源符號(hào),例3.2 文法G=(VN,VT,P,S) VN =標(biāo)識(shí)符,字母,數(shù)字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,24,推導(dǎo)的定義,直接推導(dǎo)“” 是文法G的產(chǎn)生式,若有v,w滿足: v=,w= , 其中V*,V* 則稱(chēng)v直接推導(dǎo)到w,記作 v w 或w直接歸約到v 例:G: S0S1, S01 S 0S1 00S11 000S111 00001111 . . . VAR;BEGIN READ()END. VAR A;BEGIN READ(A) END.,25,推導(dǎo)的定義,若存在v w0 w1 . wn=w,(n0) 則稱(chēng)v w,v推導(dǎo)出w,或w歸約到v 若有v w,或v=w, 則記為v w,26,文法的句型、句子的定義,句型 有文法G,若S x,則稱(chēng)x是文法G的句型。 句子 有文法G,若S x,且xVT*,則稱(chēng)x是文法G的句子。 例:G: S0S1, S01 S 0S1 00S11 000S111 00001111,27,例:GE:EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 表示一切能用符號(hào)a,+,*,(和)構(gòu)成的算術(shù)表達(dá)式,28,文法,語(yǔ)言的定義,由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的一切句子的集合: L(G)=x|S x,其中S為文法的開(kāi)始符號(hào),且x VT* 例:G: S0S1, S01 L(G)=0n1n|n1,例3.3 文法GS: (1)SaSBE (2)SaBE (3)EBBE (4)aBab (5)bBbb (6)bEbe (7)eEee L(G)= anbnen | n1 ,30,S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE (bBbb) aabbeE (bEbe) aabbee (eEee) G生成的每個(gè)串都在L(G)中 L(G)中的每個(gè)串確實(shí)能被G生成,已知語(yǔ)言描述,寫(xiě)出文法 例:若語(yǔ)言由0、1符號(hào)串組成,串中0和1的個(gè)數(shù)相同,構(gòu)造其文法。 A 0B|1C B 1|1A|0BB C 0|0A|1CC 已知文法,寫(xiě)出語(yǔ)言描述 例:GE:EE+T|T TT*F|F F(E)|a,32,語(yǔ)法 Syntax 語(yǔ)義 Semantics,偶正整數(shù)的集合0,2,4,2n , dd.0(2,4,6,8),33,文法的等價(jià),若L(G1)=L(G2),則稱(chēng)文法G1和G2是等價(jià)的。 如文法G1A:A0R 與G2S:S0S1 等價(jià) A01 S01 RA1,34,文法的類(lèi)型,通過(guò)對(duì)產(chǎn)生式施加不同的限制,Chomsky將文法分為四種類(lèi)型: 0型文法:對(duì)任一產(chǎn)生式,都有(VNVT)+, (VNVT)* 1型文法:對(duì)任一產(chǎn)生式,都有|, 僅僅 S除外 2型文法:對(duì)任一產(chǎn)生式,都有VN , (VNVT)* 3型文法:任一產(chǎn)生式的形式都為AaB或Aa,其中AVN ,BVN ,aVT,35,文法的類(lèi)型,例:1型(上下文有關(guān))文法 文法GS: SaSBE SaBE EBBE aBab bBbb bEbe eEee,36,文法的類(lèi)型,例:1型(上下文有關(guān))文法 文法GS: SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD L(G)=ww|wa,b*,37,文法的類(lèi)型,例:2型(上下文無(wú)關(guān))文法 文法GS: SaB|bA Aa|aS|bAA Bb|bS|aBB 文法GS: S0A|1B|0 A0A|1B|0S B1B|1|0,38,文法的類(lèi)型,例:定義標(biāo)識(shí)符的3型(正規(guī))文法 文法GI: I lT I l T lT T dT T l T d,39,文法和語(yǔ)言,0型文法產(chǎn)生的語(yǔ)言稱(chēng)為0型語(yǔ)言 1型文法或上下文有關(guān)文法( CSG )產(chǎn)生的語(yǔ)言稱(chēng)為1型語(yǔ)言或上下文有關(guān)語(yǔ)言(CSL) 2型文法或上下文無(wú)關(guān)文法( CFL )產(chǎn)生的語(yǔ)言稱(chēng)為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言( CF L ) 3型文法或正則(正規(guī))文法( RG )產(chǎn)生的語(yǔ)言稱(chēng)為3型語(yǔ)言正則(正規(guī))語(yǔ)言( RL ),40,文法和語(yǔ)言,四種文法之間的關(guān)系 是將產(chǎn)生式做進(jìn)一步限制而定義的。 語(yǔ)言之間的關(guān)系依次:有不是上下文有關(guān)語(yǔ)言的0型語(yǔ)言,有不是上下文無(wú)關(guān)語(yǔ)言的1型語(yǔ)言,有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。,41,文法和識(shí)別系統(tǒng),0型文法(短語(yǔ)文法)的能力相當(dāng)于圖靈機(jī),可以表征任何遞歸可枚舉集,而且任何0型語(yǔ)言都是遞歸可枚舉的 1型文法(上下文有關(guān)文法):產(chǎn)生式的形式為1A212,即只有A出現(xiàn)在1和2的上下文中時(shí),才允許取代A。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。,42,帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁頭,圖靈機(jī),43,文法的類(lèi)型,2型文法(上下文無(wú)關(guān)文法、CFG):產(chǎn)生式的形式為A,取代A時(shí)與A的上下文無(wú)關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。 3型文法(正規(guī)文法、右線性文法):產(chǎn)生的語(yǔ)言是有窮自動(dòng)機(jī)(FA)所接受的集合,44,上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù),上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu) 算術(shù)表達(dá)式 語(yǔ)句 賦值語(yǔ)句 條件語(yǔ)句 讀語(yǔ)句 ,45,算術(shù)表達(dá)式上下文無(wú)關(guān)文法表示,文法G=(E, +,*,I,(,), P, E P: E i E E+E E E*E E (E),46,條件語(yǔ)句上下文無(wú)關(guān)文法表示,ifthen | ifthenelse ,47,上下文無(wú)關(guān)文法的語(yǔ)法樹(shù),用于描述上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的語(yǔ)法樹(shù)(推導(dǎo)樹(shù)),葉子結(jié)點(diǎn):樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。 從左到右讀出推導(dǎo)樹(shù)的葉子標(biāo)記,所得的句型為推導(dǎo)樹(shù)的結(jié)果。也把該推導(dǎo)樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)。,48,上下文無(wú)關(guān)文法的語(yǔ)法樹(shù),給定文法G,對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))。這棵樹(shù)滿足下列4個(gè)條件: 1、每個(gè)結(jié)點(diǎn)都有一個(gè)V中的符號(hào)作標(biāo)記 2、根的標(biāo)記是開(kāi)始符號(hào)S 3、若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫,并且n有標(biāo)記A,則AVN 4、如果結(jié)點(diǎn)n的直接子孫,從左到右的次序是結(jié)點(diǎn)n1,n2,nk,其標(biāo)記分別為A1,A2,Ak,那么AA1A2,Ak一定是P中的一個(gè)產(chǎn)生式,49,上下文無(wú)關(guān)文法的語(yǔ)法樹(shù),定理:G為上下文無(wú)關(guān)文法, 對(duì)于,有S ,當(dāng)且僅當(dāng) 文法G有以為結(jié)果的一棵推導(dǎo)樹(shù)。,50,上下文無(wú)關(guān)文法的語(yǔ)法樹(shù),推導(dǎo)過(guò)程中施用產(chǎn)生式的順序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,51,最左(最右)推導(dǎo):在推導(dǎo)的任何一步,其中、是句型,都是對(duì)中的最左(右)非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。 由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型,52,問(wèn)題:一個(gè)句型是否對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)?,53,例:GE: E i E E+E E E*E E (E),E E + E E * E i i i,E E * E i E + E i i,句型 i*i+i 的兩個(gè)不同的最左推導(dǎo): 推導(dǎo)1:E E+E E*E+E i*E+E i*i+E i*i+i 推導(dǎo)2:E E*E i*E i*E+E i*i+E i*i+i,54,二義文法,若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù),則稱(chēng)這個(gè)文法是二義的。 或者,若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左(右)推導(dǎo),則稱(chēng)這個(gè)文法是二義的。 產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的,則稱(chēng)此語(yǔ)言是先天二義的。,55,二義文法,判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義,或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言,這兩個(gè)問(wèn)題是遞歸不可解的。但可以為無(wú)二義性尋找一組充分條件。 二義文法改造為無(wú)二義文法 GE: E i GE:E T|E+T E E+E T F|T*F E E*E F (E)|i E (E) 規(guī)定優(yōu)先順序和結(jié)合律,56,句型的分析,句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型,是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。 在語(yǔ)言的編譯實(shí)現(xiàn)中,把完成句型分析的程序稱(chēng)為分析程序或識(shí)別程序。分析算法又稱(chēng)識(shí)別算法。 從左到右的分析算法,即總是從左到右地識(shí)別輸入符號(hào)串,首先識(shí)別符號(hào)串中的最左符號(hào),進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。,57,句型的分析,分析算法可分為: 自上而下分析法: 從文法的開(kāi)始符號(hào)出發(fā),反復(fù)使用各種產(chǎn)生式,尋找與輸入符號(hào)匹配的推導(dǎo)。 自下而上分析法: 從輸入符號(hào)串開(kāi)始,逐步進(jìn)行歸約,直至歸約到文法的開(kāi)始符號(hào)。 兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造過(guò)程,58,自上而下的語(yǔ)法分析,例:文法G:S cAd A ab A a 識(shí)別輸入串w=cabd是否該文法的句子,S S S c A d c A d a b 推導(dǎo)過(guò)程:S cAd cabd,59,自下而上的語(yǔ)法分析,例:文法G:S cAd A ab A a 識(shí)別輸入串w=cabd是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過(guò)程:S cAd cabd,60,句型分析的有關(guān)問(wèn)題,1)如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)? 假定要被代換的最左非終結(jié)符號(hào)是V,且有n條規(guī)則:VA1|A2|An,那么如何確定用哪個(gè)右部去替代V? 2)如何識(shí)別可歸約的串? 在自下而上的分析方法中,在分析程序工作的每一步,都是從當(dāng)前串中選擇一個(gè)子串,將它歸約到某個(gè)非終結(jié)符號(hào),該子串稱(chēng)為“可歸約串”,61,句型分析,短語(yǔ)、直接短語(yǔ)、句柄的定義:文法GS, S A且A b則稱(chēng)b是句型b相對(duì)于非終結(jié)符A的短語(yǔ)。若有A b則稱(chēng)b是句型b相對(duì)于該規(guī)則A b的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄。,62,句型分析,E F T T F F i1 * i2 + i3 短語(yǔ): 直接短語(yǔ): 句柄:,GE:EE+T|T TT*F|F F(E)|i 句型:i*i+i,63,有關(guān)文法實(shí)用中的一些說(shuō)明,有關(guān)文法的實(shí)用限制 上下文無(wú)關(guān)文法中的規(guī)則,64,有關(guān)文法的實(shí)用限制,文法中不得含有有害規(guī)則和多余規(guī)則 有害規(guī)則:形如UU的產(chǎn)生式。會(huì)引起文法的二義性 多余規(guī)則:指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則 1)文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn),該非終結(jié)符稱(chēng)為不可到達(dá) 2)文法中某些非終結(jié)符,由它不能推出終結(jié)符號(hào)串來(lái),稱(chēng)為不可終止的,65,有關(guān)文法的實(shí)用限制,對(duì)于文法GS,為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn),必須滿足如下兩個(gè)條件: 1)A必須在某句型中出現(xiàn)。 2)必須能從A推出終結(jié)符號(hào)串t來(lái)。 即1)文法GS,對(duì) 某兩個(gè)符號(hào)串和: S A 2)A t ,tVT,66,化簡(jiǎn)文法,例:GS 1) SBe SBe 2) BCe BAf 3) BAf AAe 4) AAe Ae 5) Ae 6) CCf 7) Df,67,上下文無(wú)關(guān)文法中的規(guī)則,具有形式A的規(guī)則稱(chēng)為規(guī)則,其中AVN 某些著作和講義中限制這種規(guī)則的出現(xiàn)。因?yàn)橐?guī)則會(huì)使有關(guān)文法的一些討論和證明變得復(fù)雜 兩種定義的唯一差別是句子在不在語(yǔ)言中。,68,上下文無(wú)關(guān)文法中的規(guī)則,如果語(yǔ)言L有一個(gè)有窮的描述,則L也同樣有一個(gè)有窮描述。并且可以證明,若L是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言或正規(guī)語(yǔ)言,則L和L-分別是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言,69,上下文無(wú)關(guān)文法中的規(guī)則,定理3.1 文法G,任一P中的產(chǎn)生式A,都有AVN,(VN VT)*,(即可能為),則L(G)也能這樣一種文法產(chǎn)生,任一產(chǎn)生式A,只有如下兩種形式: AVN, (VN VT)+,(即) 或者 S且 S不出現(xiàn)在任何產(chǎn)生式右邊,70,上下文無(wú)關(guān)文法中的規(guī)則,定理3.2 G是上下文有關(guān)文法,則存在另一個(gè)上下文有關(guān)文法G1,L(G)=L(G1),且G1的開(kāi)始符號(hào)不出現(xiàn)在G1的任何產(chǎn)生式的右邊。 若G為上下文無(wú)關(guān)文法或正規(guī)文法,類(lèi)似結(jié)論成立。,71,有關(guān)文法的一些關(guān)系,一般

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論