編譯原理-文法和語言

編譯原理-文法和語言第一頁，共62頁。第三章文法和語言程序設(shè)計(jì)語言與自然語言一樣，完整的定義包括語法和語義兩個(gè)方面。所謂語法是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。語法只是定義什么樣的符號(hào)序列是合法的，與符號(hào)的含義無關(guān)。語義有兩種類型：靜態(tài)語義是一系列限定規(guī)則，確定哪些合乎語法的程序是合適的；動(dòng)態(tài)語義也稱運(yùn)行語義或執(zhí)行語義，表明程序要做些什么？要計(jì)算什么。文法是闡明語法的一種工具，描述語法的規(guī)則。第二頁，共62頁。2.1文法的直觀概念語法是用來描述語言的組成規(guī)則。語句是組成語言的基本元素。而組成語言的語句往往是無窮列舉的，這時(shí)就要給出一些規(guī)則來描述句子的組成結(jié)構(gòu)。構(gòu)成語句的組織規(guī)則就是語法的表現(xiàn)。而這種規(guī)則或者說這種語言的描述就是文法。使用文法工具，不僅為了嚴(yán)格地定義句子的結(jié)構(gòu)，也是為了用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來，是以有窮的集合刻畫無窮的集合的工具。第三頁，共62頁。以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者定義)句子的組成結(jié)構(gòu)，比如漢語句子可以是由主語后隨謂語而成，構(gòu)成謂語的是動(dòng)詞和直接賓語?！拔沂谴髮W(xué)生”。是漢語的一個(gè)句子〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語〈謂語〉∷=〈動(dòng)詞〉〈直接賓語〉〈動(dòng)詞〉∷=是｜學(xué)習(xí)〈直接賓語〉∷=〈代詞〉｜〈名詞〉第四頁，共62頁。有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開始去找∷=左端的帶有〈句子〉的規(guī)則并把它由∷=右端的符號(hào)串代替，這個(gè)動(dòng)作表示成：〈句子〉〈主語〉〈謂語〉，然后在得到的串〈主語〉〈謂語〉中，選取〈主語〉或〈謂語〉，再用相應(yīng)規(guī)則的∷=右端代替之。句子：“我是大學(xué)生”的全部動(dòng)作過程是：〈句子〉〈主語〉〈謂語〉〈代詞〉〈謂語〉我〈謂語〉我〈動(dòng)詞〉〈直接賓語〉

我是〈直接賓語〉我是〈名詞〉我是大學(xué)生“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。第五頁，共62頁。2.2符號(hào)和符號(hào)串程序設(shè)計(jì)語言的表達(dá)方式就是一個(gè)一個(gè)的程序。而程序又是由一個(gè)個(gè)指令語句組成。語句又是由數(shù)字和字母這樣一些基本符號(hào)所組成。程序設(shè)計(jì)語言可以看成是在基本符號(hào)集上定義的，按照一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。字母表：是元素的非空有窮集合，這里所指的元素就是符號(hào)。不同的語言可以有不同的字母表。符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串。符號(hào)串涉及的有關(guān)概念有：符號(hào)的順序、符號(hào)串的長度、空符號(hào)串、符號(hào)串的頭尾、符號(hào)串的省略寫法、符號(hào)串的連接、符號(hào)串的冪、符號(hào)串的集合。第六頁，共62頁。符號(hào)串集合：若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。兩個(gè)符號(hào)串集合A和B的乘積定義為AB=xy|xA且yB。若集合A=ab,cde，B=0,1，則AB=ab1,ab0,cde0,cde1。使用*表示上的一切符號(hào)串（包括ε）組成的集合。Σ*稱為Σ的閉包。上的除ε外的所有符號(hào)串組成的集合記為+。Σ+稱為Σ的正閉包。例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}第七頁，共62頁。指定字母表Σ，Σ*表示Σ上的所有有窮長的串的集合。

Σ={0，1}Σ*={ε，0，1，00，01，10，11，000，001，010，…}Σ*=Σ0U

Σ1U

Σ2U

…

U

ΣnU…Σ*稱為集合Σ的閉包:正閉包:Σ+=Σ1U

Σ2U

…

U

ΣnU…Σ*=Σ0U

Σ+Σ+=Σ

Σ*=Σ*Σ

第八頁，共62頁。2.3文法和語言的形式定義如何來描述一種語言？如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個(gè)途經(jīng)：生成方式（文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠(yuǎn)繼續(xù)下去。）目標(biāo)是用有窮的規(guī)則描述無窮的語言第九頁，共62頁。2.3文法和語言的形式定義規(guī)則(也稱重寫規(guī)則、產(chǎn)生式或生成式)：是形如α→β或α::=β的(α,β)有序?qū)Γ渲笑翞樽帜副淼恼]包中的符號(hào)，β為字母表的閉包中的符號(hào)，α稱為規(guī)則的左部，β稱為規(guī)則的右部。規(guī)則是文法的核心。第十頁，共62頁。2.3文法和語言的形式定義所謂的形式定義就是用符號(hào)串來描述文法規(guī)則的表述。形式定義1：文法G定義為四元組（VN，VT，P，S）。其中，VN為非終結(jié)符號(hào)（或語法實(shí)體，或變量）集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式（也稱規(guī)則）的集合；（VN，VT和P是非空有窮集。）S稱做識(shí)別符號(hào)或開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。

VN和VT不含公共的元素，即VNVT=。通常用V表示VN

VT，V稱為文法G的字母表或字匯表。第十一頁，共62頁。例文法G=（VN,VT,P,S），其中VN={S}VT={0,1}P={S0S1,S01}可見該文法中非終結(jié)符中只含一個(gè)符號(hào)S，終結(jié)符中含兩個(gè)符號(hào)0和1，由兩個(gè)產(chǎn)生式，開始符號(hào)是S.第十二頁，共62頁。例文法G=（VN，VT，P，S）

VN={標(biāo)識(shí)符，字母，數(shù)字} VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識(shí)符>→<字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字><字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9} S=<標(biāo)識(shí)符>第十三頁，共62頁。很多時(shí)候不用將文法的四元組顯式地表示出來，而只將產(chǎn)生式寫出。一般約定：第一條產(chǎn)生式的左部是識(shí)別符號(hào)；用尖括號(hào)括起來的是非終結(jié)符號(hào)；不用尖括號(hào)括起來的是終結(jié)符號(hào)。或者用大寫字母表示非終結(jié)符號(hào)，小寫字母表示終結(jié)符號(hào)。如：G:S0S1S01第十四頁，共62頁。文法的寫法

1G：S→aAbA→abA→aAbA→ε2G[S]：S→aAbA→abA→aAbA→ε3G[S]：S→aAbA→ab|aAb|ε第十五頁，共62頁。2.3文法和語言的形式定義為定義文法所產(chǎn)生的語言，引入推導(dǎo)概念。形式定義2：如是文法G=(VN，VT，P，S)的規(guī)則(或說是P中的一產(chǎn)生式)，和是V*中的任意符號(hào)，若有符號(hào)串v，w滿足：v=，w=。則說v（應(yīng)用規(guī)則）直接產(chǎn)生w，或說w是v的直接推導(dǎo)，或者說w直接規(guī)約到v，記作：vw。形式定義3：如果存在直接推導(dǎo)的序列：v=w0w1w2…wn=w(w>0)則稱v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長度為n），或稱w規(guī)約到v。記作v+w形式定義4：若有v+w，或vw，則記作：v*w第十六頁，共62頁。推導(dǎo)的舉例例：G：S→0S1，S→01S0S100S1100S11000S111000S11100001111S0S1<程序><分程序>.<分程序>.<變量說明部分><語句>.VAR<標(biāo)識(shí)符>;BEGINREAD(<標(biāo)識(shí)符>)END.VARA;BEGINREAD(<標(biāo)識(shí)符>)END.第十七頁，共62頁。例：G：S→0S1，S→010S100S1100S11000S111000S11100001111

S0S100S11000S11100001111S=>+00001111

S=>S00S11=>00S11第十八頁，共62頁。2.3文法和語言的形式定義形式定義5：設(shè)G[S]是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即有S*x，則稱x是文法G[S]的句型。若x僅由終結(jié)符號(hào)組成，即S*x，xV*T，則稱x為G[S]的句子。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01一定是從文法開始符號(hào)出發(fā)進(jìn)行推導(dǎo)第十九頁，共62頁。例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

寫出a+a*a的推導(dǎo)過程

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

句子：用符號(hào)a，+，*，(和)構(gòu)成的算術(shù)表達(dá)式推導(dǎo)時(shí)盡量從左到右替換第二十頁，共62頁。2.3文法和語言的形式定義形式定義6：文法G所產(chǎn)生的語言定義為集合{x|S*x，其中S為文法識(shí)別符號(hào)，且xV*T，}?？捎肔（G）表示該集合。符號(hào)串x可從識(shí)別符號(hào)推出，也即x是句型。X僅由終結(jié)符組成，即x是文法G的句子。文法描述的語言是該文法一切句子的集合。第二十一頁，共62頁。例1：G：S→0S1，S→01L(G)={0n1n|n≥1}例2文法G[S]： （1）S→aSBE

（2）S→aBE

（3）EB→BE

（4）aB→ab

（5）bB→bb

（6）bE→be

（7）eE→ee

L（G）={anbnen|n≥1}第二十二頁，共62頁。S

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE (aB→ab)

aabBEE (EB→BE)

aabbEE

（bB→bb)

aabbeE

（bE→be)

aabbee

（eE→ee)

G生成的每個(gè)串都在L(G)中L(G)中的每個(gè)串確實(shí)能被G生成第二十三頁，共62頁。使用產(chǎn)生式(1)n-1次，得到推導(dǎo)序列：S=>*

an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S=>*

an-1S(BE)n-1

an(BE)n。然后從an(BE)n繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式(3)的右部進(jìn)行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=>*

anBnEn接著，使用產(chǎn)生式(4)一次，得到S=>*

anbBn-1En，然后使用產(chǎn)生式(5)n-1次得到：S=>*

anbnEn，最后使用產(chǎn)生式(6)一次，使用產(chǎn)生式(7)n-1次，得到：S=>*

anbnen也能證明，對(duì)于n≥1，串a(chǎn)nbnen是唯一形式的終結(jié)符號(hào)串第二十四頁，共62頁。文法的等價(jià)若L（G1）=L（G2），則稱文法G1和G2是等價(jià)的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價(jià)

A→01S→01R→A1第二十五頁，共62頁。2.4文法的類型文法分成四種類型，即0型、1型、2型、3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。0型文法：設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式是這樣一種結(jié)構(gòu)：（VNVT）*，且至少含有一個(gè)非終結(jié)符，而（VNVT）*，則G是一個(gè)0型文法。0型文法也稱短語文法。任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個(gè)0型文法。對(duì)0型文法產(chǎn)生式的形式做某些限制，可以給出1，2和3型文法的定義。aA->aCaA->abcAC->bS->SSS->第二十六頁，共62頁。2.4文法的類型1型文法：設(shè)G=(VN，VT，P，S)為一文法，若P中的每一個(gè)產(chǎn)生式均滿足||>=||，僅僅S除外，則文法G是1型文法或上下文有關(guān)文法。上下文有關(guān)文法的產(chǎn)生式的形式描述為1A212，其中1、2和都在（VNVT）*中，且非空，A在VN中。體現(xiàn)“上下文有關(guān)”，表現(xiàn)在只有A出現(xiàn)在1和2的上下文中，才能用取代A。2型文法：設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式滿足：是一個(gè)非終結(jié)符，（VNVT）*則此文法稱為2型文法或上下文無關(guān)文法。產(chǎn)生式的表現(xiàn)為：A。取代A與它的上下文無關(guān)。3型文法：設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式的形式都是AB或A，其中A和B都是非終結(jié)符，是終結(jié)符，則G是3型文法或正規(guī)文法。四個(gè)文法類型的定義是逐漸增加限制，因此，每一種正規(guī)文法都是上下無關(guān)的；每一種上下無關(guān)文法都是上下有關(guān)的；而每一種上下有關(guān)文法都是0型文法。aA->aCaA->abcAC->bbA->bDA->bDA->DaA->DEA->bDA->a第二十七頁，共62頁。0型至少包含一個(gè)非終結(jié)符A->bAA->A->ACaA->aCbA->bbcAC->b1型||>=||

除外A->bAA->A->ACaA->aCbA->bbc2型是一個(gè)非終結(jié)符A->bAA->A->AC3型AB或AA->bAA->第二十八頁，共62頁。文法的類型例：1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD第二十九頁，共62頁。文法的類型例：2型（上下文無關(guān)）文法

文法G[S]： S→AB A→BS|0 B→SA|1

第三十頁，共62頁。3型文法G[S]：

S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

第三十一頁，共62頁。文法的類型2型文法1型文法0型文法四種文法之間的逐級(jí)“包含”關(guān)系3型文法第三十二頁，共62頁。文法和語言0型文法產(chǎn)生的語言稱為0型語言1型文法或上下文有關(guān)文法（CSG

）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL）2型文法或上下文無關(guān)文法（CFG

）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（CFL）

3型文法或正則（正規(guī)）文法（RG）產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言（RL）

第三十三頁，共62頁。2.5上下文無關(guān)文法及其語法樹從0型到3型文法,其后一類都是前一類的子集,且限制是逐步增強(qiáng),而描述語言的功能是逐步減弱。上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)，比如描述算術(shù)表達(dá)式，描述各種語句等。第三十四頁，共62頁。例文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P為：{E→i,E→E+E,E→E*E,E→(E),〈賦值語句〉→i∶=E}E表示算術(shù)表達(dá)式,i表示程序的“變量”，該文法定義了由變量，+，*,(和)組成的算術(shù)表達(dá)式的語法結(jié)構(gòu)，即：變量是算術(shù)表達(dá)式；若E1和E2是算術(shù)表達(dá)式，則E1+E2，E1*E2和(E1)也是算術(shù)表達(dá)式第三十五頁，共62頁。描述一種簡(jiǎn)單賦值語句的產(chǎn)生式：〈賦值語句〉→i∶=E描述條件語句的產(chǎn)生式：〈條件語句〉→if〈條件〉then〈語句〉｜

if〈條件〉then〈語句〉else〈語句〉第三十六頁，共62頁。2.5上下文無關(guān)文法及其語法樹語法樹：是一種描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法，也稱推導(dǎo)樹。給定文法G=（VN，VT，P，S），對(duì)于G的任何句型都能構(gòu)成與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹滿足下列4個(gè)條件：每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)；根的標(biāo)記是S；若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在VN中；如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,…,nk,其標(biāo)記分別為A1，A2，…，AK，那么AA1A2A3…AK，一定是P中的一個(gè)產(chǎn)生式。第三十七頁，共62頁。上下文無關(guān)文法的語法樹的用處用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

a句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號(hào)串，為G[S]的句型。也把該推導(dǎo)樹稱為該句型的語法樹。第三十八頁，共62頁。上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa最左（最右）推導(dǎo)最右推導(dǎo)為規(guī)范推導(dǎo)；規(guī)范推導(dǎo)產(chǎn)生的句型為規(guī)范句型第三十九頁，共62頁。句型、推導(dǎo)G[E]：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

EE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*a

EE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a

不同的推導(dǎo)過程，都可以得到一個(gè)相同的結(jié)果。第四十頁，共62頁。規(guī)范推導(dǎo)規(guī)范句型最左（最右）推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型第四十一頁，共62頁。一棵語法樹表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?

不是的第四十二頁，共62頁。例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i第四十三頁，共62頁。二義文法

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的

或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題是遞歸不可解的，但可以為無二義性尋找一組充分條件第四十四頁，共62頁。文法的二義性和語言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說，這兩個(gè)文法所產(chǎn)生的語言是相同的。二義文法改造為無二義文法G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)規(guī)定優(yōu)先順序和結(jié)合律如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法都是二義的，則說此語言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語言來說，常常希望它的文法是無二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語句的分析是唯一的。第四十五頁，共62頁。2.6句型的分析對(duì)于上下文無關(guān)文法，語法樹是句型推導(dǎo)過程的幾何表示。語法樹將句型結(jié)構(gòu)直觀地顯示出來，是句型分析的很好工具。句型的分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。當(dāng)給定一個(gè)符號(hào)串時(shí)，試圖按照某文法的規(guī)則為該符號(hào)串構(gòu)造推導(dǎo)或語法樹，以此識(shí)別出它是該文法的一個(gè)句型。對(duì)于程序設(shè)計(jì)語言來說，句型分析是一個(gè)識(shí)別輸入符號(hào)串是否為語法上正確的程序的過程。分析算法從左到右，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而識(shí)別右邊的一個(gè)符號(hào)第四十六頁，共62頁。2.6句型的分析分析算法又可以分成兩大類，即自上向下的和自下向上的。所謂自上向下分析法，是從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入符號(hào)串的推導(dǎo)。所謂自下向上分析法，則是從輸入符號(hào)串開始，逐步進(jìn)行“規(guī)約”，直到規(guī)約到文法的開始符號(hào)。從語法樹的角度的理解句型分析過程，自上而下方法是從文法符號(hào)開始，將它作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串；自下向上方法則是從輸入符號(hào)串開始，以它作為語法樹的末端結(jié)點(diǎn)符號(hào)串，自底向上地構(gòu)成語法樹。第四十七頁，共62頁。自上而下的分析方法文法G[S]；(1)ScAd；(2)Aab；(3)Aa識(shí)別輸入串w=cabd是否該文法的句子。從根符號(hào)S開始，為cabd構(gòu)造一棵語法樹。ScAdab推導(dǎo)過程：ScAdcabd第四十八頁，共62頁。自下而上的分析方法文法G[S]；(1)ScAd；(2)Aab；(3)Aa為輸入符號(hào)串cabd構(gòu)造推導(dǎo)或語法樹。首先從輸入符號(hào)串開始。掃描cabd，從中尋找一個(gè)子串，該子串與某一產(chǎn)生式的右端相匹配。ScAdabcAdabcdab第四十九頁，共62頁。(1)S→cAd(2)A→ab(3)A→a

識(shí)別輸入串w=cabd是否為該文法的句子

自上而下的語法分析若ScAd后選擇(3)擴(kuò)展A，ScAdcad那將會(huì)？

w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配？宣告分析失?。ㄆ湟馕吨?，識(shí)別程序不能為串cabd構(gòu)造語法樹，即cabd不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。SAdca對(duì)于自上而下分析方法中的主要問題回溯第五十頁，共62頁。(1)S→cAd(2)A→ab(3)A→a

識(shí)別輸入串w=cabd是否為該文法的句子

自下而上的語法分析對(duì)串cabd的分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么最終就達(dá)不到歸約到S的結(jié)果，因而也無從知道cabd是一個(gè)句子cabd

cAbda對(duì)于自下而上分析方法中的主要問題精確定義“可規(guī)約串”第五十一頁，共62頁。句型分析的有關(guān)問題在自上而下分析方法中的主要問題是:假定要被代換的最左非終結(jié)符號(hào)是V,且有n條規(guī)則:V::=a1|a2|…|an那么如何確定用哪個(gè)右部去代替V呢?有一種解決辦法是從各種可能的選擇中隨機(jī)挑選一種，并希望它是正確的。如果發(fā)現(xiàn)它不正確，是錯(cuò)誤的，必須退回，重新選擇。這種方式稱為回溯。在自下而上分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它規(guī)約到某個(gè)非終結(jié)符號(hào)，這個(gè)子串稱為“可規(guī)約串”。問題是，每一步如何確定這個(gè)“可規(guī)約子串”。第五十二頁，共62頁。刻畫“可歸約串”文法G[S]句型的短語S=>*

αAδ且A

=>+

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語句型的直接短語若有A

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的直接短語句型的句柄一個(gè)句型的最左直接短語稱為該句型的句柄第五十三頁，共62頁。i*i+i的短語、直接短語和句柄G[E]：E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+i短語：i1*i2+i3，i1*i2

，i1，i2，i3直接短語：i1，i2，i3

句柄：i1EET+TFTF*Fi1i2i3I1,i2,i3分別是相對(duì)于F的直接短語I1*i2是相對(duì)于T的短語,因?yàn)椴荒苤苯油茖?dǎo)出,所以,不是直接短語.同樣i1*i2+i3是相對(duì)于E的短語.第五十四頁，共62頁。指出句型F+Fi(的短語，句柄，素