第二章-前后文無(wú)關(guān)文法和語(yǔ)言

1、編譯原理前后文無(wú)關(guān)文法和語(yǔ)言,計(jì)算機(jī)與軟件學(xué)院 陸克中 手機(jī)辦公電話:26732030 QQ:8256546 Email: 辦公地點(diǎn):科技樓七樓北側(cè)701,主要內(nèi)容,本章討論與編譯實(shí)現(xiàn)相關(guān)的形式語(yǔ)言理論基本概念，主要內(nèi)容有： 文法及語(yǔ)言的表示 文法和語(yǔ)言的定義 句型的分析 文法的化簡(jiǎn)和改造 文法和語(yǔ)言的Chomsky分類,文法與語(yǔ)言,一個(gè)程序設(shè)計(jì)語(yǔ)言的確切定義是構(gòu)造編譯程序的重要前提 文法被用來(lái)精確而無(wú)歧義地描述語(yǔ)言的構(gòu)成方式 文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義,2.1 文法及語(yǔ)言的表示,1.程序設(shè)計(jì)語(yǔ)言的定義 語(yǔ)言是一個(gè)記號(hào)系統(tǒng) 漢語(yǔ)-符合漢語(yǔ)語(yǔ)法的句子的全體 英語(yǔ)

2、-符合英語(yǔ)語(yǔ)法的句子的全體 程序設(shè)計(jì)語(yǔ)言-該語(yǔ)言的程序的全體 程序設(shè)計(jì)語(yǔ)言由語(yǔ)法和語(yǔ)義定義： 語(yǔ)法：定義每個(gè)程序構(gòu)成的規(guī)則 語(yǔ)義：定義每個(gè)程序的意義,程序設(shè)計(jì)語(yǔ)言包括:語(yǔ)法和語(yǔ)義 語(yǔ)法(syntax) 定義: 是一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序 描述工具:文法 作用: 定義什么樣的符號(hào)序列是合法的，與符號(hào)的含義無(wú)關(guān),語(yǔ)義(semantics) 分類: 靜態(tài)語(yǔ)義：一系列限定規(guī)則，確定哪些合乎語(yǔ)法的程序是合適的 動(dòng)態(tài)語(yǔ)義：表明程序要做什么 描述工具: 指稱語(yǔ)義,操作語(yǔ)義等 作用: 檢查類型匹配，變量作用域等,2.文法的直觀概念,如何來(lái)描述一種語(yǔ)言？文法是描述語(yǔ)言的語(yǔ)法（形式）結(jié)構(gòu)的形式規(guī)

3、則。 如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示 如果語(yǔ)言是無(wú)窮的，要找出語(yǔ)言的有窮表示。 有兩個(gè)途經(jīng)： 生成方式 （文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造 識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去。,形式語(yǔ)言和編譯理論中的 最基本概念 符號(hào)串和符號(hào)串集合,基本定義 它們的運(yùn)算,1.符號(hào)和符號(hào)串,字母表 定義:元素的非空有窮集合 例：=01 =ab,c 元素也稱為符號(hào)，字母表也稱符號(hào)集。 程序語(yǔ)言的字母表由字母數(shù)字和若干專用符號(hào)組成。,符號(hào)串 定義

4、:由字母表中的符號(hào)組成的任何有窮序列 例： 0,00,10是字母表=01上的符號(hào)串 a,ab,aaca是=abc上的符號(hào)串 在符號(hào)串中，符號(hào)是有順序的，順序不同,代表不同的符號(hào)串，如:ab和ba不同 不含任何符號(hào)的符號(hào)串稱為空串，用表示 注意:并不等于空集合 符號(hào)串長(zhǎng)度: 符號(hào)串中含有符號(hào)的個(gè)數(shù) 如: |abc|=3| |=0,子串,設(shè)有非空符號(hào)串u=xvy, 則稱v為符號(hào)串u的子串。,例如 符號(hào)串x=a+b*(c+d),則, a, a+b*, 與(c+d)等都是x的子符號(hào)串，且 其長(zhǎng)度分別為|a|=1, |a+b*|=4, |(c+d)|=5,符號(hào)串的前綴和后綴,如果z=xy是一個(gè)符號(hào)串，則

5、x是z的前綴 ，而y是z的后綴。如果y非空，則x是z的真前綴；如果x非空，則y是z的真后綴。,例如：字母表A=a,b,c上的符號(hào)串x=abc, 則x的 前綴：, a, ab, abc, 后綴:, c, bc, abc 真前綴: , a, ab, 真后綴:, c, bc,符號(hào)串的運(yùn)算 符號(hào)串的連接：設(shè)x、y是符號(hào)串,它們的連接是把y的符號(hào)寫在 x的符號(hào)之后得到的符號(hào)串xy 例如 x=ST，y=abu ，則 xy=STabu 顯然x = x=x 符號(hào)串的方冪：把符號(hào)串a(chǎn)自身連接n次得到的符號(hào)串a(chǎn)n = aaaa 例如 a1=a a2=aa a0=,符號(hào)串集合： 定義: 若集合A中所有元素都是某字母

6、表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。 符號(hào)串集合的乘積：符號(hào)串集合A和B的乘積定義為: AB =xy|xA且yB，即AB是由A中的串x和B中的串y連接而成的串xy組成的集合。 若集合A = ab,cde B = 0,1 則 AB = ab0,ab1,cde0,cde1 顯然 A = A = A,符號(hào)串集合的方冪: 設(shè)A是符號(hào)串的集合，則稱Ai為符號(hào)串集A的方冪，其中i是非負(fù)整數(shù)。具體定義如下: A0 = A1 = A , A2 = A A AK = AA.A(k個(gè)),集合的閉包 閉包 集合的閉包 *定義如下： * = 0 1 2 3 例：設(shè)有字母表=0，1 則*=012 =,0,1,0

7、0,01,10,11,000, 即*表示上所有有窮長(zhǎng)的串的集合。,正閉包 + = 123稱為的正閉包。 + 表示上的除外的所有用窮長(zhǎng)串的集合 * = 0+ + = * = * ,字母表上的一個(gè)語(yǔ)言是上符合某種規(guī)則的一些符號(hào)串的集合 ，是*的一個(gè)子集。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 1. 集合ab,aabb,aaabbb,anbn,或 w|w*且w=anbn,n1為字母表上的一個(gè)語(yǔ)言。 集合a,aa,aaa,或w|w*且w=an,n1為字母表上的一個(gè)語(yǔ)言。 是一個(gè)語(yǔ)言。 即 是一個(gè)語(yǔ)言。,小結(jié),1 符號(hào)與字母表 2 符號(hào)串 3 符號(hào)串的運(yùn)算 4 符號(hào)串集

8、合 5 集合的閉包 6 字母表的閉包,文法和語(yǔ)言的形式定義,1文法的定義 2文法形式上的約定 3推導(dǎo)與歸約 4句型、句子、語(yǔ)言的定義 5文法的等價(jià),“我是大學(xué)生”是漢語(yǔ)的一個(gè)句子,用:=表示的漢語(yǔ)句子的構(gòu)成規(guī)則： 句子=主語(yǔ)謂語(yǔ) 主語(yǔ)=代詞名詞 代詞= 我你他 名詞= 王明大學(xué)生工人英語(yǔ) 謂語(yǔ)=動(dòng)詞直接賓語(yǔ) 動(dòng)詞= 是學(xué)習(xí) 直接賓語(yǔ)=代詞名詞,句子“我是大學(xué)生”的推導(dǎo)過(guò)程如下： 從句子出發(fā)，反復(fù)把規(guī)則中的”:=”左邊的成分替換成右邊的成分。 句子 主語(yǔ)謂語(yǔ) 代詞謂語(yǔ) 我謂語(yǔ) 我動(dòng)詞直接賓語(yǔ) 我是直接賓語(yǔ) 我是名詞 我是大學(xué)生,文法介紹,包括四個(gè)組成部分： 一組終結(jié)符號(hào)（不能被替換的符號(hào)，單詞符

9、號(hào)） 一組非終結(jié)符號(hào)（能夠被替換為終結(jié)符號(hào)或非終結(jié)符號(hào)，語(yǔ)法單位） 一個(gè)開始符號(hào)（從這個(gè)符號(hào)開始替換，最大語(yǔ)法單位-程序） 一組產(chǎn)生式（替換規(guī)則，把左邊的字符串替換為右邊的字符串）,關(guān)鍵思路,從文法的開始符號(hào)出發(fā)， 反復(fù)使用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換（展開）， 直到整個(gè)字符串中不在包含非終結(jié)符。 這時(shí)，得到了這個(gè)文法的一個(gè)句子（一個(gè)程序） 這個(gè)過(guò)程稱為推導(dǎo),1文法的形式定義,產(chǎn)生式（規(guī)則） 產(chǎn)生式是一個(gè)有序?qū)?,)，通常寫作 （或:= ） 文法定義: 文法G(Grammar)定義為四元組（VN，VT，P，S） VN (Nonternimal)：非終結(jié)符集 VT (Terminal)：終結(jié)符集

10、P (Production)：產(chǎn)生式（規(guī)則）集合 S：開始符號(hào)或識(shí)別符號(hào),說(shuō)明: V=VNVT，V稱為文法G的字母表 P中產(chǎn)生式形如：,其中V+且至少含一個(gè)非終結(jié)符，V* VN,VT和P是非空有窮集 VNVT= S是一個(gè)非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn) 非終結(jié)符代表一個(gè)語(yǔ)言中的語(yǔ)法成分，如，它是構(gòu)成程序的一個(gè)語(yǔ)法成分，這個(gè)符號(hào)本身不會(huì)在程序中出現(xiàn)，而終結(jié)符是組成程序的具體的符號(hào)。,2 文法形式定義上的約定,文法習(xí)慣上只將產(chǎn)生式寫出。并有如下約定： 第一條產(chǎn)生式的左部是開始符號(hào),或用GS表示S是開始符號(hào) 用尖括號(hào)括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符

11、 G可寫成GS，S是開始符號(hào) 希臘字母代表由終結(jié)符號(hào)和非終結(jié)符號(hào)組成的符號(hào)串 、 左部相同的產(chǎn)生式A,A可以記為A|， 其中“|”是“或”的意思，,分別稱為侯選式,如：對(duì)于文法 G：S0S1 可寫成 GS：S0S1 S01 S01 例：文法G=(VN,VT,P,S) 其中：VN=S，VT=0，1，P=S0S1,S01 開始符為S,例：文法G=(VN,VT,P,S) VN =標(biāo)識(shí)符，字母，數(shù)字， VT =a,b,c,x,y,z,0,1,9， P=， ， a, , z， 0,9 ， S= 例如: 文法GS： SA|SA|SD Aa|b|z D0|1|9,3. 推導(dǎo)(Derivation)與歸約(R

12、eduction),直接推導(dǎo)和直接歸約： 是文法G的產(chǎn)生式，若有v，w滿足：v=,w=, 其中,V* 則稱v直接推導(dǎo)出w,也稱w直接歸約到v, 記作 v w 直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過(guò)程 直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程,例 文法G： S0S1，S01 有直接推導(dǎo)： S 0S1（ S0S1） 0S1 00S11（ S0S1） 00S11 000S111（ S0S1） 000S111 00001111 （ S01 ）,推導(dǎo)例題1,文法G1：S-bA, A-aA|a定義了一個(gè)什么樣的語(yǔ)言？ S=bA=ba S=bA=baA=baa S=bA=baA=baaA=b

13、aaa S=bA=baA=baa L(G1)=ban|n=1 L(G1) = 以b開頭后跟一個(gè)或多個(gè)a的串,推導(dǎo)例題2,e.g. 文法產(chǎn)生的語(yǔ)言,文法G4對(duì)句子aaabb的推導(dǎo)： S = A B S A B = a A B A a A = a a A B A a A = a a a B A a = a a a b B B b B = a a a b b B b,S = AB = aB = ab S = AB = Ab = ab,e.g. 文法產(chǎn)生的語(yǔ)言,文法G5對(duì)句子aaaabbbb的推導(dǎo)： S = a S b S a S b = a a S b b S a S b = a a a S b b

14、 b S a S b = a a a a b b b b S a b,直接推導(dǎo)序列和廣義推導(dǎo),直接推導(dǎo)序列： 或 + 若存在v =u0 u1 . un=w, (n0) 則稱v + w，v推導(dǎo)出w，或w歸約到v（至少有1步推導(dǎo)），這個(gè)直接推導(dǎo)序列的長(zhǎng)度為n。 廣義推導(dǎo)： 或 * 若有v + w 或 v=w， 則記為v * w，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）,+ ,* ,三種推導(dǎo)的比較,直接推導(dǎo)（）的長(zhǎng)度為1 直接推導(dǎo)序列（+）的長(zhǎng)度n1 廣義推導(dǎo)（*）的長(zhǎng)度0,4句型、句子、語(yǔ)言的定義,句型和句子 設(shè)有文法GS，若符號(hào)串是從開始符推導(dǎo)出來(lái)的,即 S =*，則稱是文法G的句型。

15、若僅由終結(jié)符組成,即 S =*，且VT*，則稱是文法G的句子。 例 文法GS： S0S1， S01 因?yàn)?S 0S1 00S11 000S111 00001111 所以S、0S1、00S11、000S111、00001111都是G的句型，00001111是G的句子,語(yǔ)言的定義 由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01 S0S1 00S11 03S13 0n-1S1n-1 0n1n L(G)=0n1n|n1 文法和語(yǔ)言的關(guān)系： 文法G生成的每個(gè)串都在L(G)中 L(G)中的每個(gè)串確實(shí)能被G生成,根據(jù)

16、文法，可以通過(guò)推導(dǎo)得到該文法相應(yīng)的語(yǔ)言； 例：GE：EE+T|TTTF|F F(E)|a EE+T T+T F+T a+T a+TF a+FF a+aF a+aa 表示一切能用符號(hào)a、+、(、)構(gòu)成的算術(shù)表達(dá)式 有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法 例：若語(yǔ)言由0、1符號(hào)串組成，串中0和1的個(gè)數(shù)相同，構(gòu)造其文法為：A 0B|1CB 1|1A|0BBC 0|0A|1CC,5遞歸規(guī)則,借助于自身來(lái)定義的規(guī)則，稱為遞歸規(guī)則。如 := 遞歸規(guī)則的存在，使得能用有窮個(gè)規(guī)則來(lái)定義無(wú)窮的語(yǔ)言。 如果一個(gè)規(guī)則形如U:=U（或UxUy），則該規(guī)則是遞歸的； 如果規(guī)則形如U:=U （或UUy），則稱左遞歸的；

17、如果規(guī)則形如U:=U （或UxU），則稱右遞歸的。 例：:=, （左遞歸規(guī)則） :=! （右遞歸規(guī)則）,文法的遞歸性,定義：對(duì)于某文法，存在UVN， 如果U + U.， 則稱該文法遞歸于U； 如果U + U，則稱該文法左遞歸于U； 如果U + U，則稱該文法右遞歸于U。 例1：C語(yǔ)言中： + (文法右遞歸于) 例2：UVx VUy|z （都不遞歸） 有 U + Uxy，所以該文法是左遞歸的。 注：描述程序設(shè)計(jì)語(yǔ)言的文法必定都是遞歸的。,6文法的等價(jià),若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。 例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01 所定義的語(yǔ)言都是0n1

18、n 兩文法等價(jià),句型的分析,任務(wù): 句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。 對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，句型分析就是一個(gè)識(shí)別輸入符號(hào)串是否為語(yǔ)法上正確的程序的過(guò)程。 它是一種推導(dǎo)或語(yǔ)法樹的構(gòu)造過(guò)程。對(duì)于一個(gè)給定的符號(hào)串，試圖按照文法的規(guī)則構(gòu)造其對(duì)應(yīng)的推導(dǎo)，或語(yǔ)法樹。,1. 規(guī)范推導(dǎo)與規(guī)范規(guī)約,考慮兩種特殊推導(dǎo)：最右推導(dǎo)和最左推導(dǎo)，即對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)，都是對(duì)最左（最右）非終結(jié)符進(jìn)行替換。 最右推導(dǎo)也稱規(guī)范推導(dǎo)，它的逆過(guò)程稱為最左規(guī)約，也稱規(guī)范規(guī)約。 若用 表示規(guī)約，設(shè)Aa是文法G中的一個(gè)規(guī)則，則對(duì)于 xAy xay 有 xay xAy,. ,. ,舉例,

19、例1: 文法GS: SAB AA0|1B B0|S1 請(qǐng)給出句子101001的最左和最右推導(dǎo)。 最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001,例2 文法G：EE+T|T TTF|F F（E）|i 句子i+ii的推導(dǎo)過(guò)程如下： 最左推導(dǎo)： E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii 最右推導(dǎo)： E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii,句型的分析算法分類 自上而下分

20、析法 (Top-Down parsing) 自下而上分析法 (Bottom-Up parsing),自上而下的分析方法,定義: 從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。,例 文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子,推導(dǎo)過(guò)程：,=cabd,S,=cAd,自上而下方法的主要問題 對(duì)輸入串cabd自上而下構(gòu)造語(yǔ)法樹的另一過(guò)程,不成功，不成功的原因是選錯(cuò)產(chǎn)生式Aa,自上而下分析的主要問題是選擇產(chǎn)生式 : 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個(gè)右部去替代B？,自下而上的分析方法,定義:從

21、輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。,例 文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子,歸約過(guò)程：,用“|-”表示歸約，下劃線部分為被歸約符號(hào),cabd,|-cAd,|-S,自下而上分析的主要問題 對(duì)輸入串cabd的兩種歸約過(guò)程 （1）cabd|-cAd|-S 歸約到開始符 （2）cabd|-cAbd 不能歸約到開始符 在自下而上的分析方法中，每一步都是從當(dāng)前串中選擇一個(gè)子串加以歸約，該子串暫稱“可歸約串”。 如何確定“可歸約串”是自下而上分析的主要問題。,2.語(yǔ)法樹和二義性 作用:直觀地描述上下文無(wú)關(guān)文法的句型推導(dǎo)過(guò)程。給定文法G=(VN,

22、VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹,語(yǔ)法樹的概念,定義：語(yǔ)法樹是這樣的一個(gè)語(yǔ)法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于識(shí)別符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。 引入語(yǔ)法樹的意義：作為識(shí)別句子的輔助工具，語(yǔ)法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。,語(yǔ)法樹的相關(guān)概念,結(jié)點(diǎn)：每個(gè)樹的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。 邊：兩個(gè)結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹：語(yǔ)法樹的某個(gè)結(jié)點(diǎn)和它向下射出的部分

23、 末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)。,語(yǔ)法樹的特征,給定文法G，G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹（推導(dǎo)樹）。這棵樹具有下列特征： 1、根結(jié)點(diǎn)的標(biāo)記是開始符號(hào)S； 2、每個(gè)結(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號(hào)； 3、若一棵子樹的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2AR，那么 A:=A1A2.AR一定是P中的一條規(guī)則； 4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則AVN 5、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)

24、生的句子。,從推導(dǎo)構(gòu)造語(yǔ)法樹,方法：把識(shí)別符號(hào)做為根結(jié)點(diǎn)，對(duì)每一個(gè)直接推導(dǎo)畫一個(gè)分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無(wú)分支可畫結(jié)束。,例如：推導(dǎo) S AB AcBd Accdd abccdd,S,B,B,d,b,a,A,c,d,c,語(yǔ)法樹的構(gòu)造過(guò)程,S AB AcBd Accdd abccdd,S,S,B,A,S,B,B,d,A,c,S,B,B,d,A,c,d,c,S,B,B,d,b,a,A,c,d,c,（1）,（2）,（3）,（5）,（4）,從語(yǔ)法樹構(gòu)造推導(dǎo),方法：從分支建立直接推導(dǎo)，然后從語(yǔ)法樹中剪去之這個(gè)分支，直到無(wú)分支可剪。 語(yǔ)法樹表明了在推導(dǎo)過(guò)程中使用了哪條規(guī)則和使

25、用在哪個(gè)非終結(jié)符號(hào)上，但它并沒有表明使用規(guī)則的順序。 一棵語(yǔ)法樹可能對(duì)應(yīng)不止一種推導(dǎo)。,從語(yǔ)法樹構(gòu)造推導(dǎo)的過(guò)程,例如文法GS： S:=AB A:=aAb|ab B:=cBd|cd 存在下面的推導(dǎo)可能： S AB AcBd (4) (3) Accdd abccdd (2) (1) S AB abB abcBd abccdd （從后往前看）,S,B,B,d,b,a,A,c,d,c,(1),(2),(3),(4),例：文法G：EE+T|TTTF|F F（E）|i 句型T+TF的推導(dǎo)過(guò)程與語(yǔ)法樹,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,從語(yǔ)法樹中看不出句型中的符號(hào)被替代的

26、順序,從左到右讀出葉子結(jié)點(diǎn)得到的符號(hào)串，為文法的句型。也把該語(yǔ)法樹稱為該句型的語(yǔ)法樹。,文法G：EE+E|EE|（E）|i 句子 ii+i 對(duì)應(yīng)的語(yǔ)法樹,兩個(gè)不同的最左推導(dǎo)： 推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i 推導(dǎo)2：E EE iE iE+E ii+E ii+i,文法的二義性(Ambiguity),定義: 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則說(shuō)這個(gè)文法是二義的。二義性文法存在某個(gè)句子,它有兩個(gè)不同的最左（右）推導(dǎo),文法G1： EE+E | EE |（E） | i,文法G2： ET|E+T TF|TF F(E)| i,為什么要避免文法產(chǎn)生二義性？,二義性的文

27、法將給編譯程序的執(zhí)行帶來(lái)問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的理解。語(yǔ)法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語(yǔ)義處理上的不確定性。因此，希望描述語(yǔ)言的文法是無(wú)二義性的。,如何消除文法的二義性？(1),方法一：不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。 如1：對(duì)于文法 GE: E i E E+E E E*E E (E) 規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即*優(yōu)先于+，+、*服從左結(jié)合。 如2：Pascal中二義性的消除是通過(guò)約定，如在符合if 語(yǔ)句中，else子句總是屬于最近的尚無(wú)else子句的那個(gè)if語(yǔ)句。,如何消除文法的二義性？(2),方法二：構(gòu)造一個(gè)等價(jià)的無(wú)二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。 如文法 GE: E i E E+E E E*E E (E) 將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無(wú)二義性的文法 GE: E T|E+T T F|T*F F （E）|i,二義性文法的改造,文法的二義性是不可判定的： 注意：文法的二義性性與語(yǔ)言二義性的