1、第第2 2章章 文法和語言文法和語言 隨著高級語言的出現(xiàn)和使用，必然面臨編譯理論的隨著高級語言的出現(xiàn)和使用，必然面臨編譯理論的研究和編譯程序的設(shè)計(jì)。編譯過程是一個十分復(fù)雜的信研究和編譯程序的設(shè)計(jì)。編譯過程是一個十分復(fù)雜的信息加工過程，其加工對象是用高級語言編寫的程序。息加工過程，其加工對象是用高級語言編寫的程序。1.1.為了順利完成編譯工作，要解決的問題是：為了順利完成編譯工作，要解決的問題是： 如何確切地描述或定義一種程序設(shè)計(jì)語言？如何確切地描述或定義一種程序設(shè)計(jì)語言？ 如何識別和分析這些語言？如何識別和分析這些語言？ 2.2.在在2020世紀(jì)世紀(jì)5050年代，年代，N.choumskyN.

2、choumsky首先對語言的描述進(jìn)行探首先對語言的描述進(jìn)行探討。討。 提出了用來描述語言的數(shù)學(xué)系統(tǒng)；定義了四類性質(zhì)不同提出了用來描述語言的數(shù)學(xué)系統(tǒng)；定義了四類性質(zhì)不同的文法和語言（的文法和語言（0 0型文法、型文法、1 1型文法、型文法、2 2型文法和型文法和3 3型文型文法）。法）。主要內(nèi)容主要內(nèi)容 2.1 2.1 語言和文法的直觀概念語言和文法的直觀概念 2.2 2.2 符號和符號串符號和符號串 2.3 2.3 文法和語言的形式定義文法和語言的形式定義 2.4 2.4 文法的類型文法的類型 2.5 2.5 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹 2.6 2.6 句型的分析句型的分

3、析 2.7 2.7 有關(guān)文法中的一些說明有關(guān)文法中的一些說明2.1 2.1 語言和文法的直觀概念語言和文法的直觀概念程序設(shè)計(jì)語言的定義程序設(shè)計(jì)語言的定義語言是一個記號系統(tǒng)。語言是一個記號系統(tǒng)。漢語漢語-符合漢語語法的句子的全體符合漢語語法的句子的全體英語英語-符合英語語法的句子的全體符合英語語法的句子的全體程序設(shè)計(jì)語言程序設(shè)計(jì)語言-該語言的程序的全體該語言的程序的全體 程序設(shè)計(jì)語言由語法和語義定義：程序設(shè)計(jì)語言由語法和語義定義：q語法語法(syntax)定義定義: 是一組規(guī)則，用它可以形成和產(chǎn)生是一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序一個合適的程序描述工具描述工具:文法文法作用作用: 定義

4、什么樣的符號序列是合法的，定義什么樣的符號序列是合法的，與符號的含義無關(guān)。與符號的含義無關(guān)。q語義語義(semantics)分類分類: 靜態(tài)語義：一系列限定規(guī)則，確定靜態(tài)語義：一系列限定規(guī)則，確定哪些合乎語法的程序是合適的哪些合乎語法的程序是合適的 動態(tài)語義：表明程序要做什么動態(tài)語義：表明程序要做什么描述工具描述工具: 指稱語義指稱語義,操作語義等操作語義等作用作用: 檢查類型匹配，變量作用域等檢查類型匹配，變量作用域等文法的直觀概念 如何來描述一種語言？如何來描述一種語言？文法是描述語言的語法（形式）文法是描述語言的語法（形式）結(jié)構(gòu)的形式規(guī)則。結(jié)構(gòu)的形式規(guī)則。如果語言是有窮的（只含有有窮多個

5、句子），可以將如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示句子逐一列出來表示如果語言是無窮的，要找出語言的有窮表示。如果語言是無窮的，要找出語言的有窮表示。 有兩個途經(jīng)：有兩個途經(jīng)：生成方式生成方式 （文法）：語言中的每個句子可以用嚴(yán)格定（文法）：語言中的每個句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造義的規(guī)則來構(gòu)造識別方式（自動機(jī)）：用一個過程，當(dāng)輸入的一任意識別方式（自動機(jī)）：用一個過程，當(dāng)輸入的一任意串屬于語言時，該過程經(jīng)有限次計(jì)算后就會停止并回串屬于語言時，該過程經(jīng)有限次計(jì)算后就會停止并回答答“是是”，若不屬于，要么能停止并回答，若不屬于，要么能停止并回答“不是不是”，要么永遠(yuǎn)繼

6、續(xù)下去。要么永遠(yuǎn)繼續(xù)下去。2.2 2.2 符號和符號串符號和符號串字母表字母表定義定義: :元素的非空有窮集合元素的非空有窮集合例：例：=01 =ab,c元素也稱為符號，字母表也稱符號集。元素也稱為符號，字母表也稱符號集。程序語言的字母表由字母數(shù)字和若干專用程序語言的字母表由字母數(shù)字和若干專用符號組成。符號組成。符號串符號串定義定義: :由字母表中的符號組成的任何有窮序列由字母表中的符號組成的任何有窮序列例：例： 0,00,10是是字母表字母表=0，1上的符號串上的符號串 a,ab,aaca是是=a，b，c上的符號串上的符號串在符號串中，符號是有順序的，順序不同在符號串中，符號是有順序的，順序

7、不同,代代表不同的符號串，如表不同的符號串，如:ab和和ba不同不同不含任何符號的符號串稱為空串，用不含任何符號的符號串稱為空串，用表示表示注意注意: :并不等于空集合并不等于空集合 符號串長度符號串長度: 符號串中含有符號的個數(shù)符號串中含有符號的個數(shù)如如: |abc|=3| |=0 子符號串子符號串v設(shè)有非空符號串設(shè)有非空符號串u=xvy，其中符號其中符號 串串 則稱則稱v為符號串為符號串u的的子符子符號串號串。Vv例如例如 符號串符號串x=a+b*(c+d)，則則a，a+b*， 與與(c+d)等都是等都是x的子符號串，的子符號串，且其長度分別且其長度分別|a|=1， |a+b*|=4， |

8、(c+d)|=5符號串的頭與尾符號串的頭與尾v如果如果z=xy是一個符是一個符號串，則號串，則x是是z的的頭頭，而而y是是z的的尾尾。如果。如果y非空，則非空，則x是是z的的固固有頭有頭；如果；如果x非空，非空，則則y是是z的的固有尾固有尾。v例如：字母表例如：字母表A=a,b,c上的符號串上的符號串x=abc, 則則x的的 頭：頭：, a, ab, abc, 尾尾:, c, bc, abc 固有頭固有頭: , a, ab, 固有尾固有尾:, c, bc符號串的運(yùn)算符號串的運(yùn)算符號串的連接符號串的連接：設(shè)設(shè)x、y是符號串是符號串,它們它們的連接是把的連接是把y的符號寫在的符號寫在 x的符號之后

9、的符號之后得到的符號串得到的符號串xy例如例如 x=ST，y=abu ，則，則 xy=STabu 顯然顯然x = x=x符號串的方冪符號串的方冪：把：把符號串符號串a(chǎn) a自身連接自身連接n n次次得到的符號串得到的符號串a(chǎn) an n = = aaaaaaaa例如例如 a a1 1=a a=a a2 2=aa a=aa a0 0=符號串集合：符號串集合：定義定義: : 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符號串，則稱的符號串，則稱A A為字母表為字母表 上的符號串集合。上的符號串集合。符號串集合的乘積：符號串集合符號串集合的乘積：符號串集合A和和B的乘積的乘積定

10、義為定義為:AB = xy|xA且且yB ，即，即AB是由是由A中的串中的串x和和B中的串中的串y連接而成的串連接而成的串xy組成的集合。組成的集合。若集合若集合A = ab,cdeab,cde B = 0,10,1 則則 AB = ab0,ab1,cde0,cde1ab0,ab1,cde0,cde1 顯然顯然 A = A = A符號串集合的方冪符號串集合的方冪: : 設(shè)設(shè)A A是符號串的集合，則稱是符號串的集合，則稱A Ai i為符號串集為符號串集A A的方冪，其中的方冪，其中i i是非負(fù)整數(shù)。具體是非負(fù)整數(shù)。具體定義如下定義如下: :vA A0 0 = = vA A1 1 = A , A=

11、 A , A2 2 = A A= A AvA AK K = AA.A(k = AA.A(k個個) )集合的閉包集合的閉包閉包閉包集合集合的閉包的閉包 *定義如下：定義如下： * = 0 1 2 3例：設(shè)有字母表例：設(shè)有字母表=0，1則則*=012=,0,1,00,01,10,11,000,即即*表示表示上所有有窮長的串的集合。上所有有窮長的串的集合。正閉包正閉包+ = 123稱為稱為的正閉包。的正閉包。 + 表示表示 上的上的除除外外的所有用窮長串的集合的所有用窮長串的集合* = 0+ = * = * 字母表字母表 上上的一個語言是的一個語言是 上符合某種規(guī)則的一些符號上符合某種規(guī)則的一些符號

12、串的集合串的集合 ，是是 *的一個子集。的一個子集。例如：例如：=a,b =a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,1. 集合集合 ab,aabb,aaabbb,aab,aabb,aaabbb,an nb bn n,或或 w|ww|w* *且且w=aw=an nb bn n,n1,n1為為字母表字母表 上上的一個語言。的一個語言。 集合集合 a,aa,aaa,a,aa,aaa,或或 w|ww|w* *且且w=aw=an n,n1,n1為為字母字母表表 上上的一個語言。的一個語言。 是一個語言。是一個語言。小結(jié)1 符號

13、與字母表符號與字母表2 符號串符號串3 符號串的運(yùn)算符號串的運(yùn)算4 符號串集合符號串集合5 集合的閉包集合的閉包6 字母表的閉包字母表的閉包2.3 文法和語言的形式定義1文法的定義2文法形式上的約定3推導(dǎo)與歸約4句型、句子、語言的定義5文法的等價1文法的定義“我是大學(xué)生”是漢語的一個句子用:=表示的漢語句子的構(gòu)成規(guī)則：句子=主語謂語主語=代詞名詞代詞= 我你他名詞= 王明大學(xué)生工人英語謂語=動詞直接賓語動詞= 是學(xué)習(xí)直接賓語=代詞名詞句子句子“我是大學(xué)生我是大學(xué)生”的推導(dǎo)過程如下：的推導(dǎo)過程如下：從句子出發(fā)，反復(fù)把規(guī)則中的從句子出發(fā)，反復(fù)把規(guī)則中的”:=”:=”左邊的左邊的成分替換成右邊的成分

14、。成分替換成右邊的成分。句子句子 主語主語謂語謂語 代詞代詞謂語謂語 我我謂語謂語 我我動詞動詞直接賓語直接賓語 我我是是直接賓語直接賓語 我是我是名詞名詞 我是我是大學(xué)生大學(xué)生關(guān)鍵思路v從文法的開始符號出發(fā)，v反復(fù)使用產(chǎn)生式，對非終結(jié)符進(jìn)行替換（展開），v直到整個字符串中不在包含非終結(jié)符。v這時，得到了這個文法的一個句子句子（一個程序）v這個過程稱為推導(dǎo)推導(dǎo)文法的定義v包括四個組成部分：一組終結(jié)符號終結(jié)符號（不能被替換的符號，單詞符號）一組非終結(jié)符號非終結(jié)符號（能夠被替換為終結(jié)符號或非終結(jié)符號，語法單位）一個開始符號開始符號（從這個符號開始替換，最大語法單位-程序）一組產(chǎn)生式產(chǎn)生式（替換規(guī)則

15、，把左邊的字符串替換為右邊的字符串）文法的形式定義q產(chǎn)生式（規(guī)則）產(chǎn)生式是一個有序?qū)?,)，通常寫作 （或:= ）q文法定義:文法G(Grammar)定義為四元組（VN，VT，P，S）VN (Nonternimal)：非終結(jié)符集VT (Terminal)：終結(jié)符集P (Production)：產(chǎn)生式（規(guī)則）集合S：開始符號或識別符號q說明:V=VNVT，V稱為文法G的字母表P中產(chǎn)生式形如：,其中V+且至少含一個非終結(jié)符，V*VN,VT和P是非空有窮集VNVT=S是一個非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn)非終結(jié)符代表一個語言中的語法成分，如，它是構(gòu)成程序的一個語法成分，這個符號本身不會在程序

16、中出現(xiàn)，而終結(jié)符是組成程序的具體的符號。2. 文法形式定義上的約定文法形式定義上的約定v文法習(xí)慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式的左部是開始符號,或用GS表示S是開始符號用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符G可寫成GS，S是開始符號希臘字母代表由終結(jié)符號和非終結(jié)符號組成的符號串v 、左部相同的產(chǎn)生式A,A可以記為A|，其中“|”是“或”的意思，,分別稱為侯選式v如：對于文法 G：S0S1 可寫成 GS：S0S1 S01 S01例：文法G=(VN,VT,P,S)其中：VN=S，VT=0，1，P=S0S1,S01開始符為S例：文法G=(V

17、N,VT,P,S)VN =標(biāo)識符，字母，數(shù)字，VT =a,b,c,x,y,z,0,1,9，P=， ， a, , z，0,9 ，S=q例如:文法GS： SA|SA|SDAa|b|zD0|1|93. 推導(dǎo)(Derivation)與歸約(Reduction)q直接推導(dǎo)和直接歸約： 是文法G的產(chǎn)生式，若有v，w滿足：v=,w=, 其中,V* 則稱v直接推導(dǎo)出w,也稱w直接歸約到v,記作 v w直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程例 文法G： S0S1，S01 有直接推導(dǎo)： S 0S1（ S0S1 ）0S1 00S11（ S0S1 ） 00S1

18、1 000S111（ S0S1 ） 000S111 00001111（ S01 ） 推導(dǎo)例題1v文法G1：S-bA, A-aA|a定義了一個什么樣的語言？vS=bA=bavS=bA=baA=baavS=bA=baA=baaA=baaavvS=bA=baA=baavL(G1)=ban|n=1 vL(G1) = 以b開頭后跟一個或多個a的串推導(dǎo)例題2e.g. 文法產(chǎn)生的語言文法G4對句子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 bA= aB =

19、 abA= Ab = abe.g. 文法產(chǎn)生的語言文法G5對句子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 b S a S b = a a a a b b b b S a b直接推導(dǎo)序列和廣義推導(dǎo)v直接推導(dǎo)序列： 或 + 若存在v =u0 u1 . un=w, (n0) 則稱v + w，v推導(dǎo)出w，或w歸約到v（至少有1步推導(dǎo)），這個直接推導(dǎo)序列的長度為n。v廣義推導(dǎo)： 或 * 若有v + w 或 v=w， 則記為v * w，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）+*三種推導(dǎo)的比較v直接推導(dǎo)（直接推

20、導(dǎo)（）的長度為）的長度為1v直接推導(dǎo)序列（直接推導(dǎo)序列（ +）的長度）的長度n1v廣義推導(dǎo)（廣義推導(dǎo)（ *）的長度）的長度0規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約v對于一文法而言，從開始符到某句型的對于一文法而言，從開始符到某句型的推導(dǎo)過程可能不唯一推導(dǎo)過程可能不唯一。例如，文法例如，文法GE中從中從 E 到到 i+i*i 的推導(dǎo)有：的推導(dǎo)有：(1)E E+T E+T*F T+T*F T+T*i F+T*i i+T*i i+F*ii+i*i(2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*F i+i*i(3)E E+T E+T*F E+T*i E+F*i E+

21、i*i T+i*i F+i*i i+i*i(4) 規(guī)范推導(dǎo)v為了讓計(jì)算機(jī)自動地進(jìn)行推導(dǎo)，通常我們只考慮最左或最右為了讓計(jì)算機(jī)自動地進(jìn)行推導(dǎo)，通常我們只考慮最左或最右推導(dǎo)。推導(dǎo)。v最左（右）推導(dǎo)最左（右）推導(dǎo)：在推導(dǎo)序列的每一步直接推導(dǎo)中，被替換在推導(dǎo)序列的每一步直接推導(dǎo)中，被替換的總是當(dāng)前句型中最左（右）的非終結(jié)符。的總是當(dāng)前句型中最左（右）的非終結(jié)符。v例如，上頁中的（例如，上頁中的（2）、（）、（3）分別是最左、最右推導(dǎo)。）分別是最左、最右推導(dǎo)。v形式上，形式上，從符號串從符號串 到符號串到符號串 的推導(dǎo)序列的推導(dǎo)序列 * xUy xuy * 總有總有 x VT* (y VT*) 時，稱為

22、時，稱為最左（右）推導(dǎo)最左（右）推導(dǎo)v定義：最左（右）推導(dǎo)所得句型稱為定義：最左（右）推導(dǎo)所得句型稱為左（右）句型；左（右）句型；最右推最右推導(dǎo)導(dǎo)稱為稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)；右句型右句型稱為稱為規(guī)范句型規(guī)范句型。 舉例v例例1: 文法文法GS: SAB AA0|1B B0|S1 請給出句子請給出句子101001的最左和最右推導(dǎo)。的最左和最右推導(dǎo)。 最左推導(dǎo)：最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推導(dǎo)：最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001q例2 文法G：EE+T|T T

23、TF|F F（E）|i句子i+ii的推導(dǎo)過程如下：最左推導(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遞歸規(guī)則v借助于自身來定義的規(guī)則，稱為遞歸規(guī)則。如 := 遞歸規(guī)則的存在，使得能用有窮個規(guī)則來定義無窮的語言。v如果一個規(guī)則形如U:=U（或UxUy），則該規(guī)則是遞歸的； 如果規(guī)則形如U:=U （或UUy），則稱左遞歸的； 如果規(guī)則形如U:=U （或UxU），則稱右遞歸的。v例：:=, （左遞歸規(guī)則） :=! （右遞歸規(guī)則）文法的遞歸性v定義：對于某文法，存在UVN，

24、 如果U + U.， 則稱該文法遞歸于U； 如果U + U，則稱該文法左遞歸于U； 如果U + U，則稱該文法右遞歸于U。v例1：C語言中： + (文法右遞歸于)v例2： UVx VUy|z （都不遞歸） 有 U + Uxy，所以該文法是左遞歸的。v注：描述程序設(shè)計(jì)語言的文法必定都是遞歸的。遞歸文法遞歸文法文法文法GE：顯然，顯然，G1，G2都是遞歸定義的。都是遞歸定義的。所謂所謂遞歸定義遞歸定義，指在定義一個，指在定義一個語法成分時，直接或間接地使用了語法成分自身語法成分時，直接或間接地使用了語法成分自身。例如，文法例如，文法G1G1，含有遞歸非終結(jié)符，含有遞歸非終結(jié)符 ，文法，文法G2 G

25、2 中的中的E E、T T是直接遞歸的，是直接遞歸的，F(xiàn) F是間接遞歸的：是間接遞歸的：F F(E)(E)(T)(T)( (F F) )注意注意，文法與語言之間無一一對應(yīng)的關(guān)系。一文法可文法與語言之間無一一對應(yīng)的關(guān)系。一文法可唯一地確定一語言，但對一語言而言，產(chǎn)生它的文唯一地確定一語言，但對一語言而言，產(chǎn)生它的文法不止一個。法不止一個。4句型、句子、語言的定義q句型和句子設(shè)有文法GS，若符號串是從開始符推導(dǎo)出來的,即 S =* ，則稱是文法G的句型。若僅由終結(jié)符組成,即 S =* ，且VT*，則稱是文法G的句子。例 文法GS： S0S1， S01因?yàn)镾 0S1 00S11 000S111 00

26、001111所以S,0S1 ,00S11 ,000S111,00001111都是G的句型00001111是G的句子由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型q語言的定義由文法G生成的語言記為L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1q文法和語言的關(guān)系：文法G生成的每個串都在L(G)中L(G)中的每個串確實(shí)能被G生成根據(jù)文法，可以通過推導(dǎo)得到該文法相應(yīng)的語言；例：GE：EE+T|TTTF|F F(E)|aE E+T T+T F+T a+T a+TF

27、 a+FF a+aF a+aa表示一切能用符號a，+，(，)構(gòu)成的算術(shù)表達(dá)式有了語言的要求，也可以為該語言設(shè)計(jì)文法例：若語言由0、1符號串組成，串中0和1的個數(shù)相同，構(gòu)造其文法為：A 0B|1CB 1|1A|0BBC 0|0A|1CC5.文法的等價若L(G1)=L(G2)，則稱文法G1和G2是等價的。例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01所定義的語言都是0n1n兩文法等價2.4 文法的類型Chomsky對文法中的規(guī)則施加不同限制，將文法和語言分為四大類：v0型文法（PSG） 0型語言或短語結(jié)構(gòu)語言v1型文法（CSG） 1型語言或上下文有關(guān)語言v2型文法（CFG） 2

28、型語言或上下文無關(guān)語言v3型文法（RG）3型語言或正則（正規(guī)）語言v文法的四元組表示是由文法的四元組表示是由N.ChomskyN.Chomsky于于19561956年描述形式語言時給出年描述形式語言時給出的。他還對產(chǎn)生式的形式給予不同的限制而定義了的。他還對產(chǎn)生式的形式給予不同的限制而定義了四類基本文法四類基本文法。v0 0型文法型文法: :若若P P中任一產(chǎn)生式都有一般形式中任一產(chǎn)生式都有一般形式 V+ V+ V V* * 且對且對 ， 不加任何限制，則稱不加任何限制，則稱GG為為0 0型文法型文法（短語結(jié)構(gòu)文法，記為短語結(jié)構(gòu)文法，記為PSG: PSG: Phrase Structure G

29、rammarPhrase Structure Grammar) )。由。由0 0型文法生成（或者說：定義）型文法生成（或者說：定義）的語言稱為的語言稱為0 0型型（遞歸可枚舉遞歸可枚舉）語言語言。它可由。它可由圖靈圖靈（TuringTuring）機(jī)機(jī)識識別。別。v例如：例如：S SACaB CaACaB CaaaC CBaaC CBDB CBDB CBE aDE aDDa Da ADADAC aEAC aEEa AEEa AE 就是一個就是一個0 0型文法型文法，它所產(chǎn)生的語言為，它所產(chǎn)生的語言為,|20aaaaaaaaaaaaaaIiaLi對于程序設(shè)計(jì)語言來，對于程序設(shè)計(jì)語言來，0 0型文法

30、型文法有很大的隨意性有很大的隨意性，還須加以限制，還須加以限制1 1型文法和語言型文法和語言v若一若一0型文法所有產(chǎn)生式具有形式型文法所有產(chǎn)生式具有形式 1A 2 1 2 其中，其中， 1, 2 V* V+ A VN,則稱則稱G 為為1型型(前后文前后文有關(guān)有關(guān))文法文法，記為，記為CSG ( Context Sensitive Grammar) 。v1型文法型文法產(chǎn)生的語言稱為產(chǎn)生的語言稱為前后文有關(guān)前后文有關(guān)語言語言CSL，它可由，它可由線性限界自動機(jī)線性限界自動機(jī)識別。識別。v命名的由來命名的由來：只有當(dāng)非終結(jié)符：只有當(dāng)非終結(jié)符A的的前后分別為前后分別為 1, 2 時，才能將時，才能將A

31、替換替換為為 。v1 型文法還有另一種定義形式：型文法還有另一種定義形式： G的每個產(chǎn)生式形為的每個產(chǎn)生式形為且滿足且滿足： | | | | , V+ 則則G是是1型文型文法法v上述兩種定義形式是等價的。上述兩種定義形式是等價的。即任一即任一種形式定義的文法所產(chǎn)生的語言都可種形式定義的文法所產(chǎn)生的語言都可由另一種形式定義的文法產(chǎn)生由另一種形式定義的文法產(chǎn)生v注注：根據(jù)定義，含有根據(jù)定義，含有 產(chǎn)生式的文法產(chǎn)生式的文法不是不是1型文法。由于實(shí)際需要，我們型文法。由于實(shí)際需要，我們將將 -產(chǎn)生式作為產(chǎn)生式作為1型文法的特例而接型文法的特例而接受之。受之。v例例 文法文法G：S | A AaABC

32、AabC CBBC bBbb bCbc cCccv因因G含有含有 -產(chǎn)生式產(chǎn)生式，所以它不是一個，所以它不是一個嚴(yán)格意義下的嚴(yán)格意義下的1型文法。它所產(chǎn)生的型文法。它所產(chǎn)生的語言為語言為0|)(icbaGLiii2 2型文法和語言型文法和語言v若一若一1型文法型文法G中所有產(chǎn)生式具有形式中所有產(chǎn)生式具有形式: A V+ A VN 則稱則稱G為為2型型 (前后文無關(guān)前后文無關(guān))文法文法，記為，記為CFG(Context Free Grammar)。v2型文法產(chǎn)生的語言稱為型文法產(chǎn)生的語言稱為前后文無關(guān)語言前后文無關(guān)語言CFL，它可由，它可由下下推自動機(jī)推自動機(jī)識別。識別。v若允許若允許 -產(chǎn)生式

33、存在，則產(chǎn)生式存在，則CFG產(chǎn)生式形式為產(chǎn)生式形式為 A V* A VN v例例：GS=(S,a,b,SaSb Sab,S) 產(chǎn)生的語言為產(chǎn)生的語言為1|)(ibaGLii3 3型文法和語言型文法和語言v若一若一2型文法型文法G中僅含有形如中僅含有形如AaB Aa 的產(chǎn)生式，其的產(chǎn)生式，其中中 A,B VN , a VT 則稱則稱G為為右線性文法右線性文法。v類似地，若類似地，若G中僅含有形如中僅含有形如 ABa Aa的產(chǎn)生式，則稱的產(chǎn)生式，則稱G為為左線性文法左線性文法。v通常，把通常，把左線性文法左線性文法和和右線性文法右線性文法都稱為都稱為3型文法型文法（正規(guī)文正規(guī)文法法）v3型文法型文

34、法產(chǎn)生的語言稱為產(chǎn)生的語言稱為3型（型（正規(guī)正規(guī)）語言）語言，它可由，它可由有限自動有限自動機(jī)機(jī)識別。識別。正規(guī)語言正規(guī)語言可用可用正規(guī)表達(dá)式正規(guī)表達(dá)式表示。表示。v注：注：若一文法即含若一文法即含左線性左線性又含又含右線性產(chǎn)生式右線性產(chǎn)生式，則它，則它不一定是不一定是3型文法型文法！v3型文法型文法還可拓廣定義為還可拓廣定義為 AB A （ VT +）由各類文法的定義可知，由各類文法的定義可知，3 3型語言一定是型語言一定是2 2型語言，而反型語言，而反之不一定成立；同理，之不一定成立；同理，2 2型語言是型語言是1 1型的也是型的也是0 0型的，反型的，反之不真。之不真。若把各類語言視為語

35、言族若把各類語言視為語言族L LK K ，K=0,1,2,3 K=0,1,2,3 則它們之間有則它們之間有真包含關(guān)系：真包含關(guān)系：0123LLLL文法類型文法名稱語言名稱自動機(jī)名稱0短語結(jié)構(gòu)遞歸可枚舉圖靈機(jī)1前后文有關(guān)前后文有關(guān)線性限界2前后文無關(guān)前后文無關(guān)下推自動機(jī)3正規(guī)有限狀態(tài)有限自動機(jī)四種文法之間的逐級四種文法之間的逐級“包含包含”關(guān)系關(guān)系2型文法型文法1型文法型文法3型文法型文法0型文法型文法2.5 上下文無關(guān)文法及其語法樹1上下文無關(guān)文法(Context-Free Grammar)自然語言是上下文有關(guān)的。 上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)例：算術(shù)表達(dá)式：Ei|

36、E+E|E*E|（E）i:=Eif then | if then else 我們更關(guān)心上下文無關(guān)文法產(chǎn)生的句子的分析2.語法樹(推導(dǎo)樹Parse Tree)作用:直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹語法樹的概念v定義：語法樹是這樣的一個語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號組成。根結(jié)點(diǎn)對應(yīng)于識別符號。只有非終結(jié)符號對應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對應(yīng)于文法中的一個規(guī)則的左部和右部。v引入語法樹的意義：作為識別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對于其后的語義分析有非常重要的意義。語法樹的相關(guān)概念v結(jié)

37、點(diǎn)：每個樹的結(jié)點(diǎn)對應(yīng)于一個符號。結(jié)點(diǎn)的名字就是該符號。v邊：兩個結(jié)點(diǎn)之間的連線。v根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。v分支：某個結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）v子樹：語法樹的某個結(jié)點(diǎn)和它向下射出的部分v末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號。語法樹的特征v給定文法G，G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點(diǎn)的標(biāo)記是開始符號S；2、每個結(jié)點(diǎn)的標(biāo)記都是V中的一個符號；3、若一棵子樹的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2AR，那么

38、A:=A1A2.AR一定是P中的一條規(guī)則；4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個除它以外的子孫，則AVN5、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。從推導(dǎo)構(gòu)造語法樹v方法：把識別符號做為根結(jié)點(diǎn)，對每一個直接推導(dǎo)畫一個分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號，直到再無分支可畫結(jié)束。v例如：推導(dǎo)S AB AcBd Accdd abccddSBBdbaAcdc語法樹的構(gòu)造過程S AB AcBd Accdd abccddSSBASBBdAc（1）（2）（3）SBBdAcdcSBBdbaAcdc（5）（4）q例：文法G：EE+T|

39、TTTF|F F（E）|i句型T+TF的推導(dǎo)過程與語法樹TFTE=E+TEET+EET+TFTE=E+T=E+TF=T+TF=T+T=T+TF從語法樹中看不出句型中的符號被替代的順序從語法樹中看不出句型中的符號被替代的順序從左到右讀出葉子從左到右讀出葉子結(jié)點(diǎn)得到的符號結(jié)點(diǎn)得到的符號串串，為文法的句型。也為文法的句型。也把該語法樹稱為該把該語法樹稱為該句型的語法樹。句型的語法樹。從語法樹構(gòu)造推導(dǎo)v方法：從分支建立直接推導(dǎo)，然后從語法樹中剪去之這個分支，直到無分支可剪。v語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個非終結(jié)符號上，但它并沒有表明使用規(guī)則的順序。v一棵語法樹可能對應(yīng)不止一種推導(dǎo)。

40、從語法樹構(gòu)造推導(dǎo)的過程v例如文法GS： S:=AB A:=aAb|ab B:=cBd|cd 存在下面的推導(dǎo)可能：vS AB AcBd (4) (3) Accdd abccdd (2) (1)vS AB abB abcBd abccdd（從后往前看）SBBdbaAcdc(1)(2)(3)(4)文法G：EE+E|EE|（E）|i句子 ii+i兩個不同的最左推導(dǎo)：兩個不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i推導(dǎo)推導(dǎo)2：E EE iE iE+E ii+E ii+i3.文法的二義性文法的二義性(Ambiguity)文法的二義性v存在這樣的文法存在這樣的文法G，其某個

41、句子，其某個句子w L(G),可對應(yīng)結(jié)構(gòu)不同可對應(yīng)結(jié)構(gòu)不同的語法樹，即的語法樹，即w對應(yīng)了多個不同的最左（右）推導(dǎo)，這類對應(yīng)了多個不同的最左（右）推導(dǎo)，這類文法稱為文法稱為。v例如，例如，G3E：EE+E|E*E|(E)|i 的句型的句型及文法及文法vCif B then C|if B then C else CC S的句型：的句型：if B1 then if B2 then S1 else S2v上面兩個句型均有兩個不同的語法推導(dǎo)樹（見下頁），所上面兩個句型均有兩個不同的語法推導(dǎo)樹（見下頁），所以，它們是二義性文法以，它們是二義性文法EEEEE+*iiiEEEEE+*iii S1 S2if

42、B1 then C else Cif B2 then CCCif B1 then CS1 S2if B1 then C else C關(guān)于二義性文法v應(yīng)指出應(yīng)指出，二義性，二義性是一種常見的語法現(xiàn)象，然而，對于編譯程是一種常見的語法現(xiàn)象，然而，對于編譯程序而言，序而言，二義性文法二義性文法是是有害有害的。的。v為解決二義性文法帶來的不確定性問題，通常的方法一是為解決二義性文法帶來的不確定性問題，通常的方法一是修修改文法改文法。v二是二是利用附加條件利用附加條件。例如，例如， i+ii+i* *i i的歸約過程中，若規(guī)定的歸約過程中，若規(guī)定* *比比+ +優(yōu)先級高，則可強(qiáng)制性地讓系統(tǒng)先按優(yōu)先級高，

43、則可強(qiáng)制性地讓系統(tǒng)先按E E* *E E進(jìn)行歸約，而不進(jìn)行歸約，而不是先按是先按E+EE+E進(jìn)行歸約；進(jìn)行歸約；又比如，若又比如，若強(qiáng)制規(guī)定強(qiáng)制規(guī)定elseelse只能和距其只能和距其最近的尚未被匹配的最近的尚未被匹配的thenthen進(jìn)行匹配，就可解決進(jìn)行匹配，就可解決elseelse懸空的問懸空的問題。題。關(guān)于二義性文法關(guān)于二義性文法v應(yīng)指出，任一應(yīng)指出，任一前后文無關(guān)文法前后文無關(guān)文法是否是是否是二義性的是不可判定的二義性的是不可判定的。v對于某個對于某個具體的文法具體的文法而言，其而言，其二義性還是可判定的二義性還是可判定的。v存在一些判定文法是否二義性的充分條件：存在一些判定文法是否

44、二義性的充分條件：v若一文法含有若一文法含有既是左遞歸又是右遞歸既是左遞歸又是右遞歸的文法符號，即有的文法符號，即有A+ AvA v V*或或A+ A或或A+ A 及及 AA則則G必定是二義性的必定是二義性的。v并非所有的文法可消除二義性并非所有的文法可消除二義性。即存在這樣的。即存在這樣的CFL，定義它的一切文法，定義它的一切文法都是二義性的。這樣的語言稱為都是二義性的。這樣的語言稱為先天二義性語言先天二義性語言。例如，。例如，1,|1,|mndcbamndcbaLnmmnmmnn為一先天二義性語言。為一先天二義性語言。CFLCFL的先天二義性也是不可判定的的先天二義性也是不可判定的。為什么

45、要避免文法產(chǎn)生二義性？v二義性的文法將給編譯程序的執(zhí)行帶來問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。如何消除文法的二義性？v方法二：構(gòu)造一個等價的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。v如文法 GE: E i E E+E E E*E E (E) 將運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無二義性的文法 GE: E T|E+T T F|T*F F （E）|i二義性文法的改造v注意：文法的二義性性與語言二義性的區(qū)別 因

46、為可能有兩個不同的文法G1和G2，其中有一個是二義性的，但卻有L(G1)=L(G2)。如果產(chǎn)生某上下文無關(guān)語言的每個文法都是二義性的，則說明該語言是先天二義性的，即該語言是二義性的。2.6 句型的分析q任務(wù): 句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。q對于程序設(shè)計(jì)語言來說，句型分析就是一個識別輸入符號串是否為語法上正確的程序的過程。q它是一種推導(dǎo)或語法樹的構(gòu)造過程。對于一個給定的符號串，試圖按照文法的規(guī)則構(gòu)造其對應(yīng)的推導(dǎo)，或語法樹。q句型的分析算法分類自頂向下的語法分析 (Top-Down parsing)自底向上的語法分析自底向上的語法分析(Bottom-Up p

47、arsing)2.6.1 自頂向下的分析方法q定義:對于給定的符號串對于給定的符號串w，采用，采用自頂向下自頂向下的分析來判斷的分析來判斷w是否是否為為L(GS)的句子的常見方法是：的句子的常見方法是：試圖建立從開始符試圖建立從開始符 S到到w最左推導(dǎo)最左推導(dǎo): S* w 顯然，每步推導(dǎo)時，對應(yīng)于最左非終結(jié)符相應(yīng)的產(chǎn)生式顯然，每步推導(dǎo)時，對應(yīng)于最左非終結(jié)符相應(yīng)的產(chǎn)生式可能會有多個，若無特殊的辦法，只能一個一個地試探?？赡軙卸鄠€，若無特殊的辦法，只能一個一個地試探。因此，推導(dǎo)過程可能是因此，推導(dǎo)過程可能是帶回溯帶回溯的的。 為提高效率，就應(yīng)盡量避免回溯為提高效率，就應(yīng)盡量避免回溯v語法樹的構(gòu)造

48、：將文法的開始符號作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號串正好是輸入符號串。例 文法G：S cAd A ab A a識別輸入串w=cabd是否為該文法的句子S推導(dǎo)過程：推導(dǎo)過程：cAdab=cabdS =cAdq自上而下方法的主要問題對輸入串cabd自上而下構(gòu)造語法樹的另一過程不成功，不成功的原因不成功，不成功的原因是選錯產(chǎn)生式是選錯產(chǎn)生式Aa自上而下分析的主要問題是選擇產(chǎn)生式自上而下分析的主要問題是選擇產(chǎn)生式 :假定要被代換的最左非終結(jié)符號是假定要被代換的最左非終結(jié)符號是B B，且有且有n n條規(guī)則：條規(guī)則：BABA1 1|A|A2 2|A|An n，那么如何確定用那么如

49、何確定用哪個右部去替代哪個右部去替代B B？ScA dav就是從已給的符號串就是從已給的符號串w出發(fā)，試圖以相反的方向?yàn)槌霭l(fā)，試圖以相反的方向?yàn)閣建立一個規(guī)建立一個規(guī)范推導(dǎo)，最終得到文法的開始符。范推導(dǎo)，最終得到文法的開始符。v推導(dǎo)的逆過程稱作推導(dǎo)的逆過程稱作歸約歸約，它是把當(dāng)前的符號串，它是把當(dāng)前的符號串中的構(gòu)成文法中的構(gòu)成文法某個產(chǎn)生式某個產(chǎn)生式A右部的子串右部的子串 替換成產(chǎn)生式的左部符號替換成產(chǎn)生式的左部符號A，得到，得到一個新的符號串一個新的符號串 A 。這樣的一步動作，稱為進(jìn)行了一步。這樣的一步動作，稱為進(jìn)行了一步歸約歸約。v例如，符號串例如，符號串F+i*i中的中的F可按產(chǎn)生式可

50、按產(chǎn)生式TF歸約為歸約為T，從而得到新，從而得到新的符號串的符號串T+i*i。v若從給定的符號串若從給定的符號串w出發(fā)，一步步地將其歸約，最終得到文法的出發(fā)，一步步地將其歸約，最終得到文法的開始符號，則說明開始符號，則說明w是該文法定義的一個句子。歸約成功，否則，是該文法定義的一個句子。歸約成功，否則，歸約失敗。歸約失敗。v若歸約的每一步都?xì)w約的是當(dāng)前符號串中最左邊的某產(chǎn)生式的右若歸約的每一步都?xì)w約的是當(dāng)前符號串中最左邊的某產(chǎn)生式的右部，則稱該歸約是部，則稱該歸約是規(guī)范歸約規(guī)范歸約（即（即最左歸約最左歸約）。）。v規(guī)范歸約是規(guī)范推導(dǎo)的逆過程規(guī)范歸約是規(guī)范推導(dǎo)的逆過程。v關(guān)于最左（右）歸約、直接

51、歸約、歸約等的形式定義不再贅述。關(guān)于最左（右）歸約、直接歸約、歸約等的形式定義不再贅述。2.6.2 自底向上的語法分析自底向上的語法分析步序 當(dāng)前符號串wi 所用的產(chǎn)生式 歸約后的符號 0 i+i*i Fi F+i*i 1 F+i*i TF F T+i*i 2 T+i*i E ET T E+i*i 3 E+i*i F Fi i E+F*i 4 E+F*i T TF F E+T*i 5 E+T*i F Fi i E+T*F 6 E+T*F T TT T* *F F E+T 7 E+T E EE E+ +T T E 由上表可以看出，歸約過程是由上表可以看出，歸約過程是最左最左歸約，它恰好是歸約，它

52、恰好是規(guī)規(guī)范推導(dǎo)的逆過程范推導(dǎo)的逆過程。這正是把最左歸約定義為規(guī)范歸約。這正是把最左歸約定義為規(guī)范歸約的原因。的原因。例 文法G：S cAd A ab A a識別輸入串w=cabd是否為該文法的句子cabd歸約過程：歸約過程：用用“|-”表示歸表示歸約，下劃線部分約，下劃線部分為被歸約符號為被歸約符號cabd |-cAd |-SAS關(guān)于歸約的一點(diǎn)說明v注意，前面例子中歸約的第五步中，當(dāng)前的符號串為注意，前面例子中歸約的第五步中，當(dāng)前的符號串為 E+T*i，除了可將，除了可將i歸約成歸約成F外，還可將外，還可將E+T或或T歸約成歸約成E，分別得到符號串分別得到符號串E*i和和E+E*i。但是，若

53、真按這兩個方案。但是，若真按這兩個方案進(jìn)行歸約，則當(dāng)我們把其歸約成進(jìn)行歸約，則當(dāng)我們把其歸約成E*E或或E+E*E時，就再時，就再也歸約不下去了。這就告訴我們在第五步時，唯一正確也歸約不下去了。這就告訴我們在第五步時，唯一正確的歸約是將的歸約是將i歸約為歸約為F，也就是說，也就是說，i是唯一可被歸約的最是唯一可被歸約的最左子串。左子串。v對輸入串cabd的兩種歸約過程（1）cabd|-cAd|-S 歸約到開始符（2）cabd|-cAbd 不能歸約到開始符 那么，對于規(guī)范歸約的每一步，如何確定符號串中的當(dāng)那么，對于規(guī)范歸約的每一步，如何確定符號串中的當(dāng)前應(yīng)被歸約的最左子串呢？前應(yīng)被歸約的最左子串

54、呢？短語和句柄短語和句柄v問題問題: : 在自底向上在自底向上( (簡記為簡記為 ) )的語法分析中的語法分析中, ,對對于每一步直接歸約于每一步直接歸約, ,應(yīng)如何正確地確定當(dāng)前句應(yīng)如何正確地確定當(dāng)前句型中應(yīng)被歸約的型中應(yīng)被歸約的最左子串最左子串? ?v考慮文法考慮文法G G2 2EE的句型的句型 = E+T= E+T* *F+iF+i, ,從開始符從開始符E E 推導(dǎo)出推導(dǎo)出 的語法樹見右圖的語法樹見右圖v該樹中含有若干子樹該樹中含有若干子樹, ,如如T T(2)(2)為根的子樹對應(yīng)的為根的子樹對應(yīng)的葉結(jié)點(diǎn)為葉結(jié)點(diǎn)為T T(3)(3)* *F F(3),(3),由于它是一直接子樹由于它是一

55、直接子樹, ,文法中文法中必有產(chǎn)生式必有產(chǎn)生式T-TT-T* *F F; ;因此因此, ,稱稱T T* *F F是句型是句型 相對于相對于產(chǎn)生式產(chǎn)生式T-TT-T* *F F的的直接短語直接短語. .同理同理, ,F F(1)(1)對應(yīng)的對應(yīng)的直直接短語接短語為為i i. .v以以E E(1)(1)為根的子樹相應(yīng)的葉結(jié)點(diǎn)為為根的子樹相應(yīng)的葉結(jié)點(diǎn)為 E E(2)(2)+T+T(3)(3)* *F F(3)(3), ,所以所以, ,稱為句型稱為句型 相對于非終結(jié)符相對于非終結(jié)符E E 的的短語短語. .同同理理, ,i i是相對于是相對于T T(1)(1)的的短語短語短語、直接短語及句柄的定義短語

56、、直接短語及句柄的定義定義:設(shè)是文法GS中的一個句型，如果有S=*A且A=+，則稱是句型相對于非終結(jié)符A的短語特別的如有A=，則稱是句型相對于規(guī)則A的(直接短語直接短語)簡單短語。一個句型的最左簡單短語稱為該句型的句柄(Handle)。句柄就是“可歸約串”v例如，對句型例如，對句型 = E+T*F+i，由定義，有：由定義，有：v(1)E* E+T+i( =E+,A=T, =+i)及及TT*F(= ),故故T*F是是 相相對于產(chǎn)生式對于產(chǎn)生式T-T*F的直接短語的直接短語;v(2)E* E+T*F+F Fi,i是是 相對于產(chǎn)生式相對于產(chǎn)生式F-i的直接短語的直接短語;v(3)E* E+i與與 E

57、 + E+T*F,E+T*F是相對于非終結(jié)符是相對于非終結(jié)符E的短的短語語;v(4)E* E及及E* E+T*F+i(= ), 是是 相對于相對于E的短語的短語v注注:由定義可知由定義可知,直接短語也是短語直接短語也是短語,但短語不一定是直接短語但短語不一定是直接短語.歸約時被替換子串的選擇v從句型 =E+T=E+T* *F+iF+i的語法樹可知,E+T絕不是它的一個直接短語,因?yàn)殡m然E-E+T是G2的一個產(chǎn)生式,但不存在從E到E*F+i的推導(dǎo),所以,當(dāng)判斷一符串是否為某一句型的短語時,須檢查定義的兩個條件是否同時滿足.v采用采用 分析時分析時, ,每步每步歸約歸約就是將一個產(chǎn)生式就是將一個產(chǎn)

58、生式右部右部替換替換其其左部左部, ,也就是把該也就是把該句型的語法樹中的句型的語法樹中的一棵直接子樹的末端結(jié)點(diǎn)剪去一棵直接子樹的末端結(jié)點(diǎn)剪去. .即每次歸約的符號串即每次歸約的符號串必是當(dāng)前句型的一個直接短語必是當(dāng)前句型的一個直接短語. .v但是但是, ,對一句型而言對一句型而言, ,其其直接短語可能不唯一直接短語可能不唯一. .為了讓分析能夠機(jī)械地進(jìn)為了讓分析能夠機(jī)械地進(jìn)行行, ,我們只考慮規(guī)范歸約我們只考慮規(guī)范歸約( (最左歸約最左歸約),),即歸約過程替換的是歸左直接短語即歸約過程替換的是歸左直接短語. .v我們以L(G2)的句子i+i*i+i為例,給出其最右推導(dǎo)(規(guī)范歸約的逆過程),

59、來說明每次規(guī)范歸約的子符號串用語法樹求短語、句柄v短語：（子）樹的末端結(jié)點(diǎn)形成的符號串是相對于(子)樹根的短語。v簡單短語（直接短語）：簡單子樹的末端結(jié)點(diǎn)形成的符號串是相對于簡單子樹根的簡單短語。v句柄：最左簡單子樹的末端結(jié)點(diǎn)形成的符號串是句柄。例：對于文法例：對于文法GS：S:=AB A:=Aa|bB B:=a|Sb 求句型求句型baSb的全部短語、直接短的全部短語、直接短語和句柄？語和句柄？lbaSb為句型為句型baSb的相對于的相對于S的的短語；短語；lba為句型為句型baSb的相對于的相對于A的短語；的短語；la為句型為句型baSb的相對于的相對于B的短語的短語,且為直接短語和句柄；且

60、為直接短語和句柄；lSb為句型為句型baSb的相對于的相對于B的短的短語語,且為直接短語。且為直接短語。SSABbabSB例：文法GE: EE+T|T TTF|F F（E）| i 的一個句型是 TF+i，相應(yīng)的語法樹見右圖：EET+TTFFi . 因?yàn)橐驗(yàn)镋=* T+i 且且 T=TF，所以所以TF是句型相對于是句型相對于T的短語，且是相對的短語，且是相對于于TTF的直接短語的直接短語 . 因?yàn)橐驗(yàn)镋=* TF+F 且且 F=i，所以所以i是句是句型相對于型相對于F的短語，且是相對于的短語，且是相對于Fi的直接短語的直接短語 . 因?yàn)橐驗(yàn)镋=* E 且且E=+ TF+i，所以所以TF+i是句型