形式語言與自動機理論基礎(chǔ)(形式語言).ppt

《形式語言與自動機理論基礎(chǔ)(形式語言).ppt》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機理論基礎(chǔ)(形式語言).ppt（45頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第二章 形式語言與自動機理論基礎(chǔ),2.1 預備知識 2.2 文法的討論 2.3 文法和語言的定義 2.4 分析樹和二義性 2.5 形式語言概觀,2.1 預備知識,2.1.1 字母表 2.1.2 符號串 一、符號串的定義 二、術(shù)語 三、符號串的運算 四、符號串集合的運算,字母表是符號的非空有窮集合；例：=a，b，c 任何程序語言都有自己的字母表。,2.1.1 字母表,1.計算機語言：由符號“0”和“1”組成的字 母表: =0，1 2. Pascal語言字母表： = AZ, az, 09, +, -, *, /, , :, ,”,;，.， , (, ), , , , 3. C語言字母表

2、： = AZ, az, 09, +, -, *, /, ,_,，.，?, (, ),,, , ,空格,!,#,% ,一. 符號串的定義 由字母表中的符號所組成的的任何有窮序列被稱之為該字母表上的符號串。空符號串：無任何符號的符號串，記作 ,2.1.2 符號串,符號串的形式定義： (1) 字母表上字符是上的符號串。 (2) 若x是上的符號串，而a是的元素,則xa 是上的符號串。 (3) y是上的符號串,當且僅當它由(1)和(2) 導出。,二 術(shù)語,（設s是符號串banana） 前 綴：移走s的尾部的零個或多于零個符號所得符號串 ,b,ba,ban,bana,banan,banana 后 綴

3、：刪去s的頭部的零個或多于零個符號所得符號串 banana,anana,nana,ana,na,a, 子 串: 從s中刪去一個前綴和一個后綴所得符號串 banana,anana,banan 真前綴、真后綴和真子串：不是s和的前綴、后綴和子串 子序列: 從s中刪去零個或多于零個符號(不要求是連續(xù)） 而得到的符號串。如baaa 長 度：是符號串中符號的個數(shù)。例如|aab|=3,||=0,語 言：確定字母表上字符串的任何集合,例如： 不含任何元素的空集合，即 只含有空符號串的集合 符合Pascal語法的程序組成的集合 （ Pascal語言） 符合英文語法

4、的句子組成的集合,1.連接：設x和y是符號串，它們的連接xy是把符號串y寫在符號串x的之后得到的符號串。 例如 x=ba,y=nana,xy=banana. x= x = ba 2.方冪：x0= x1=x x2=xx xn=xn-1x 例如 x=ba x1=ba x2=baba x3=bababa,,三. 符號串的運算,（語言L和M ） 1.合并：LMs|sL or sM 屬于L或?qū)儆贛的符號串s所組成的集合 2.連接：LMst|sL and tM s屬于L和t屬于M的所有符號串st組成的集合 L = L = L 3.方冪： L0 = L1L LnL（n-1）L

5、 (n0),四. 語言 (符號串集合）的運算,4.語言L的正閉包，記作L+ L+ L1L2L3L4 5.語言L的Kleene閉包(自反閉包)，記作L* L* L0 L L0L1L2L3,例：A=x,y A？ A* ？,x,y, xx,xy,yx,yy , A1 A2 , x,y, xx,xy,yx,yy , A0 A1 A2,例:（語言 L=AZ,az D=09） 1LD =A Z,a z ,0 9 2LD 所有一字母后跟一數(shù)字組成的符號串構(gòu)成的集合 3L4 所有的四個字母的符號串構(gòu)成的集合 4L（LD)* 所有字母打頭的字母和數(shù)字符號串構(gòu)成的集合 5D+ 所有

6、長度大于等于1的數(shù)字串構(gòu)成的集合,2.2 文法的討論,例：有一英文句子：“The grey wolf will eat the goat.” 。這是一個在語法、語義上都正確的句子。如何用語法單位如、等推導出該句子？,BNF范式表示法：如果用符號“ ”(或“::=”)表示“定義為”，用符號“|”表示“或”，表示語法成分,句子 主語 謂語 （1） 主語 冠詞 形容詞 名詞 （2） 冠詞the （3） 形容詞 grey （4） 謂語 動詞 直接賓語 （5） 動詞 助動詞 動詞原形 （6） 助動詞will （7） 動詞原形 eat （8） 直接賓語 冠詞 名詞

7、 （9） 名詞wolf （10） 名詞 goat （11）,名詞wolf |goat,由規(guī)則推導句子：有了一組規(guī)則之后，可以按照一定的方式 用它們?nèi)ネ茖Щ虍a(chǎn)生句子。 推導方法：從一個要識別的符號開始推導，即用相應規(guī)則的 右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進行推導。, = = 冠詞 形容詞 名詞 這種推導一直進行下去，直到所有帶的符號都由終結(jié)符號替代為止。,1、終結(jié)符號集 VT=the , gray, wolf, will, eat, goat 2、非終結(jié)符號集 VN=句子，主語， 謂語， 冠詞，形容詞，名詞， 動詞 ， 直接賓語，助動詞，動詞原形 3、語

8、法規(guī)則集 P=句子 主語謂語， 4、開始符號 S= 句子,推導句子所需的四部分,2.3 文法和語言的形式定義,一. 文法的形式定義 二. 直接推導和推導 三. 語言的形式定義 四. 短語、直接短語、句柄,一.文法和語言的形式定義,定義1.1：一個上下文無關(guān)文法G是一個四元組G=（ VT，VN S, P ），其中： 1. VT 是一個非空有窮終結(jié)符號集合； 2. VN 是一個非空有窮的非終結(jié)符號集合， 且VTVN，表示一類具有某種性質(zhì)的符號 3. S VN 開始符號。 4. P是一個產(chǎn)生式的非空有窮集合，每個產(chǎn)生式的形式是A，其中 AVN，（VTVN）* 開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)

9、一次,(VTVN）*表示什么集合?,一般情況下（缺省）符號指稱： 1、A，B，C等，表示非終結(jié)符號 2、a,b,c,d等，表示終結(jié)符號 3、,，等,表示文法符號串（終結(jié)符號和非終結(jié)符號組成的符號串）,G=( a, +, *, (, ) , ，， ， ，P ) P： * （ ) a （用E、T、F分別代替 、 、 ） E E+T T T T*F F F ( E ) a,例 簡單算術(shù)表達式的文法G,二. 直接推導和推導,令G=(VT,VN,S,P), S A；若A P, 且,(VTVN)*稱A直接推出,表示成A 同時也稱是A的直接推導，或稱 直接歸約到A 如果存

10、在一個直接推導序列： 012 n（n0） 表示成 0 n ，稱從0到n的長度為n的推導。 0 n表示從0出發(fā)，經(jīng)0步或若干步，可推導出n（ 0 = n 或 0 n ）,+ ,* ,+ ,推導 ：E E+T T+T F+T a+T a+F a+a,E E+T T T T*F F F ( E ) a,例如 EE+TT+TF+Ta+Ta+T*F a+F*Fa+a*Fa+a*a 特點：A (A)，VT* （最左推導） 每一步推導都是對最左非終結(jié)符號進行替換 EE+TE+T*FE+T*aE+F*a E+a*a T+a*aF+a*aa+a*a 特點：A (A)， VT*（最右推導）

11、每一步推導都是對最右非終結(jié)符號進行替換，也稱規(guī)范推導，其歸約稱為規(guī)范歸約,最左推導和最右推導,三. 語言的形式定義,四. 短語、直接短語、句柄,令G是一個文法，如果有S A且A 則稱是一個關(guān)于非終結(jié)符號A的，句型的 短語。 其次如果有 S A 且 A則稱是直接短語。 一個句型的最左直接短語稱為該句型的句柄。,* ,+ ,* ,注意：短語、直接短語是相對于句型而言，一個句型 可能有多個短語、直接短語，句柄只能有一個。,S aAS aSbAS aabAS,例：S aAS|a A SbA,一. 分析樹的定義 二. 畫出分析樹 三. 子樹 四. 二義性文法的定義,2.4 分析樹(語法樹) 和二義性

12、,設G=（VT，VN，S，P）是一個上下文無關(guān)文法,G的一棵分析樹應滿足如下條件： 每個結(jié)點有個標記，是VTVN中的符號 根的標記是S 如果結(jié)點是內(nèi)部結(jié)點，則其標記A必在VN中 如果編號為n的結(jié)點其標記為A,n1,n2,,nk是結(jié)點n的從左到右的兒子，并分別有標記X1,X2,,Xk，則AX1X2Xk必須是P的產(chǎn)生式 如果結(jié)點n有標記，那么結(jié)點n是葉子，且是它父親唯一的兒子，其他葉子結(jié)點是終結(jié)符,一.分析樹（語法樹）的定義,G (S): (1) SaASa (2) A SbA SS ba 句子aabbaa的分析樹,3,1,2,4,6,5,7,8,9,10,11,,,,,,,,,,,S,a,A,S

13、,S,b,A,a,a,b,a,A,S,a,S,b,S,A,a,a,b,a,,,,,,,,,,,aSbAS,aabAS,aabbaS,aabbaa,aAS,,S,二. 畫分析樹 (自頂向下）,1、短語：一棵子樹的所有葉子自左至右排列起來形成一個相對于子樹根的短語。 2、直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。 3、句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。,子樹和短語、直接短語、句柄,S aAS aSbAS,例：S aAS|a A SbA,對表達式文法G和句子a+a*a，挑選出最左推導過程中產(chǎn)生的句型中的短語，直接短語，句

14、柄,G=( a, +, *, (, ) , ，， ， ，P ) P：（用E、T、F分別代替 、 、 ） E E+T T T T*F F F ( E ) a,E,E+T,T+T,F+T, a+T, a+T*F, a+F * F, a+a *F,a+a *a,E,E+T,T+T,F+T, a+T, a+T*F, a+F * F, a+a *F,E+T,T, T+T,F, F+T,a, a+T,a, T*F, a+T*F,a, F , F*F, a+F*F,a, a, a+ a *F, a *F,a, a, a, a * a a+ a *a,E,E,+,T,T,F,a,T,*,

15、F,F,a,a,a+a *a,短語,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例,給定文法G=(a,b,c,d,e,S,A,B,S,P) 其中P: SaAcBe Ab AAb Bd 給出句子abbcde的最右推導過程，并指出每一步推導的短語、直接短語、句柄。,S aAcBe aAcBe aAcBe aAcBe,abbcde abbcde,b,bb,d b,d b,,,,短語 直接短語 句柄,aAcde aAcde, d d d,aAbcde aAbcde,d,Ab Ab, d Ab,,引例 文法 G產(chǎn)

16、生式如下： EE+EE*E (E) a 對于句子a+a*a, 有如下兩個最左推導： EE+E a+E a+E*E a+a*E a+a*a EE*EE+E*E a+E*Ea+a*E a+a*a,四. 文法的二義性（ ambiquity ）的定義,EE+E a+E a+E*E a+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a*a,E,E,+,E,E,*,E,a,a,a,,,,,,,,,,E,E,*,E,+,E,E,a,a,a,,,,,,,,,,如果一個文法的句子存在兩棵語法樹,則稱該句子是二義性的；換而言之，無二義性文法的句子只有一棵語法樹，盡管推

17、導過程可以不同。 如果一個文法包含二義性句子,則稱這個文法是二義性的; 否則，該文法是無二義性的。,不存在一個算法，它能在有限步驟內(nèi)，確切地判定一個文法是否是二義的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。,文法等價,定義：如果兩個文法G1、G2對應的語言集合相同L(G1)=L(G2)，則稱文法等價,若文法G存在形如A A的推導,則稱文法G是遞歸文法. 文法 G1產(chǎn)生式如下： EE+EE*E (E) a 直接遞歸文法 文法 G2產(chǎn)生式如下： ET+a T E*a 間接遞歸文法,遞歸文法,2.5 形式語言概觀,N.Chomsky把文法分為四種類型，即0型、

18、1型、2型、3型。差別在于對產(chǎn)生式施加了不同限制 0型：G=(VT,VN,S,P) 規(guī)則形式： , (VT VN)*, 0型文法產(chǎn)生的語言稱為0型語言 1型（上下文有關(guān)）： 規(guī)則有 產(chǎn)生式形式 ： A A VN, ,, (VT VN)*, 1型文法產(chǎn)生的語言稱為1型語言（上下文有關(guān)）,2型（上下文無關(guān)）：規(guī)則形式 ： A A VN， (VT VN)* 2型文法產(chǎn)生的語言稱為2型語言（上下文無關(guān)） 3型（正規(guī)文法）：左線性和右線性文法 AaB或Aa（右線性） A, BVN a VT ABa或Aa （左線性） 3型文法產(chǎn)生的語言稱為3型語言（正規(guī)語言),,,,,,語言層,正規(guī)語言3,上下文無關(guān)語言2,上下文有關(guān)語言1,遞歸可枚舉語言0,圖靈機TM,線性界限自動機LBA,下推自動機PDA,有窮自動機FA,,,,,小 結(jié),掌握符號串和符號串集合的運算、文法和語言的定義 幾個重要概念：短語、直接短語和句柄、分析樹（語法樹）、文法的二義性。 了解文法和語言的分類。,