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

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

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

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

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

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

7、不同,代代表不同的符號串，如表不同的符號串，如:ab和和ba不同不同不含任何符號的符號串稱為空串，用不含任何符號的符號串稱為空串，用表示表示注意注意: :并不等于空集合并不等于空集合 符號串長度符號串長度: 符號串中含有符號的個數符號串中含有符號的個數如如: |abc|=3| |=0 子符號串子符號串v設有非空符號串設有非空符號串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符號串的運算符號串的運算符號串的連接符號串的連接：設設x、y是符號串是符號串,它們它們的連接是把的連接是把y的符號寫在的符號寫在 x的符號之后

9、的符號之后得到的符號串得到的符號串xy例如例如 x=ST，y=abu ，則，則 xy=STabu 顯然顯然x = x=x符號串的方冪符號串的方冪：把：把符號串符號串a a自身連接自身連接n n次次得到的符號串得到的符號串a 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符號串集合的方冪符號串集合的方冪: : 設設A A是符號串的集合，則稱是符號串的集合，則稱A Ai i為符號串集為符號串集A A的方冪，其中的方冪，其中i i是非負整數。具體是非負整數。具體定義如下定義如下: :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例：設有字母表例：設有字母表=0，1則則*=012=,0,1,00,01,10,11,000,即即*表示表示上所有有窮長的串的集合。上所有有窮長的串的集合。正閉包正閉包+ = 123稱為稱為的正閉包。的正閉包。 + 表示表示 上的上的除除外外的所有用窮長串的集合的所有用窮長串的集合* = 0+ = * = * 字母表字母表 上上的一個語言是的一個語言是 上符合某種規則的一些符號上符合某種規則的一些符號

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為為字母字母表表 上上的一個語言。的一個語言。 是一個語言。是一個語言。小結1 符號

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

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

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

16、中出現，而終結符是組成程序的具體的符號。2. 文法形式定義上的約定文法形式定義上的約定v文法習慣上只將產生式寫出。并有如下約定：第一條產生式的左部是開始符號,或用GS表示S是開始符號用尖括號括起的是非終結符，否則為終結符。或者大寫字母表示非終結符，小寫字母表示終結符G可寫成GS，S是開始符號希臘字母代表由終結符號和非終結符號組成的符號串v 、左部相同的產生式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 =標識符，字母，數字，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. 推導(Derivation)與歸約(Reduction)q直接推導和直接歸約： 是文法G的產生式，若有v，w滿足：v=,w=, 其中,V* 則稱v直接推導出w,也稱w直接歸約到v,記作 v w直接推導就是用產生式的右部替換產生式的左部的過程直接歸約就是用產生式的左部替換產生式的右部的過程例 文法G： S0S1，S01 有直接推導： S 0S1（ S0S1 ）0S1 00S11（ S0S1 ） 00S1

18、1 000S111（ S0S1 ） 000S111 00001111（ S01 ） 推導例題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的串推導例題2e.g. 文法產生的語言文法G4對句子aaabb的推導：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. 文法產生的語言文法G5對句子aaaabbbb的推導：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直接推導序列和廣義推導v直接推導序列： 或 + 若存在v =u0 u1 . un=w, (n0) 則稱v + w，v推導出w，或w歸約到v（至少有1步推導），這個直接推導序列的長度為n。v廣義推導： 或 * 若有v + w 或 v=w， 則記為v * w，v廣義推導出w，w廣義規約到v（可以包含0步推導）+*三種推導的比較v直接推導（直接推

20、導（）的長度為）的長度為1v直接推導序列（直接推導序列（ +）的長度）的長度n1v廣義推導（廣義推導（ *）的長度）的長度0規范推導和規范歸約規范推導和規范歸約v對于一文法而言，從開始符到某句型的對于一文法而言，從開始符到某句型的推導過程可能不唯一推導過程可能不唯一。例如，文法例如，文法GE中從中從 E 到到 i+i*i 的推導有：的推導有：(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) 規范推導v為了讓計算機自動地進行推導，通常我們只考慮最左或最右為了讓計算機自動地進行推導，通常我們只考慮最左或最右推導。推導。v最左（右）推導最左（右）推導：在推導序列的每一步直接推導中，被替換在推導序列的每一步直接推導中，被替換的總是當前句型中最左（右）的非終結符。的總是當前句型中最左（右）的非終結符。v例如，上頁中的（例如，上頁中的（2）、（）、（3）分別是最左、最右推導。）分別是最左、最右推導。v形式上，形式上，從符號串從符號串 到符號串到符號串 的推導序列的推導序列 * xUy xuy * 總有總有 x VT* (y VT*) 時，稱為

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

23、TF|F F（E）|i句子i+ii的推導過程如下：最左推導：E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii最右推導：E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii遞歸規則v借助于自身來定義的規則，稱為遞歸規則。如 := 遞歸規則的存在，使得能用有窮個規則來定義無窮的語言。v如果一個規則形如U:=U（或UxUy），則該規則是遞歸的； 如果規則形如U:=U （或UUy），則稱左遞歸的； 如果規則形如U:=U （或UxU），則稱右遞歸的。v例：:=, （左遞歸規則） :=! （右遞歸規則）文法的遞歸性v定義：對于某文法，存在UVN，

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

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

26、001111所以S,0S1 ,00S11 ,000S111,00001111都是G的句型00001111是G的句子由規范推導所得的句型稱為規范句型q語言的定義由文法G生成的語言記為L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1q文法和語言的關系：文法G生成的每個串都在L(G)中L(G)中的每個串確實能被G生成根據文法，可以通過推導得到該文法相應的語言；例：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，+，(，)構成的算術表達式有了語言的要求，也可以為該語言設計文法例：若語言由0、1符號串組成，串中0和1的個數相同，構造其文法為：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對文法中的規則施加不同限制，將文法和語言分為四大類：v0型文法（PSG） 0型語言或短語結構語言v1型文法（CSG） 1型語言或上下文有關語言v2型文法（CFG） 2

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

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

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

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

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

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

34、法產生的語言稱為產生的語言稱為3型（型（正規正規）語言）語言，它可由，它可由有限自動有限自動機機識別。識別。正規語言正規語言可用可用正規表達式正規表達式表示。表示。v注：注：若一文法即含若一文法即含左線性左線性又含又含右線性產生式右線性產生式，則它，則它不一定是不一定是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 則它們之間有則它們之間有真包含關系：真包含關系：0123LLLL文法類型文法名稱語言名稱自動機名稱0短語結構遞歸可枚舉圖靈機1前后文有關前后文有關線性限界2前后文無關前后文無關下推自動機3正規有限狀態有限自動機四種文法之間的逐級四種文法之間的逐級“包含包含”關系關系2型文法型文法1型文法型文法3型文法型文法0型文法型文法2.5 上下文無關文法及其語法樹1上下文無關文法(Context-Free Grammar)自然語言是上下文有關的。 上下文無關文法有足夠的能力描述現今程序設計語言的語法結構例：算術表達式：Ei|

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

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

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

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

40、從語法樹構造推導的過程v例如文法GS： S:=AB A:=aAb|ab B:=cBd|cd 存在下面的推導可能：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兩個不同的最左推導：兩個不同的最左推導：推導推導1：E E+E EE+E iE+E ii+E ii+i推導推導2：E EE iE iE+E ii+E ii+i3.文法的二義性文法的二義性(Ambiguity)文法的二義性v存在這樣的文法存在這樣的文法G，其某個

41、句子，其某個句子w L(G),可對應結構不同可對應結構不同的語法樹，即的語法樹，即w對應了多個不同的最左（右）推導，這類對應了多個不同的最左（右）推導，這類文法稱為文法稱為。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上面兩個句型均有兩個不同的語法推導樹（見下頁），所上面兩個句型均有兩個不同的語法推導樹（見下頁），所以，它們是二義性文法以，它們是二義性文法EEEEE+*iiiEEEEE+*iii S1 S2if

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

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

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

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

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

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

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

49、何確定用哪個右部去替代哪個右部去替代B B？ScA dav就是從已給的符號串就是從已給的符號串w出發，試圖以相反的方向為出發，試圖以相反的方向為w建立一個規建立一個規范推導，最終得到文法的開始符。范推導，最終得到文法的開始符。v推導的逆過程稱作推導的逆過程稱作歸約歸約，它是把當前的符號串，它是把當前的符號串中的構成文法中的構成文法某個產生式某個產生式A右部的子串右部的子串 替換成產生式的左部符號替換成產生式的左部符號A，得到，得到一個新的符號串一個新的符號串 A 。這樣的一步動作，稱為進行了一步。這樣的一步動作，稱為進行了一步歸約歸約。v例如，符號串例如，符號串F+i*i中的中的F可按產生式可

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

51、歸約、歸約等的形式定義不再贅述。關于最左（右）歸約、直接歸約、歸約等的形式定義不再贅述。2.6.2 自底向上的語法分析自底向上的語法分析步序 當前符號串wi 所用的產生式 歸約后的符號 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、恰好是規規范推導的逆過程范推導的逆過程。這正是把最左歸約定義為規范歸約。這正是把最左歸約定義為規范歸約的原因。的原因。例 文法G：S cAd A ab A a識別輸入串w=cabd是否為該文法的句子cabd歸約過程：歸約過程：用用“|-”表示歸表示歸約，下劃線部分約，下劃線部分為被歸約符號為被歸約符號cabd |-cAd |-SAS關于歸約的一點說明v注意，前面例子中歸約的第五步中，當前的符號串為注意，前面例子中歸約的第五步中，當前的符號串為 E+T*i，除了可將，除了可將i歸約成歸約成F外，還可將外，還可將E+T或或T歸約成歸約成E，分別得到符號串分別得到符號串E*i和和E+E*i。但是，若

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

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

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

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

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

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

59、來說明每次規范歸約的子符號串用語法樹求短語、句柄v短語：（子）樹的末端結點形成的符號串是相對于(子)樹根的短語。v簡單短語（直接短語）：簡單子樹的末端結點形成的符號串是相對于簡單子樹根的簡單短語。v句柄：最左簡單子樹的末端結點形成的符號串是句柄。例：對于文法例：對于文法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，相應的語法樹見右圖：EET+TTFFi . 因為因為E=* T+i 且且 T=TF，所以所以TF是句型相對于是句型相對于T的短語，且是相對的短語，且是相對于于TTF的直接短語的直接短語 . 因為因為E=* TF+F 且且 F=i，所以所以i是句是句型相對于型相對于F的短語，且是相對于的短語，且是相對于Fi的直接短語的直接短語 . 因為因為E=* E 且且E=+ TF+i，所以所以TF+i是句型