《編譯原理》第3章(1)

1、【學習指南】【學習指南】 什么是文法什么是文法, ,什么是它定義的語言？什么是它定義的語言？ 在喬姆斯基（在喬姆斯基（ChomskyChomsky）的文法類型中，我們?yōu)槭裁吹奈姆愋椭?，我們?yōu)槭裁?關注上下文無關文法？關注上下文無關文法？ 什么是語法分析？語法分析方法的分類。什么是語法分析？語法分析方法的分類。【難重點】【難重點】關于文法和語言的概念是形式語言的理論基礎，形式關于文法和語言的概念是形式語言的理論基礎，形式語言抽象地定義為一個數學系統(tǒng)。語言抽象地定義為一個數學系統(tǒng)。 形式形式 是指這樣的是指這樣的事實：語言的所有規(guī)則只以什么符號串能出現的方式事實：語言的所有規(guī)則只以什么符號串能出

2、現的方式來陳述。這里介紹的語言的語法描述工具正是這樣的來陳述。這里介紹的語言的語法描述工具正是這樣的系統(tǒng)。系統(tǒng)。知識體系知識體系文法文法組成組成終結符號集合終結符號集合非終結符號集合非終結符號集合產生式集合產生式集合識別符號識別符號( (開始符號開始符號) )句型句型句子句子語言語言分類分類0 0型文法型文法( (短語結構文法短語結構文法) )1 1型文法型文法( (上下文有關文法上下文有關文法) )2 2型文法型文法( (上下文無關文法上下文無關文法) )3 3型文法型文法( (正規(guī)文法正規(guī)文法) )與語法分析有關的概念與語法分析有關的概念推導推導語法樹語法樹遞歸文法遞歸文法二義性文法二義性

3、文法短語短語 直接短語直接短語句柄句柄推導推導/ /歸約歸約湊湊規(guī)規(guī)則則 字母表與符號串字母表與符號串 文法與語言的關系文法與語言的關系- 文法的概念文法的概念- 文法與語言的形式定義文法與語言的形式定義 文法構造與文法簡化文法構造與文法簡化- 由語言構造文法的例子由語言構造文法的例子- 文法的簡化文法的簡化 語法樹與文法的二義性語法樹與文法的二義性語言語言 漢語漢語-所有符合漢語語法的句子的全體所有符合漢語語法的句子的全體 英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體 程序設計語言程序設計語言-所有該語言的程序的全體所有該語言的程序的全體 研究語言研究語言 ： 每個句子

4、構成的規(guī)律每個句子構成的規(guī)律 每個句子的含義每個句子的含義 每個句子和使用者的關系每個句子和使用者的關系研究程序設計語言：研究程序設計語言： 每個程序構成的規(guī)律每個程序構成的規(guī)律 每個程序的含義每個程序的含義 每個程序和使用者的關系每個程序和使用者的關系語言研究的三個方面：語言研究的三個方面： 語法語法 SyntaxSyntax 語義語義 SemanticsSemantics 語用語用 PragmaticsPragmatics語法語法 - - 表示構成語言句子的各個記號之間的表示構成語言句子的各個記號之間的語義語義 - - 表示按照各種表示方法所表示的各個記號的特定表示按照各種表示方法所表示的

5、各個記號的特定 。（各個記號和記號所表示的對象之間的關系）。（各個記號和記號所表示的對象之間的關系）語用語用 - -表示在各個記號所出現的行為中，它們的表示在各個記號所出現的行為中，它們的。 如果不考慮語義和語用，即只從如果不考慮語義和語用，即只從這一側面來這一側面來看語言，這種意義下的語言稱作看語言，這種意義下的語言稱作。 形式語言抽象地定義為一個數學系統(tǒng)。形式語言抽象地定義為一個數學系統(tǒng)?！靶问叫问健笔侵高@樣的事實：語言的所有規(guī)則只以什么符號是指這樣的事實：語言的所有規(guī)則只以什么符號串能出現的方式來陳述。串能出現的方式來陳述。形式語言理論是對符號形式語言理論是對符號串集合的表示法、結構及其

6、特性的研究。串集合的表示法、結構及其特性的研究。是程序是程序設計語言語法分析研究的基礎。設計語言語法分析研究的基礎。形式形式語言語言 字母表是符號的字母表是符號的非空非空有窮有窮集合。任何程序語言集合。任何程序語言都有自己的字母表，例如都有自己的字母表，例如: :1.1.機器語言：由符號機器語言：由符號“0 0”和和“1 1”組成的字母表組成的字母表, ,=0=0，1 1 2.2.ASCIIASCII字符集；字符集；3.3.漢語的字母表中包括漢字、數字及標點符號漢語的字母表中包括漢字、數字及標點符號4.4.C C字母表為：字母表為： = =A A Z, Z, a a z z, 0, 0 9,

7、+, -, 9, +, -, * *, /, , , /, , :, , ; =, , :, , ; ，. .， , (, ), , , , (, ), , , , , 1.1.符號符號 一個抽象實體一個抽象實體, ,我們不再形式地定義它我們不再形式地定義它( (就象幾何中就象幾何中的的”點點”一樣一樣).).例如字母是符號例如字母是符號, ,數字也是符號數字也是符號2.2.符號串符號串 由字母表中的符號所組成的的任何由字母表中的符號所組成的的任何有窮序列有窮序列被稱之被稱之為該字母表上的符號串為該字母表上的符號串, ,也稱作也稱作“字字”或或“句子句子”。(1)(1)不包含任何符號的符號串不

8、包含任何符號的符號串，稱為，稱為空符號串簡稱空符號串簡稱空空串，串，記為記為 。(2) (2) 若若=a,ba,b 則則a,b,ab,ba,abb,baa.a,b,ab,ba,abb,baa.是是上的符號串。上的符號串。在符號串中，符號的在符號串中，符號的順序順序是很重要的，符號串是很重要的，符號串abab就不就不同于同于ba,abcaba,abca和和aabcaabc也不同。也不同。設設z z是符號串是符號串長度長度: :是該符號串中的符號的數目。例如是該符號串中的符號的數目。例如| |aabaab|=3,|=0|=3,|=0。前綴前綴( (頭頭):):刪去刪去z z尾部的若干個尾部的若干個

9、( (包括包括0 0個個) )符號所得的。符號所得的。 表示表示: : z=xz=x 后綴后綴( (尾尾):):刪去刪去z z頭部的若干個頭部的若干個( (包括包括0 0個個) )符號所得的。符號所得的。 表示表示: : z=xz=x真真前綴前綴( (固有頭固有頭) )x x，真真后綴后綴( (固有尾固有尾) )x :x :xzxz子串子串: : 從從z z中刪去一個前綴和一個后綴中刪去一個前綴和一個后綴逆轉（用逆轉（用z z表示）表示）：將：將z z中的符號按相反次序寫出而得中的符號按相反次序寫出而得到的符號串。到的符號串。 例例：符號串符號串z=bananaz=banana長度：長度： b

10、ananabanana =6=6前綴：前綴： , ,b b,ba,ba,banban,bana,bana,bananbanan,banana,banana真真前綴前綴: : , ,b b,ba,ba,banban,bana,bana,bananbanan后綴：后綴：banana,banana,ananaanana,nana,nana,anaana,na,na,a a, , 真真后綴后綴: : anana,anana,nananana,ana,ana,nana,a,a, , 子串子串: : banana,banana,ananaanana,banan,banan,anananan, , , 逆轉

11、逆轉（用（用z z表示）：表示）：ananabananab1.1.連接：連接：設設x x和和y y是符號串，它們的連接是符號串，它們的連接 xyxy是把是把y y的符號寫在的符號寫在x x的符號之后得到的符號串。的符號之后得到的符號串。例如，例如，x=x=ba,yba,y= =nana,xynana,xy=banana=banana 顯然：顯然：xx= =xx=x =x 2.2.方冪：方冪：符號串符號串x x自身連接自身連接n n次得到的。次得到的。 x x0 0= = ; ; x x1 1=x; x=x; x2 2=xx;=xx; ; ;x xn n=x=xn-1n-1x= xxx= xxn

12、-1n-1; ; 例如例如, , x=x=baba, , x x1 1= = baba, x, x2 2= =babababa, x, x3 3= =babababababa, , x xn n=(=(ba)ba)n n定義定義: :集合中的一切元素都是某字母表上的符號串。集合中的一切元素都是某字母表上的符號串。設設A A和和B B是兩個是兩個符號串集合，則符號串集合，則 1. 1. 乘積乘積( (連接連接) )：ABAB xy|x xy|x A and yA and y BBA=ab,bcB=ac,cbAB=A=ab,bcB=ac,cbAB=abac,abcb,bcac,bccbabac,a

13、bcb,bcac,bccb 2. 2. 合并：合并：ABABx|xx|x A or xA or x BBAB=ab,bc,ac,cbAB=ab,bc,ac,cb 3. 3. 空集空集: : A=AA=A = =A A 4. 4. ：符號串集合符號串集合的自身乘積。的自身乘積。 A A0 0=， A A1 1A A， A A2 2AA, ., AAA, ., An nA An n- -1 1A AAAAAn n- -1 1 A=a,b A A=a,b A0 0=， A A1 1A=a,bA=a,b， A A2 2AA=aa,ab,ba,bbAA=aa,ab,ba,bb A A3 3A A2 2A

14、=AAA=AA2 2=aaa,aab,aba,abb, =aaa,aab,aba,abb, 5. 5. 集合集合A A的的KleeneKleene閉包閉包( (星閉包星閉包) )，記作，記作A A* *，字母表字母表A A的的各次方冪之并。其含義是由各次方冪之并。其含義是由A A上符號組成的所有串的集上符號組成的所有串的集合（包括空串合（包括空串)A A* *A Ai i(i(i=0) =A=0) =A0 0AA1 1AA2 2AA3 3 A=A=a,ba,b A A* * ,a,b,aa,ab,ba,bb,a,b,aa,ab,ba,bb, , aaa,aab,aba,abbaaa,aab,a

15、ba,abb, , 6 6集合集合A A的正閉包的正閉包，記作，記作A A+ +，其含義是由字母表其含義是由字母表A A上的上的符號組成的所有串符號組成的所有串( (不包括空串不包括空串)的集合。的集合。A A+ +AAi i(i(i =1) =A =1) =A1 1AA2 2AA3 3AA4 4A=A=a,ba,b A A+ +a,b,aa,ab,ba,bba,b,aa,ab,ba,bb, , aaa,aab,aba,abbaaa,aab,aba,abb, , A A* * A A0 0 A A+ + A A+ + AAAA* *A A* *A A n 語言是由語言是由句子組成的集合句子組成

16、的集合，是由一組符號所構成的集，是由一組符號所構成的集合。換言之合。換言之, ,字母表字母表 上上的一個語言是的一個語言是 上的一些符號上的一些符號串的集合串的集合 ( (字母表字母表 上上的每個語言是的每個語言是 * *的一個子集的一個子集) )。例如：字母表例如：字母表=a,ba,b * *=,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab, , 集合集合 ab,aabb,aaabbbab,aabb,aaabbb, , ,a an nb bn n, , 或表示為或表示為 w|ww|w* *且且w=aw=an nb bn n,n1 ,n1 字母

17、表字母表 上上的一個語言的一個語言。集合集合 a,aa,aaaa,aa,aaa, , 或或表示為表示為 w|ww|w* *且且w=aw=an n,n1 ,n1 字母表字母表 上上的一個語言。的一個語言。 是一個語言。是一個語言。 即即 是一個語言。是一個語言。設設L L是（是（ 上的）一個語言上的）一個語言, ,M M是（是（ 上的）一個語言上的）一個語言, , 語言語言L L和和M M的的并，交，差，補并，交，差，補是一個是一個語言語言。 語言語言L L和和M M的并為的并為 L L M M: : L L M=M= w|ww|w L L 或或 w w M M 如：如： L L1 1 = =a

18、,ba,b, ,y,zy,z M M1 1 =1,2 =1,28,9 8,9 L L1 1 M M1 1=a,ba,b, , y,z y,z，1,21,28,9 8,9 語言語言L L和和M M的連接為的連接為 LM:LM=LM:LM= stst | |s sL L且且t tM M 如：如： L L1 1M M1 1 =a1,b1, =a1,b1,y1,z1,a2,b2y1,z1,a2,b2a9a9z9 z9 有有L L = = L L=L=L。 L L的的n n次連接次連接L Ln n= = LL.L LL.L 如：如： L L1 12 2 = =aa,abaa,ab, ,az,ba,bba

19、z,ba,bb, , bzbz, , , ,za,zbza,zbzzzz 語言語言L L的的閉包記閉包記為為 L L* *， L L* *= L= L0 0 L L1 1 L L2 2 . . L L0 0= = ， L Ln n= L L= L Ln-1n-1= = L Ln-1n-1 L,n L,n 1 1 語言語言L L的正的正閉包記閉包記為為 L L+ +， L L+ += L= L1 1 L L2 2 L L3 3 . . L L+ += LL= LL* *= L= L* *L L L L* *= L= L+ + 如：如： L L1 1 =a,ba,b, ,y,zy,z M M1 1

20、 =1,2=1,28,9 8,9 （L L1 1 M M1 1）=a,ba,b, , y,z y,z，1,21,28,9 8,9 （L L1 1 M M1 1）* *=a,ba,b, , y,z y,z，1,21,28,9 8,9 ，aa,1a,aa,1a,xyz,6789st.xyz,6789st. L L1 1（L L1 1 M M1 1）* *=所有字母打頭的字母和數字符號所有字母打頭的字母和數字符號串串 例如：例如：L L=AZ,azAZ,az D=09 D=091 1LDLD是由所有一個字母后跟一個數字組成的符號串所是由所有一個字母后跟一個數字組成的符號串所構成的集合。構成的集合。2

21、 2LDLD= = AZ,azAZ,az ,09 ,09 3.L3.L4 4是由所有的四個字母的符號串構成的集合。是由所有的四個字母的符號串構成的集合。4 4L L（LD)LD)* * 是由所有的字母打頭的字母和數字組成是由所有的字母打頭的字母和數字組成的符號串所構成的集合。的符號串所構成的集合。5 5D D+ +是由所有長度大于等于是由所有長度大于等于1 1的數字串所構成的集合。的數字串所構成的集合。如何來描述一種語言？如何來描述一種語言？(1)(1)枚舉法枚舉法 例例:1,11,111,1111 :1,11,111,1111 (2)(2)自然語言自然語言(3)(3)省略表示法省略表示法 例

22、例:1,11,111,:1,11,111, (4)(4)描述法描述法 例例:1:1i i|i|i00 如果語言是有窮的（只含有有窮多個句子），可以將如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示；句子逐一列出來表示； 如果語言是無窮的，找出語言的有窮表示。語言的有如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經：窮表示有兩個途經：- 生成方式生成方式 （文法）（文法）：語言中的每個句子可以用嚴：語言中的每個句子可以用嚴格定義的規(guī)則來構造。格定義的規(guī)則來構造。- 識別方式（自動機）識別方式（自動機）：是使用自動機的行為描述語：是使用自動機的行為描述語言：它的行為相

23、當于一個過程，當輸入的一任意串言：它的行為相當于一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回屬于語言時，該過程經有限次計算后就會停止并回答答“是是”，若不屬于，要么能停止并回答，若不屬于，要么能停止并回答“不是不是”，（要么永遠繼續(xù)下去。）（要么永遠繼續(xù)下去。） 文法即是生成方式描述語言的：文法即是生成方式描述語言的：語言中的每個句子可以用嚴格定義的語言中的每個句子可以用嚴格定義的規(guī)則規(guī)則來構造。來構造。 下面給出文法的定義下面給出文法的定義. .進而在文法的定義的基礎進而在文法的定義的基礎 上上, ,給出推導的概念給出推導的概念, ,句型、句子和語言的定義。句型、句

24、子和語言的定義。 文法的直觀概念和語言概述文法的直觀概念和語言概述 當我們表述一種語言時，無非是說明這種語言的句子，當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有窮集就行了，但對于含有無窮句子無窮句子的語言來講，存在的語言來講，存在著如何給出它的著如何給出它的有窮表示有窮表示的問題。的問題。 以自然語言為例，人們無法列出全部句子，但是人們以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明可以給出一些規(guī)則，用這些規(guī)則來說明( (或者定義或者定義) )句

25、句子的組成結構，比如漢語句子可以是由主語后隨謂語子的組成結構，比如漢語句子可以是由主語后隨謂語而成，構成謂語的是動詞和直接賓語，我們采用而成，構成謂語的是動詞和直接賓語，我們采用BNFBNF來表示這種來表示這種句子的構成規(guī)則句子的構成規(guī)則： 語法規(guī)則：語法規(guī)則：“句子由主語后跟隨謂語組成句子由主語后跟隨謂語組成”表示表示為：為： 句子句子 主語主語 謂語謂語 句子句子 主語主語 謂語謂語 主語主語 代詞代詞 主語主語 名詞名詞 代詞代詞我我 代詞代詞你你 代詞代詞他他 名詞名詞王明王明 名詞名詞 大學生大學生 名詞名詞工人工人 名詞名詞 英語英語 謂語謂語 動詞動詞 直接賓語直接賓語 動詞動詞

26、 是是 動詞動詞 學習學習 直接賓語直接賓語 代詞代詞 名詞名詞 有了一組規(guī)則以后，按照如下方式用它們導出句子：開有了一組規(guī)則以后，按照如下方式用它們導出句子：開始去找始去找左端的帶有左端的帶有 的規(guī)則并把它由的規(guī)則并把它由右端的符右端的符號串代替，這個動作表示成：號串代替，這個動作表示成： 句子句子 主語謂語，主語謂語，然后在得到的串然后在得到的串 中中, ,選取選取 或或 ,再用相應再用相應規(guī)則的規(guī)則的右端代替之右端代替之。比如。比如, ,選取了選取了 ,并并采用規(guī)則采用規(guī)則 , , 那么得到那么得到: : ,重復做下去。重復做下去。 句子句子主語主語 謂語謂語 代詞代詞 謂語謂語 我我

27、謂語謂語 我我 動詞動詞 直接賓語直接賓語 我我是是 直接賓語直接賓語 我是我是 名詞名詞 我是我是大學生大學生分析：分析：我我是大學生是大學生謂語謂語主語主語代詞代詞動詞動詞直接賓語直接賓語句子句子大學生大學生我我是是名詞名詞 句子句子 + + 我是大學生我是大學生 英語英語是工人是工人 大學生是英語大學生是英語符合語法且符合語義的句子僅是：符合語法且符合語義的句子僅是： 我是大學生。我是大學生?！拔沂谴髮W生我是大學生”的構成符合上述規(guī)則，而的構成符合上述規(guī)則，而“我大學生是我大學生是”不符合上述規(guī)則，我們說它不是句子。這些不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為規(guī)則成為我我們們判別句

28、子結構合法與否的依據判別句子結構合法與否的依據，換句話說，這些規(guī)則，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結構描述。其中一種描述元語言稱為文法。句子的結構描述。其中一種描述元語言稱為文法。 每種語言具有兩個可識別的特性，即語言的每種語言具有兩個可識別的特性，即語言的形式形式和和該形式相關聯(lián)的該形式相關聯(lián)的意義意義。 語言的實例若在語法上是正確的，其相關聯(lián)的意義語言的實例若在語法上是正確的，其相關聯(lián)的意義可以從兩個觀點來看，可以從兩個觀點來看， 其一是該句子的創(chuàng)立者所想要表示的意義，其一是該句子的創(chuàng)立者所想要表示的

29、意義， 另一是接收者所檢驗到的意義。另一是接收者所檢驗到的意義。o 這兩個意義并非總是一樣的，前者稱為語言的語這兩個意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關語和謎語就義，后者是其語用意義。幽默、雙關語和謎語就是利用這兩方面意義間的差異。是利用這兩方面意義間的差異。 如果不考慮語義和語用，即只從如果不考慮語義和語用，即只從語法語法這一側面來看語言，這一側面來看語言，這種意義下的語言稱作這種意義下的語言稱作形式語言形式語言。形式語言抽象地定義。形式語言抽象地定義為一個數學系統(tǒng)。為一個數學系統(tǒng)。 “形式形式”是指這樣的事實：語言的所有規(guī)則只以什么符是指這樣的事實：語言的所

30、有規(guī)則只以什么符號串能出現的方式來陳述。形式語言理論是對符號串集號串能出現的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程序設計語言語合的表示法、結構及其特性的研究。是程序設計語言語法分析研究的基礎。法分析研究的基礎。1 1 文法文法-是一個是一個數學系統(tǒng)數學系統(tǒng) v文法是描述語言的語法結構的形式規(guī)則文法是描述語言的語法結構的形式規(guī)則( (語法規(guī)則語法規(guī)則) )。v由下列基本成分來刻畫：由下列基本成分來刻畫：一組基本符號，一組形成規(guī)一組基本符號，一組形成規(guī)則，一組公理，一組推理規(guī)則則，一組公理，一組推理規(guī)則。 v有關文法術語的概念：有關文法術語的概念：v非終結符非終結

31、符用來代表語法范疇（語法單位）；用來代表語法范疇（語法單位）；v終結符終結符語言中不可再分的字符串；語言中不可再分的字符串；v開始符號開始符號一個特殊的非終結符號，他表示了所定一個特殊的非終結符號，他表示了所定義的是什么樣的語法范疇；義的是什么樣的語法范疇；產生式產生式( (規(guī)則規(guī)則) )用來定義符號串之間關系的一組規(guī)用來定義符號串之間關系的一組規(guī)則則( (語法規(guī)則語法規(guī)則) )； V VN N是一個非空有窮非終結符號集合，是一個非空有窮非終結符號集合， V VT T是一個非空有窮終結符號集合；是一個非空有窮終結符號集合；且且V VT TVVN N；字母表字母表( (詞匯表詞匯表) )V= V

32、V= VT TVVN N S S V VN N ，稱為開始符號或識別符號。，稱為開始符號或識別符號。至少要在一條產生式中作為左部出現。至少要在一條產生式中作為左部出現。 P P是一個產生式是一個產生式( (規(guī)則規(guī)則) )的的非空有窮非空有窮集合，集合，每個產生式的形式是每個產生式的形式是( (或或 ) )，其中其中 VV+ +，VV* *。開始符號開始符號S S至至少少必須在某個產生式的必須在某個產生式的左部出現一次左部出現一次 。 縮寫形式：縮寫形式：句子的語法有四部分：句子的語法有四部分：終結符號集，非終結終結符號集，非終結符號集，語法規(guī)則，開始符號符號集，語法規(guī)則，開始符號。上例：上例：

33、終結符號集終結符號集V VT T=我我, ,你你, ,他他, ,王明王明, ,大學生大學生, ,工人工人, ,英語英語, ,是是, ,學習學習 非終結符號集非終結符號集V VN N= 句子句子 ， 主語主語 ， 謂語謂語 ， 代詞代詞 ， 名詞名詞 ， 動詞動詞 ， 直接賓語直接賓語 語法規(guī)則集語法規(guī)則集P=P= 句子句子 主語主語謂語謂語 ， 開始符號開始符號S=S= 句子句子 文法的優(yōu)點文法的優(yōu)點 文法給出了精確的，易于理解的語法說明文法給出了精確的，易于理解的語法說明自動產生高效的分析器自動產生高效的分析器可以給語言定義出層次結構可以給語言定義出層次結構以文法為基礎的語言的實現便于語言的

34、修改以文法為基礎的語言的實現便于語言的修改G=(G=(, , ， a,+,a,+,* *,(,),(,), P, P, ) ) P P： * * （ ) ) a a E E E+T E+T T T T T T T* *F F F F F F ( E ) ( E ) a av第一條產生式的左部是開始符號第一條產生式的左部是開始符號v用尖括號括起的是非終結符，否則為終結符。或者用尖括號括起的是非終結符，否則為終結符?；蛘叽髮懽帜副硎痉墙K結符，小寫字母表示終結符大寫字母表示非終結符，小寫字母表示終結符vG G可寫成可寫成GSGS，其中其中S S是開始符號是開始符號 例：例： 文法文法G=G=（V V

35、N N，V VT T，P P，S S）V VN N = S , V = S , VT T = a, b = a, b P= P= SaSbSaSb, , SabSab S S為開始符號為開始符號 可寫成：可寫成： G G：SaSbSaSb SabSab 或寫成：或寫成： GSGS：SaSbSaSb SabSab為定義文法所產生的語言，我們還需要引入推導的概為定義文法所產生的語言，我們還需要引入推導的概念。念。推導與歸約推導與歸約-推導推導是從是從開始符號開始開始符號開始，通過產生式的，通過產生式的右部右部取代取代左部左部的過程，最終能產生一個語言的的過程，最終能產生一個語言的句子句子。-定義了

36、定義了V V* *中的符號之間的關系。中的符號之間的關系。-歸約歸約是從給定源語言的是從給定源語言的句子開始句子開始，通過產生式的，通過產生式的左部取代右部左部取代右部的過程，最終到達的過程，最終到達開始符號開始符號。直接推導直接推導推導（長度為推導（長度為n(n1)n(n1)的推導）的推導）廣義推導（長度為廣義推導（長度為n(n0)n(n0)的推導）的推導） 最左推導最左推導最右推導最右推導定義定義2.2 2.2 直接推導直接推導 “”令令G=(VG=(VN N ,V,VT T,P,S,P,S），），若若 P, P, 且且,(V(VT TVVN N) )* *, ,則稱則稱 ( (應用規(guī)則應

37、用規(guī)則) )直接推出直接推出, , 記作記作 或說：或說：直接直接推導推導出出 直接直接歸約歸約到到例：例：G G： S0S1 S0S1， S01 S01直接推導：直接推導：0 0S1S100110011（v=0S1v=0S1，w=0011w=0011，使用規(guī)則使用規(guī)則S01S01，=0=0，=1=1）S S 0S10S1（v=v=S S，w w=0S1=0S1，使用規(guī)則使用規(guī)則S0S1S0S1，= =，= =）0 0S1S100S11 00S11 （v=0S1v=0S1，w=00S11w=00S11，使用規(guī)則使用規(guī)則S0S1S0S1，=0=0，=1=1）定義定義2.3 2.3 推導：推導：

38、+ + 如果存在一個如果存在一個直接推導直接推導序列：序列： v=w v=w0 0w w1 1w w2 2 w wn n（n n 、11） 表示成表示成 v v + + w wn n ( (v v推導出推導出w w，或或w w歸約到歸約到v)v)定義定義2.4 2.4 廣義推導廣義推導： * * 或者或者v=wv=w或者或者v v + + w wn n , ,表示成表示成 v v * * w wn n最左推導最左推導： A A (A (A) ) ， V VT T* *最右推導最右推導： A A (A (A) )， V VT T* *例：例：G G： S0S1 S0S1， S01 S010S1

39、0S1 00S11 00S11 000S111 000S111 00001111 00001111 即即 0S1 0S1 + + 00001111 00001111也記作也記作 0S1 0S1 * * 00001111 00001111 T T+T+T F F+T+T a+a+T T a+a+T T* *F F E E+T+T E E a+a+F F* *F F a+aa+a* *F F a+aa+a* *a a例如：例如：E EE+TE+T T TT TT T* *F F F FF F(E)(E) a a 寫出對符號串寫出對符號串w=w=a+aa+a* *a a的的最左、最右推導過程。最左、

40、最右推導過程。 E+TE+T* *F F E E+ +T T* *a a E E+ +F F* *a a E E+a+a* *a a E+E+T T E E T T+a+a* *a a F F+a+a* *a a a+aa+a* *a a最左推導最左推導最右推導最右推導E EE E+T+TT T+T+TF F+T+T a+a+T Ta+a+T T* *F F a+a+F F* *F Fa+aa+a* *F F a+aa+a* *a aE EE+TE+TE+TE+T* *F FE E+ +T T* *a a E E+ +F F* *a aE E+a+a* *a a T T+a+a* *a aF

41、F+a+a* *a aa+aa+a* *a a可以可以記作：記作：E E + +a+aa+a* *a a定義定義2.52.5句型句型: :設文法設文法G=(VG=(VN N ,V,VT T,P,S),P,S)。如果符號串如果符號串x x是從識是從識別符號推導出來的，即別符號推導出來的，即S S * *x x，則稱則稱x x是文法是文法GSGS的的句型句型。句子句子: : x x僅由終結符號組成（即僅由終結符號組成（即S S* *x x，且且xVxVT T* *），），則稱則稱x x是是GSGS的句子。的句子。簡記：僅含終結符號的句型是一個簡記：僅含終結符號的句型是一個句子句子。定義定義2.62

42、.6 語言語言 L(GL(G）: :是由文法是由文法G G產生的所有產生的所有句子句子組成組成 的集合：的集合：L(G)L(G) x |S x |S * * x x且且 xVxVT T* * S S0S10S1 00S1100S11 0 03 3S1S13 3 0 0n-1n-1S1S1n-1n-1 0 0n n1 1n nS S0 0S1S1 00110011句型句型S,0S1,0011S,0S1,0011句子句子00110011S S0101句型句型S,01S,01句子句子0101使用第二使用第二個產生式個產生式一次得到一次得到L(GS)=0L(GS)=0n n1 1n n|n|n 11使

43、用第一個產生式使用第一個產生式n-1n-1次，再使次，再使用第二個產生式一次得到用第二個產生式一次得到若若L L（G1G1）= L= L（G2G2），），則成文法則成文法G1G1和和G2G2等價。等價。如如： GS GS S S0S1 S0S1 S0101S S0 01 1 S S0 0S1S1 00110011 S S0 0S1S1 00S1100S11 0 0n1 1nL(GS)=0L(GS)=0n1 1n|n n 11 GA GA A A0R A0R A01 01 R RA1A1 A A0101 A A0 0R R 0 0A1A1 00110011 A A0 0R R 0 0A1A1 0

44、000R1R1 0000A11A11 0 0n1 1nL(GA)=0L(GA)=0n1 1n|n|n 11L(GS)=L(GA)L(GS)=L(GA)GSGS和和GAGA等價。等價。遞歸產生式與遞歸文法遞歸產生式與遞歸文法遞歸遞歸: :同一操作或一組操作的連續(xù)重復。同一操作或一組操作的連續(xù)重復。遞歸產生式遞歸產生式: :左部和右部出現了相同非終結符的產生式左部和右部出現了相同非終結符的產生式左遞歸產生式左遞歸產生式 U UUU右遞歸產生式右遞歸產生式 U UUU自嵌入產生式自嵌入產生式 U UUU遞歸文法遞歸文法直接遞歸直接遞歸: :文法中有遞歸產生式。文法中有遞歸產生式。間接遞歸間接遞歸：經

45、若干步推導，出現遞歸。：經若干步推導，出現遞歸。例例: : U UVxVx V VUy|zUy|z U UVxVxUyxUyx遞歸文法的用處遞歸文法的用處: :用于定義無限語言用于定義無限語言( (遞歸語言遞歸語言) )總結：總結：語言無限，一定存在遞歸。語言無限，一定存在遞歸。 語言有限，一定不存在遞歸。語言有限，一定不存在遞歸。例例1 1：GS: SGS: SaB|bBaB|bB B Ba|ba|bS SaBaB aaaaS SaBaB ababS SbBbB babaS SbBbB bbbbL(GS)=L(GS)=aa,ab,ba,bbaa,ab,ba,bb 例例: :GG: | 0|1

46、|2|3|0|1|2|3|9 |9 D DN N S S 1 1位數位數 0|1|0|1|9|9D DN N N NS S SSSS 0 0S S|1|1S S| |9|9S S 2 2位數位數D DN N N NS S N NSSSS SSSSSS 0SS|0SS|9SS|9SS 3 3位數位數等等。等等。 L(GD)=VL(GD)=V+ + V=0,1,V=0,1,，99例：例：GSGS：S SaA|aaA|a A AaSaS S Sa a S SaAaA aaSaaS aaaaaa S SaAaA aaSaaS aaaAaaaA aaaaSaaaaS aaaaaaaaaa L(GS)=a

47、L(GS)=a2n+12n+1|n|n 00說明：說明：這些是較簡單的文法的例這些是較簡單的文法的例子，比較容易理解文法能子，比較容易理解文法能產生什么，一般來說，確產生什么，一般來說，確定文法將產生什么可能是定文法將產生什么可能是困難的。困難的。 自從喬姆斯基自從喬姆斯基( (Chomsky)Chomsky)于于19561956年建立形式語言的描述年建立形式語言的描述以來，形式語言的理論發(fā)展很快。這種理論對計算機科以來，形式語言的理論發(fā)展很快。這種理論對計算機科學有著深刻的影響，特別是對程序設計語言的設計、編學有著深刻的影響，特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作

48、用。譯方法和計算復雜性等方面更有重大的作用。喬姆斯基把文法分成四種類型，即喬姆斯基把文法分成四種類型，即0 0型、型、1 1型、型、2 2型和型和3 3型。型。這幾類文法的這幾類文法的差別在于對產生式施加不同的限制差別在于對產生式施加不同的限制。0 0型型( (短語結構短語結構phrase structure grammar, PSGphrase structure grammar, PSG) )：產生式形式產生式形式: : , ,(V(VN NVVT T) )+ +且至少含有一個非終且至少含有一個非終結符，而結符，而(V(VN NVVT T) )* *- -規(guī)則的左部和右部都可以是符號串，一

49、個短語可以產生規(guī)則的左部和右部都可以是符號串，一個短語可以產生另一個短語。另一個短語。SACaBSACaBCaaaCCaaaCCBDBCBDBaBBaaBBaCBECBE aDDaaDDaADACADACaEEaaEEaAEAE例：例：0 0型文法型文法文法文法GSGS：1 1型（上下文有關型（上下文有關context sensitive grammar, CSG context sensitive grammar, CSG ）: :產生式形式產生式形式: :均滿足均滿足| | |；僅僅 SS例外。例外。-A ，只有在只有在 、 這樣的上下文中才能把這樣的上下文中才能把A A改寫改寫為為例：例

50、：1 1型（上下文有型（上下文有關）文法關）文法GSGS：SaSBESaSBESaBESaBEBEbEBEbEaBabaBabbBbbbBbbbEbebEbeeEeeeEee2 2型（上下文無關型（上下文無關context-free grammar, CFGcontext-free grammar, CFG）： 產生式形式：產生式形式：， V VN N，( (V VT T V VN N) )* * - - A ，把把A改寫為改寫為時，不必考慮上下文時，不必考慮上下文3 3型型( (正規(guī)文法正規(guī)文法regular grammar, RGregular grammar, RG) )( (右線性右線

51、性) ) A AaBaB 或或 A A a ; a ; ( (左左線性線性) ) A ABaBa或或A A a a A,B A,B V VN N, , a a V VT T - -它是對它是對2 2型文法進行進一步限制型文法進行進一步限制 - -左線性和右線性文法是相互等價的左線性和右線性文法是相互等價的 例：例：2 2型（上下文無關）型（上下文無關）文法文法GSGS：SABSABABS|0ABS|0BSA|1BSA|1例：例：3 3型（正規(guī)）型（正規(guī)）GSGS：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|0GIGI：I I lTlT I l

52、I l T T lTlT T T dTdT T l T l T d T d四種文法之間的逐級四種文法之間的逐級“包含包含”關系關系2 2型文法型文法1 1型文法型文法0 0型文法型文法3 3型文法型文法w0 0型文法強于型文法強于1 1型文法，型文法，w1 1型文法強于型文法強于2 2型文法，型文法，w2 2型文法強于型文法強于3 3型文法。型文法。0 0型文法產生的語言稱為型文法產生的語言稱為0 0型語言型語言1 1型文法或上下文有關文法（型文法或上下文有關文法（CSGCSG）產生的語言稱為產生的語言稱為1 1型型語言或上下文有關語言（語言或上下文有關語言（CSLCSL）2 2型文法或上下文

53、無關文法（型文法或上下文無關文法（CFGCFG）產生的語言稱為產生的語言稱為2 2型型語言或上下文無關語言（語言或上下文無關語言（CFLCFL） 3 3型文法或正則（正規(guī)）文法（型文法或正則（正規(guī)）文法（RGRG）產生的語言稱為產生的語言稱為3 3型語言正則（正規(guī)）語言（型語言正則（正規(guī)）語言（RLRL） v四種文法之間的關系是將產生式做進一步限制而定義四種文法之間的關系是將產生式做進一步限制而定義的。的。v語言之間的關系依次：有不是上下文有關語言的語言之間的關系依次：有不是上下文有關語言的0 0型語型語言，有不是上下文無關語言的言，有不是上下文無關語言的1 1型語言，有不是正則語型語言，有不

54、是正則語言的上下文無關語言。言的上下文無關語言。2 2型文法型文法（不確定（不確定的下推自動機）的下推自動機）1 1型文法型文法（不確定（不確定的界限自動機）的界限自動機）0 0型文法型文法（圖靈機）（圖靈機）3 3型文法型文法（有限（有限自動機）自動機）形式語言與自動機形式語言與自動機 計算機語言的描述需借助形式語言計算機語言的描述需借助形式語言如：用如：用2 2型文法描述高級語言的語法規(guī)則型文法描述高級語言的語法規(guī)則 文法的用途文法的用途以有限的規(guī)則和符號，說明無窮的句子以有限的規(guī)則和符號，說明無窮的句子成為語言設計和實現的依據成為語言設計和實現的依據 文法特征（文法特征（0, 1, 2,

55、 3 0, 1, 2, 3 型型) )反映語言結構的復雜性、決定分析方法反映語言結構的復雜性、決定分析方法1.1.語法樹的定義語法樹的定義 表示一個句型推導的圖表稱為語法樹，它描述的句子的表示一個句型推導的圖表稱為語法樹，它描述的句子的 結構。結構。設設G=(VG=(VN N,V,VT T,P,S),G,P,S),G的一棵語法樹滿足如下條件：的一棵語法樹滿足如下條件： 1 1）每一個結點有一個標記，此標記是）每一個結點有一個標記，此標記是V VT TVVN N中的符中的符號。號。2 2）根的標記是）根的標記是S S。3 3）若一個結點是內部結點，且有標記）若一個結點是內部結點，且有標記A,A,

56、那么那么A A必在必在V VN N中中4 4）若編號為）若編號為n n的結點有標記的結點有標記A,A,結點結點n n1 1,n,n2 2,n nk k是點是點n n的從的從左到右的兒子左到右的兒子, ,并分別有標記并分別有標記A A1 1,A,A2 2,A Ak k, ,則則A AA A1 1A A2 2A Ak k必必須是須是P P中的產生式。中的產生式。 語法樹的結果：語法樹的結果： 從左到右從左到右讀出葉子的標記而構成的行。讀出葉子的標記而構成的行。b bS SA A5 56 67 7A Aa aS S2 23 34 4例例： G=(G=(S,AS,A, ,a,b,P,Sa,b,P,S）

57、, ,其中其中 P: P: S SaASaAS a a A A SbASbA SS SS babaG G的一棵推導樹如下圖：的一棵推導樹如下圖：S S1 1a a8 8a a9 9b ba a10101111語法樹是描述上下文無關文法語法樹是描述上下文無關文法句型推導句型推導的直觀方法的直觀方法葉子結點葉子結點：樹中沒：樹中沒有子孫的結點。有子孫的結點。從左到右讀出推導從左到右讀出推導樹的葉子標記連接樹的葉子標記連接成的文法符號串，成的文法符號串，為為GSGS的的句型句型。也。也把該推導樹稱為該把該推導樹稱為該句型的句型的語法樹語法樹。句子：句子：aabbaaaabbaa 給定文法給定文法G=

58、(VG=(VN N,V,VT T,P,S),P,S)，對于對于G G的任何句型都的任何句型都能構造與之關聯(lián)的語法樹能構造與之關聯(lián)的語法樹( (推導樹推導樹) ) 定理：定理： G G為上下文無關文法，為上下文無關文法，對于對于，有有S S =* * ，當且僅當當且僅當文法文法G G有以有以為結果的一棵語法樹為結果的一棵語法樹( (推導樹推導樹) ) 根據推導序列，對每步推導畫相應分枝根據推導序列，對每步推導畫相應分枝P: P: S SaASaAS a a A A SbASbA SS SS baba符號串：符號串：aabbaaaabbaa的推導過程和語法樹如下：的推導過程和語法樹如下：S SA

59、Aa aS Sb bS SA Aa ab ba aa a a aS SbAbAS S a aa ab bA AS S aabaabbabaS S aabbaaabbaa a a aA AS S S S a aA Aa a a aSbSbA Aa a a aS Sb bbabaa a a aa abbaabbaa aAaAS S S SS SA Aa aS Sb bS SA Aa ab ba aa a看不出句型中的符號看不出句型中的符號被替代的順序被替代的順序可見，對符號可見，對符號串串aabbaaaabbaa至少至少存在兩種推導。存在兩種推導。推導過程不同，推導過程不同，語法樹的生長語法樹的生

60、長過程不同，但過程不同，但最終的語法樹最終的語法樹完全相同。完全相同。a ab ba aa ab ba aS SA AS SA AS SS Sb ba ab ba aS SA AS SA Aa aa aP: P: S SaASaAS a a A A SbASbA SS SS baba語法樹是推導的圖形表示。語法樹是推導的圖形表示。1. 1. 一個句型推導或分析用一棵樹結構圖示一個句型推導或分析用一棵樹結構圖示 出來，它反映了一個句子的語法結構。出來，它反映了一個句子的語法結構。2. 2. 對于一個句子的多種推導對于一個句子的多種推導( (若文法是無二若文法是無二義性的義性的) )，采用各種推導