《《形式語言概論》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《形式語言概論》PPT課件.ppt（44頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第2章 形式語言概論,,文法和語言形式化定義 文法的類型 語言和語法樹 文法和語言的幾點說明 分析方法簡介 本章小結(jié),形式語言理論： 是指由數(shù)學方法研究自然語言和人工語言(程序設計語言)之語法理論，主要討論了語言和文法的數(shù)學機制以及語言和文法的分類。,文法的直觀概念,如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在 如何給出它的有窮表示的問題。雖然無法列出全部句 子，但是可以給出一些規(guī)則，用這些規(guī)則來說明句子 的組成結(jié)構(gòu)，然后用它們?nèi)ネ茖Мa(chǎn)生句子。,文法：是闡述語法的一個工具,“你是大學生” 對 “我是教師”對 “我大學生是”錯 “我學習大學生”對,〈句子〉∷=〈主語〉〈謂語〉 〈主語〉 ∷ =〈代詞〉|〈名詞〉 〈代詞〉 ∷ = 我|你|他 〈名詞〉 ∷ = 王明|大學生|教師|英語 〈謂語〉 ∷ =〈動詞〉〈直接賓語〉 〈動詞〉 ∷ = 是|學習 〈直接賓語〉 ∷ =〈代詞〉| ,〈句子〉 ? 〈主語〉〈謂語〉 ? 〈代詞〉〈謂語〉 ? 我〈謂語〉 ? 我〈動詞〉〈直接賓語〉 ?我是〈名詞〉 ? 我是教師,推導： 我是教師,,例如，描述標識符的文法如下： ::= ::= ::= ::=a|b|c|d|…|z ::=0|1|2|3|4|5|6|7|8|9,字母表和符號串,字母表：是元素的非空有窮集合，用?表示。字母表中的元素稱為符號。 例如：漢語的字母表中包括漢字、數(shù)字及標點符號等。 PASCAL語言的字母表是由字母、數(shù)字、算符、保留字等組成。,符號串的長度：符號串中符號的個數(shù)。符號串x的長度記為|x|。如|ab012|=5。 空符號串：不含任何符號的符號串，記為ε。|ε|=0。,符號串：符號的有窮序列稱為符號串，如compiler, string等。,符號串的連接：設x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。 如: x=ab、y=123，則xy=ab123。顯然，εx=xε=x。,符號串集合的乘積：兩個符號串集合A和B的乘積定義為：AB={xy|x∈A且y∈B}。特別地{ε}A=A{ε}=A。 如: A={ab,c}, B={d, efg}, 則AB={abd,abefg,cd,cefg}。,符號串的方冪：設x為符號串，則xn=xx…x(x連接n次)。 特別有x0=ε。,符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。,符號串集合的方冪：同一符號串集合的乘積。 如: A={a,bc},則A2={aa,abc,bca,bcbc} A3 = A2A=?,符號串集合的正閉包: 符號串集合A正閉包A+=A1?A2?…. ?An?….即A+為集合A上所有符號串的集合。 符號串集合的自反閉包: 符號串集合A正閉包A*={?}?A+ = A+?{?} 顯然有 A+=AA*=A*A,文法,產(chǎn)生式： 設VN,VT分別是非空有限的非終結(jié)符號集和終結(jié)符號集，令V=VN?VT, VN?VT=?，一個產(chǎn)生式是一般形式為： A - ? ，其中A? VN, ? ? V*，，A稱為產(chǎn)生式的左部， ?稱為產(chǎn)生式的右部。 -表示為定義為… 如果產(chǎn)生式集合中的產(chǎn)生式有共同的左部， 如: A- ?， A- ?，則可將其簡寫為：A- ?| ? 。,,變量表,符號表,文法：文法G定義為四元組(VN,VT,P,S)。其中： VN：非終結(jié)符號集。非終結(jié)符號代表某一類的記號，如“算術(shù)表達式”、“賦值句”等等。 VT：終結(jié)符號集。終結(jié)符號代表不可再分的基本符號，如保留字、標識符、常數(shù)、運算符、界符等。 VN∩VT =Φ；V= VN∪VT稱為文法G的詞匯表。 S：開始符號。開始符號是一個特殊的非終結(jié)符號，表示文法G所定義的最終的語法范疇。 P：產(chǎn)生式的集合。產(chǎn)生式是定義語法范疇的一種書寫格式，形式如下： α→β 其中，α稱為產(chǎn)生式左部，它必須是包含非終結(jié)符；β稱為產(chǎn)生式右部，它可以是終結(jié)符、非終結(jié)符或他們的組合。,例1：文法G=（VN，VT，P，S） VN ={標識符，字母，數(shù)字} VT ={a,b,c,…x,y,z,0,1,…,9} P={ → → → →a,…, →z →0,…, →9 } S= 習慣上只將產(chǎn)生式寫出。并有如下約定： 1、第一條產(chǎn)生式的左部是開始符號； 2、用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符； 3、G可寫成G[S]，其中S是開始符號；,文法例子,例2：無符號二進制數(shù)的描述文法 如下形式：1011.0101 G=(VN,VT,P,B) VN ={B，Bi} VT ={0,1,.} P={ B→Bi | Bi .Bi Bi→0|1| Bi 0| Bi 1 },例3：設E代表“算術(shù)表達式”；i代表單個變量或常數(shù)； +、*、（、）是構(gòu)成算術(shù)表達式的運算符和括號。定義由前面符號組成的單個變量或常量組成的算術(shù)表達式；若E是一個算術(shù)表達式，則E+E,E*E,(E)也是算術(shù)表達式，寫成文法形式： G=(VN,VT,P,S) VN ={E} VT ={i ,+,*,(,)} P={ E→i , E →E+E, E →E*E, E →(E) },思考：(i+i)是不是該文法定義的表達式？,文法的類型： 語言學家喬姆斯基(Chomsky)把文法分成以下四種類型：,0型 ? 短語文法 1型 ? 上下文有關(guān)文法 2型 ? 上下文無關(guān)文法 3型 ? 正規(guī)文法,,文 法 類 型,,逐 漸 增 加 限 制,0型文法：對任一產(chǎn)生式α→β，都有α?(VN∪VT)+， β ?(VN∪VT)* 。 α至少含有一個非終結(jié)符。 1型文法（上下有關(guān)文法）：對任一產(chǎn)生式α→β，都有|β|≥|α|， 僅僅 S→ε除外。,1型文法又稱為上下文有關(guān)文法，它具有如下形式: α→β，除有可能S→ε外，均有 α=γ1Aγ2 β=γ1δγ2 , 其中γ1,γ2 ? (VN∪VT)*, A?VN, ,δ? (VN∪VT)+, 只有A出現(xiàn)在γ1,γ2的上下文中，才允許用δ取代A。 1型文法中, 1=|α|=|β|,1型文法例： G=（VN, VT，P，S），其中VN={S,B,C}，VT={a,b,c}， P={S→aSBC, S→abC, CB→BC, bB→bb, bC→bc, cC→cc},S=aSBC =aabCBC=aabBCC= aabbCC=aabbcC=aabbcc,,,,,,CB→CA CA→BA BA→BC,,2型文法（上下無關(guān)文法）：除有可能S→ε,對任一產(chǎn)生式A→δ，都有A?VN ， δ ?(VN∪VT)+。 2型文法左邊是單個非終結(jié)符，右邊是由終結(jié)符和非終結(jié)符組成的符號串。 上下無關(guān)文法也稱CFG文法(Context Free Grammar),2型文法例1： G=（VN，VT，P，S），其中VN={S，T}，VT={a，b，c, d}，P={S→aTd, T→bT|cT|b|c } 2型文法例2： G=（VN，VT，P，S），其中VN={S}，VT={0，1 }， P={S→0S1, S→01},3型文法（正規(guī)文法）：除S→ε外,所有產(chǎn)生式α→β的形式都為 A→aB或A→a， 其中A ? VN ，B ? VN ，a ? VT。 正規(guī)文法是CFG文法的一個子集,正規(guī)文法例： G=（VN，VT，P，A），其中VN={A, B, C, D}，VT={x, y, z }，P={A→xB|yC, B→zB|y|yC, C→xD, D→yD|x },若 則稱右線型文法,直接推導(定義2.3) ： 設文法G=（VN, VT, P, S），A→α是文法G的產(chǎn)生式，若有γ,δ∈V*，使得U=γAδ, w= γαδ, 則說：U（應用規(guī)則A→α）直接產(chǎn)生w 或說：w是U的直接推導 或說：w直接歸約到U 記作 U ?w。 特別地，當γ=δ=ε時， A ?α 例4： 文法G[S]： S→0S1， S→01 ，其中VN=S, VT={0,1} 直接推導： 0S1?0011 （U=0S1，w=0011，使用規(guī)則S→01，γ=0，δ=1） S ?0S1 （U=S，w=0S1，使用規(guī)則S→0S1，γ=ε，δ= ε ） 0S1?00S11 （U=0S1，w=00S11，使用規(guī)則S→0S1，γ=0，δ=1）,推導(定義2.4) ： 存在v =?0 =?1=…=?n=w, (n0) 則稱w為v的一個推導，記為v u。 另使用(定義2.5) v u 表示v u或 v=u,前面例子 G=(VN,VT,P,S) VN ={E} VT ={i ,+,*,(,)} P={ E→i , E →E+E, E →E*E, E →(E) },由 E →(E)，E=(E) 再由 E →E+E，(E)=(E+E) 再使用E →(E)， (E+E)=(i+E) =(i+i) 證明(i+i)是文法G的一個算術(shù)表達式(由終結(jié)符組成)。,v推導出w w規(guī)約到v,,最左推導,定義2.9 在xUy=xuy直接推導中，若x? VT*, U? VN, 即U是符號串xUy中最左非終結(jié)符，則稱此直接推導為最左直接推導。若一個推導的每一步直接推導都是最左直接推導，那么此推導稱為最左推導。 例 G12[]： →|| →a|b|c|…|x|y|z →0|1|2|3|4|5|6|7|8|9 ????a?a6?a69,最右推導,定義2.10 在xUy=xuy直接推導中，若y? VT*, U? VN, 即U是符號串xUy中最右非終結(jié)符，則稱此直接推導為最右直接推導。若一個推導的每一步直接推導都是最右直接推導，那么此推導稱為最右推導。 最右直接推導又稱為規(guī)范直接推導，最右推導又稱為規(guī)范推導。 例 文法如G12. ??9?9?69?69?a69,句型、句子和語言,定義2.6 如果符號串x是從開始符號推導出來的，即S x，則稱x是文法G[S]的句型。開始符號S也是文法G的句型。 定義2.7 如果符號串x是終結(jié)符號構(gòu)成，即S x，x? VT*，則稱x是文法G[S]的句子。 定義2.8 設S是文法G的開始符號，文法G的語言 L(G)={u|S?+ u, u? VT*}，即文法的語言是文法的所有句子構(gòu)成的集合。,例4中文法： S，0S1，000111都是文法G的句型，000111是G的句子。 〖結(jié)論〗句子一定是句型，句型不一定是句子。,區(qū)別,例: 文法G =（VN ，VT ，P，S）， 其中 VN={S}，VT ={0，1}， P={S → 0S1，S → 01} 表示什么語言？,答案：L(G)＝｛0n1n ?n?1｝,因為S?0S1?00S11 ?…? 0n1n 重復利用規(guī)則S?0S1,例：證明 (i*i+i)是文法 G(E)： E ? i | E+E | E*E | (E) 的一個句子。 證明： E ? (E) ? (E+E)? (E*E+E)? (i*E+E)? (i*i+E) ? (i*i+i) E，(E)，(E*E+E)，…，(i*i+i)是句型。,表示語言,表示語言,有文法推出語言,文法G[N]為： N-D|ND D-0|1|2|3|4|5|6|7|8|9 G[N]的語言是什么？,表示語言,G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9},G[N]的語言是 G(N)={(0|1|2|3|4|5|6|7|8|9)n |n=1},有語言推出文法,文法為,文 法 為,文 法 為,習題二2.2(4) 若i,j,k=0文法變成？,文 法 為,更 巧 妙 文 法 為,習題二2.2(6)能被5整除的整數(shù)集合的文法 E→N0|N5 N →ε| D D→0|2|3|4|5|6|7|8|9,N,(1)允許0開頭的偶正整數(shù)集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允許0開頭的偶正整數(shù)集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0,文法的化簡,化簡文法,例：G[S] 1) S→Be 2) B→Ce 3) B→Af 4) A→Ae 5) A→e 6) C→Cf 7) D→f,S→Be B→Af A→Ae A→e,文法和語言,0型文法產(chǎn)生的語言稱為0型語言 1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL） 2型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言（ RL ）,語法樹,設文法G=（VN, VT, P, S），對于文法G的任意一個句型都存在一個相應的語法樹： 樹中每個結(jié)點都有一個標記，該標記是VN?VT中的一個符號； 樹的根結(jié)點標記是文法的識別符號S； 若樹的一個結(jié)點至少有一個葉子結(jié)點，則該結(jié)點的標記一定是一個非終結(jié)符； 若樹的一個結(jié)點有多個葉結(jié)點，該結(jié)點的標記為A，這些葉結(jié)點的標記從左到右分別是B1，B2，….，Bn，則A?B1B2…Bn?P,文法的句型都可依據(jù)其產(chǎn)生式來生成相應的語法樹。,,問題：一個句型是否對應唯一的一棵語法樹？,例：G[Z]: Z → aZb Z → Z Z → ab,Z a Z b a b,,,,,,Z a Z b Z a b,,,,,,,句型aabb的語法樹,句型(i*i+i)的語法樹,E ?(E) ?(E+E) ?(E*E+E) ?(i*E+E) ?(i*i+E) ?(i*i+i),E ?(E) ?(E*E) ?(i*E) ?(i*E+E) ?(i*i+E) ?(i*i+i),文法G(E)： E ? i | E+E | E*E | (E),E ?T ?F ?(E) ?(E+T) ?(T+T) ?(T*F+T) ?(F*F+T) ?(i*F+T) ?(i*i+T) ?(i*i+F) ?(i*i+i),改寫為無二義文法 :,G(E)： E ? E+E E ? E*E E ? (E) E ? i,G[E]: E→E+T|T T→T*F|F F→(E)|i,,,上下文無關(guān)文法的語法樹,例: G[S]: E→E+T|T T→T*F|F F→(E)|i,E E + T T * F ( E ) i E + T,,,,,,,,,句型E+(E+T)*i的語法樹,葉子結(jié)點：樹中沒有子孫的結(jié)點。 從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結(jié)果。也把該推導樹稱為該句型的語法樹。,,,,,,產(chǎn)生式樹,例: G[S]:E→E+T|T, T→T*F|F, F→(E)|i,,,,*,T,F,i,,F,,,,,E,(,),,,,*,T,F,i,,F,,,,,E,(,),,,+,E,F,,(a),(b),(c),(d),(e),(f),文法和語言的幾點說明,(1) 文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達的； (2) 文法中某些非終結(jié)符，由它不能推出終結(jié)符號串來，稱為不可終止的（無用非終結(jié)符）； (3)可空終結(jié)符,可以用于消除左遞歸； (4)一個文法，如果它的一個句子有兩棵或兩棵以上的語法樹，則稱該句子具有二義性。如果一個文法含有二義性的句子，則該文法具有二義性。形如U→U的產(chǎn)生式。會引起文法的二義性。,自上而下分析方法,自上而下分析方法的基本思想是從文法的識別符號出發(fā)，看是否能夠推導出待檢查的符號串，如果能夠推導出這個符號串，則表明此符號串是該文法的一個句型或句子，否則便不是?；蛘哒f，以文法識別符號作為根結(jié)點，看其是否能夠構(gòu)造一個語法樹，而且此語法樹的所有葉子結(jié)點從左到右所構(gòu)成的符號串恰好是待檢查的符號串。如果能夠生成這樣的語法樹，則表明待檢查的符號串是該文法的一個句型或句子，否則便不是。 自上而下分析方法可分為：不確定的自上而下分析方法和確定的自上而下分析方法兩種。不確定的自上而下分析方法可能需要回溯，因此時間花費多，效率低,,自上而下的語法分析,例：文法G：S → cAd A → ab A → a 識別輸入串 w = cabd 是否該文法的句子,S S S c A d c A d a b 推導過程：S ? cAd ? cabd,,,,,,,,,自下而上分析方法,自下而上分析方法的基本思想是從待檢查的符號串出發(fā)，看最終是否能歸約（推導的逆過程）到文法的識別符號。如果能夠歸約到文法的識別符號，則表明此待檢查的符號串是該文法的一個句型或句子，否則便不是。 從待檢查的符號串出發(fā)，在其中尋找一個稱為句柄的子串，此句柄如果與文法中某一產(chǎn)生式右部相匹配，那么就用此產(chǎn)生式左部（一個非終結(jié)符）去替換待檢查符號串的句柄，替換之后得一個新符號串，然后，對這個新符號串作同樣的處理。這個過程稱為歸約過程。,,自下而上的語法分析,例：文法G：S → cAd A → ab A → a 識別輸入串 w = cabd 是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過程：S ? cAd ? cabd,,,,,,,,句型分析的有關(guān)問題,1）如何選擇使用哪個產(chǎn)生式進行推導？ 假定要被代換的最左非終結(jié)符號是V，且有n條規(guī)則：V→A1|A2|…|An，那么如何確定用哪個右部去替代V？ 2）如何識別可歸約的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結(jié)符號，該子串稱為“可歸約串”,小結(jié),文法和語言形式化定義； 文法的類型，0型文法，上下相關(guān)文法，上下無關(guān)文法，正規(guī)文法； 語言和語法樹，推導和規(guī)范推導、句型句子和語言、產(chǎn)生式樹； 文法和語言的幾點說明，多余規(guī)則，有害規(guī)則，二義性、可空終結(jié)符； 分析方法簡介 ，自上而下和自下而上的分析方法；,