編譯原理：第2章 形式語言與自動機基礎1

1、 課 程 內(nèi) 容第 1 章 編 譯 引 論第 2 章 形式語言與自動機基礎第 3 章 詞法分析 (Lexical Analysis)第 4 章 語法分析(Syntax Analysis) 自上而下分析法第 5 章 語法分析(Syntax Analysis) 自下而上分析法第 6 章 語義分析與中間代碼生成第 7 章 運 行 環(huán) 境第 8 章 代碼優(yōu)化（optimization）第 2 章內(nèi)容、要點與特點形式語言理論 編譯程序的加工對象（源語言）的形式化描述。自動機理論 源程序的識別、處理工具。 特點 形式化的 、抽象的。 第 2 章 形式語言與自動機基礎2.1 文法和語言2.2 有限自動機2.

2、3 正規(guī)式與有限自動機本節(jié)展開思路從文法和語言的直觀概念文法、語言的形式定義表示方法 類型二義性問題關于語言： 自然語言 人與人交互的工具； 程序設計語言 人機交互的工具。 Ch2 形式語言自動機理論基礎 2.1 文法和語言第 2 章 形式語言與自動機基礎2.1 文法和語言 2.1.1 語言的語法和語義 2.1.2 文法和語言的定義 2.1.3 文法的表示方法 2.1.4 語法樹與二義性 2.1.5 文法和語言的類型 自然語言的問題打白條傍大款考托Time Flies光陰似箭蒼蠅飛的速度下雨天留客天留我不留 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義屌絲牛

3、孩正能量Time Flies光陰似箭蒼蠅飛的速度 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義下雨天留客，天留我不留。自然語言的問題打白條傍大款考托屌絲牛孩正能量Time Flies光陰似箭蒼蠅飛的速度 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義下雨天，留客天，留我不？留。自然語言的問題打白條傍大款考托屌絲牛孩正能量 語言要素語法 （語言的描述規(guī)則）語義 （語言的含義） 語法是一種媒介，語義以語法為媒介來予以說明。 語言是由單詞按一定規(guī)則（文法）組成來表達特定意思的句子的集合。故對語言的分析集中于對句子的分析。而句子的分

4、析依據(jù)語言的文法規(guī)則。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 下面列出漢語語法規(guī)則中的其中七條規(guī)則： 句子主語謂語主語形容詞名詞謂語動詞賓語 賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃例2.1 : 分析漢語句子 “小八哥吃大花生”。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 巴科斯諾爾范式（BackusNaur Form）表示法 ，簡稱BNF。 ：表示語法成分。 ：（通常也用 := ）表示“定義為”或“由 組合成”的含義。 | ：“或”的含義。表示具有相同左部的產(chǎn)生規(guī) 則可用 “ | ”分開。

5、 元語言: 描述另一種語言的語言。元語言符號 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 下面列出漢語語法規(guī)則中的其中七條規(guī)則： 句子主語謂語主語形容詞名詞謂語動詞賓語 賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃例2.1 : 分析漢語句子 “小八哥吃大花生”。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 語句“小八哥吃大花生”分析的分析樹上 下句子主語謂語形容詞名詞動詞賓語小八哥吃花生形容詞名詞 大 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義句子主語謂語主語形容詞

6、名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃 句子的推導 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義句子主語謂語主語形容詞名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃 語句“小八哥吃大花生”的分析 句子的推導 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義句子主語謂語主語形容詞名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃 語句“小八哥吃大花生”的分析 句子的推導 小 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1

7、 語言的語法和語義句子主語謂語主語形容詞名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃 語句“小八哥吃大花生”的分析 小 小 八哥 小 八哥 小八哥吃 小八哥吃 小八哥吃大 小八哥吃大花生 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 句子的推導句子主語謂語主語形容詞名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃 語句“小八哥吃大花生”的分析句子謂語主語形容詞動詞名詞賓語名詞形容詞小八哥吃花生 大下 上 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.1 語言的語法和語義 句子的歸約句子

8、主語謂語主語形容詞名詞謂語動詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃第 2 章 形式語言與自動機基礎2.1 文法和語言 2.1.1 語言的語法和語義 2.1.2 文法和語言的定義 2.1.3 文法的表示方法 2.1.4 語法樹與二義性 2.1.5 文法和語言的類型 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 2.1.2 文法和語言的定義 一. 字符和字符串 二. 字符串運算 三. 文法形式定義 四. 語 言 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 一. 字符、字符串 任何一種語言，都是

9、由該語言的基本字符遵循一定規(guī)則所組成的字符串的集合。 定義2.1 ( 字母表 ) 字母表是元素的非空有窮集合。字母表中的元素稱為符號或字符，因此字母表也稱為符號集。 用希臘字母或大寫英文字母等表示字母表，用集合的列舉法表示枚舉出字母表中的符號 。 例如，字母表 A=a,b,c,d與字母表 =0,1。 定義2.2 ( 符號串 ) 由字母表中的符號組成的任何有窮序列稱為 符號串，也稱為串或字符串。 通常使用小寫希臘字母表示符號串，如 =STR表示 是由符號S、T和R，并按此順序組成的符號串。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義已知是字母表, 上的字符

10、串的集合*可遞歸定義如下:i) (是由中的0個字符組成的符號串，稱為空串)*；ii) 如果*且a,那么a*；iii) *當且僅當由有限步i)和ii)產(chǎn)生。*中的元素稱為字符串。 符號串長度 如果某符號串中有m個符號，則稱其長度為m，記為 | | = m?？沾?的長度定義為0，記為 | | = 0。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 例: 1） 定義在字母表=0，1上的符號串 | 001110 | = 6 2） 定義在字母表= x，y，z，=，0，1，+，; 上的符號串 | x=y+; z=0; | = 10 符號串的前綴、后綴和子符號串 設是一

11、個符號串，從的尾部刪去0個或若干個符號之后剩余的部分稱為的前綴。 從的首部刪去0個或若干個符號之后剩余的部分稱為的后綴。 若的前綴(后綴)不是自身，則將其稱為的真前綴(真后綴)。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 例如: 設 = abc 則 ,a,ab,abc都是的前綴，且除abc外都為 真前綴。 ,c,bc,abc都是的后綴，且除abc外都為 真后綴。 abc是的前綴和后綴，但既不是真前綴也 不是真后綴。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2

12、.1.2 文法和 語言的定義 子符號串（子串） 從一個符號串中刪去它的一個前綴 和一個后綴之后剩余的部分稱為該符號串的子符號串或子串。例如: = abcd 則,a,b,c,ab,bc,cd,abc,bcd及abcd都是 的子符號串。 而ac，ad，cb，bd，ba等都不是的子符號串。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義判斷：一個符號串的前綴肯定是此符號串的子串。一個符號串的子串或者是此符號串的前綴，或者是此符號串的后綴。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 2.1.2 文法和語言的定義 一. 字符和

13、字符串 二. 字符串運算 三. 文法形式定義 四. 語 言 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 符號串運算定義2.3 ( 符號串的連接 ) 設和 是兩個符號串，如果將符號串直接拼接在符號串之后，則稱此操作為符號串和 的連接，記作 。 例如， 設有字符串 =abc， =xyz 則 =abcxyz， =xyzabc。 連接運算是有序的。一般來說 ，僅當 或其中之一為 ，才有 = 。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.4 ( 符號串的方冪 ) 設是某字母表上符號串，把自身連接 n 次得到符號串 ，即

14、 = (n個) ，稱是符號串 的n次冪，記作 = n。注意設是符號串，則有定義 0= 1= 2= 3= 2 = 2= n= n-1 = n-1= n個 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.5 ( 符號串集合的乘積 ) 設A、B 是兩個符號串集合，AB表示A與B的乘 積，則有定義 AB= | ( A)( B) 例如，設A=ab,c, B=d,ef, 則 AB=abd, abef, cd, cef 注意： 有 A= A=A, A= A = ，其中為空集。 = 。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義判

15、斷：A、B 是兩個符號串集合，|A|=m，|B|=n，則|AB|=mn。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.6 ( 符號串集合的方冪 ) 設A是符號串集合，A自身的乘積可以用方冪表 示。 A0= A1=AA2=AAA3= A2A =AAA An= An-1A =AAA注意 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 顯然有： Ai+j = Ai Aj例: A= ab, x, aby ， 則 A2 = AA =abab, abx, ababy, xab, xx, xaby, abyab, abyx, a

16、byaby Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.7 ( 符號串集合的并 ) 設P、Q為字符串集，集合P Q為P和Q 的并，它的元素是P或Q中的元素。 例如，P=0, 1, 01 Q=0, 10, 11, 00 , 則 P Q = 0, 1, 01, 10, 11, 00 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.8 ( 符號串集合的閉包 ) 設A為符號串集，A的正閉包記作A+，有A+ = A1 A2 An A*定義為A的自反閉包，有A* = A0 A+= A+= A+ 由定義知， A+= A

17、A* A * = A0 A + Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義例如， 設有 A=01,10 則 A*= ，01，10，0101，0110，1001，1010， 010101，010110， A+ = 01，10，0101，0110，1001，1010， 010101，010110， Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 2.1.3 文法和語言的定義 一. 字符和字符串 二. 字符串運算 三. 文法形式定義 四. 語 言 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義

18、 文法定義2.9: 一部文法G是一個四元組 G =（ VN, VT, S, P）其中：VN：非空有限的非終結(jié)符號集(一般用大寫字母表示)。其中的元素稱為非終結(jié)符，或語法變量，代表了一個語法范疇。表示一類具有某種性質(zhì)的符號。 VT：非空有限的終結(jié)符號集（一般用小寫字母表示）。 設V是文法G的符號集，則有V= VT VN ，VT VN =。 S：文法的開始符號或識別符號，亦稱公理，S VN。S代表語言最終要得到的語法范疇。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義P：有限產(chǎn)生式集。 產(chǎn)生式就是按一定格式書寫的定義語法范疇的文法規(guī)則，它是一部文法的實體。 產(chǎn)生

19、式的形式(BNF): 或 :=其中：稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部或稱為的候選式。 V+，且中至少包含VN中的一個元素，V*。 注意，公理S至少且必須在文法某個產(chǎn)生式的左部出現(xiàn)一次。 以S為開始符號的文法G可記為G (S)。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義例2.2: 簡單的算術表達式文法G1定義為 E,i, +, *, (, ),E,E i | i+i | i *i | (E) 四元式形式例如， 數(shù)字文法 0 | 1 | 2 | 3 | 9 其中: VN = NUMBER ，VT =0,1,2,9， S= NUMBER ，P為定義式本身。

20、Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義漢語語法規(guī)則中的其中七條規(guī)則： 句子主語謂語主語形容詞名詞謂語動詞賓語 賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動詞 吃VNVTSP Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 2.1.2 文法和語言的定義 一. 字符和字符串 二. 字符串運算 三. 文法形式定義 四. 語 言 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 四. 語言 1. 語言的非形式化定義 給定一部文法G, 從G的開始符號S出發(fā)，反復使用產(chǎn)生式對非終結(jié)符進行替

21、換，最后所得到的終結(jié)符號串的全體，即為文法G所描述的語言L(G)。 例2.3 : 設有文法G S P | aPb P ba | bQa Q ab寫出該文法所描述的語言。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 定義2.10 ( 直接推導 “ = ” ) 有=A=(,(VNVT)*),當且僅當P中存在一條規(guī)則A ，稱直接推導出（或直接歸約到），記作： = 。 定義2.11 ( 直接推導序列 ) 如果存在= 0= 1 , 1 = 2 , n-1= n = 或 0= 1= 2 = 3 = = n-1= n ，則經(jīng)過n步(n0)可以推導出 ，記作: = 。當

22、= 或 = ，記作： = 。+*+ Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 四. 語言 1. 文法語言 語言是字符串（句子）的集合。 由給定文法構(gòu)造字符串的思想是：從文法的開始符 號出發(fā)，對當前符號串中的非終結(jié)符替換為相應產(chǎn) 生式右部的符號串，如此反復，直至最終符號串全 由終結(jié)符號組成。 例2.3 : 設有文法G S P | aPb P ba | bQa Q ab Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義 S S baba S aPb abQab ababab P ba aPb abab文法G：S P | aPb

23、P ba | bQaQ ab則： L(G)=ba, baba, abab, abababS P bQa 定義2.13 ( 句型 ) 設有文法GS，若 S =(VTVN)*)，則稱為GS的句型 。* 定義2.14 ( 句子 ) 設有文法GS , 若S = ( VT*) ，則稱為 GS的句子。* Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和語言的定義判斷：由終結(jié)符組成的符號串是句子，由非終結(jié)符組成的符號串是句型。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 定義2.12 (最左(右)推導) 在推導過程中，總是對句型中的最左(右)邊的

24、非終結(jié)符進行替換，稱為最左(右)推導。 定義2.15 (規(guī)范推導/規(guī)范句型/ 規(guī)范歸約) 最右推導也稱為規(guī)范推導 。僅用規(guī)范推導得到的句型稱為規(guī)范句型 。規(guī)范推導的逆序為規(guī)范歸約。注意： 對給定的一個句子或句型其最左和最右 推導的唯一性問題。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 例2.4: 設有文法GE： E E *E | E+E | (E) | i$1: i*i+i 是該文法的句子E E *E i *E i *E+E i *i+E i*i+i=L=L=L=L=LE E *E E *E+E E *E+i E *i+i i*i+i=R=R=R=R=

25、R最左推導最右推導/規(guī)范推導規(guī)范句型句子句型 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 定義2.16 ( 文法的遞歸 ) 設有文法G，A 是G的產(chǎn)生式，若具有A 的形式，或 = A ，則稱G是遞歸文法。 若=，則G為左遞歸文法。若 = ，則G為右遞歸文法。+ 直接遞歸遞歸文法 間接遞歸 左（右）遞歸直接遞歸文法間接遞歸文法 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 例2.5： 設有文法G1 ： E E+E | E*E | (E) | i 例2.6： 設有文法G2 ：T Qc | cQ Rb | bR Ta |

26、a 其中有T=Qc =Rbc =Tabc， 即 T= Tabc，則文法G2是間接左遞歸文法。 +其中有E E 這樣的產(chǎn)生式，所以文法G1是直接左遞歸文法。 定義2.17 ( 語言 ) 文法 G所產(chǎn)生（描述）的語言L(G)： L(G) = | VT* S = ，S是文法 的開始符號 + Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義2. 語言的形式定義例2.7: 設有文法 G： S S0 | 0 求L (G)？ L (G) = 0n | n=1 G: S 0S | 0 后面為0n（n1)L(G) = L(G)前面為0 Ch2 形式語言自動機理論基礎 2.1 文

27、法和語言 2.1.2 文法和 語言的定義例2.8: 設有文法 G： S 0S1 | 01 求L(G)？ L（G）= 0n 011n | n=0 = 0m 1m | m=1 例2.9: 設有語言 L(G1)= a bn a | n=0 , 求G1？ G1(S) ： S aa | aRa R b | Rb G1(S) ： S aRa前面為0n,后面為1n(n1)中間為01作為一個語法范疇R Rb | G1(S) ： S aT T RaR Rb | Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義 定義2.18 ( 文法等價 ) 若 L(G1)= L(G2)，則稱文

28、法G1和G2是等價的 。 例2.11: 設有語言L : L= a(bn) a | n=0 G: S a(B)a B Bb | G: S a()a | a(B)a B Bb | b Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義例：寫出文法 G S Sb | R R aRb | ab 描述的語言L(G) 所以L(G)anbnbm| n1, m0 anbnm| n1, m0 anbj| jn 1產(chǎn)生串a(chǎn)nbn（n1)后面為bm（m1)例： 設 L(G) = (an)(bn) | n=1,2,3, , 求G(S)？ G： S (A)(B) A aA | a B b

29、B | b G： S ( B ) B a)(b | aBb a,b個數(shù)可以不相同一個語法范疇 (非終結(jié)符）描述B aBb | a)(b Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義例： 設 L6(G) = 1n0m 1m0n | n,m0 , 求G（S）？G（S）： S 1S0 | B B 0B1 | 一個語法成分 (非終結(jié)符）描述一個語法成分 (非終結(jié)符）描述B 0B1 | S 1S0 | B Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義例:設語言S=aibj| 0ij，滿足L(G)=S的文 法G為【 】。 Ch2

30、形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義j=i+m m 0aibj=aibi+m=aibibmTAB AaAb| B Bb| TTb| A AaAb| TTb| aTb |例:設語言S=aibj| 0ij2i，滿足L(G)=S的文 法G為【 】。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義j=i+m 0 m ii=m+n n0 j=2m+n n0 m 0 aibj=am+nb2m+n=ama nbnb2mTaTbb|A AaAb| 思考：設語言S=aibj| 0ij3i，滿足L(G)=S的文 法G為【 】。TaTb|aT

31、bb| 練習:設字母表=a,b,0,1上的語言 R=ai(01) n bj | 0ij,n0，滿足L(G)= R的文法G為【 】。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.2 文法和 語言的定義第 2 章 形式語言與自動機基礎2.1 文法和語言 2.1.1 語言的語法和語義 2.1.2 文法和語言的定義 2.1.3 文法的表示方法 2.1.4 語法樹與二義性 2.1.5 文法和語言的類型 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示 BNF表示法 元語言符號集： , , | 2. 擴充BNF表示法 （EBNF） 1) 引入花括號 t 表示字符串

32、t 的多次或任意次出現(xiàn)，其中下角 標n 表示串t重復的最小次數(shù)，上角標m表示字符 串 t 重復的最大次數(shù)。 省略m,n表示可重復0到任意多次。nm Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示例2.12: FORTRAN語言中標識符的定義。 標識符是長度8的字母開頭后跟字 母或數(shù)字的字符串，則有： |07 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示 例2.13: 有文法規(guī)則 U xa | xb | | xz 引入圓括號提取公共字符串x后有： U x（a | b | | z） 2) 引入圓括號 “(” “)” 提取產(chǎn)生式中的公共因子，

33、簡化產(chǎn)生式的表 示。 注意：與終結(jié)符的（）區(qū)分開。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示 3) 引入方括號 t 表示字符串 t 可有可無。 例2.14: 設有條件語句的文法 |else if then引入方括號后，可簡化為： else if then Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示3. 語法圖(上下文無關文法）由一組圖組成，每個圖定義了一個非終結(jié)符的產(chǎn)生式 。每個圖都有一個起始結(jié)點和一個終止結(jié)點，其他的結(jié)點標記為文法符號。終結(jié)符結(jié)點用圓形表示。非終結(jié)符結(jié)點用方形表示。 從起始結(jié)點到終止結(jié)點的所有路徑（標記為結(jié)點序

34、列）定義候選式。例：產(chǎn)生式P bEFn | c 。表示為PEFbnc標識符字母數(shù)字字母 例2.15: PASCAL語言中標識符的定義如下圖。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.3 文法的表示第 2 章 形式語言與自動機基礎2.1 文法和語言 2.1.1 語言的語法和語義 2.1.2 文法和語言的定義 2.1.3 文法的表示方法 2.1.4 語法分析樹與二義性 2.1.5 文法和語言的類型 表示： 分析樹的根結(jié)點 G的S 分析樹的中間結(jié)點 G的產(chǎn)生式左部 分析樹的葉結(jié)點 G的VT 父子結(jié)點間關系 G的產(chǎn)生式規(guī)則葉結(jié)點從左到右連接的符號串 句子 Ch2 形式語言自動機理論

35、基礎 2.1 文法和語言 2.1.4 語法樹與二義性一 . 語法分析樹與二義性 語法分析樹是句子結(jié)構(gòu)的圖形表示，它代表了句子的推導過程，有利于理解句子語法結(jié)構(gòu)的層次。句型 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與二義性 例2.16 ： 設有無符號整數(shù)的文法 | 0 | 1 | 2 | | 9對句子25的最左推導過程是： = = = = 2 = 25對句子25的最右推導過程是： = = = 5 = 5 = 25 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與二義性無符號整數(shù)數(shù)字串 數(shù)字數(shù)字串 數(shù)字25 問題：任何一個句型的一棵分析樹包括了

36、這個句型的所有可能的推導過程? 一個句型是否只對應一棵分析樹？或者是否只有惟一的最左（右）推導？文法二義性問題 | 0 | 1 | 2 | | 9分析樹最左推導最右推導一對一一對一任意推導 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與二義性 定義2.19 ( 二義文法 ) 對一部文法G，如果至少存在一個句子,有兩棵( 或兩棵以上 )不同的分析樹，則稱該句子是二義性的。包含有二義性句子的文法稱為二義文法。否則，該文法是無二義性的。 定義提供了對給定文法在某一范圍內(nèi)判定是否是二義性文法的充分條件。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與

37、二義性例2.17： 設有文法G1 ： E E+E | E*E | (E) | iE E +E E *E+E i *E+E i *i+E i*i+iE E *E i *E i *E+E i *i+E i*i+i=L=L=L=L=L=L=L=L=L=LEE * Ei E + E i iEE + E E * E i i i文法G1中的句子i*i+i存在兩棵不同的分析樹，所以文法G1為二義文法。文法G1中的句子i*i+i存在兩個不同的最左推導，所以文法G1為二義文法。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與二義性 注意： 文法的二義性與語義的二義性是完全不同的概念。并

38、非文法是二義的，語言就二義。 Time Flies. 君君臣臣父父子子 你真可以。既有語法又有語義的二義性有語法的二義性但無語義的二義性有語義的二義性但無語法的二義性 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.4 語法樹與二義性 二. 文法二義性的消除 例如， 對有文法G1 ： E E+E | E*E | (E) | i 1） 分析二義性原因 a) 運算符 “+”和“*”未體現(xiàn)優(yōu)先級； b) “+”和“*”自身結(jié)合規(guī)則不明確； 2） 構(gòu)造G1 ，使L( G1）=L( G1) G1: E T | E+T T F | T*F F (E) | i第 2 章 形式語言與自動機基礎2.

39、1 文法和語言 2.1.1 語言的語法和語義 2.1.2 文法和語言的定義 2.1.3 文法的表示方法 2.1.4 語法分析樹與二義性 2.1.5 文法和語言的類型 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型 N.Chomsky 分類 ：1. 0型文法（ 短語文法 ） 定義2.20： 如果對文法G中的規(guī)則不加任何限制，則稱G為0型文法或短語文法。 能用0型文法描述的語言為0型語言L0，0型語言 可由圖靈機（Turing）來識別。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型 例2.18: 設有文法G S aQb aQb

40、caRbc aRb caba 顯然，G是0型文法。 任何一個文法都是0型文法。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型21型文法（ 上下文有關文法 ） 定義2.21： 設文法G=(VN,VT,S,P)，對P中的每個產(chǎn)生式（除S 外，但此時S不得出現(xiàn)在任何產(chǎn)生式的右部 ）限制為形如：A 其中，AVN，,(VTVN)，(VTVN)+，則稱文法G為1型文法或上下文有關文法。 能用1型文法描述的語言為1型語言L1，1型語言可由線性有界自動機來識別。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型例2.19 設有文法G1S aS

41、BC | abCCB CDCD BDBD BC bB bbbC bccC cc G1是1型文法，G1產(chǎn)生的語言：L(G1) =anbncn | n1San+1bC(BC)n an+1b(CB)nCan+1b(BC)nCan+1bB(CB)n-1C2an+1bb(CB)n-1C2an+1bb(BC)n-1C2an+1bn+1Cn+1an+1bn+1cn+1CBBC Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型32型文法（上下文無關文法）定義2.22： 設文法G =（VN ,VT , S , P），對P中的每個產(chǎn)生式限制形如： A其中，AVN，(VTVN)*則稱

42、文法G為2型文法。 2型文法也稱為上下文無關文法。能用2型文法描述的語言為2型語言L2，2型語言可由非確定的下推自動機來識別。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型 G2是2型文法例2.19 : 設有文法G2S Ac | ScA ab | aAb G2產(chǎn)生的語言：L(G2) =anbncm | n,m1 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型43型文法（正則文法、線性文法） 定義2.23： 設文法G=（VN,VT, S, P），若P中的每個產(chǎn)生式形如 AB或A其中，A，B VN，VT*，則稱文法G為右線性文法若P中的每個產(chǎn)生式形如： AB 或 A其中，A，B VN，VT*，則稱文法G為左線性文法右線性文法和左線性文法統(tǒng)稱為3型文法。（正則文法或線性文法）。 能用3型文法描述的語言為3型語言L3，3型語言可由確定的有限狀態(tài)自動機來識別。 Ch2 形式語言自動機理論基礎 2.1 文法和語言 2.1.5 文法和語言的類型 G3是3型文法例2.19 設有文法G3S Bc | Sc B Ab | BbA Aa | aG3產(chǎn)生的語言： L(G3)