編譯原理-西安交通大學(xué)第三章上下文無(wú)關(guān)文法課件

15三月2024編譯原理-西安交通大學(xué)第三章上下文無(wú)關(guān)文法本章內(nèi)容引言 -文法文法與語(yǔ)言 -上下文無(wú)關(guān)文法 -推導(dǎo)與語(yǔ)言語(yǔ)法樹(shù)與二義性第三章上下文無(wú)關(guān)文法(context-freegrammar)文法（grammar)問(wèn)題： 如何描述語(yǔ)言定義： 文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則)目的： 解決語(yǔ)言的有窮說(shuō)明問(wèn)題，包含對(duì)語(yǔ)法的描述，但 卻不表達(dá)任何語(yǔ)義一、引言1、文法的描述應(yīng)達(dá)到要求：2、文法分類(lèi)：分為四類(lèi)（0、1、2、3型文法），對(duì)應(yīng)四類(lèi)語(yǔ)言； 與程序語(yǔ)言語(yǔ)法有關(guān)的是上下文無(wú)關(guān)文法 形式上嚴(yán)格、準(zhǔn)確； 易于理解； 具有較強(qiáng)的描述能力； 有利于句子的分析和翻譯，構(gòu)造語(yǔ)法分析器3、上下文無(wú)關(guān)文法的特點(diǎn)： 它所定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的說(shuō)明上下文無(wú)關(guān)文法只能描述一部分語(yǔ)言，但已足夠描述現(xiàn)今的程序設(shè)計(jì)語(yǔ)言自然語(yǔ)言要用其他的文法來(lái)描述二、文法與語(yǔ)言1、

一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式（VT,VN,S,P），其中:VT：是非空有限集，它的每個(gè)元素是終結(jié)符號(hào)；VN：是非空有限集，它的每個(gè)元素是非終結(jié)符號(hào)； VT∩VN=Φ; VT∪VN=V;P：產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式形式是{P->α|P∈VN，α∈(VT∪VN)*，S至少一次為P}；S：S∈VN，稱(chēng)為開(kāi)始符號(hào)；例1、考慮下面的算術(shù)表達(dá)式的文法及語(yǔ)言 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的左部所有符號(hào)集合

V是P的所有符號(hào) ∴VT=V\VN S是該文法所定義的句子名字∴寫(xiě)出了P，就能找出其它三元素由此可見(jiàn)，文法G1(E)所定義的語(yǔ)言是上述算術(shù)表達(dá)式，如：id+id，id*(id+id)等它表達(dá)了簡(jiǎn)單算術(shù)表達(dá)式由id用A連接起來(lái)2、從此可見(jiàn)

終結(jié)符：是用以組成語(yǔ)言中的串的基本符號(hào)，與程序語(yǔ)言中“單詞”是同義語(yǔ)；如：表達(dá)式id+(id)*(-id)中，+、－、*、/、↑、id均為終結(jié)符

非終結(jié)符：是標(biāo)記某種串的集合的特定符號(hào)，與“語(yǔ)法變量”、“語(yǔ)法范疇”是同義詞；如：表達(dá)式、運(yùn)算符都表示一個(gè)串的集合該語(yǔ)法范疇叫“句子”，在程序語(yǔ)言中叫“程序”語(yǔ)言的句子是由一串VN定義，到最后才是一串VT

開(kāi)始符號(hào)：一個(gè)VN，標(biāo)記感興趣的語(yǔ)法范疇。其它非終結(jié)符用以定義其它的串集，這有助于定義該語(yǔ)言，也有助于為它處理的語(yǔ)言提供一個(gè)分層的結(jié)構(gòu)；

產(chǎn)生式：規(guī)定由終結(jié)符和別的語(yǔ)法范疇組成一個(gè)新的語(yǔ)法范疇的辦法；結(jié)構(gòu)：非終結(jié)符->一串非終結(jié)符和終結(jié)符如：A->α A -> α ↓ ↓ 左部符號(hào)右部候選式 VN α=X1X2…Xn，Xi∈V3、習(xí)慣記號(hào)VN: 大寫(xiě)字母A、B、C、S等VT: 小寫(xiě)字母，0~9，+、－等運(yùn)算符， 標(biāo)點(diǎn)，分界符，黑體字母串id、ifX、Y、Z： 文法符號(hào)，或VN或VT一個(gè)符號(hào)u、v、w…z：VT中串α、β、γ: 文法符號(hào)串∈(VT∪VN)*S: 開(kāi)始符號(hào)，第一個(gè)產(chǎn)生式中出現(xiàn)->: 定義為（元語(yǔ)言符號(hào)）|： 或（元語(yǔ)言符號(hào)）有窮條產(chǎn)生式，產(chǎn)生無(wú)窮集，要求產(chǎn)生式必須遞歸定義算術(shù)表達(dá)式，用了兩條濃縮的產(chǎn)生式，一般定 義一個(gè)語(yǔ)言的產(chǎn)生式是很復(fù)雜的對(duì)遞歸的算術(shù)表達(dá)式的產(chǎn)生式，進(jìn)行反復(fù)推導(dǎo)產(chǎn)生 表達(dá)式語(yǔ)言問(wèn)題：表達(dá)式語(yǔ)言無(wú)窮，如何定義？4、推導(dǎo)與語(yǔ)言問(wèn)題：用文法如何定義一個(gè)語(yǔ)言？思路：從S出發(fā)，反復(fù)使用P，對(duì)非終結(jié)符替換展開(kāi)，最后得到全由終結(jié)符串組成的一個(gè)串涉及到：替換->推導(dǎo)->句型->句子->語(yǔ)言②推導(dǎo)：如兩個(gè)串u0、un，存在一個(gè)串序列

u0u1…un 則u0

R1

un，R1記為或u0un：表示從u0出發(fā)，經(jīng)一步或若干步，可推導(dǎo)出unu0un：表示從u0出發(fā)，經(jīng)0步或若干步，可推導(dǎo)出un①直接推導(dǎo)：是兩個(gè)字符串之間的一種關(guān)系R如：（αAβ）R（αγβ），它表示： 若 A->γ∈P，α、β∈V* 則R就是直接推導(dǎo)，R記為 即：αAβαγβ如令u0為S，即推導(dǎo)要從開(kāi)始符號(hào)開(kāi)始，那么： Sα，α∈V*，稱(chēng)α為G的句型如再要求α∈VT*，則α為G的句子文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，記為L(zhǎng)(G)

L(G)={α|Sα&α∈VT*}③怎樣由推導(dǎo)引出語(yǔ)言？只需在推導(dǎo)中加一些限制即對(duì)： u0un 或 u0un①由文法G定義語(yǔ)言L是依賴(lài)一種運(yùn)算，關(guān)系 V*中有許多的串，僅有那些(S,u)(S,v)存在關(guān)系的u、v才有可能成為語(yǔ)言中的句子。②α、β、γ是句型，表示(S，α)(S，β)，有 的關(guān)系，但它的構(gòu)成不全為VT的字符。③G的句型集，是指存在Sα關(guān)系的所有α，該 集的子集是L(G)④V*句型集L(G)說(shuō)明例2根據(jù)文法G: E->E+E|E*E|(E)|i句子i1*(i2+i3)推導(dǎo)過(guò)程如下：②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)注意：從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程并不唯一，但 通常只考慮最左推導(dǎo)和最右推導(dǎo)。最左推導(dǎo)最右推導(dǎo)

最左推導(dǎo)是指，任何一步α=>β都是對(duì)α中的最左非終結(jié)符進(jìn)行替換的

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

E－Eidid(E)E+E語(yǔ)法樹(shù)由此可見(jiàn)，每一中間過(guò)程，句型很容易獲得樹(shù)忽略了符號(hào)的替換順序的不同，不同推導(dǎo)過(guò)程 得到相同的語(yǔ)法樹(shù)有的語(yǔ)法，對(duì)于同一句子、應(yīng)用不同規(guī)則進(jìn)行推 導(dǎo)得到不同的語(yǔ)法樹(shù)例4根據(jù)文法G對(duì)句子id+id*id進(jìn)行推導(dǎo)①文法G E->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=>id+E*E=>id+id*E=>id+id*id②與③兩種推導(dǎo)對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，如下所示：推導(dǎo)1的語(yǔ)法樹(shù)推導(dǎo)2的語(yǔ)法樹(shù)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*id2、二義性問(wèn)題定義： 文法G的某一句子有兩棵不同的樹(shù)，則G為二義的。二義性對(duì)語(yǔ)法分析不便，因此希望： 1）判定二義否 2）無(wú)二義性的充分條件 3）如何消除二義性解決辦法：盡量去掉二義性 ①如對(duì)