前后文無關(guān)文法和語言

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

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

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

4、人英語謂語=動(dòng)詞直接賓語動(dòng)詞=是學(xué)習(xí)直接賓語=代詞名詞 第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言 “我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言英語句子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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言語言概述語言概述n 語言是由句子組成的集合，是由一組記號所構(gòu)成的語言是由句子組成的集合，是由一組記號所構(gòu)成的集合。集合。n 漢語漢語-所有符合漢語語法的句子的全體所有符合漢語語法的句子的全體n 英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體n 程序設(shè)計(jì)語言程序設(shè)計(jì)語言-所有

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

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

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

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

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

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

12、前后文無關(guān)文法和語言符號串的運(yùn)算符號串的運(yùn)算符號串的符號串的長度長度：符號串中符號的個(gè)數(shù)：符號串中符號的個(gè)數(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個(gè)個(gè)a aa a1

13、1=a, a=a, a2 2=aa=aa則則a a0 0=符號串符號串集合集合：若集合：若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符號串，則稱的符號串，則稱A A為字母表為字母表 上的符號串集合。上的符號串集合。第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言兩個(gè)符號串集合兩個(gè)符號串集合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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言語言語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。換言之,字母表上的一個(gè)語言是上的一些符號串的集合 (字母表上的每個(gè)語言是*的一

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

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

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

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

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

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

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

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

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

24、關(guān)文法和語言圖21 奇數(shù)劃分示意MB最高位中 間 位DDDA最低位第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言 由于中間部分可出現(xiàn)任意位，所以另引入了一個(gè)非終結(jié)符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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言推導(dǎo)推導(dǎo) 推導(dǎo)把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結(jié)符用其產(chǎn)生式右部的串來代替。亦即：從識(shí)別符號開始，不斷將

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

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

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

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

29、型、句子的定義句型句型：有文法G，若S = x，則稱x是文法G的句型。句子句子：有文法G，若S = x，且xVT*，則稱x是文法G的句子。由定義可知，僅含終結(jié)符的句型是一個(gè)句子。開始符S本身只能是文法的一個(gè)句型而不可能是一個(gè)句子；此外，上面推導(dǎo)出的i+i*i是文法GE的一個(gè)句子(當(dāng)然也是一個(gè)句型)，而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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語

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，+ +，* *，( (和和) )構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)式第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言文法，語言的定義文法，語言的定義由文法由文法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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bE

32、be) aabbee （eEee)G生成的每個(gè)串都在L(G)中L(G)中的每個(gè)串確實(shí)能被G生成第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言使用產(chǎn)生式(1)n-1次，得到推導(dǎo)序列：S=an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S=an-1S(BE)n-1 an(BE)n。然后從an(BE)n繼續(xù)推導(dǎo)，總是對EB使用產(chǎn)生式(3)的右部進(jìn)行替換，而最終在得到的串中，所有的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是唯一形式的終結(jié)符號串 *第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言n已知語言描述，寫出文法已知語言描述，寫出文法y例：若語言由例：若語言由0 0、1 1符號串組成，串中符號串組成，串中0 0和和1 1的個(gè)的個(gè)數(shù)相同，構(gòu)造其文法。數(shù)相同，構(gòu)造其文法。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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言文法的等價(jià)文法的等價(jià)若若L(GL(G1 1)=L(G)=L(G2 2) )，則稱文法，則稱文法G G1 1和和G G2 2是等價(jià)的。是等價(jià)的。如文法如文法G G1 1AA：A0R A0R 與與G G2 2SS：S0S1 S0S1 等價(jià)等價(jià) A01 S01A01 S01 RA1 RA1第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言文法的類型文法的類型 語言學(xué)家NoamChomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，并分別

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

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

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

38、ADaD C C BDbD BDbD D D AabD AabD第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言例：例：2 2型（上下文無關(guān)）文法型（上下文無關(guān)）文法 文法文法GS：SABAB ABS|0BS|0 BSA|1SA|1第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言例：例：3 3型（正規(guī)）文法型（正規(guī)）文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0GI：I lTI lT lTT dTT lT d第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言 四類文法的關(guān)系與區(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)生式左部存在含有終結(jié)符號的符號串或兩個(gè)以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個(gè)的非終結(jié)符號。第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言2型文法型文法1型文法型文法0型文法型文法四種四種文法文法之間之間的的逐級逐級“包含包含”關(guān)系關(guān)系3型文法型文法第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的

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

41、se語句第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言句型、推導(dǎo) 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推導(dǎo)序列中的每一步推導(dǎo)都是對句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jì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推導(dǎo)序列中的每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換 ）EE+T T+T T+T*F F+T*F F+F*Fa+F*F a+F*a a+a*a （推導(dǎo)序列中的每一步

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

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

44、它對應(yīng)的產(chǎn)生式右部的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符所對應(yīng)的結(jié)點(diǎn)就產(chǎn)生出下一代新結(jié)點(diǎn)，即候選式中從左至右的每一個(gè)符號都依次順序?qū)?yīng)一個(gè)新結(jié)點(diǎn)，且每個(gè)新結(jié)點(diǎn)與其父結(jié)點(diǎn)之間都有一條連線(樹枝)。在一棵語法樹生長過程中的任何時(shí)刻，所有那些沒有后代的樹葉結(jié)點(diǎn)自左至右排列起來就是一個(gè)句型。 構(gòu)造語法樹構(gòu)造語法樹第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言EEEE*Eiii第一代第二代第三代第四代 圖2-2 句子i+i*i的語法樹 第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言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章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言上下文無關(guān)文法的語法樹的用處上下文無關(guān)文法的語法樹的用處用于描述上下文無關(guān)文法用于描述上下文無關(guān)文法句型推導(dǎo)句型推導(dǎo)的的直觀方法直觀方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的語法樹語法樹（推導(dǎo)樹）（推導(dǎo)樹）葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：樹中：樹中沒有子孫的結(jié)點(diǎn)沒有子孫的結(jié)點(diǎn)。從左到右從左到右讀出推導(dǎo)樹的讀出推導(dǎo)樹的葉子標(biāo)記葉子標(biāo)記連接成的連接成的文文法符號法符

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

47、導(dǎo)過程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢? 第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言例：例：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 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i

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

49、文法是二義文法，否則是無二義文法。例如，對文法GE，句子i+i*i存在著兩種最左推導(dǎo)或最右推導(dǎo)，所形成的兩棵不同的語法樹如圖23所示。第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言EEEE*EiEEEE*Eiii(a)ii(b)圖23 句子i+i*i的兩棵不同語法樹第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言 再如，條件語句的文法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所對應(yīng)的兩棵不同語法樹見圖24。因此，文法GS是二義性文法。 第第2

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

51、關(guān)文法和語言解決二義性的基本方法有兩個(gè)解決二義性的基本方法。其一是：設(shè)置一個(gè)規(guī)則，該規(guī)則可在每個(gè)二義性情況下指出哪一個(gè)分析樹（或語法樹）是正確的。這樣的規(guī)則稱作消除二義性規(guī)則。這樣的規(guī)則的用處在于：它無需修改文法（可能會(huì)很復(fù)雜）就可消除二義性；它的缺點(diǎn)在于語言的語法結(jié)構(gòu)再也不能由文法單獨(dú)提供了。例如，我們強(qiáng)制規(guī)定else與最近的一個(gè)if匹配。另一種方法是通過重寫文法而消除二義性，將文法改變成一個(gè)強(qiáng)制正確分析樹的構(gòu)造的格式，這樣就可以解決二義性了。 第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言 例如，可以把文法改寫成下面無二義的文法。 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的第二個(gè)產(chǎn)生式的右部if expr then matched_stmt else unmatched_stmt的matched_stmt 和和unmatched_stmt是不能對調(diào)的，否則仍然是二義的。第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言為

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

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

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

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

57、bd是否為該文法的是否為該文法的句子句子自上而下的語法分析自上而下的語法分析若S cAd 后選擇(3)擴(kuò)展A，S cAd cad那將會(huì)？ w的第二個(gè)符號可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號卻不能與下一葉子結(jié)點(diǎn)d匹配，宣告分析失敗（其意味著，識(shí)別程序不能為串cad構(gòu)造語法樹，即cad不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對A的選擇不是正確的。 S c A d a第第2章章 前后文無關(guān)文法和語言前后文無關(guān)文法和語言(1)S cAd (2) A ab (3)A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子自下而上的語法分析自下而上的語法分析 對串cabd的

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

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

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