《編譯原理實用教程》-楊德芳-電子教案 第2章　形式語言概述

1、第二章　形式語言概述,本章學習目標,形式語言由Chomsky于1956年提出，主要討論語言和文法的數學機制以及語言和文法的分類。形式語言 的形成和發(fā)展，對編譯原理和技術產生了重要的影響。本章主要內容是:文法和語言的形式定義文法的分類句型的分析和語法樹,2.1字母表和符號串,任何一種語言都是由基本符號構成的。計算機高級語言作為計算機的語言，程序有語句構成，語句有一些基本符號構成，這些基本符號是保留字如main，if，then等、字母

2、、數字和專用符號等。每個程序可以看成基本符號串。將所有的基本符號定義成一個基本符號集合，則語言可以看成是在這個基本符號集合上定義的，按一定的規(guī)則構成的一切基本符號串組成的集合，給出如下的一些基本概念。,2.1.1字母表,定義2.1 字母表是元素的非空有窮集合，字母表中的元素稱為符號，因此字母表也稱為符號表。高級語言如C語言的字母表是由字母、數字、特殊符號和一些專用符號構成。例?={a,b}， ?={0,1}，?={0,1，

3、2，3，4，5，6，7，8，9}，∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;（，）},2.1.2符號串,1．符號串定義2.2 符號串是由字母表中的符號所組成的有窮序列。例2.1 某個字母表∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;}，則建立在∑上的符號串有：if (2+3

4、==5) then a=6 else b=8;2．符號串的長度符號串x中所包含的符號的個數稱為符號串x的長度，記為|x| 。例如字母表{0，1}，則|010110|=6。ε記為空串，長度為0。,3．子字符串定義2.3 設有非空符號串u=xvy，其中x、v、y是符號串，且v≠ε，則稱v為符號串u的子符號串。例題2.2設字母表Σ={a，b，c，d，+，-，*，/，(，)}上有符號串x=a+b*(c+d)，則a、a+b*與（c+d）等

5、都是x的子符號串，且其長度分別為∣a∣=1、∣a+b*∣=4與∣(c+d)∣=54．符號串的頭和尾定義2.4 如果z=xy是一個符號串，則x是z的頭,而y是z的尾。如果y非空，則x是z的固有頭，又稱為真前綴；若x非空，則y是z的固有尾，又稱為真后綴。,例題2.3 假設字母表?={a,b,c}上的符號串z=abc，則ε、a、ab、abc都是z的頭，且除abc外都是x的固有頭；ε、c、bc、abc都是z 的尾，且除abc外都是z的固有

6、尾。若只對符號串的頭部感興趣，記做z=x…。若只對尾部感興趣，則記為z=…x。5．符號串的運算定義2.5 符號串的連接運算 ：設 x與y是同一個字母表上的兩個符號串，把y的各個符號相繼寫在x的符號后所得到的符號串稱為x與y的連接，記為xy。,例題2.4設在字母表{a,b,c}上有符號串 x=ab與y=cba，則z=xy=abcba。這里∣x∣=2, ∣y∣=3, ∣z∣=5。對于字母表上的任何符號串x，都有εx=xε=x定義2.

7、6 符號串的方冪：設x是某個字母表上的符號串，把x自身連接n次，即z=xx…x（n個x），稱為符號串x的n次方冪，記為z=xn。例如，x=ab則x3=ababab,2.1.3符號串集合,1．符號串集合的定義定義2.6 若集合A中一切元素都是某字母表∑上的符號串，則稱A是該字母表∑上的符號串的集合。字母表上的符號串的集合通常用大寫字母來表示A、B、C、…表示。例題2.5 設某個字母表{a,b,c,d}上有兩個符號串的集合記為A

8、={a,bc},B={abc,cd,ab},2．符號串集合的運算定義2.7 兩個符號串集合A和B的乘積AB定義為：AB={xy∣x∈A ，且y∈B}例題2.6 設A={a,b}，B={c,d,e} 則AB={ac,ad,ae,bc,bd,be}對于任何空集合Φ，都有ΦA=AΦ=A類似于符號串的方冪，可以定義符號串集合的方冪，特別地定義字母表A的方冪為：A0={ε}，A1=A，An=An-1A (n>0),3．字母表的

9、閉包與正閉包的運算設有字母表A，由它做方冪A0，A1，A2，… An, …。A的閉包定義如下：定義 2.8 A的閉包A*=A0∪A1 ∪ A2 ∪…∪An∪…,其中，An （n=0，1，2，3，…）中所有的符號串的長度為n，因此字母表A的閉包 A*為字母表上一切長度為n的符號串所組成的集合。如果不允許包含空串ε，則得到字母表A的正閉包。定義2.9 A的正閉包 A+=A1 ∪ A2 ∪…∪An∪…顯然，A*= A0

10、 ∪A+ ，且A+=AA*=A*A。,例題2.7 設字母表Σ={a,b,c},依次寫出長度為1、2…的符號串，可得到 Σ的正閉包Σ+ ：Σ+={a,b,c,aa,ab,ac,bb,bc,…},在Σ+上添入空串ε即得Σ*。說明：根據閉包和正閉包的定義，則有Σ+=Σ*Σ=ΣΣ* 由于一個字母表的正閉包包含了該字母表中的符號所能組成的一切符號串，而語言是該字母表上某個符號串的集合，因此，在某個字母表上的語言是該字母表上正閉包的子集，且

11、是真子集。對于C語言，可以說，C語言是基本符號集合的正閉包的真子集。,2.2 文法的定義及其分類,什么是文法，文法的直觀概念是，文法作為一種工具，不僅嚴格地定義句子的結構，也是為了用適當條數的規(guī)則把語言的全部句子描述出來，是以有窮的集合刻劃無窮的集合的工具。。,2.2.2文法的形式定義,1．重寫規(guī)則定義2.10重寫規(guī)則，也叫產生式規(guī)則，或稱為生成式，是形如α→β或α::═β的（α,β）有序對,其中, α是某個字母表V+中的一個元素，

12、β是V* 中的一個元素。α稱為規(guī)則的左部，β稱為規(guī)則的右部。例如 A??B?讀作“A定義為?B?”，也就是說它是一條關于A的規(guī)則（產生式）。2．文法定義2.11 文法G是一個四元組，G=（VN，VT，P，S），其中，VN、VT分別是非空有限的非終結符號集和終結符號集，VN∩VT=?，P是產生式的集合，S∈VN 稱為文法的識別符號或開始符號。例題2.8在程序設計語言中，假設我們定義標識符的命名規(guī)則為字母a、b、c開頭的，字母a、

13、b、c和數字1、2、3的序列。命名規(guī)則為：,→→→→a→b→c→1→2→3,我們一般用大寫字母代表左邊的非終結符，設N 代表，D代表，L代表，則定義標識符的文法是：G=(VN，VT，P，N)其中，VN={N，L，D}VT={a,b,c,1,2,3}P為產生式的規(guī)則：{N→L， N→NL ，N→ND ，L→a ，L→b ，L→c ，D→1 ，D→2，D→3}S 是開始符號,為N.關于產生式的規(guī)則說明一點，

14、即若A→α，A→β，A→γ可寫成A→α|β|γ ?！皘”讀做“或者”。上面的產生式規(guī)則可以改寫為：,P為產生式的規(guī)則：{N→L|NL|NDL→a|b| cD→1|2|3},2.2.3文法的分類,自從喬姆斯基（Chomsky）于1956年建立形式語言的描述以來，把文法分成四種類型，即0型、1型、2型和3型文法。0型文法(短語文法)設G=（VN，VT，P，S），如果它的每個產生式α→β是這樣一種結構：α∈（VN∪VT ）+ ，

15、且至少含有一個非終結符，而β∈（VN∪VT ）*，則稱G是一個0型文法。0型文法又稱短語文法，它的能力相當于一個圖靈機。例如，?A?→?,1型文法（上下文有關文法）設G=（VN，VT，P，S）為一文法，若P中的每一個產生式α→β均滿足∣β∣≥∣α∣，僅僅S→ε除外，則文法G是1型文法或上下文有關文法。所謂上下文有關文法即：α=γ1Aγ2，β=γ1δγ2，符號串γ1 和γ2可以認為是上下文，A只有出現在上下文之間中，才可以被符號串δ

16、替代，成為α=γ1Aγ2?β=γ1δγ2因此，1型文法又稱為上下文有關文法。,3．2型文法（上下文無關文法）設G=(VN，VT，P，S)，若P中的每個產生式α→β滿足: α是一個非終結符, β∈(VN∪VT ) *，則此文法稱為2 型文法或上下文無關文法。有時將2型文法的產生式表示為形如：A→β，其中A∈VN 。 也就是當用β取代非終結符A時，與A所在的上下文無關。上下文無關文法有足夠的能力描述現今的程序設計語言。,例題2.10

17、2 型文法G=（VN，VT，P，N）其中，VN={N，D}VT={0，1，2，3，4，5，6，7，8，9}P={N→ND∣D，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9}該文法描述的符號串的集合是整數。,3型文法（右線性文法或正規(guī)文法）對2型文法的產生式做進一步的限制，限制產生式右部是單一終結符或單一終結符跟著單一非終結符，即：A→a A→aB則稱該文法為3型文法，又稱為右線性文法或正規(guī)文法，其中A、B∈VN，a∈

18、VT.例題2.113型文法 G=（VN，VT，P，S）其中，VN={S，A，B}VT={0，1}P={S→0∣1∣1A∣0B，A→1A∣0B，B→0∣1∣0B}該文法產生的是二進制整數。,2.2.4文法舉例,例題2.15正規(guī)文法G=（VN，VT，P，A）其中, VN={A,B,C,D}VT={x,y,z }P={A→xB∣yCB→zB ∣y∣yC C→xDD→ yD∣x}例題2.162型文法G=（VN，

19、VT，P，E）其中，VN={E，T，F}VT={+，*，（，），i}P={E→E+T|T, T→T*F|T, F→(E)|i}該文法能推出具有乘和加運算的算術表達式。,例題2.17正規(guī)文法G=（VN，VT，P，S）其中VN={S，A，B，G，H}，VT={d，·，+，－}P={S→dB|+A|－A|.GA→dB|.GB→dB|.H|dG→dHH→dH|d}其中，d代表十進制數字。 根據以上我們對文法的定

20、義我們不難發(fā)現3型文法類是2型文法類的特殊情況，2型文法類是1型文法類的特殊情況。每一類文法都是在前一類文法的基礎上加上一些限定規(guī)則而產生的。因此，四類文法產生的語言就會有如下關系：3型語言?2型語言?1型語言?0型語言,2.2.5各類文法與自動機的關系,語言是句子的集合，而句子又是由字母表上的符號串組成的。對于程序設計語言來講，程序由語句構成，語句則有數字、標識符、保留字、數字等單詞構成。因此對程序的編譯事實上就是對句子進行檢查。方

21、法就是編寫一個檢查過程，運行該過程來判斷編寫的程序是否合法。合法就回答“正確”，不合法就回答“不正確”，并且將錯誤報出。,編寫該過程的算法，抽象成一個數學模型，該數學模型稱為自動機。將算法對程序的合法與否的檢查轉化為數學模型對程序中的句子的識別過程。自動機給出了用有窮方式來描述潛在的無窮的語言的另一種手段。自動機能夠識別的句子的集合稱為語言。對于每一類Chomsky語言類，正好有一類自動機與它相對應。,1．0型語言與圖靈機,圖靈機是識別

22、0型文法的識別裝置。圖靈機被引進作為描述過程的數學模型，過程的直觀概念被看成是能機械實現的有窮指令的序列。圖靈機的基本模型如圖2-1所示。它有一個有限控制器、一個被分成若干單元的輸入帶和一個一次讀入一個單元的讀頭組成,2．1型文法與線性界限自動機相對應,。上下文有關文法所對應的自動機稱為線性界限自動機。其功能是能夠識別上下文無關語言，縮寫為LBA。,3．2型語言與下推自動機,2型語言或上下文無關語言對應的自動機稱為下推自動機。它是識別

23、上下文無關語言的數學模型?？s寫為PDA。,3．３型語言與有窮狀態(tài)自動機,3型語言或正則語言所對應的自動機稱為有窮自動機?？s寫為FA。無論那種自動機都分為確定性和非確定性之分,2.2.6文法分類的意義,一個文法實際上是某種語言的一個簡明、確切的描述，它表示了該語言中所允許的一類語法結構。從一個文法能推導出多個終結符的句子。但是知道了如何去構造屬于某一個語言的一個合法串只是問題的一個方面。同時我們還要有能力判定一個串是否合法。也就是說，我

24、們需要確定這個給定串的推導序列。如果從文法出發(fā)找不到這個推導序列，則該串就是非法的。以上四類文法都分別與一個相當簡單但功能很強的自動機相關。右線性文法可由一種有窮狀態(tài)自動機識別。,2.3文法產生的語言和句型的語法樹,2.3.1推導和規(guī)范推導為了定義文法產生的語言，我們必須給出推導的概念。推導分為三大類：直接推導 、?，長度為n(n≥1)的推導和長度為n（ n≥0）的推導。定義2.12如α→β是文法G=(VN,VT,

25、P,S)的規(guī)則（或說是P中的一產生式），γ,δ∈(VN∪VT)*，則稱符號串γβδ為符號串γαδ應用產生式α→β所得到的直接推導。記為γαδ?γβδ。,定義2.13推導長度大于0的推導：如果 對于符號串v 與w存在一個直接推導序列u0 ? u1?u2?u3?…un (n>0)其中u0=v與un =w,則稱符號串v推導出w或稱w歸約到v，記作v ? *w，稱這個直接推導序列是長度為n的推導，且稱符號串w是相對于符號串v的一個字

26、。定義2.14推導長度大于等于0的推導：如果對于符號串v和w，v=>w或v=w，則記作v ? *w，稱符號串v廣義推導到符號串w，或稱w廣義歸約到v。,例2.18根據文法，考慮以C語言中的無正負號整數作為識別符號的文法。（1）?（2）?| (3 ) ? 0|1|2|3|4|5|6|7|8|9VT ={0,1,2,3,4,5,6,7,8,9} VN ={ , ,}判斷數據2634是否是C語言合法的數據。給

27、出數據2634的推導。???4?4?34?34?634?2634由此可見，2634是C 語言的合法數據。每一步推導都是直接推導?？梢员硎緸楠?634,定義2.15如果在推導的任何一步???，其中?、?是句型，都是對?中的最左非終結符進行替換，則稱這種推導為最左推導。定義2.16如果在推導的任何一步???，其中?、?是句型，都是對?中的最右非終結符進行替換，則稱這種推導為最右推導。定義2.17在形式語言中，最右推導常稱為規(guī)范

28、推導，由規(guī)范推導所得的句型稱為規(guī)范句型。,定義2.15如果在推導的任何一步???，其中?、?是句型，都是對?中的最左非終結符進行替換，則稱這種推導為最左推導。定義2.16如果在推導的任何一步???，其中?、?是句型，都是對?中的最右非終結符進行替換，則稱這種推導為最右推導。定義2.17在形式語言中，最右推導常稱為規(guī)范推導，由規(guī)范推導所得的句型稱為規(guī)范句型。,例2.19給出了下列文法G（1）?（2）?| (3 ) ? 0|

29、1|2|3|4|5|6|7|8|9VT ={0,1,2,3,4,5,6,7,8,9} VN ={ , ,}判斷數據2634是否是C語言合法的數據?！窘狻浚?）用最右推導，每次用產生式的規(guī)則替換最右邊的非終結符，推導過程如下：???4?4?34?34?634?2634,（2）用最左推導，每次直接推導都替換最左邊的非終結符，推導過程如下：??????2?26?263?2634,2.3.2句型、句子和語言,定義

30、2.18句型：設G[S]是一個文法，如果符號串x是從開始符號S推導得到的，即有S=>+x，x?V+，則稱符號串x是該文法G的一個句型。定義2.19句子：G[S]是一個文法，如果符號串x是從開始符號S推導得到的，即有S=>+x，并且x?VT，則稱該符號串為該文法的一個句子。實質上，句子是句型的特殊情況，句子是由終結符組成，而句型是有終結符和非終結符組成。定義2.20語言G[S]是一個文法，文法G產生的語言L(G)={x

31、|S=>x，并且x?VT}，即文法的語言是文法所有句子的集合。,例2.20 2型文法G=(VN，VT，P，S)其中，VN={S}VT={0,1}P={S→0S1,S→01}該文法產生的語言是L(G)={0n1n,,其中n≥1},例2.21 文法G[S]定義如下S?if E then S| if E then S else S|while E do S|begin L end|A該文法產生的語言就是程序設計語言中的單分

32、支、雙分支、循環(huán)語句和順序語句，其中每個非終結符的意義是：S代表語句，L代表語句串、A代表賦值語句，E代表布爾表達式。,例2.22 設文法G[S]：E?E+T|TT?T*F|FF?(E)|i證明符號串E+(E+T)*i是文法的句型，i+i*i 是文法的句子；并說明該文法產生的語言是什么?！咀C明】,①由于E?E+T?E+T*F?E+T*i?E+F*i?E+(E)*i ?E+(E+T)*i所以 E+(E+T)*i是文法的句型。

33、②由E?E+T?E+F?E+F*i?E+i*i?T+i*i?F+i*i?i+i*i所以i+i*i 是文法的句子。③該文法產生的語言是程序設計語言中的算術運算式，其中包括加、乘和括號運算。,2.3.3語法樹,在自然語言中，句子結構可以借助一種樹形表示進行分析。如下面的句子：They are students and teachers of the Physics Department。對該句子的結構進行分析，其樹型結構如圖2-3所

34、示，由此可以看出，該句子是由主語、系詞和表語組成，是一個語法正確的句子。,在自然語言中，可以通過樹型表示直觀地分析句子的結構；在形式語言中，我們提到了句型、推導的概念，在證明某個符號串是否是某個文法的句型時，采用從文法開始符號推導的方法，這個推導過程可以用語法樹直觀的表示出來。語法樹也稱為推導樹，其定義如下：,給定文法G=(VN,VT,P,S) ，對于G的任何句型都能構造與之關聯(lián)的語法樹，這棵樹滿足下列四個條件：（1）每個結點都有一個

35、標記，此標記是V的一個符號。（2）根的標記是S。（3）若一結點n至少有一個它自己除外的子孫，并且有標記A，則A肯定在VN中。（4）如果結點n的直接子孫，從左到右的次序是結點n1,n2,n3….nk，其標記分別為A1，A2，A3，…AK。那么A→A1A2A3AK一定是P中的一個產生式。,例2.23 設文法G[S] ：E?E+T|TT?T*F|FF?(E)|i證明符號串E+(E+T)*i是文法的句型。,2.3.4二義性文法及其

36、他,1．二義性文法及其定義一個文法，如果它的一個句子或句型有兩棵或兩棵以上的語法樹，則稱此句子具有二義性。如果一個文法含有二義性的句子，則稱該文法具有二義性。例2.24 設文法G[S]：S→if B then S|if B then S else S|i：=E給出符號串if B then if B then S else S的語法樹。語法樹的結構如圖2-5所示。從上面的語法圖我們可以看出，字符串if B then if B

37、then S else S能夠畫出兩棵語法樹，所以該文法是一個二義性文法。,在語言中，為了避免二義性的文法，往往對文法加以一定的限制，如限制條件語句then之后不允許再是條件語句，或者從語義解釋方面限制條件語句中的else只能與其前面的、還沒有和其他else配對的then配對。如此限制之后，符號串if B then if B then S else S就只有圖2-5左邊的樹形結構了。,2．二義性文法的證明,要判定一個文法是否是二義性文法

38、，或它是否產生一個先天二義性的上下文無關語言，是個遞歸不可解的。即不存在一個算法，它能在有限的步驟內，確切的判斷出某個給定的文法是否是一個二義性文法。我們要證明一個文法是否是一個二義性文法，就是找到該文法的一個句型特例，能夠畫出這個句型的兩棵語法樹，該文法就是二義性文法。,例2.25 文法G=（{E}，{+，*，I,(,)}，P，E）其中P為：E?i E?E+EE?E*EE?(E)證明該文法是二義性文法，并將該文法改為等

39、價的非二義性文法（等價的文法是指產生的語言相等的文法）。,【證明】取句型i*i+i，寫出該句型的兩個不同的推導。畫出推導的兩棵不同的語法樹。推導1：E?E+E?E*E+E?i*E+E?i*i+E?i*i+i推導2：E?E*E?i*E?i*E+E?i*i+E?i*i+i推導的兩棵語法樹如圖2-6所示。將文法改為非二義性文法為：E?T |E+TT?F |T*FF?（E）|i,2.3.5文法產生的語言和產生語言的文法,例2.26

40、 設G=（VN，VT，P，S），VN={S,B,E}，VT={a,b,c}，P由下列產生式組成：①S?aSBE②S?aBE③EB?BE④aB?ab⑤bB?bb⑥bE?be⑦eE?ee（1）問該文法是Chomsky哪一類型的文法？（2）它生成的語言是什么？,答：根據文法分類定義，由于文法中存在產生式，其左部由長度大于1的符號串構成，如產生式“EB?BE”，顯然不符合Chomsky 的2型和3型文法的定義。該文法產生式左部

41、串的長度均小于等于右部串的長度，符合1型文法的定義，所以該文法是上下文有關文法。,,（2）根據如下推導：對于每一個n≥1，我們將①號產生式使用n-1次，得到推導序列：S ? an-1S(BE)n-1，然后使用產生式(2)一次，得到：S ? an(BE)n，然后從an(BE)n.繼續(xù)推導，總是對EB使用產生式③的右部進行替換，而最終在得到的串中，所有的B都限于所有的E。設n=3，aaBEBEBE?aaaBBEEBE?aaaBBEBEE?a

42、aaBBBEEE。即有：S ? anBnEn.接著，使用產生式(4)一次,得到SanbBn-1En，然后使用產生式⑤n-1 次得到：S ? anbnEn，然后使用產生式⑥一次，使用產生式⑦n-1次，得到：S ? anbnen 因此該文法產生的語言是L(G)={anbnen|n≥1}。,,,,例2.27 設有上下文無關文法如下：G[S]：S?ABA?UTU?a|aUT?b|bTB?c|cC將文法的產生式代入

43、產生如下文法：G[S]： S?UTB U?a| aUT?b|bTB?c|cC,考察文法，用L(S)，L(U)，L(T)和L(B)分別表示從終結符S，U，T和B出發(fā)推導出的符號串的集合，不難發(fā)現：L（U）={ai|i≥1}={a}+L（T）={bj|j≥1}={a}+L（B）={ck|k≥1}={a}+由于有S?UTB，則有：L（S）=L(U)L(T)L(B)=(aibjck|i≥1,j≥1, k≥1)={a}

44、++{c}+,例2.28 構造一個上下文無關文法G，使其描述的語言L（G）是能夠被5整除的無符號整數集合。能夠被5整除的整數其結構特點是，末位數一定是0或5。所以，只要保證生成的整數末位數字是0或5即可。據此，構造描述能被5整除的無符號整數集合的文法如下：G[S]：S?N0|N5N?DN|?D?0|1|2|3|4|5|6|7|8|9,例2.29 寫出一個上下文無關文法G，使得L(G)={anbmcmdn|n≥0，m≥1}

45、分析該語言的特點，可以看出，a和d的個數是一樣的，b和c的個數是一樣的。m的取值范圍從1開始，所以至少有一個bc，n的最小值為0。寫出文法為：S?aAd|A A?bAc|bc,2.4句型分析與句柄,對于上下文無關文法，語法樹是句型推導過程的幾何表示；是進行句型分析極好的工具。所謂句型分析就是識別一個符號串是否是某一個文法的句型。進一步說就是給定一個符號串時，按照某文法的規(guī)則為該符號串

46、構造推導或語法樹，以此來識別它是文法的一個句型。對于上下文無關文法，其句型分析方法有兩大類，一類是自上而下的分析方法（又稱自頂向下），另一類是自下而上（自底向上）的分析方法。,2.4.1 自上向下的分析方法,1．基本思想 自上而下的分析方法就是從識別符號出發(fā)，看是否能推導出待檢查的符號串，如果能推導出這個符號串，則表明此符號串是該文法的句型或句子，否則就不是?；蛘哒f，以文法的識別符號作為根結點，看是否能構造出一個語法樹，而且此語法樹所

47、有葉子結點從左到右所構成的符號串恰好是待檢查的符號串。如果能生成這樣的語法樹，則表明待檢查的符號串是該文法的一個句型或句子，否則就不是。,,例2.30 設文法G[S]：S?aAbc| aBA?baB?beB|d輸入串：abed，識別該串是否是該文法的一個句子。方法：從文法的識別符號S開始出發(fā)，選擇它的一個產生式S?aAbc 得到直接推導S? aAbc以識別符S作為根結點，構造語法樹，如下圖2-7所示,2．分析過程,符號串aA

48、bc與待檢查的符號串abed的第一個符號相匹配。由于符號串aAbc的第2個符號是非終結符，因此需要對它進行替換。A只有一個產生式A?ba。以其右部替換A，得推導S?aAbc?ababc得到語法樹，如圖2-7（b）所示。符號串ababc與待查符號串abed的第2個符號相匹配，但與第3個符號不相匹配，匹配失敗。此時，需要退回到非終結符 A，重新選擇S另外的產生式，再做試探。這種選擇的過程稱之為回溯。,選擇S的另外一條產生式的規(guī)則S?aB，

49、得到直接推導S?aB，得到語法樹2-7（c），再選取其中的一條產生式B?beB，得到推導S?aB?abeB，得到語法樹如圖（d），將B?d代入即可得到該字符串abed。。,3．存在問題,自上而下分析方法是從文法的識別符號開始，選擇相應的產生式規(guī)則進行推導。但在推導過程中會出現回溯現象。我們把出現回溯的分析稱為不確定的自頂上下分析方法。這種方法花費時間多，效率低，編程實現時復雜，如果對文法加以限制，就可以避免回溯，這就出現了我們后面要提

50、到的LL(1)分析方法,2.4.2確定的自上而下的分析方法,例2.31 設文法G[S]S?aBc|bCdB?eB|fC?dC|c試檢查符號串aefc是不是該文法的句子。,識別符S有兩條產生式，它們的右部首符號分別是終結符a和b。待檢查符號串aefc的首符號是a，所以從識別符S出發(fā)，只能選擇其產生式S?aBc得到直接推導S?aBc得到語法樹如圖2-8（a）所示。其中，非終結符B有兩條產生式，它們右部首符號分別是終結符e與f，而待檢

51、查的符號串aefc的第2個符號是終結符e，所以選擇B的產生式B?eB得到推導S?aBc?aeBc，得到語法樹如圖2-8（b）所示。,由于待檢查的符號串aefc的第3個符號是終結符f，因而對句型aeBc中的非終結符B選擇其產生式B?f的推導S?aBc?aeBc?aefc得到語法樹如圖2-8（c）所示。如此推導出的符號串aefc，語法樹的葉子結點序列是aefc，與待檢查的符號串aefc相匹配。,例2.32 若有文法G[S]S?Ap|B

52、qA?aA?cAB?bB?dB當輸入串W=ccap，那么試圖推出輸入串的推導過程為：S?Ap?cAp?ccAp?ccap很容易構造相應語法樹，如圖2-9所示。,2.4.3自下而上的分析方法,1．基本思想自下而上的分析方法的基本思想是從待檢查的符號串出發(fā)，看最終是否能歸約到文法的識別符號。如果能歸約到文法的開始的識別符號，則表明此待檢查的符號串是該文法的一個句型或句子，否則便不是。,例2.33 若有文法G[S]①S?c

53、Ad②A?ab③A?a識別輸入串w=cabd是否是該文法的句子。首先從輸入串開始，掃描cabd，從中尋找一個子串，該子串與某一產生式的右端相匹配。子串a和子串ab都是合格的，假若我們選用了ab，用產生式②的左端A去替代它，即把ab歸約到A，得到串cAd。構造一個直接推導cAd?cabd，即從cabd葉子開始向上構造語法樹，接下去在得到的串cAd中又找到了子串cAd與產生式①的右端相匹配，則用S替代cAd，或稱將cAd歸約到S，

54、得到了又一直接推導S?cAd，形成了最終的語法樹。分析過程如圖2-10所示。,2．存在問題,在自上向下的分析中，假定要被代換的最左非終結符的符號是V，且有n條規(guī)則：V??1|?2|?3|…|?n，那么如何確定用哪個右部去替換V？有一種解決方法是從各種可能的選擇中挑選一種，并希望它是正確的。如果發(fā)現它是錯誤的，我們必須退回，再試著進行另外的選擇，這種方式稱為回溯。,在自下向上的分析方法中，在分析程序工作的每一步中，都從當前串中選擇一個子串

55、，將它歸約到某個非終結符號，我們暫且把這個子串稱為“可歸約串”。出現的問題是如何確定這個“可歸約串”？比如在上例中，我們在對輸入串cabd 的分析中，如果不是選擇ab，用產生式②，而是選擇a，用產生式③將a歸約到A，那么最終就達不到S的結果，也就不知道cabd是一個句子。因此在歸約時，ab是“可歸約串”而不是a。如何求“可歸約串”成為自下而上進行分析的關鍵。下面我們用“句柄”的概念來描述“可歸約,3．句柄的概念,（1）形式化定義定義2

56、.21令G是一文法，S是文法的開始符號，??? 是文法的一個句型。如果有：S?A?且A?則稱?是句型???相對于非終結符A的短語。特別地，如有A??則稱?是句型???相對于規(guī)則A??的直接短語。一個句型的最左直接短語稱為該句型的句柄。（2）求一個句型的句柄給定某個句型，要求出該句型的句柄，比較直觀的方法就是畫出該句型的語法樹。該語法樹的一棵子樹的葉子結點（從左到右）組成的符號串便是這個句型關于子樹根結點的一個短語。,語法樹的一棵

57、簡單子樹（只有單層子樹）的葉子結點組成的符號串是這個句型關于簡單子樹根結點的一個直接短語。語法樹的最左的簡單子樹葉子結點組成的符號串就是這個句型的句柄。例2.34 已知文法G[S]：S?(R)|a|∧R?TT?S,T|S句型?=(a,(T),(S,T))的語法樹如圖2-11所示。,【解答】觀察該語法樹，共有10個非葉子結點，10棵子樹。因此有短語aT(T)S,T(S,T)(T), (S,T)a, (T),

58、(S,T)(a, (T), (S,T)),2.4.4文法的存儲,一個文法的語法圖由該文法所有非終結符的定義圖組成。每個非終結符號的定義圖是一個結構型數據。名字定義下一個候選式右部后繼寫成高級語言的結構型數據形式，則為：type struc=↑boxesboxes=recordname:array[1‥10] of char;def:struc;nextp:struc;righ

59、ts:struc;end;,其中，“名字”是用某種內部形式表示的終結符號或非終結符號的名字?！岸x”是一個指針，對于非終結符號，它指向其第一個侯選式結構圖的開始位置。對于終結符號，它為0；“下一個侯選式”是一個指針，指向相同左部的下一個侯選式的開始位置。若無侯選式，則它為0；“右部后繼”是一個指針，指向同一個右部的下一個符號。另用一個一維數組記錄所有的非終結符號定義圖的開始地址。也就是說，這個數組的每個元素都是一個指針，分別

60、指向相應的非終結符號的第一個候選式的定義圖。,例2.35文法E?EAT|TT?TMF|FF?（E）|iA?+|－M?*|/按照上面的存儲結構，畫出文法的存儲結構如圖2-12所示：,小 結,文法是形式語言的一個十分重要的基本概念。文法可定義為一個四元組，文法G=（VN，VT，P，S），其中，VN是一個非終結符集，VT是一個終結符集，P是一個產生式集，S是文法的開始符號。Chomsky 將文法分為0 型，1型，2型和3型文法

61、。程序設計語言的詞法規(guī)則屬于3型文法（正規(guī)文法），程序設計語言的語法和語義部分一般是采用2型文法來描述。,對于一個文法，我們需要研究它的句型，句子和語言。要識別一個符號串是不是一個文法的句子，需要對它進行語法分析。分析方法有兩類，一類是自上而下分析法，另一類是自下而上的分析方法。為了進行語法分析，需要事先將產生式存儲在計算機中。可以為文法建立一個產生式表，把文法的所有的產生式都放在這個產生式表中。為了在分析過程中能迅速查找到相應的產生

62、式，還可以建立一個目錄表。,習 題,1．設字母表A={a}，符號串x=aaa，寫出下列符號串及其長度：x0，xx，x5以及A+和A*。2．令?={a,b,c}，又令x=abc，y=b，z=aab，寫出下列符號串及它們的長度：xy，xyz，(xy)3。3．設文法G[S]：S→SS*|SS+|a，寫出符號串aa+a*規(guī)范推導，并構造語法樹。4．已知文法①S?AB ②A??|aA ③B?bc|bBc寫出該

63、文法描述的語言。,5．已知文法①E?T|E+T|E-T②T?F|T*F|T/F③F?(E)|i寫出該文法的開始符號、終結符集合VT、非終結符集合VN。,6．對于文法①E?T|E+T|E-T②T?F|T*F|T/F③F?(E)|i寫出句型T+T*F+i的短語、簡單短語以及句柄。7．設計出語言{anbm|n,m≥1}的文法。8．文法G=({A，B，S}，{a,b,c},P,S)其中P為：S→Ac|AbA→abB→

64、bc寫出LG[S]）的全部元素。,9．已知文法Z→aZb Z→ab 寫出L（G[Z]）的全部元素。10．為句子i+i*i構造兩棵語法樹，從而證明下述文 法是二義性的。 →i|()| →+|－|*|/11．寫出生成下述語言的上下文無關文法。 （1）{anbnambm|n,m≥0} (2) {1n0m1m0n|n,m≥0}12．句型、句子和語言之間有