前后文無關文法和語言

1、1第二章第二章 前后文無關文法和語言前后文無關文法和語言n語言文法概述語言文法概述n文法和語言的形式定義文法和語言的形式定義n文法的類型文法的類型n上下文無關文法及其語法樹上下文無關文法及其語法樹n句型的分析句型的分析n有關文法實用中的一些說明有關文法實用中的一些說明第第2章章 前后文無關文法和語言前后文無關文法和語言本章目的本章目的 為語言的語法描述尋求工具。為語言的語法描述尋求工具。 通過該工具，可以：通過該工具，可以：y掌握掌握對源程序給精確無二義（嚴謹、簡潔、易對源程序給精確無二義（嚴謹、簡潔、易讀）讀）的語法描述手段之一的語法描述手段之一-文法。文法。y根據(jù)語言文法的特點來指導語法分

2、析的過程根據(jù)語言文法的特點來指導語法分析的過程y從描述語言的文法可以自動構造出可用的分析從描述語言的文法可以自動構造出可用的分析程序程序y制導語義翻譯制導語義翻譯第第2章章 前后文無關文法和語言前后文無關文法和語言本章難重點本章難重點 關于文法和語言的概念是形式語言的理論基礎，形式語言抽象地定義為一個數(shù)學系統(tǒng)。形式是指這樣的事實：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。這里介紹的語言的語法描述工具正是這樣的系統(tǒng)。第第2章章 前后文無關文法和語言前后文無關文法和語言第第2章章 前后文無關文法和語言前后文無關文法和語言文法及語言的表示 當我們表述一種語言時，無非是說明這種語言的句子（句子句

3、子：一定字符集（稱字母表）上的一字符一定字符集（稱字母表）上的一字符串串），如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。 以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者定義)句子的組成結構（也就是各種屬性的單詞所允許的排列規(guī)則），比如漢語句子可以是由主語后隨謂語而成，構成謂語的是動詞和直接賓語，我們采用EBNF來表示這種句子的構成規(guī)則： 第第2章章 前后文無關文法和語言前后文無關文法和語言“我是大學生”。是漢語的一個句子句子=主語謂語主語=代詞名詞代詞=我你他名詞=王明大學生工

4、人英語謂語=動詞直接賓語動詞=是學習直接賓語=代詞名詞 第第2章章 前后文無關文法和語言前后文無關文法和語言 “我是大學生”的構成符合上述規(guī)則，而“我大學生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結構合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結構描述。其中一種描述元語言稱為文法。第第2章章 前后文無關文法和語言前后文無關文法和語言英語句子sentence subject This | Computers | Iverb-phrase | adverb neververb is | run | am | tellobject t

5、he | a | noun university | world | cheese | liesThis is a university.Computers run the world.I am the cheese.I never tell lies.第第2章章 前后文無關文法和語言前后文無關文法和語言語言概述語言概述n 語言是由句子組成的集合，是由一組記號所構成的語言是由句子組成的集合，是由一組記號所構成的集合。集合。n 漢語漢語-所有符合漢語語法的句子的全體所有符合漢語語法的句子的全體n 英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體n 程序設計語言程序設計語言-所有

6、該語言的程序的全體所有該語言的程序的全體 語法語法：每個句子構成的規(guī)律：每個句子構成的規(guī)律n 研究語言研究語言 語義語義：每個句子的含義：每個句子的含義 語用語用：每個句子和使用者的關系：每個句子和使用者的關系第第2章章 前后文無關文法和語言前后文無關文法和語言研究程序設計語言 語法：每個程序構成的規(guī)律 語義：每個程序的含義1、 - 表示構成語言句子的各個記號之間的組合規(guī)律。語法包括：詞法規(guī)則和語法規(guī)則 例如：C語法規(guī)定了構成條件語句的各個記號的組合規(guī)律為：第一個單詞（記號）必須是”if”，然后是單詞”(”、表達式，.。2、 - 表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關系）

7、 對一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。離開語義，語言只不過是一堆符號的集合。 所謂一個語言的語義是這樣的一組規(guī)則，使用它可以定義一個程序的意義。這些規(guī)則稱為語義規(guī)則。 闡明語義要比闡明語法難的多，現(xiàn)在還沒有一種形式系統(tǒng)描述語義。第第2章章 前后文無關文法和語言前后文無關文法和語言 例如：我們根據(jù)例如：我們根據(jù)C C語法可以判斷出聲明語句語法可以判斷出聲明語句”int i=999;”int i=999;”是正確的，但是無法判斷出聲明語句是正確的，但是無法判斷出聲明語句”int i=9999999;”int i=9999999;”是是錯誤的，因為該

8、語句的語法沒有錯誤（即單詞的排列順序是錯誤的，因為該語句的語法沒有錯誤（即單詞的排列順序是對的），其錯誤是因為數(shù)值對的），其錯誤是因為數(shù)值99999999999999超過了整型變量的最大超過了整型變量的最大允許值。這個錯誤就需要語義檢查才能發(fā)現(xiàn)。允許值。這個錯誤就需要語義檢查才能發(fā)現(xiàn)。 如果不考慮語義，即只從語法這一側面來看語言，這種意如果不考慮語義，即只從語法這一側面來看語言，這種意義下的語言稱作義下的語言稱作形式語言形式語言。形式語言抽象地定義為一個數(shù)學。形式語言抽象地定義為一個數(shù)學系統(tǒng)。系統(tǒng)?！靶问叫问健笔侵高@樣的事實：語言的所有規(guī)則只以什么是指這樣的事實：語言的所有規(guī)則只以什么符號串能

9、出現(xiàn)的方式來陳述。形式語言理論是對符號串集合符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程序設計語言語法分析的表示法、結構及其特性的研究。是程序設計語言語法分析研究的基礎。研究的基礎。第第2章章 前后文無關文法和語言前后文無關文法和語言有關定義和記號有關定義和記號符號符號：可以相互區(qū)別的記號（元素）。：可以相互區(qū)別的記號（元素）。字母表字母表 ：符號（元素）的非空有窮集合。：符號（元素）的非空有窮集合。符號串符號串：由字母表：由字母表 中的符號組成的任何有窮序列中的符號組成的任何有窮序列稱為該字母表上的符號串。稱為該字母表上的符號串。1.1.空符號串空符

10、號串(沒有沒有符號的符號串符號的符號串) )是是 上的符號串上的符號串 2.2.若若x x是是 上的符上的符號串號串,a,a是是 的元素的元素, ,則則xaxa是是 上的符號串上的符號串 3.3. y y是是 上的符號串上的符號串, ,當且僅當它可以由當且僅當它可以由1 1和和2 2導出。導出。 例如：例如： =a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符號串上的符號串第第2章章 前后文無關文法和語言前后文無關文法和語言 符號串符號串s s的頭（的頭（前綴前綴）：移走符號串）：移走符號串s s尾部尾部的零個或多于零個符號得到的符號串的零個或

11、多于零個符號得到的符號串. . 如：如：b b是符號串是符號串bananabanana的一個前綴的一個前綴. . 符號串符號串s s的尾（的尾（后綴后綴）：刪去符號串）：刪去符號串s s頭部頭部的零個或多于零個符號得到的符號串的零個或多于零個符號得到的符號串. . 如如:nana:nana是符號串是符號串bananabanana的一個后綴的一個后綴. . 符號串符號串s s的的子串子串：從：從s s中刪去一個前綴和一中刪去一個前綴和一個后綴得到的符號串個后綴得到的符號串. . 如如:ana:ana是符號串是符號串bananabanana的一個子串的一個子串. .第第2章章 前后文無關文法和語言

12、前后文無關文法和語言符號串的運算符號串的運算符號串的符號串的長度長度：符號串中符號的個數(shù)：符號串中符號的個數(shù). .符號串符號串s s的長的長度記為度記為|s|s|。 的長度為的長度為0 0連接連接：符號串：符號串x x、y y的連接的連接, ,是把是把y y的符號寫在的符號寫在x x的符號的符號之后得到的符號串之后得到的符號串xy xy 如如 x=ab,y=cd x=ab,y=cd 則則 xy=abcd xy=abcd 有有a = a a = a 方冪方冪：符號串自身連接：符號串自身連接n n次得到的符號串次得到的符號串 a an n 定義為定義為 aaaa naaaa n個個a aa a1

13、1=a, a=a, a2 2=aa=aa則則a a0 0=符號串符號串集合集合：若集合：若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符號串，則稱的符號串，則稱A A為字母表為字母表 上的符號串集合。上的符號串集合。第第2章章 前后文無關文法和語言前后文無關文法和語言兩個符號串集合兩個符號串集合A A和和B B的乘積定義為的乘積定義為 AB =AB = xy|xxy|x A A且且y y B B 若集合若集合A=A= ab,cdeab,cde ，B = B = 0,10,1 則則 AB =AB = ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使用

14、 * *表示表示 上的一切符號串（包括上的一切符號串（包括）組成的集）組成的集合。合。* *稱為稱為的的閉包閉包。 上的上的除除外的所有符號串組成的集合記為外的所有符號串組成的集合記為 + + 。+ +稱為稱為的的正閉包正閉包。.2*.32*第第2章章 前后文無關文法和語言前后文無關文法和語言例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,第第2章章 前后文無關文法和語言前后文無關文法和語言語言語言是由句子組成的集合，是由一組符號所構成的集合。換言之,字母表上的一個語言是上的一些符號串的集合 (字母表上的每個語言是*的一

15、個子集)。例如：字母表=a,b , *=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示為w|w*且w=anbn,n1為字母表上的一個語言。集合a,aa,aaa,或表示為w|w*且w=an,n1 為字母表上的一個語言。 是一個語言。 即 是一個語言。第第2章章 前后文無關文法和語言前后文無關文法和語言文法和語言的形式定義 如何來描述一種語言？如何來描述一種語言？如果語言是有窮的（只含有有窮多個句子），可以如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的如果語言是無

16、窮的，找出語言的有窮表示。語言的有窮表示有兩個途經(jīng)：有窮表示有兩個途經(jīng)： - - 生成方式生成方式 （文法文法）：語言中的每個句子可以用）：語言中的每個句子可以用嚴格定義的規(guī)則來構造。嚴格定義的規(guī)則來構造。 - - 識別方式（識別方式（自動機自動機）：用一個過程，當輸入的一）：用一個過程，當輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答止并回答“是是”，若不屬于，要么能停止并回答，若不屬于，要么能停止并回答“不是不是”，（要么永遠繼續(xù)下去。），（要么永遠繼續(xù)下去。） 第第2章章 前后文無關文法和語言前后文無關文法和語言文法是程序語言的生

17、成系統(tǒng)，而自動機則是程序語言的識別系統(tǒng)；用文法可以精確地定義一個語言，并依據(jù)該文法構造出識別這個語言的自動機。因此，文法對程序語言和編譯程序的構造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關文法描述，而語義則要借助于上下文有關文法描述。下面給出文法的定義.進而在文法的定義的基礎上,給出推導的概念,句型、句子和語言的定義.第第2章章 前后文無關文法和語言前后文無關文法和語言文法和語言的形式定義文法和語言的形式定義n文法的定義文法的定義n推導的定義推導的定義n句型、句子、語言的定義句型、句子、語言的定義第第2章章 前后文無關文法和語言前后文無關文法和語言文法的定義文法的定義文

18、法文法G定義為四元組（定義為四元組（VN，VT，P，S） VN ：非終結符集非終結符集 VT ：終結符集終結符集 P：產(chǎn)生式（規(guī)則）集合產(chǎn)生式（規(guī)則）集合 S：開始符號開始符號VNVT= ， SSVNV=V=VNVT，稱為文法稱為文法G G的文法的文法符號集合符號集合第第2章章 前后文無關文法和語言前后文無關文法和語言文法文法G定義為四元組定義為四元組(VN，VT，P，S )，其中 VN為非終結符號(或語法實體，或變量)集； VT為終結符號集； P為產(chǎn)生式(也稱規(guī)則)的集合； VN，VT和P是非空有窮集。 S稱作識別符號或開始符號，它是一個非終結符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN和V

19、T不含公共的元素，即VN VT = 用V表示VN VT ，稱為文法G的字母表或字匯表第第2章章 前后文無關文法和語言前后文無關文法和語言規(guī)則的定義規(guī)則的定義n規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式），規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式），是形如是形如或或=的（的（，）有有序對，且序對，且VV+ +，VV* *。 稱為規(guī)則的左部稱為規(guī)則的左部( (或生成式或生成式的左部的左部) )。 稱為規(guī)則的右部稱為規(guī)則的右部( (或生成式或生成式的右部的右部) )。第第2章章 前后文無關文法和語言前后文無關文法和語言文法的定義文法的定義n例：文法例：文法G=（VN，VT，P，S） VN = S , VT = 0, 1

20、P= S0S1, S01 S為開始符號為開始符號第第2章章 前后文無關文法和語言前后文無關文法和語言 是指語言不可再分的基本符號，通常是一個語言的字母表；終結符代表了語法的最小元素，是一種個體記號。也稱語法變量，它代表語法實體或語法范疇；非終結符代表一個一定的語法概念，因此，一個非終結符是一個類、一個集合。例如，在程序語言中，可以把變量、常數(shù)、“+”、“*”等看作是終結符，而像“算術表達式”這個非終結符則代表著一定算術式組成的類，如i*(i+i)、i+i+i等；也即每個非終結符代表著由一些終結符和非終結符且滿足一定規(guī)則的符號串組成的集合。第第2章章 前后文無關文法和語言前后文無關文法和語言 文

21、法開始符號是一個特殊的非終結符，它代表文法所定義的語言中我們最終感興趣的語法實體，即語言的目標，而其它語法實體只是構造語言目標的中間變量；如表達式文法的語言目標是表達式，而程序語言的目標通常為程序。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則)是定義語法實體的一種書寫規(guī)則。一個語法實體的相關規(guī)則可能不止一個。例如，有： P1 P2 Pn 為書寫方便，可將這些有相同左部的產(chǎn)生式合并為一個，即縮寫成 P12n 其中，每個i(i=1,2,n)稱為P的一個候選式，直豎“”讀為“或”，它與“”一樣是用來描述文法的元語言符號(即不屬于的字符)。第第2章章 前后文無關文法和語言前后文無關文法和語言例例 文法文法G=（VN，

22、VT，P，S） VN =標識符，字母，數(shù)字標識符，字母，數(shù)字 VT =a,b,c,x,y,z,0,1,9 P= a, zz 0, 0, 99 S=第第2章章 前后文無關文法和語言前后文無關文法和語言例:試構造產(chǎn)生標識符的文法。解答首先，標識符是以字母開頭的字母數(shù)字串，我們用L表示“字母”類非終結符，用D表示“數(shù)字”類非終結符，而用T表示“字母或數(shù)字”類非終結符，則有： Labz D019 TLD 其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有 STST 其中，產(chǎn)生式STST是一種左遞歸形式，由它可以產(chǎn)生一串T。第第2章章 前后文無關文法和語言前后文無關文法和語

23、言 最后，作為“標識符”的非終結符I，它或者是一單個字母，或者為一字母后跟字母數(shù)字串，即 ILLS 因此，產(chǎn)生標識符的文法GI為： G=(a,b,z,0,9,I,S,T,L,D,P,I) P:ILLS STST TLD Labz D019第第2章章 前后文無關文法和語言前后文無關文法和語言例:寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。解答根據(jù)題意，我們可以將奇數(shù)劃分為如圖21所示的三個部分，即最高位允許出現(xiàn)19，用非終結符B表示；中間部分可以出現(xiàn)任意多位數(shù)字09，每一位用非終結符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。第第2章章 前后文無關文法和語言前后文無

24、關文法和語言圖21 奇數(shù)劃分示意MB最高位中 間 位DDDA最低位第第2章章 前后文無關文法和語言前后文無關文法和語言 由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法GN為： G=(0,1,9,N,A,M,B,D,P,N) P:N NAMA/*一位數(shù)字多位數(shù)字*/ M MBMD/*僅兩位數(shù)字(無中間位)多于兩位數(shù)字*/ A A13579 B B123456789 D D0B第第2章章 前后文無關文法和語言前后文無關文法和語言推導推導 推導把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結符用其產(chǎn)生式右部的串來代替。亦即：從識別符號開始，不斷將

25、當前符號串中的非終結符號替換為該符號的某個規(guī)則的右部。直到當前的符號串中所有的符號都是終結符號為止。第第2章章 前后文無關文法和語言前后文無關文法和語言“我是大學生”的推導過程 開始先找=左端的帶有句子的規(guī)則并把它由=右端的符號串代替，這個動作表示成：句子 主語謂語 然后在得到的串主語謂語中，選取主語或謂語，再用相應規(guī)則的=右端代替之。比如，選取了主語，并采用規(guī)則主語=代詞， 那么得到：主語謂語 代詞謂語， 重復做下去. 句子：“我是大學生”的全部動作過程是：句子 主語謂語 代詞謂語 我謂語 我動詞直接賓語 我是直接賓語 我是名詞 我是大學生 第第2章章 前后文無關文法和語言前后文無關文法和語

26、言 實際上，推導過程就是對所要分析的句子進行斷句（語法分析）的過程。 例如，句子“我是大學生 ”如果符合句子的規(guī)則，則其在語法結構上必然是由兩部分組成的：前一部分是主語，后一部分是謂語；又因為主語是由代詞或名詞組成的，所以符合上述文法的句子的前綴必是代詞或名詞。這樣，如果所要識別的字符串的第一個單詞不是或，則該句子不符合文法；否則，繼續(xù)判斷其后續(xù)子串是否符合謂語的語法. 第第2章章 前后文無關文法和語言前后文無關文法和語言推導的定義推導的定義直接推導“”是文法G的產(chǎn)生式，若有v,w滿足：v=,w= , 其中V*,V*則稱v直接推導到w,記作 v w 或w直接歸約到v其中“”表示直接推導出，是應

27、用產(chǎn)生規(guī)則進行推導的記號。注意“”與“”不同，“”是產(chǎn)生式中的定義記號。直接推導是對文法符號串A中的非終結符A用相應的產(chǎn)生式A的右部來替換，從而得到。我們給出推導的說明如下： 第第2章章 前后文無關文法和語言前后文無關文法和語言例：例：G G： S0S1S0S1， S01S01 S S 0S1 0S1 00S11 00S11 000S111 000S111 0000111100001111 句子 主語謂語 代詞謂語 我謂語我動詞直接賓語 我是直接賓語 我是名詞 我是大學生第第2章章 前后文無關文法和語言前后文無關文法和語言(1)如果1可直接推出2，2可直接推出3，n-1可直接推出n，即存在一個

28、自1至n的推導序列：123n(n0)，則我們稱1可推導出n，記為1 n，它表示從1出發(fā)經(jīng)過一步或若干步可推導出n。(2)如果記1 1，則表示從1出發(fā)，經(jīng)過0步或者若干步可推導出n；也即1 n意味著或者1 n，或者1 n。推導的定義推導的定義第第2章章 前后文無關文法和語言前后文無關文法和語言例如，對下面的文法GE： EE+EE*E(E)i(3.1)其中，惟一的非終結符E可以看成是代表一類算術表達式。我們可以從E出發(fā)進行一系列的推導，如表達式i+i*i的推導如下： EE+EE+E*E E+E*iE+i*ii+i*i第第2章章 前后文無關文法和語言前后文無關文法和語言文法的句型、句子的定義文法的句

29、型、句子的定義句型句型：有文法G，若S = x，則稱x是文法G的句型。句子句子：有文法G，若S = x，且xVT*，則稱x是文法G的句子。由定義可知，僅含終結符的句型是一個句子。開始符S本身只能是文法的一個句型而不可能是一個句子；此外，上面推導出的i+i*i是文法GE的一個句子(當然也是一個句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。例：G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 01*第第2章章 前后文無關文法和語言前后文無關文法和語

30、言例：例：GEGE： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a句子：用符號句子：用符號a a，+ +，* *，( (和和) )構成的算術表達式構成的算術表達式第第2章章 前后文無關文法和語言前后文無關文法和語言文法，語言的定義文法，語言的定義由文法由文法G G生成的生成的語言語言記為記為L(G),L(G),它是文法它是文法G G的一的一切句子的集合切句子的集合: : L(G)=x|S

31、 L(G)=x|S = x x，其中，其中S S為文法的開始符號，且為文法的開始符號，且xVxVT T* * 例：例：G G： S0S1S0S1， S01S01 L(G)=0 L(G)=0n n1 1n n|n1|n1*例 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 第第2章章 前后文無關文法和語言前后文無關文法和語言S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bE

32、be) aabbee （eEee)G生成的每個串都在L(G)中L(G)中的每個串確實能被G生成第第2章章 前后文無關文法和語言前后文無關文法和語言使用產(chǎn)生式(1)n-1次，得到推導序列：S=an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S=an-1S(BE)n-1 an(BE)n。然后從an(BE)n繼續(xù)推導，總是對EB使用產(chǎn)生式(3)的右部進行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有： S =* anBnEn接著，使用產(chǎn)生式(4)一次，得到S = anbBn-1En，然

33、后使用產(chǎn)生式(5)n-1次得到：S = anbnEn，最后使用產(chǎn)生式(6)一次，使用產(chǎn)生式(7)n-1次，得到：S = anbnen 也能證明，對于n1，串a(chǎn)nbnen是唯一形式的終結符號串 *第第2章章 前后文無關文法和語言前后文無關文法和語言n已知語言描述，寫出文法已知語言描述，寫出文法y例：若語言由例：若語言由0 0、1 1符號串組成，串中符號串組成，串中0 0和和1 1的個的個數(shù)相同，構造其文法。數(shù)相同，構造其文法。A 0B|1CA 0B|1CB 1|1A|0BBB 1|1A|0BBC 0|0A|1CCC 0|0A|1CCn已知文法，寫出語言描述已知文法，寫出語言描述y例：例：GEGE

34、：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a第第2章章 前后文無關文法和語言前后文無關文法和語言文法的等價文法的等價若若L(GL(G1 1)=L(G)=L(G2 2) )，則稱文法，則稱文法G G1 1和和G G2 2是等價的。是等價的。如文法如文法G G1 1AA：A0R A0R 與與G G2 2SS：S0S1 S0S1 等價等價 A01 S01A01 S01 RA1 RA1第第2章章 前后文無關文法和語言前后文無關文法和語言文法的類型文法的類型 語言學家NoamChomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應的形式語言，并分別

35、與相應的識別系統(tǒng)相聯(lián)系，它對程序語言的設計、編譯方法、計算復雜性等方面都產(chǎn)生了重大影響。第第2章章 前后文無關文法和語言前后文無關文法和語言 1、0型文法與0型語言(對應圖靈機) 如果文法G的每一個產(chǎn)生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一個非終結符；V*；則稱文法G為0型文法或短語文法，記為PSG。0型文法相應的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機。第第2章章 前后文無關文法和語言前后文無關文法和語言 2、1型文法與1型語言(對應線性界限自動機，自然語言) 文法G的每一個產(chǎn)生式，均在0型文法的基礎上增加了字符長度上滿足的限制，

36、則稱文法G為1型文法或上下文有關文法，記為CSG。1型文法相應的語言稱為1型語言或上下文有關語言，它的識別系統(tǒng)是線性界限自動機。 1型文法的另一種定義方法是文法G的每一個產(chǎn)生式具有下列形式： A 其中，、V*，AVN，V+；顯然它滿足前述定義的長度限制，但它更明確地表達了上下文有關的特性，即A必須在、的上下文環(huán)境中才能被所替換。第第2章章 前后文無關文法和語言前后文無關文法和語言 3、2型文法與2型語言(對應下推自動機，程序設計語言) 文法G的每一個產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無關文法，記為CFG。2型文法相應的語言稱為2型語言或上下文無關語言，它

37、的識別系統(tǒng)是下推自動機。第第2章章 前后文無關文法和語言前后文無關文法和語言 4、3型文法與3型語言(對應有限自動機) 文法G的每個產(chǎn)生式具有下列形式： Aa或AaB 其中，A、BVN，aVT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機。 3型文法還可以呈左線性形式： Aa或ABa第第2章章 前后文無關文法和語言前后文無關文法和語言例：例：1 1型（上下文有關）文法型（上下文有關）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbB ADaD

38、ADaD C C BDbD BDbD D D AabD AabD第第2章章 前后文無關文法和語言前后文無關文法和語言例：例：2 2型（上下文無關）文法型（上下文無關）文法 文法文法GS：SABAB ABS|0BS|0 BSA|1SA|1第第2章章 前后文無關文法和語言前后文無關文法和語言例：例：3 3型（正規(guī)）文法型（正規(guī)）文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0GI：I lTI lT lTT dTT lT d第第2章章 前后文無關文法和語言前后文無關文法和語言 四類文法的關系與區(qū)別 由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。13型文法都屬于0型文法，2、

39、3型文法均屬于1型文法，3型文法屬于2型文法。四類文法的區(qū)別如下： (1)1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則允許形如“A”的產(chǎn)生式存在； (2)0、1型文法的產(chǎn)生式左部存在含有終結符號的符號串或兩個以上的非終結符，而2型和3型文法的產(chǎn)生式左部只允許是單個的非終結符號。第第2章章 前后文無關文法和語言前后文無關文法和語言2型文法型文法1型文法型文法0型文法型文法四種四種文法文法之間之間的的逐級逐級“包含包含”關系關系3型文法型文法第第2章章 前后文無關文法和語言前后文無關文法和語言上下文無關文法及其語法樹上下文無關文法及其語法樹上下文無關文法有足夠的能力描述程序設計語言的

40、上下文無關文法有足夠的能力描述程序設計語言的語法結構語法結構語法樹語法樹-句型推導句型推導的的直觀表示直觀表示第第2章章 前后文無關文法和語言前后文無關文法和語言 例文法G=(E,+,*,i,(,),P,E)其中P為： Ei , EE+E , EE*E , E(E) E表示算術表達式, i表示程序的“變量”，該文法定義了由變量，+，*,(和)組成的算術表達式的語法結構，即： 變量是算術表達式；若E1和E2是算術表達式，則E1+ E2，E1*E2和(E1)也是算術表達式 描述一種簡單賦值語句的產(chǎn)生式： 賦值語句i=E 描述條件語句的產(chǎn)生式： 條件語句if條件then語句 if條件then語句el

41、se語句第第2章章 前后文無關文法和語言前后文無關文法和語言句型、推導 GE EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*Fa+F*F a+a*F a+a*a （對所給句子a+a*a推導序列中的每一步推導都是對句型中的最左非終結符用相應產(chǎn)生式的右部進行替換 ） EE+T E+T*F E+T*a E+F*a E+a*aT+a*a F+a*a a+a*a （對所給句子a+a*a推導序列中的每一步推導都是對句型中的最右非終結符用相應產(chǎn)生式的右部進行替換 ）EE+T T+T T+T*F F+T*F F+F*Fa+F*F a+F*a a+a*a （推導序列中的每一步

42、推導沒有固定的替換規(guī)律 ）第第2章章 前后文無關文法和語言前后文無關文法和語言規(guī)范推導最左最左（最右最右）推導：在推導的任何一步,其中、是句型，都是對中的最左（右）非終結符進行替換最右推導被稱為規(guī)范推導規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型第第2章章 前后文無關文法和語言前后文無關文法和語言語法樹 對程序語言來說，有兩個問題需要解決： 其一是判別程序在語法上是否正確； 其二是句子的識別或分析。在編譯方法中，為了便于識別或分析句子而引入了語法樹這一重要的輔助工具。語法樹以圖示化的形式把句子分解成各個組成部分來描述或分析句子的語法結構，這種圖示化的表示與所定義的文法規(guī)則完全一致，但更為直觀和完

43、整。 第第2章章 前后文無關文法和語言前后文無關文法和語言 對文法G=(VT,VN,S,) ，滿足下列條件的樹稱為GS的語法樹： (1) 每個結點用GS的一個終結符或非終結符標記； (2) 根結點用文法開始符S標記； (3) 內部結點(指非樹葉結點)一定是非終結符，如果某內部結點A有n個分支，它的所有子結點從左至右依次標記為x1、x2、xn，則Ax1x2xn一定是文法GS的一條產(chǎn)生式； (4) 如果某結點標記為，則它必為葉結點且是其父結點的惟一子結點。第第2章章 前后文無關文法和語言前后文無關文法和語言 相應于一個句型的語法樹是以文法的開始符S作為根結點的，并隨著推導逐步展開；當某個非終結符被

44、它對應的產(chǎn)生式右部的某個候選式所替換時，這個非終結符所對應的結點就產(chǎn)生出下一代新結點，即候選式中從左至右的每一個符號都依次順序對應一個新結點，且每個新結點與其父結點之間都有一條連線(樹枝)。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的樹葉結點自左至右排列起來就是一個句型。 構造語法樹構造語法樹第第2章章 前后文無關文法和語言前后文無關文法和語言EEEE*Eiii第一代第二代第三代第四代 圖2-2 句子i+i*i的語法樹 第第2章章 前后文無關文法和語言前后文無關文法和語言GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T

45、F+T a+T a+T*F a+F*F a+a*F a+a*a E EE + T E + T T E E + T T F第第2章章 前后文無關文法和語言前后文無關文法和語言上下文無關文法的語法樹的用處上下文無關文法的語法樹的用處用于描述上下文無關文法用于描述上下文無關文法句型推導句型推導的的直觀方法直觀方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的語法樹語法樹（推導樹）（推導樹）葉子結點葉子結點：樹中：樹中沒有子孫的結點沒有子孫的結點。從左到右從左到右讀出推導樹的讀出推導樹的葉子標記葉子標記連接成的連接成的文文法符號法符

46、號串串，為，為GS的的句型句型。也把該推導樹稱。也把該推導樹稱為該為該句型句型的的語法樹語法樹。第第2章章 前后文無關文法和語言前后文無關文法和語言上下文無關文法的語法樹上下文無關文法的語法樹推導過程中推導過程中施用施用產(chǎn)生式產(chǎn)生式的的順序順序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第第2章章 前后文無關文法和語言前后文無關文法和語言 一棵語法樹表示了一個句型的種種可能的(但未必是所有的)不同推

47、導過程，包括最左(最右)推導。但是，一個句型是否只對應唯一的一棵語法樹呢?一個句型是否只有唯一的一個最左(最右)推導呢? 第第2章章 前后文無關文法和語言前后文無關文法和語言例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個不同的最左推導：的兩個不同的最左推導：推導推導1：E E+E E*E+E i*E+E i*i+E i*i+i推導推導2：E E*E i*E i

48、*E+E i*i+E i*i+i第第2章章 前后文無關文法和語言前后文無關文法和語言 在構造語法樹時可以發(fā)現(xiàn)，一個句型的最左推導及最右推導只是決定先生長左子樹還是先生長右子樹，句型推導結束時相應的語法樹也隨之完成，這時已不能看出是先生長左子樹還是先生長右子樹，所呈現(xiàn)的只是已經(jīng)長成的這個句子或句型的語法樹，這與使用文法規(guī)則進行推導是有差異的，即使用文法規(guī)則的推導過程是有先后之分的。 第第2章章 前后文無關文法和語言前后文無關文法和語言二義文法二義文法文法GS的一個句子如果能找到兩種不同的最左推導(或最右推導)，或者存在兩棵不同的語法樹，則稱這個句子是二義性的。一個文法如果包含二義性的句子，則這個

49、文法是二義文法，否則是無二義文法。例如，對文法GE，句子i+i*i存在著兩種最左推導或最右推導，所形成的兩棵不同的語法樹如圖23所示。第第2章章 前后文無關文法和語言前后文無關文法和語言EEEE*EiEEEE*Eiii(a)ii(b)圖23 句子i+i*i的兩棵不同語法樹第第2章章 前后文無關文法和語言前后文無關文法和語言 再如，條件語句的文法GS為： GS: Sif B S Sif B S else S SA /*A指其它語句*/ 其中，VN = B,S,A，VT=if, else，則句型if B if B S else S所對應的兩棵不同語法樹見圖24。因此，文法GS是二義性文法。 第第2

50、章章 前后文無關文法和語言前后文無關文法和語言SifS(a)(b)BSifSelseBSBSifSelseifSB圖24 句型 if B if B S else S 的兩棵不同語法樹 第第2章章 前后文無關文法和語言前后文無關文法和語言 哪一個是正確的則取決于將單個else部分與第1個或第2個if語句結合：第1個分析樹將else部分與第1個if語句結合；第2個分析樹將它與第2個if語句結合。這種二義性稱作懸掛else問題。 可生成帶有兩個不同分析樹的串的文法稱作二義性文法。由于這個文法并不能準確地指出程序的語法結構，所以它是分析程序表示的一個嚴重問題。 第第2章章 前后文無關文法和語言前后文無

51、關文法和語言解決二義性的基本方法有兩個解決二義性的基本方法。其一是：設置一個規(guī)則，該規(guī)則可在每個二義性情況下指出哪一個分析樹（或語法樹）是正確的。這樣的規(guī)則稱作消除二義性規(guī)則。這樣的規(guī)則的用處在于：它無需修改文法（可能會很復雜）就可消除二義性；它的缺點在于語言的語法結構再也不能由文法單獨提供了。例如，我們強制規(guī)定else與最近的一個if匹配。另一種方法是通過重寫文法而消除二義性，將文法改變成一個強制正確分析樹的構造的格式，這樣就可以解決二義性了。 第第2章章 前后文無關文法和語言前后文無關文法和語言 例如，可以把文法改寫成下面無二義的文法。 stmt matched _stmt | unmat

52、ched_stmt matched_stmtif expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt 注意，unmatched_stmt的第二個產(chǎn)生式的右部if expr then matched_stmt else unmatched_stmt的matched_stmt 和和unmatched_stmt是不能對調的，否則仍然是二義的。第第2章章 前后文無關文法和語言前后文無關文法和語言為

53、什么文法中要保留二義性我們總希望一個文法是無二義性的，這樣，句子的分析可以按惟一確定的方式進行。但是，文法的二義性是不可判定的，即不存在一種算法，能夠在有限步內判定一個文法是否為二義性的。有時候，二義性文法也可帶來一定的好處，如語法分析中二義性文法的應用，從而使文法保持了簡潔性。定義語言語法的文法有二義并不可怕，只要有消除二義性的規(guī)則就可以了。第第2章章 前后文無關文法和語言前后文無關文法和語言句型的分析句型分析句型分析就是就是識別識別一個符號串是否為某文法一個符號串是否為某文法的的句型句型，是某個，是某個推導推導的構造過程。的構造過程。在語言的編譯實現(xiàn)中，把在語言的編譯實現(xiàn)中，把完成句型分析

54、完成句型分析的的程程序序稱為稱為分析程序分析程序或或識別程序識別程序。分析算法又。分析算法又稱稱識別算法識別算法。從左到右的分析算法從左到右的分析算法，即，即總是從總是從左左到到右右地地識識別輸入符號串別輸入符號串，首先識別符號串中的，首先識別符號串中的最左最左符號，進而符號，進而依次識別右邊依次識別右邊的一個符號，的一個符號，直直到分析結束到分析結束。第第2章章 前后文無關文法和語言前后文無關文法和語言句型的分析算法分類自上而下分析法自上而下分析法：從文法的開始符號出發(fā)從文法的開始符號出發(fā)，反復使用文法的，反復使用文法的產(chǎn)生式，產(chǎn)生式，尋找尋找與與輸入符號串輸入符號串匹配匹配的的推導推導。自

55、下而上分析法自下而上分析法：從從輸入符號串輸入符號串開始開始，逐步進行逐步進行歸約歸約，直至，直至歸約歸約到到文法的文法的開始符號開始符號。 第第2章章 前后文無關文法和語言前后文無關文法和語言兩種方法反映了兩種語法樹的構造過程。兩種方法反映了兩種語法樹的構造過程。自上而下方法自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結果正好是輸入符號串自下而上方法自下而上方法則是從輸入符號串開始，以它做為語法樹的結果，自底向上地構造語法樹第第2章章 前后文無關文法和語言前后文無關文法和語言自上而下的語法分析自上而下的語法分析例：文法例：文法G：S cAd A ab A

56、a識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導過程：推導過程：S cAd cAd cabd第第2章章 前后文無關文法和語言前后文無關文法和語言自下而上的語法分析自下而上的語法分析例：文法例：文法G： S cAd A ab A a識別輸入串識別輸入串w=cabd是否該文法的是否該文法的句子句子SAA c a b d c a b d c a b d 規(guī)約規(guī)約過程構造的推導：過程構造的推導： cAd cabd S cAd第第2章章 前后文無關文法和語言前后文無關文法和語言(1)S cAd (2) A ab (3)A a識別輸入串識別輸入串w=ca

57、bd是否為該文法的是否為該文法的句子句子自上而下的語法分析自上而下的語法分析若S cAd 后選擇(3)擴展A，S cAd cad那將會？ w的第二個符號可以與葉子結點a得以匹配，但第三個符號卻不能與下一葉子結點d匹配，宣告分析失?。ㄆ湟馕吨?，識別程序不能為串cad構造語法樹，即cad不是句子）-顯然是錯誤的結論。導致失敗的原因是在分析中對A的選擇不是正確的。 S c A d a第第2章章 前后文無關文法和語言前后文無關文法和語言(1)S cAd (2) A ab (3)A a識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子自下而上的語法分析自下而上的語法分析 對串cabd的

58、分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么最終就達不到歸約到S的結果，因而也無從知道cabd是一個句子c a b d c A b d a第第2章章 前后文無關文法和語言前后文無關文法和語言句型分析的有關問題1 1）在自上而下的分析方法中）在自上而下的分析方法中如何如何選擇選擇使用使用哪個哪個產(chǎn)生式產(chǎn)生式進行推導進行推導？假定要被代換的最左非終結符號是假定要被代換的最左非終結符號是B B，且有，且有n n條規(guī)則：條規(guī)則：BA1|A2|AnBA1|A2|An，那么如何確定用哪個右部去替代，那么如何確定用哪個右部去替代B B？2 2）在自下而上的分析方法中）

59、在自下而上的分析方法中如何如何識別可歸約串識別可歸約串？在分析程序工作的每一步，都是從當前串中在分析程序工作的每一步，都是從當前串中選擇一選擇一個個子串子串，將它，將它歸約歸約到到某個非終結符號某個非終結符號，該子串稱為，該子串稱為“可歸約串可歸約串”第第2章章 前后文無關文法和語言前后文無關文法和語言刻畫刻畫“可歸約串可歸約串”文法文法GSGS句型的短語句型的短語S S = A A且且 A A = ，則稱，則稱是是句型句型相對相對于非終結符于非終結符A A的的短語短語句型的直接短語句型的直接短語若有若有A A ，則稱，則稱是句型是句型相對于非終結符相對于非終結符A A 的的直接短語直接短語句

60、型的句柄句型的句柄一個句型的一個句型的最左直接短語最左直接短語稱為稱為該句型該句型的的句柄句柄*+第第2章章 前后文無關文法和語言前后文無關文法和語言一個有用的定理一個有用的定理n 定義：定義：由某一結點及其所屬分支組成的部分樹稱為由某一結點及其所屬分支組成的部分樹稱為原樹的一顆子樹。只有單層分支的子樹稱為簡單子原樹的一顆子樹。只有單層分支的子樹稱為簡單子樹。樹。n 定理：定理： 1.1.每個句型都有一顆語法樹，每個語法樹的葉組成每個句型都有一顆語法樹，每個語法樹的葉組成一句型。一句型。 2.2.每棵子樹的葉組成短語，每顆簡單子樹的葉組成每棵子樹的葉組成短語，每顆簡單子樹的葉組成簡單短語，最左