編譯原理西安交通大學(xué)(馮博琴)第三章上下文無關(guān)文法

1、程序語言的語法描述與分析目的：語言的語法結(jié)構(gòu)的形式描述從形式描述中，研究語法分析器的構(gòu)造（算符優(yōu)先分析法和遞歸子程序分析法）第一頁，共三十頁。本章內(nèi)容引言-文法文法與語言-上下文無關(guān)文法-推導(dǎo)與語言語法樹與二義性第三章 上下文無關(guān)文法(context-free grammar)第二頁，共三十頁。文法（grammar)問題：如何描述語言定義：文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則 )目的：解決語言的有窮說明問題，包含對語法的描述，但卻不表達(dá)任何語義一、引言第三頁，共三十頁。1、文法的描述應(yīng)達(dá)到要求：2、文法分類：分為四類（0、1、2、3型文法），對應(yīng)四類語言； 與程序語言語法有關(guān)的是上下

2、文無關(guān)文法形式上嚴(yán)格、準(zhǔn)確；易于理解；具有較強(qiáng)的描述能力；有利于句子的分析和翻譯，構(gòu)造語法分析器第四頁，共三十頁。3、上下文無關(guān)文法的特點(diǎn)：它所定義的語法范疇（或語法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的說明上下文無關(guān)文法只能描述一部分語言，但已足夠 描述現(xiàn)今的程序設(shè)計(jì)語言自然語言要用其他的文法來描述第五頁，共三十頁。二、文法與語言1、一個上下文無關(guān)文法G是一個四元式（VT,VN,S, P ），其中:VT：是非空有限集，它的每個元素是終結(jié)符號；VN：是非空有限集，它的每個元素是非終結(jié)符號；VTVN=; VTVN=V;P ：產(chǎn)生式集合（有限），每個產(chǎn)生式形式是 P-| PVN， (VTVN)

3、*，S至少一次為P ；S：SVN，稱為開始符號；第六頁，共三十頁。例1、 考慮下面的算術(shù)表達(dá)式的文法及語言VT：id + * / ( )VN：表達(dá)式、運(yùn)算符S： 表達(dá)式P： 表達(dá)式 -表達(dá)式 運(yùn)算符 表達(dá)式表達(dá)式 -（表達(dá)式）表達(dá)式 - 表達(dá)式表達(dá)式 - id運(yùn)算符 - +| | * |/|得到 文法G1(E):E -EAE|( E )| E |idA - + |*|/|第七頁，共三十頁。該文法的：VN是出現(xiàn)P的左部所有符號集合V是P的所有符號VT = V VNS是該文法所定義的句子名字寫出了P ，就能找出其它三元素由此可見，文法G1(E)所定義的語言是上述算術(shù)表達(dá)式，如：id+id，id*(

4、id+id) 等它表達(dá)了簡單算術(shù)表達(dá)式由id用A連接起來第八頁，共三十頁。2、從此可見終結(jié)符：是用以組成語言中的串的基本符號，與程序語言中“單詞”是同義語；如：表達(dá)式id+(id)*( - id)中，+、*、/、id均為終結(jié)符非終結(jié)符：是標(biāo)記某種串的集合的特定符號，與“語法變量”、“語法范疇”是同義詞；如：表達(dá)式、運(yùn)算符都表示一個串的集合第九頁，共三十頁。該語法范疇叫“句子”，在程序語言中叫“程序”語言的句子是由一串VN定義，到最后才是一串VT開始符號：一個VN，標(biāo)記感興趣的語法范疇。其它非終結(jié)符用以定義其它的串集，這有助于定義該語言，也有助于為它處理的語言提供一個分層的結(jié)構(gòu)；第十頁，共三十頁

5、。產(chǎn)生式：規(guī)定由終結(jié)符和別的語法范疇組成一個新的語法范疇的辦法；結(jié)構(gòu)：非終結(jié)符 - 一串非終結(jié)符和終結(jié)符如：A -A -左部符號 右部候選式VN=X1X2Xn，XiV第十一頁，共三十頁。3、習(xí)慣記號VN:大寫字母A、B、C、S等VT:小寫字母，09，+、 等運(yùn)算符，標(biāo)點(diǎn)，分界符，黑體字母串id、ifX、Y、Z： 文法符號，或VN或VT一個符號u、v、 wz： VT中串、: 文法符號串(VTVN)*S: 開始符號，第一個產(chǎn)生式中出現(xiàn)-: 定義為（元語言符號）|： 或（元語言符號）第十二頁，共三十頁。有窮條產(chǎn)生式，產(chǎn)生無窮集，要求產(chǎn)生式必須遞歸定義算術(shù)表達(dá)式，用了兩條濃縮的產(chǎn)生式，一般定義一個語言

6、的產(chǎn)生式是很復(fù)雜的對遞歸的算術(shù)表達(dá)式的產(chǎn)生式，進(jìn)行反復(fù)推導(dǎo)產(chǎn)生表達(dá)式語言問題：表達(dá)式語言無窮，如何定義？第十三頁，共三十頁。4、推導(dǎo)與語言問題：用文法如何定義一個語言？思路：從S出發(fā)，反復(fù)使用P，對非終結(jié)符替換展開，最后得到全由終結(jié)符串組成的一個串涉及到：替換-推導(dǎo)-句型-句子-語言第十四頁，共三十頁。推導(dǎo)：如兩個串u0、un，存在一個串序列u0 u1 un則 u0 R1 un，R1記為 或 u0 un：表示從u0出發(fā)，經(jīng)一步或若干步，可推導(dǎo)出unu0 un：表示從u0出發(fā)，經(jīng)0步或若干步，可推導(dǎo)出un直接推導(dǎo)：是兩個字符串之間的一種關(guān)系R如：（A） R （），它表示：若A-P， 、V*則R

7、就是直接推導(dǎo)，R 記為即：A 第十五頁，共三十頁。如令u0為S，即推導(dǎo)要從開始符號開始，那么： S ，V*，稱為G的句型如再要求VT*，則 為G的句子文法G所產(chǎn)生的句子的全體是一個語言，記為L(G) L(G) = |S & VT* 怎樣由推導(dǎo)引出語言？只需在推導(dǎo)中加一些限制即對：u0 un或u0 un第十六頁，共三十頁。由文法G定義語言L是依賴一種運(yùn)算，關(guān)系 V*中有許多的串，僅有那些(S,u) (S,v)存在 關(guān)系的u、v才有可能成為語言中的句子。、是句型，表示(S，) (S，) ，有 的關(guān)系，但它的構(gòu)成不全為VT的字符。G的句型集，是指存在S 關(guān)系的所有，該集的子集是L(G)V* 句型集

8、L(G)說明第十七頁，共三十頁。例2 根據(jù)文法G: E - E+E|E*E|( E )| i句子i1*(i2+i3)推導(dǎo)過程如下： E = E*E = E*(E) = E*(E+E) =E*(E+i3) =E*(i2+i3)= i1*(i2+i3) E = E*E = i1*E = i1*(E) =i1*(E+E) =i1*(i2+E)= i1*(i2+i3)注意：從一個句型到另一個句型的推導(dǎo)過程并不唯一，但通常只考慮最左推導(dǎo)和最右推導(dǎo)。最左推導(dǎo)最右推導(dǎo)最左推導(dǎo)是指，任何一步=都是對中的最左非終結(jié)符進(jìn)行替換的最右推導(dǎo)是指，任何一步=都是對中的最右非終結(jié)符進(jìn)行替換的第十八頁，共三十頁。三、語法樹

9、與二義性1、語法樹定義：句型推導(dǎo)的圖形表示，它與替換順序的選取無關(guān)作用：明顯的形成文法所暗含的句子分層語法結(jié)構(gòu)， 為語法分析提供一些新的途徑目的：為了理解句子的語法，得到句子如何從開始符 號推導(dǎo)得到，因此引入“圖”第十九頁，共三十頁。樹的葉：非終結(jié)符|終結(jié)符，對應(yīng)一個句型語法樹為語法分析提供一些新的途徑樹的內(nèi)節(jié)點(diǎn)：非終結(jié)符A標(biāo)記若A -，則該產(chǎn)生式的一棵子樹為AXYZ第二十頁，共三十頁。在語法樹中找出文法中的概念內(nèi)結(jié)點(diǎn)AVN葉文法符號子樹直接推導(dǎo)根結(jié)點(diǎn)S任一次全剪句型葉子VT時(shí)，將葉子順序排列句子第二十一頁，共三十頁。例3 E ( id + id )的語法樹最左推導(dǎo)：E - E - ( E )

10、 - (E+E) -(id+E) (id+id) 最右推導(dǎo)：E - E - ( E ) - (E+E) -(E+id) (id+id) EEidid(E)E+E語 法 樹第二十二頁，共三十頁。由此可見，每一中間過程，句型很容易獲得樹忽略了符號的替換順序的不同，不同推導(dǎo)過程得到相同的語法樹有的語法，對于同一句子、應(yīng)用不同規(guī)則進(jìn)行推導(dǎo)得到不同的語法樹例4 根據(jù)文法G對句子id + id * id進(jìn)行推導(dǎo)第二十三頁，共三十頁。文法GE - E+E|E*E|( E )| i推導(dǎo)1E = E+E = id+E = id+E*E = id+id*E = id+id*id推導(dǎo)2E = E*E = E+E*E

11、 = id+E*E = id+id*E= id+id*id與 兩種推導(dǎo)對應(yīng)兩棵不同的語法樹，如下所示：第二十四頁，共三十頁。推導(dǎo)1的語法樹推導(dǎo)2的語法樹EE*ididEidE+E+ididEEEE*EidE = E+E = id+E = id+E*E = id+id*E = id+id*idE = E*E = E+E*E = id+E*E = id+id*E = id+id*id第二十五頁，共三十頁。2、二義性問題定義：文法G的某一句子有兩棵不同的樹，則G為二義的。二義性對語法分析不便，因此希望：1）判定二義否2）無二義性的充分條件3）如何消除二義性第二十六頁，共三十頁。解決辦法：盡量去掉二義

12、性如對上例，可以通過闡明運(yùn)算符的優(yōu)先性和結(jié)合性來解除文法的二義性通過重寫一個文法，把結(jié)合性和優(yōu)先規(guī)則結(jié)合進(jìn)文法本身中去注意到，L(G)=L(G)，GG第二十七頁，共三十頁。語言的二義性問題與文法的二義性問題如L找到一個文法是無二義的，則L是無二義的；如未找到一個文法是無二義的，則也不能斷定它二義，但先天二義也存在；文法的二義性是不可判定的。 （因?yàn)槲姆ǖ亩x性由句子的語法樹決定，不可能對無窮句子來判別）第二十八頁，共三十頁。最后，作為描述程序語言的上下文無關(guān)文法，我們限制： G不含下面的產(chǎn)生式P-P每一PVN，必須都有用處，即 S P，P在句型中出現(xiàn) VT*, P ，即對P不存在不終結(jié)的回路第二十九頁，共三十頁。內(nèi)容總結(jié)程序語言的語法描述與分析。VN：是非空有限集，它的每個元素是非終結(jié)符號。S：SVN，稱為開始符號。表達(dá)式 -（表達(dá)式）。由此可見，文法G1(E)所定義的語言是上述算術(shù)表達(dá)式，。該語法范疇叫“句子”，在程序語言中叫