編譯原理-西安交通大學第三章上下文無關文法課件

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

一個上下文無關文法G是一個四元式（VT,VN,S,P），其中:VT：是非空有限集，它的每個元素是終結符號；VN：是非空有限集，它的每個元素是非終結符號； VT∩VN=Φ; VT∪VN=V;P：產(chǎn)生式集合（有限），每個產(chǎn)生式形式是{P->α|P∈VN，α∈(VT∪VN)*，S至少一次為P}；S：S∈VN，稱為開始符號；例1、考慮下面的算術表達式的文法及語言 VT： id+－*/↑() VN： 表達式、運算符 S： 表達式 P： 表達式->表達式運算符表達式 表達式->（表達式） 表達式->－表達式 表達式->id 運算符->+|－|*|/|↑得到文法G1(E):E->EAE|(E)|－E|idA->+|－|*|/|↑該文法的： VN是出現(xiàn)P的左部所有符號集合

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

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

非終結符：是標記某種串的集合的特定符號，與“語法變量”、“語法范疇”是同義詞；如：表達式、運算符都表示一個串的集合該語法范疇叫“句子”，在程序語言中叫“程序”語言的句子是由一串VN定義，到最后才是一串VT

開始符號：一個VN，標記感興趣的語法范疇。其它非終結符用以定義其它的串集，這有助于定義該語言，也有助于為它處理的語言提供一個分層的結構；

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

u0u1…un 則u0

R1

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

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

最左推導是指，任何一步α=>β都是對α中的最左非終結符進行替換的

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

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