編譯原理形式語言基礎(chǔ)

（優(yōu)選）編譯原理第章形式語言基礎(chǔ)本文檔共152頁；當前第1頁；編輯于星期二\21點40分1一、語言的定義

任何一種語言都是在某個特定字母表上定義的、按照一定的規(guī)則構(gòu)成的字符串的集合。本文檔共152頁；當前第2頁；編輯于星期二\21點40分2二、形式語言提出

形式語言是研究符號的語言，它僅考慮符號間的關(guān)系，不考慮含義，即用數(shù)學(xué)方法（主要是代數(shù)方法）對語言進行形式化描述。

1956年N.Chomsky(喬姆斯基）在研究自然語言過程中提出一種文法數(shù)學(xué)模型，為形式語言理論打下了基礎(chǔ)，成為計算機科學(xué)理論一個重要分支，即形式語言與自動機。本文檔共152頁；當前第3頁；編輯于星期二\21點40分3三、語言描述方法枚舉法文法生成法：就是用有限個規(guī)則來產(chǎn)生出語言中無限個句子，這種規(guī)則集合稱文法。自動機識別法：用自動機對語言中的句子進行識別本文檔共152頁；當前第4頁；編輯于星期二\21點40分4四、與語言有關(guān)的幾個概念元語言：可用來描述其它語言的一種語言語法：是在字母表上構(gòu)造句子的一組規(guī)則語義：是按照語法規(guī)則所構(gòu)成結(jié)構(gòu)的含義語用：是表示語言符號與使用者關(guān)系本文檔共152頁；當前第5頁；編輯于星期二\21點40分5§2.2符號和符號串

一、字母表二、符號串三、符號串集合本文檔共152頁；當前第6頁；編輯于星期二\21點40分6一、字母表

有限個元素的非空集合稱字母表，也稱符號集。它是組成一個語言最基本的成分。字母表中元素稱符號。習(xí)慣上用V、Σ或其它大寫字母表示。例如V={a,b,c}，V={α,β…ω}|V|表示字母表中符號的個數(shù)。對于不同程序設(shè)計語言有不同字母表。例如，機器語言字母表={0,1}，PASCAL語言的字母表由字母、數(shù)字以及一些特殊符號，如+，-，*，/，·，(，)，=，…等組成。

注意：在一個語言中不能出現(xiàn)字母表以外的符號。本文檔共152頁；當前第7頁；編輯于星期二\21點40分7二、符號串

1、定義

符號串是字母表中的符號所組成的任何有窮序列(有時也稱為符號行或字)例如：設(shè)V={a,b,c},則符號串有a,b,c,aa,ab,ac,ba,abc…又如：設(shè)V={0,1},則符號串有

0，1，00，01，10，11，000…

由上例可以看出，符號串與符號組成順序有關(guān)，如符號串a(chǎn)b不同于ba，符號串01不同于10，今后我們常用t,u,v,…x,y,z等小寫字母表示符號串。本文檔共152頁；當前第8頁；編輯于星期二\21點40分82、空符號串

不包含任何符號的符號串稱為空符號串，記為ε。3、符號串長度

符號串中所含符號個數(shù)稱為該符號串的長度，設(shè)符號串為x，則用|x|來表示x的長度。例如：x=abc，則|x|=3,顯然,|ε|=0。本文檔共152頁；當前第9頁；編輯于星期二\21點40分94、關(guān)于符號串的幾種運算

（1）符號串的聯(lián)結(jié)設(shè)有符號串x和y，則它們的聯(lián)結(jié)xy是將符號串y直接拼接在符號串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn

則

xy

=x1x2x3…xmy1y2y3…yn

顯然εx=x，xε=x

本文檔共152頁；當前第10頁；編輯于星期二\21點40分10（2）符號串的方冪

若x是符號串則x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n個）如x=abc則x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩本文檔共152頁；當前第11頁；編輯于星期二\21點40分11三、符號串集合舉例：字母表V={a,b}，問用V中的符號，可以組成哪些符號串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,…1、定義：若集合A中的一切元素都是字母表V上的符號串，則稱A為字母表V上的符號串集合本文檔共152頁；當前第12頁；編輯于星期二\21點40分12V*定義：字母表V上各種長度符號串構(gòu)成串集合，記為V*，不包括空行的集合記為V+即V*={x|x是V上符號串且包括空符號串}V+={x|x是V上符號串且不包括空符號串}V+=V*-{ε}如：V={a,b}，則V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}本文檔共152頁；當前第13頁；編輯于星期二\21點40分132、關(guān)于串集合的運算（1）串集合乘積設(shè)A和B為兩個符號串集合，并包含于V*，則A和B的乘積定義為：AB={xy|x∈A且y∈B}由此定義，乘積AB是滿足x∈A且y∈B的所有符號串xy所組成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}如果A={0，101}B={10，11，110}則AB={010，011，0110，10110，10111，101110}符號?表示空集

本文檔共152頁；當前第14頁；編輯于星期二\21點40分14（2）符號串集合的方冪設(shè)符號串集合A則A的方冪運算定義為：A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n個）如：設(shè)A={a,b}，則A0={ε},A1={a,b}A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}本文檔共152頁；當前第15頁；編輯于星期二\21點40分15(3)符號串集合的閉包和正閉包

設(shè)A為符號串集合，則A的正閉包定義為A+=A1∪A2∪…∪An∪…符號串集合A的閉包定義為A*=A0∪A+={ε}∪A+

如A={a,b}則A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}我們可以證明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…）=A1∪A2∪…An∪…=A+本文檔共152頁；當前第16頁；編輯于星期二\21點40分16作業(yè)：

P.38：習(xí)題2、3本文檔共152頁；當前第17頁；編輯于星期二\21點40分17§2.3文法與語言一、巴科斯范式BNF(BackusNormalForm)二、語法樹三、產(chǎn)生式（規(guī)則）四、文法五、推導(dǎo)和歸約六、句型和句子七、語言八、遞歸文法九、短語和簡單短語十、最左推導(dǎo)和最右推導(dǎo)十一、文法二義性本文檔共152頁；當前第18頁；編輯于星期二\21點40分18一、巴科斯范式BNF例子：Themanhasadog.(這人有一條狗）我們以“∷=”符號(或“→”符號)表示”定義為”，以“|”符號表示“或”，以“<>”符號表示語法實體(語法單位)，這些符號是元語言符號，本文檔共152頁；當前第19頁；編輯于星期二\21點40分19①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the|a④<名詞>∷=man|book|dog⑤<謂語>∷=<動詞><賓語>⑥<動詞>∷=has⑦<賓語>∷=<冠詞><名詞>我們把這種描述語法規(guī)則方法稱巴科斯范式，也稱為巴科斯--瑙爾范式(BackusNormalForm)，簡稱BNF。那么上面敘述<句子>的語法規(guī)則可寫為：本文檔共152頁；當前第20頁；編輯于星期二\21點40分20例如,在高級語言中大家所熟知的<標識符>這種語法成分,它用巴科斯范式描述為:<標識符>∷=<字母>|<標識符><字母>|<標識符><數(shù)字><字母>∷=A|B|C|D|…|Z|a|b|…|z<數(shù)字>∷=0|1|2|…|9這樣便刻畫出了<標識符>是以字母開始的一串字母和數(shù)字任意組合這種特點。本文檔共152頁；當前第21頁；編輯于星期二\21點40分21如果定義<句子>的巴科斯范式改為：①〈句子〉∷=<主語><謂語>②〈主語〉∷=We|He|I③〈謂語〉∷=ran|ate|sat則下面9個句子都是正確的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat可見，如果一個語言有無窮多個句子，那么用上述規(guī)則來描述更有實際意義.它用一組規(guī)則來代替枚舉法，用有窮來描述無限。本文檔共152頁；當前第22頁；編輯于星期二\21點40分22二、語法樹

除了上面可以根據(jù)語言語法規(guī)則來推導(dǎo)出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結(jié)構(gòu)關(guān)系，稱語法樹。

本文檔共152頁；當前第23頁；編輯于星期二\21點40分23<句子>（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）本文檔共152頁；當前第24頁；編輯于星期二\21點40分24（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語>①<句子>∷=<主語><謂語>本文檔共152頁；當前第25頁；編輯于星期二\21點40分25（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><謂語><主語><名詞><冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>本文檔共152頁；當前第26頁；編輯于星期二\21點40分26（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語>the<名詞><冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the|a本文檔共152頁；當前第27頁；編輯于星期二\21點40分27（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞>manthe<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④<名詞>∷=man本文檔共152頁；當前第28頁；編輯于星期二\21點40分28（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manthe<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④<名詞>∷=man⑤<謂語>∷=<動詞><賓語>本文檔共152頁；當前第29頁；編輯于星期二\21點40分29（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhasthe<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④⑤<謂語>∷=<動詞><賓語>⑥<動詞>∷=has本文檔共152頁；當前第30頁；編輯于星期二\21點40分30（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>the<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④⑤<謂語>∷=<動詞><賓語>⑥⑦本文檔共152頁；當前第31頁；編輯于星期二\21點40分31（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>athe<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④⑤<謂語>∷=<動詞><賓語>⑥⑦③本文檔共152頁；當前第32頁；編輯于星期二\21點40分32（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>abookthe<冠詞>①<句子>∷=<主語><謂語>②<主語>∷=<冠詞><名詞>③<冠詞>∷=the④⑤<謂語>∷=<動詞><賓語>⑥⑦③④本文檔共152頁；當前第33頁；編輯于星期二\21點40分33（句子themanhasabook的推導(dǎo)過程及對應(yīng)的語法樹）<句子><主語><謂語><名詞><動詞><賓語>manhas<名詞><冠詞>abookthe<冠詞>本文檔共152頁；當前第34頁；編輯于星期二\21點40分34其中：<句子>稱為語法樹根帶<>和不帶<>的都稱為語法樹的結(jié)點一個結(jié)點以及向下射出部分稱為子樹沒有向下射出部分的結(jié)點稱為末端結(jié)點本文檔共152頁；當前第35頁；編輯于星期二\21點40分35三、產(chǎn)生式（規(guī)則）

1.定義

產(chǎn)生式(規(guī)則)就是一個符號與另一個符號串的有序偶(U,x),通常記為U→x或U∷=x其中：U是符號,x是有限非空符號串。

U稱為規(guī)則的左部,x稱為規(guī)則的右部如果U→x1，U→x2，U→x3，…，U→xn可以寫成U→x1|x2|…|xn,并稱xi是U的一個候選式。本文檔共152頁；當前第36頁；編輯于星期二\21點40分362.字匯表(符號表)

（1）定義用于規(guī)則左部和右部中所有符號形成集合為字匯表，記為V。

本文檔共152頁；當前第37頁；編輯于星期二\21點40分37（2）分類1）非終結(jié)符號

出現(xiàn)在規(guī)則左部,且能派生出符號或符號串的那些符號稱為非終結(jié)符,也稱語法實體或語法單位,它們的全體構(gòu)成一個非終結(jié)符的集合,記為VN

2）終結(jié)符

規(guī)則中不屬于VN的那些符號,稱為終結(jié)符,它們的全體組成終結(jié)符的集合,記為VT。終結(jié)符一般出現(xiàn)在規(guī)則的右部。顯然,V=VN∪VT,VN∩VT=?本文檔共152頁；當前第38頁；編輯于星期二\21點40分38如：在PASCAL中，對標識符的定義規(guī)則為：<標識符>∷=<字母>|<標識符><字母>|<標識符><數(shù)字><字母>∷=a|b|…|z|A|B|…|Z<數(shù)字>∷=0|1|…|9由此得：VN

={<字母>,<數(shù)字>,<標識符>}VT={a,b,…,z,A,B,…Z,0,1,…9}本文檔共152頁；當前第39頁；編輯于星期二\21點40分39例如：有產(chǎn)生式:S∷=0S1S∷=01則VN={S}VT={0,1}V={S,0,1}本文檔共152頁；當前第40頁；編輯于星期二\21點40分40四、文法為研究方便，下面給出文法的形式定義定義：文法是規(guī)則的有窮集合,形式定義為四元組形式為G=(VN,VT,P,Z)其中：VN是非終結(jié)符集合,VT是終結(jié)符集合,P代表產(chǎn)生式集,Z∈VN是文法G開始符號,也稱識別符號,它至少要在一條產(chǎn)生式左部出現(xiàn)。文法G通常記為G［Z］。本文檔共152頁；當前第41頁；編輯于星期二\21點40分41對于前面英語句子的例子中用7條文法規(guī)則來描述英語句子,其文法可表示為G=(VN,VT,P,Z)其中:VN={<句子>，<主語>，<謂語>，<賓語>，<冠詞>，<動詞>，<名詞>}VT={the,a,man,book,dog}P是前述7條規(guī)則Z=<句子>本文檔共152頁；當前第42頁；編輯于星期二\21點40分42又例如：標識符文法可定義如下:G［Z］=(VN,VT,P,Z)VN={<字母>,<數(shù)字>,<標識符>}VT={a,b,…,z,A,B,…,Z,0,1,…9}Z=<標識符>P由下列規(guī)則組成:<標識符>∷=<字母>|<標識符><字母>|<標識符><數(shù)字><字母>∷=a|b|…|z|A|B|…|Z<數(shù)字>∷=0|1|…|9本文檔共152頁；當前第43頁；編輯于星期二\21點40分43五、推導(dǎo)和歸約

定義1設(shè)G為一個文法，U∷=u是G中一個規(guī)則，x和y是V*上符號串，使得v=xUy與w=xuy則稱符號串v直接推導(dǎo)出符號串w，或稱w直接歸約到v，并把w叫做v直接派生式，記作vw若x=y=ε，則v=xUy=U，w=xuy=u可見vw即Uu說明一個規(guī)則就是一個直接推導(dǎo)例如<句子>直接推導(dǎo)到<主語><謂語>，而<主語><謂語>直接歸約到<句子>。

本文檔共152頁；當前第44頁；編輯于星期二\21點40分44例如:

G=(VN,VT,P,S)VN={S},VT={0,1}P:S∷=0S1S∷=01

令v=xSy,w=x01y,因S∷=01(U∷=u)即vwxSyx01y若x=y=ε則S01(一個規(guī)則就是一個直接推導(dǎo))同樣S∷=0S1

v=00S11，w=000S111Uu即vw00S11000S111本文檔共152頁；當前第45頁；編輯于星期二\21點40分45又如：標識符文法定義如下:G［Z］=(VN,VT,P,Z)VN={<字母>,<數(shù)字>,<標識符>}VT={a,b,…,z,A,B,…,Z,0,1,…9}P由下列規(guī)則組成:

<標識符>∷=<字母>|<標識符><字母>|<標識符><數(shù)字>

<字母>∷=a|b|…|z|A|B|…|Z<數(shù)字>∷=0|1|…|9Z=<標識符>則有：<標識符><標識符><字母>

<標識符>a本文檔共152頁；當前第46頁；編輯于星期二\21點40分46定義2

設(shè)u0,u1,u2,…,un均為V*上符號串,若w是v經(jīng)過一系列直接推導(dǎo)得到的,即v=u0

u1

u2

…un-1

un=w(n>0)則稱v推導(dǎo)到w,或稱w歸約到v,記作v+w稱這個直接推導(dǎo)序列為長度為n的推導(dǎo)。如果v+w或者v=w(表示0步推導(dǎo)),則記作v*w稱v廣義推導(dǎo)到w或稱w廣義歸約到v。

顯然,直接推導(dǎo)的長度為1,推導(dǎo)

+的長度≥1,而廣義推導(dǎo)

*的長度≥0例如在前面的例子中,因S∷=0S1

S∷=01

0S100S11000S11100001111所以0S1+00001111(n=3)本文檔共152頁；當前第47頁；編輯于星期二\21點40分47例設(shè)有文法G［<整數(shù)>］:(1)<整數(shù)>∷=<數(shù)字串>(2)<數(shù)字串>∷=<數(shù)字串><數(shù)字>(3)<數(shù)字串>∷=<數(shù)字>(4)<數(shù)字>∷=0(5)<數(shù)字>∷=1(6)<數(shù)字>∷=2(7)<數(shù)字>∷=3(8)<數(shù)字>∷=4(9)<數(shù)字>∷=5(10)<數(shù)字>∷=6(11)<數(shù)字>∷=7(12)<數(shù)字>∷=8(13)<數(shù)字>∷=9整數(shù)23的推導(dǎo)過程:<整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字><數(shù)字>2<數(shù)字>23因此,<整數(shù)>+23,其推導(dǎo)長度為5。顯而易見,在推導(dǎo)時,任意地選取規(guī)則(4)到(13),就可以推導(dǎo)得到任意整數(shù)。本文檔共152頁；當前第48頁；編輯于星期二\21點40分48六、句型和句子定義：設(shè)G［Z］是一文法,若符號串x是由識別符Z推導(dǎo)而得,即Z*xx∈V*則稱符號串x為該文法G的一個句型。如果一個句型x僅由終結(jié)符組成,即Z*xx∈VT*則稱句型x為該文法一個句子。例如：在書中的例2.16中,<整數(shù)>,<數(shù)字><數(shù)字>,2<數(shù)字>,23等都是文法G[<整數(shù)>]的句型,其中僅23是句子。

可見：句子一定是句型，而句型未必是句子。一個正確的源程序是句子。本文檔共152頁；當前第49頁；編輯于星期二\21點40分49七、語言定義：設(shè)G［Z］為一文法,由該文法所產(chǎn)生的一切句子的集合稱為由該文法所定義的語言,記為L(G［Ｚ］)(或記為L(G)),即L(G)={x|Z*x且x∈VT*}有時我們稱這樣定義的語言為形式語言，以區(qū)別于自然語言。上述公式包含兩層意思：語言是句子集合，是VT*一個子集合，即VT中行集合子集。句子必須由該語言文法識別符推導(dǎo)出。本文檔共152頁；當前第50頁；編輯于星期二\21點40分50例如：G[S]=(VN,VT,P,S)VN={S}VT={0,1}P:{S∷=01,S∷=0S1}S:識別符很容易推出：L（G）={0n1n|n≥1}本文檔共152頁；當前第51頁；編輯于星期二\21點40分51又如：寫一個文法，使其語言為偶整數(shù)集合。首先分析以下偶整數(shù)（1）偶整數(shù)最后一個數(shù)字應(yīng)該是偶數(shù)字0，2，4，6，8（2）偶整數(shù)前面符號可以是+，-或不帶符號由此得其文法應(yīng)由下列規(guī)則組成：<偶整數(shù)>∷=<符號><偶數(shù)字>|<偶數(shù)字>|<符號><數(shù)字串><偶數(shù)字>|<數(shù)字串><偶數(shù)字><偶數(shù)字>∷=0|2|4|6|8<數(shù)字>∷=1|3|5|7|9|<偶數(shù)字><數(shù)字串>∷=<數(shù)字>|<數(shù)字串><數(shù)字><符號>∷=+|-所以文法可表示為：G=(VN,VT,P,<偶整數(shù)>)其中：VN={<偶整數(shù)>，<偶數(shù)字>，<數(shù)字>，<數(shù)字串>，<符號>}VT={0，1，2，3，4，5，6，7，8，9，+，-}本文檔共152頁；當前第52頁；編輯于星期二\21點40分52對于通常的程序設(shè)計語言其文法為:G［程序］=(VN,VT,P,<程序>)其中VN={<程序>,<說明>,<語句>,…}VT={0,1,…,9,a,…,z,-,(,),…}P={<程序>∷=…,<說明>∷=…,<語句>∷=…,…}L(G)={w|<程序>*w且w∈VT*}由此可知,每一個w就是一個源程序，所謂PASCAL語言也就是所有PASCAL程序的集合。本文檔共152頁；當前第53頁；編輯于星期二\21點40分53作業(yè)：P.38習(xí)題6、7本文檔共152頁；當前第54頁；編輯于星期二\21點40分54八、遞歸文法構(gòu)成一個語言的句子集合可以是有窮的，也可以是無窮的，例如文法G［<句子>］所描述的語言L(G［<句子>］)是有窮的。但文法G［<整數(shù)>］所描述的語言L(G［<整數(shù)>］)是無窮的，它包含無窮多個句子。

本文檔共152頁；當前第55頁；編輯于星期二\21點40分55例如：文法G(<句子>)包含的下列規(guī)則如下：①〈句子〉∷=<主語><謂語>②〈主語〉∷=We|He|I③〈謂語〉∷=ran|ate|sat所描述的語言為：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat本文檔共152頁；當前第56頁；編輯于星期二\21點40分56例如文法G［<整數(shù)>］的規(guī)則如下：(1)<整數(shù)>∷=<數(shù)字串>(2)<數(shù)字串>∷=<數(shù)字串><數(shù)字>(3)<數(shù)字串>∷=<數(shù)字>(4)<數(shù)字>∷=0(5)<數(shù)字>∷=1(6)<數(shù)字>∷=2(7)<數(shù)字>∷=3(8)<數(shù)字>∷=4(9)<數(shù)字>∷=5(10)<數(shù)字>∷=6(11)<數(shù)字>∷=7(12)<數(shù)字>∷=8(13)<數(shù)字>∷=9所描述的語言包括無窮多個句子。本文檔共152頁；當前第57頁；編輯于星期二\21點40分57不難發(fā)現(xiàn)，兩個文法其根本差別在于文法G［<整數(shù)>］有形如<數(shù)字串>∷=<數(shù)字串><數(shù)字>的規(guī)則。在這個規(guī)則中左部和右部皆出現(xiàn)非終結(jié)符<數(shù)字串>。這種借助于自己來定義自己的規(guī)則，即在規(guī)則左部和右部具有相同的非終結(jié)符規(guī)則稱為遞歸規(guī)則。

本文檔共152頁；當前第58頁；編輯于星期二\21點40分58八、遞歸文法

1.

定義對于一個文法,若有一個規(guī)則U∷=…U…,則稱直接遞歸,若有規(guī)則U∷=U…,則稱直接左遞歸,若有規(guī)則U∷=…U,則稱直接右遞歸。若有推導(dǎo)式U+…U…,則稱間接遞歸,若有推導(dǎo)式U+U…,則稱間接左遞歸,若有推導(dǎo)式U+…U,則稱間接右遞歸。非終結(jié)符U稱遞歸非終結(jié)符。如果一個文法中至少含有一個遞歸非終結(jié)符,則將此文法稱為遞歸文法。本文檔共152頁；當前第59頁；編輯于星期二\21點40分59例如：規(guī)則S∷=0S1是直接遞歸規(guī)則A∷=Aa是直接左遞歸規(guī)則B∷=aBB是直接右遞歸

本文檔共152頁；當前第60頁；編輯于星期二\21點40分60例如：設(shè)有文法G的規(guī)則P為S∷=Qc|cQ∷=Rb|bR∷=Sa|a在這些條規(guī)則中,無直接遞歸規(guī)則,但有如下推導(dǎo):QRbSabQcab所以Q+Qcab因此是間接左遞歸。文法G為遞歸文法顯然，直接遞歸是間接遞歸一種特殊情況。

本文檔共152頁；當前第61頁；編輯于星期二\21點40分61八、遞歸文法

2.說明

如果一個語言是無窮的，則描述該語言的文法必定是遞歸的。一般說，程序設(shè)計語言是無窮的，因此描述它們的文法必定是遞歸的。應(yīng)當指出，從語法定義的角度來看，遞歸定義使文法的形式比較簡練，給無限的語言有限的表示提供了一種可用的方法。然而在后面我們將會看到，文法的左遞歸性將會給某些語法分析方法的實現(xiàn)帶來很大的麻煩。

本文檔共152頁；當前第62頁；編輯于星期二\21點40分62九、短語和簡單短語

1.短語和簡單短語2.句柄(柄短語)

3.再談?wù)Z法樹本文檔共152頁；當前第63頁；編輯于星期二\21點40分631.短語和簡單短語定義：設(shè)G［Z］是一文法，w=xuy是其中一句型，若有Z*xUy,U∈VN且U+u,u∈V+則稱u是一個相對于非終結(jié)符U、句型w的短語。若Z*xUy且Uu則稱u是一個相對于非終結(jié)符U、句型w的簡單短語。本文檔共152頁；當前第64頁；編輯于星期二\21點40分64例設(shè)有文法G［S］=({S,A,B},{a,b},P,S),其中P為S∷=ABA∷=Aa|bBB∷=a|Sb找出句型baSb的全部短語，簡單短語.本文檔共152頁；當前第65頁；編輯于星期二\21點40分65根據(jù)句型推導(dǎo)過程有

SABbBBbaBbaSb由上可見，下式成立：S*baB且BSb所以子串Sb是相對于非終結(jié)符B，句型baSb的簡單短語。同樣有SABASbbBSbbaSb即S*bBSb且Ba子串a(chǎn)是相對于B，句型baSb的簡單短語。還有S*ASb且A+ba即子串ba是相對于非終結(jié)符A，句型baSb的短語。對于句型baSb，再沒有其它能產(chǎn)生新的短語推導(dǎo)了，所以句型baSb有短語ba簡單短語a和Sb本文檔共152頁；當前第66頁；編輯于星期二\21點40分662、句柄(柄短語)

定義

一個句型最左邊的簡單短語稱為該句型的句柄(或柄短語)，而且句柄最左邊的符號稱句柄的頭，句柄最右邊的符號稱句柄的尾。

如上例句型baSb簡單短語為a和Sb，由于a是最左簡單短語，所以a又是句柄。

本文檔共152頁；當前第67頁；編輯于星期二\21點40分67例如：設(shè)文法G[S]S∷=AA∷=B|A+BB∷=C|B*CC∷=|(A)現(xiàn)在我們看w=C+B*C句型∵SAA+BB+BC+BC+B*C∴S*C+BBB*C∴B*C是相對于B和句型C+B*C的簡單短語同樣∵SAA+BB+BB+B*CC+B*C∴S*B+B*CBC∴C是相對于B，句型C+B*C的簡單短語。由于C在左邊，所以C是句柄，柄頭和柄尾都是C本文檔共152頁；當前第68頁；編輯于星期二\21點40分683.再談?wù)Z法樹

前面我們曾利用語法樹直觀地描述句子語法結(jié)構(gòu)關(guān)系，現(xiàn)在我們?nèi)匀唤柚谡Z法樹進行句型和句子的推導(dǎo)，同時，利用它尋找短語和簡單短語也是十分直觀和方便的。（1）語法樹形式定義設(shè)有文法G=（VN，VT，P，Z），滿足下列條件的樹即為一個語法樹

a.樹中每一個結(jié)點都有標記，且該標記是VN∪VT中某一符號b.樹根標記是識別符號c.若有一個結(jié)點至少有一個后繼結(jié)點，則該結(jié)點標記必為非終結(jié)符d.若一個標記為U的結(jié)點，它有標記依次為X1，X2,X3，…，Xn的直接后繼結(jié)點，則U∷=X1X2…Xn必定是G的一條規(guī)則。本文檔共152頁；當前第69頁；編輯于星期二\21點40分69SABbBSba我們以書中的例2.22的文法G［S］為例，句型baSb的推導(dǎo),設(shè)有文法G［S］=({S,A,B},{a,b},P,S),其中P為S∷=ABA∷=Aa|bBB∷=a|SbSABbBBbaBbaSb畫出語法樹如下圖所示

本文檔共152頁；當前第70頁；編輯于星期二\21點40分70語法樹中的幾個術(shù)語：①結(jié)點：每個符號(終結(jié)符或非終結(jié)符)對應(yīng)于一個結(jié)點，以符號名為結(jié)點名稱；②邊：兩個結(jié)點間的連線稱為邊；③根結(jié)點：由文法識別符號標記，如S；④分支：從某結(jié)點向下射出的邊連同邊上的結(jié)點稱為分支，分支的深度為1。分支的名字是射出該分支結(jié)點的名字，分支的各個結(jié)點稱為分支結(jié)點；⑤子樹：語法樹的某結(jié)點連同從它向下射出的部分稱為該語法樹的子樹，該結(jié)點稱為子樹根結(jié)點；⑥末端結(jié)點/葉結(jié)點。本文檔共152頁；當前第71頁；編輯于星期二\21點40分71（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB,規(guī)則S∷=AB)。SAB本文檔共152頁；當前第72頁；編輯于星期二\21點40分72（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。SAB本文檔共152頁；當前第73頁；編輯于星期二\21點40分73（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。SABbB本文檔共152頁；當前第74頁；編輯于星期二\21點40分74（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB),(規(guī)則B∷=a)。SABbB本文檔共152頁；當前第75頁；編輯于星期二\21點40分75（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB),(規(guī)則B∷=a)。SABbBa本文檔共152頁；當前第76頁；編輯于星期二\21點40分76（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB),(規(guī)則B∷=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb),(規(guī)則B∷=Sb)。SABbBa本文檔共152頁；當前第77頁；編輯于星期二\21點40分77（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB),(規(guī)則B∷=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb),(規(guī)則B∷=Sb)。SABbBSba本文檔共152頁；當前第78頁；編輯于星期二\21點40分78（2）語法樹構(gòu)造過程句型baSb的語法樹構(gòu)造過程如下：(1)從識別符號S開始,向下畫一分支,表示第一個直接推導(dǎo)(SAB),(規(guī)則S∷=AB)。(2)從分支結(jié)點A出發(fā),向下畫一分支,表示第二個直接推導(dǎo)(ABbBB),(規(guī)則A∷=bB)。(3)再由分支A的分支結(jié)點B向下畫分支,表示第三個直接推導(dǎo)(bBBbaB),(規(guī)則B∷=a)。(4)最后由句型baB中標記B的結(jié)點向下畫分支,表示最后一個推導(dǎo)(baBbaSb),(規(guī)則B∷=Sb)。SABbBSba這時末端結(jié)點自左至右排列起來就是句型baSb。這棵語法樹形象地表示了句型baSb上述推導(dǎo)過程。本文檔共152頁；當前第79頁；編輯于星期二\21點40分79結(jié)論：對于每一個語法樹（或者子樹）至少對應(yīng)一個推導(dǎo)（可能是直接推導(dǎo)?？赡苁莕步推導(dǎo)）對于每個推導(dǎo)必存在有一個語法樹，畫語法樹過程中，每個分支對應(yīng)于一個直接推導(dǎo)。不同推導(dǎo)可能有相同的語法樹。如：SABbBBbaBbaSbSABASbbBSbbaSb同一句型的兩個不同的推導(dǎo)對應(yīng)的語法樹確是相同的。樹的末端結(jié)點標記從左到右連接起來就是要推導(dǎo)的句型或句子本文檔共152頁；當前第80頁；編輯于星期二\21點40分80作業(yè)P.38：習(xí)題8；P.39：習(xí)題11(1)、(2)本文檔共152頁；當前第81頁；編輯于星期二\21點40分81（3）語法樹的作用1）利用語法樹可以構(gòu)造文法的句型；（前面我們已經(jīng)講了句型baSb的語法樹構(gòu)造過程）2）根據(jù)語法樹可以確定短語、簡單短語和句柄；樹末端結(jié)點的符號串是相對于子樹根的短語，分支結(jié)點的符號串是相對于分支名字的簡單短語，最左簡單子樹(只有父子兩代)的末端結(jié)點的符號串是句柄。從右圖語法樹可直觀看出：ba是句型baSb，相對于A的短語，Sb是句型baSb相對于B的簡單短語，a是句型baSb相對于B簡單短語，也是句柄。

3）當給定文法G后，我們可借助于推導(dǎo)語法樹的逆過程把句型推導(dǎo)構(gòu)造出來（見下頁舉例）SABbBSba本文檔共152頁；當前第82頁；編輯于星期二\21點40分82對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSbSABbBSba本文檔共152頁；當前第83頁；編輯于星期二\21點40分83對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSbSABbBSb本文檔共152頁；當前第84頁；編輯于星期二\21點40分84對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSbSABSbbB本文檔共152頁；當前第85頁；編輯于星期二\21點40分85對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSbSABSb本文檔共152頁；當前第86頁；編輯于星期二\21點40分86對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSbSABSb本文檔共152頁；當前第87頁；編輯于星期二\21點40分87對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSbSAB本文檔共152頁；當前第88頁；編輯于星期二\21點40分88對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSb最后剪去分支AB(將AB歸約為S)，得到樹根S，建立了句型baSb推導(dǎo)為SABASbbBSbbaSbSAB本文檔共152頁；當前第89頁；編輯于星期二\21點40分89對于右圖baSb語法樹，最左末端分支是文法G中一條規(guī)則B∷=a，若剪去此分支(將a歸約為B)，則得句型bBSb的語法樹，也就是重新構(gòu)造了一個直接推導(dǎo)為bBSbbaSb此時該語法樹最左末端分支相應(yīng)規(guī)則為A∷=bB，再剪去此分支(即將bB歸約為A)，又得到句型ASb的語法樹，于是又構(gòu)造了推導(dǎo)為ASbbBSbbaSb繼續(xù)下去，再剪去最左末端分支(將Sb歸約為B)，則得句型AB的語法樹，又建立了推導(dǎo)為ABASbbBSbbaSb最后剪去分支AB(將AB歸約為S)，得到樹根S，建立了句型baSb推導(dǎo)為SABASbbBSbbaSbS本文檔共152頁；當前第90頁；編輯于星期二\21點40分90結(jié)論：從語法樹構(gòu)造推導(dǎo)也就是不斷地重復(fù)構(gòu)造最后直接推導(dǎo)和剪去相應(yīng)分支直到無分支可剪過程。對于每個語法樹至少存在一個推導(dǎo)。上例我們選用了最左歸約，即每次剪去最左末端分支，實際上每次歸約是句柄。如果改變剪去相應(yīng)分支順序便將得到不同推導(dǎo)。本文檔共152頁；當前第91頁；編輯于星期二\21點40分91十、最左推導(dǎo)和最右推導(dǎo)對于一給定的文法來說，從其開始符號到某一句型，或從某一句型到另一句型間的推導(dǎo)序列可能不唯一。為了使句型或句子能按照一確定的推導(dǎo)序列來產(chǎn)生，通常我們僅考慮最左推導(dǎo)或最右推導(dǎo)。本文檔共152頁；當前第92頁；編輯于星期二\21點40分92定義1：在任何一步推導(dǎo)vw中，都是對符號串v的最左(右)的非終結(jié)符進行替換，則稱最左(右)推導(dǎo)。

例如：G[S]S∷=ABA∷=Aa|BbB∷=a|SSABbBBbaB------最左推導(dǎo)SABASbAABbAAabAbBab-------最右推導(dǎo)SABASbbBSbbaSb------非左非右推導(dǎo)本文檔共152頁；當前第93頁；編輯于星期二\21點40分93定義2：最右推導(dǎo)叫規(guī)范推導(dǎo)，即在規(guī)范推導(dǎo)過程中，每步直接推導(dǎo)xUyxuy中，符號串y只含有終結(jié)符。如果推導(dǎo)v+w中每一步直接推導(dǎo)是規(guī)范的，則稱推導(dǎo)v+w為規(guī)范推導(dǎo)。本文檔共152頁；當前第94頁；編輯于星期二\21點40分94相關(guān)概念：規(guī)范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。規(guī)范歸約：我們把最左推導(dǎo)的逆過程稱最右歸約最右推導(dǎo)的逆過程稱最左歸約最左歸約也稱為規(guī)范歸約

本文檔共152頁；當前第95頁；編輯于星期二\21點40分95應(yīng)當指出，對于文法中的每一句子都必定有最左和最右推導(dǎo)，但對于一句型來說則不盡然。例如，對于文法G［E］E∷=E+T|TT∷=T*F|FF∷=(E)|i中句型T*i+T，僅有唯一的推導(dǎo)EE+TT+TT*F+TT*i+T顯然，推導(dǎo)E+T*i+T既非最左推導(dǎo)亦非最右推導(dǎo)。本文檔共152頁；當前第96頁；編輯于星期二\21點40分96十一、文法二義性1.定義2.文法二義性消除3.幾點說明本文檔共152頁；當前第97頁；編輯于星期二\21點40分971.定義

如果一個文法中某個句型對應(yīng)兩棵不同的語法樹，則稱這個文法是二義性的。也就是說，若一個文法中的某句型對應(yīng)兩個不同的最左推導(dǎo)或最右推導(dǎo)，則這個文法是二義性的。本文檔共152頁；當前第98頁；編輯于星期二\21點40分98例如：文法G［E］E∷=E+E|E*E|(E)|i符號串i+i*i是L(G)中一個句子,有兩個不同的最右推導(dǎo)

EE+EE+E*EE+E*iE+i*ii+i*i(1)

EE*EE*iE+E*iE+i*ii+i*i(2)對應(yīng)兩棵不同的語法樹推導(dǎo)序列(1)和(2)分別對應(yīng)兩棵不同的語法樹,所以文法G［E］是二義性的。若將+，*看成算術(shù)運算符，則出現(xiàn)對表達式i+i*i是先做+還是先做*的不確定問題。EE+EiEEii*EE*EiEEii+本文檔共152頁；當前第99頁；編輯于星期二\21點40分99對于不少高級語言中，例如PASCAL語言，在描述條件語句(IF語句)時，使用文法G［C］，其規(guī)則P為C∷=ifBthenCC∷=ifBthenCelseCC∷=SB∷=B1|B2S∷=S1|S2其中C是開始符號，B代表布爾表達式，S代表語句，顯然，句子ifB1thenifB2thenS1elseS2存在兩種不同最右推導(dǎo)。本文檔共152頁；當前第100頁；編輯于星期二\21點40分100①CifBthenC

ifB1thenifB2thenCelseCifB1thenifB2thenS1elseS2

CifBCthenifBCthenelseCSSB1B2S1S2本文檔共152頁；當前第101頁；編輯于星期二\21點40分101②CifBthenCelseCifB1thenCelseS2

ifB1thenifB2thenC

elseS2

ifB1thenifB2thenS1elseS2

CifBCthenelseCifBCthenSSB1S2S1B2本文檔共152頁；當前第102頁；編輯于星期二\21點40分1022.文法二義性消除由于二義性文法的存在，使得在語法分析時帶來了麻煩，為此，們可以具體采用兩種途徑來解決文法二義性問題。

（1）在語義上加些限制，或者說加一些語法非形式規(guī)定。例如對于上例中G［E］文法，我們可以通過規(guī)定運算符之間的優(yōu)先級來避免文法的二義性。又例如對于條件語句文法G[C]，我們可以規(guī)定else永遠與最靠近它前面一個尚未匹配then配對，這樣就避免文法二義性。（2）對原二義性文法加上一定條件，將其改造成一個等價的無二義性文法。本文檔共152頁；當前第103頁；編輯于星期二\21點40分103例如對于上述G［E］文法可以構(gòu)造出一個無二義性文法G’[E]。即E∷=T|E+TT∷=F|T*FF∷=(E)|iEE+TTFiTFFii*本文檔共152頁；當前第104頁；編輯于星期二\21點40分1043.幾點說明（1）業(yè)已證明，文法的二義性是不可判定的。（2）文法的二義性和語言的二義性是兩個不同的概念。產(chǎn)生該語言的文法都是二義性文法，稱該語言為二義性語言，也稱先天二義性。至少有一個非二義文法產(chǎn)生該語言稱此語言為非二義性語言。對于由二義性文法描述的語言，有時可以找到等價的無二義性文法描述它，如上例文法G［E］和G’[E]，因此，我們只說文法二義性，而不說語言的二義性。本文檔共152頁；當前第105頁；編輯于星期二\21點40分105作業(yè)P.39：習(xí)題15P.41：習(xí)題22本文檔共152頁；當前第106頁；編輯于星期二\21點40分106

§2.4語法分析初步若已有文法G，如果給定一個符號串w，如何來確定該符號串是否是文法的句子呢?本文檔共152頁；當前第107頁；編輯于星期二\21點40分107一、自頂向下語法分析

1.分析基本思想2.分析方法二、自底向上語法分析

1.分析基本思想2.分析方法本文檔共152頁；當前第108頁；編輯于星期二\21點40分108一、自頂向下語法分析（導(dǎo)出法）

1.分析基本思想

自頂向下分析就是從文法的開始符號出發(fā)，利用其中產(chǎn)生式，逐步推導(dǎo)出要分析的符號串。換言之，對于任何給定的輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下、從左到右地為輸入串建立語法樹。這種分析過程本質(zhì)上是一個試探過程，是反復(fù)使用不同規(guī)則謀求匹配輸入串的過程。本文檔共152頁；當前第109頁；編輯于星期二\21點40分1092.分析方法例如：設(shè)有文法G=(VN，VT,P,S),其中VN={S,A}VT={a,b,c,d}P:S∷=cAdA∷=ab|a試分析符號串x=cad是否是文法G的句子.根據(jù)推導(dǎo)ScAdcad容易判斷出x=cad是該文法的句子。若用畫語法樹的方法我們同樣可以判斷出cad是文法的句子。SAdca本文檔共152頁；當前第110頁；編輯于星期二\21點40分110（1）為了自上而下為符號串x建立語法樹，首先將文法的開始符號S作為樹的根結(jié)點，并設(shè)輸入串指針i指向其第一個符號c，然后用S為左部的產(chǎn)生式來擴展這棵樹.若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadi本文檔共152頁；當前第111頁；編輯于星期二\21點40分111（2）此時該樹最左邊末結(jié)點c與x的第一個符號c相匹配，于是調(diào)整指針i使其指向輸入串下一符號a。我們再試圖讓樹的中間端末結(jié)點A去匹配a，顯然，由于A是非終結(jié)符，它不可能直接與終結(jié)符a匹配，我們只得在文法中選擇以A為左部的產(chǎn)生式，這里以A為左部的產(chǎn)生式有兩個，我們試著用第一個選擇來匹配輸入串,并擴展語法樹。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAd

cabdcadiab本文檔共152頁；當前第112頁；編輯于星期二\21點40分112（3）此時子樹A最左端末結(jié)點a與i所指的符號a匹配。于是再調(diào)整i使其指向下一輸入符號d，并試圖用A的最右端末結(jié)點b與之匹配。但它們不匹配，因此，子樹A的匹配失敗，這意味著選用A的第一個候選式對此時的情況不適合，不能構(gòu)造出輸入串x的語法樹，在這種情況下，我們應(yīng)該回頭看看(回溯)是否還有其它的候選式可供利用.若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAd

cabdcadiabERROR!本文檔共152頁；當前第113頁；編輯于星期二\21點40分113（4）我們應(yīng)把A的第一個候選式所擴展的子樹剪掉，還應(yīng)把指針i恢復(fù)到進入A時所指的輸入符號a，再選用A第二個候選式來構(gòu)造語法樹.若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadi本文檔共152頁；當前第114頁；編輯于星期二\21點40分114（5）此時子樹A的唯一端末結(jié)點a與i所指的輸入符號a匹配，因此A匹配成功，調(diào)整指針i，使其指向下一個輸入符號d。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadcadia本文檔共152頁；當前第115頁；編輯于星期二\21點40分115（6）最后考慮S的第三個端末結(jié)點d，它與i所指的最后一個輸入符號匹配，因此完成了構(gòu)造輸入串x的語法樹的任務(wù)，從而證明了x是所給文法推導(dǎo)出一個句子。若按自上而下語法分析程序的步驟進行分析判斷，其過程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadcadiaSUCCESS!本文檔共152頁；當前第116頁；編輯于星期二\21點40分116下面我們將上述分析過程總結(jié)一下：（1）自根開始建樹試圖生成一個和所給的符號串相一致的終結(jié)符號串

（2）選擇不同的規(guī)則反復(fù)試探在建樹過程中，反復(fù)選擇不同的規(guī)則，每一步試圖將語法樹最左的葉子與所給的符號串進行匹配

（3）匹配失敗退回出錯點當匹配失敗時，必須回到出錯點，然后再選擇其他規(guī)則進行試探這種方法稱為回溯采用自頂向下分析時，不僅可能遇到回溯問題，而且還可能由于文法中有左遞歸規(guī)則而陷入無限循環(huán)。我們將在第四章中要介紹這兩方面問題及其解決辦法。

本文檔共152頁；當前第117頁；編輯于星期二\21點40分117二、自底向上語法分析1.分析基本思想

自底向上分析是從所給的符號串w開始，在其中尋找與文法規(guī)則右部相匹配的子串，并用該規(guī)則的左部取代此子串(即歸約)，重復(fù)此過程，步步向上歸約，最后試圖將符號串w歸約到文法識別符號，如歸約成功，則符號串w是文法的句子。

本文檔共152頁；當前第118頁；編輯于星期二\21點40分118二、自底向上語法分析

2.分析方法例2.24設(shè)有文法G=(VN,VT,P,S),其中VN={A,B,S}VT={a,b,c,d,e}P:S∷=aAcBeA∷=Ab|bB∷=d試分析w=abbcde是否為此文法的句子。

本文檔共152頁；當前第119頁；編輯于星期二\21點40分119歸約過程描述:

先設(shè)立一個符號棧，即將輸入串中符號逐個移進棧，當棧頂符號串形成一個句柄時，就進行一次歸約，把棧頂句柄那個符號串用相應(yīng)規(guī)則左部的非終結(jié)符號來代替，接著再檢查在棧頂是否形成新的句柄，若出現(xiàn)新的句柄，那么再進行歸約；若沒有形成新句柄，則再從輸入符號串中移進新符號，……，如此繼續(xù)到整個輸入符號串處理完畢。最終，如棧底為開始符號，則輸入符號串是該文法的句子，報告成功，否則，是不合法的符號串，報告錯誤。本文檔共152頁；當前第120頁；編輯于星期二\21點40分120為了具體實現(xiàn)方便，我們統(tǒng)一以符號“#”作為待分析符號串左右分界符，作為初始狀態(tài)，先將符號串的左分界符壓入符號棧，作為棧底符號。對符號串a(chǎn)bbcde分析過程如下所示。步驟符號棧輸入符號串動作#abbcde#左界符進棧#abbcde#a進棧#abbcde#b進棧#aAbcde#用A→b歸約#aAbcde#b進棧#aAcde#用A→Ab歸約#aAcde#c進棧#aAcde#d進棧#aAcBe#用B→d歸約#aAcBe#e進棧#S#用S→AcBe歸約#S

#接受P:S∷=aAcBeA∷=Ab|bB∷=d本文檔共152頁；當前第121頁；編輯于星期二\21點40分121歸約過程描述:

先設(shè)立一個符號棧，即將輸入串中符號逐個移進棧，當棧頂符號串形成一個句柄時，就進行一次歸約，把棧頂句柄那個符號串用相應(yīng)規(guī)則左部的非終結(jié)符號來代替，接著再檢查在棧頂是否形成新的句柄，若出現(xiàn)新的句柄，那么再進行歸約；若沒有形成新句柄，則再從輸入符號串中移進新符號，……，如此繼續(xù)到整個輸入符號串處理完畢。最終，如棧底為開始符號，則輸入符號串是該文法的句子，報告成功，否則，是不合法的符號串，報告錯誤。本文檔共152頁；當前第122頁；編輯于星期二\21點40分122§2.5文法和語言分類一、文法分類二、文法和自動機三、壓縮過文法本文檔共152頁；當前第123頁；編輯于星期二\21點40分123如前所述，文法G形式定義為G=(VN,VT,P,Z)其規(guī)則P呈如下形式:U∷=w其中,U∈VN,w∈V*但僅有這種文法,還不足以描述許多語言,例如語言L(G)={anbncn|n≥1}便不能完全用上述形式規(guī)則來描述,因此還得定義其它類型的文法。根據(jù)對P中規(guī)則施加不同限制,Chomsky將文法和語言分為四類。一、文法分類本文檔共152頁；當前第124頁；編輯于星期二\21點40分124一、文法