編譯原理形式語言基礎

（優(yōu)選）編譯原理第章形式語言基礎當前第1頁\共有152頁\編于星期六\18點1一、語言的定義

任何一種語言都是在某個特定字母表上定義的、按照一定的規(guī)則構成的字符串的集合。當前第2頁\共有152頁\編于星期六\18點2二、形式語言提出

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

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

一、字母表二、符號串三、符號串集合當前第6頁\共有152頁\編于星期六\18點6一、字母表

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

注意：在一個語言中不能出現(xiàn)字母表以外的符號。當前第7頁\共有152頁\編于星期六\18點7二、符號串

1、定義

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

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

由上例可以看出，符號串與符號組成順序有關，如符號串ab不同于ba，符號串01不同于10，今后我們常用t,u,v,…x,y,z等小寫字母表示符號串。當前第8頁\共有152頁\編于星期六\18點82、空符號串

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

符號串中所含符號個數稱為該符號串的長度，設符號串為x，則用|x|來表示x的長度。例如：x=abc，則|x|=3,顯然,|ε|=0。當前第9頁\共有152頁\編于星期六\18點94、關于符號串的幾種運算

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

x=x1x2x3…xm,y=y1y2y3…yn

則

xy

=x1x2x3…xmy1y2y3…yn

顯然εx=x，xε=x

當前第10頁\共有152頁\編于星期六\18點10（2）符號串的方冪

若x是符號串則x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n個）如x=abc則x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩當前第11頁\共有152頁\編于星期六\18點11三、符號串集合舉例：字母表V={a,b}，問用V中的符號，可以組成哪些符號串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,…1、定義：若集合A中的一切元素都是字母表V上的符號串，則稱A為字母表V上的符號串集合當前第12頁\共有152頁\編于星期六\18點12V*定義：字母表V上各種長度符號串構成串集合，記為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,…}當前第13頁\共有152頁\編于星期六\18點132、關于串集合的運算（1）串集合乘積設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}符號?表示空集

當前第14頁\共有152頁\編于星期六\18點14（2）符號串集合的方冪設符號串集合A則A的方冪運算定義為：A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n個）如：設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}當前第15頁\共有152頁\編于星期六\18點15(3)符號串集合的閉包和正閉包

設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+當前第16頁\共有152頁\編于星期六\18點16作業(yè)：

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

除了上面可以根據語言語法規(guī)則來推導出句子，還可以用圖解形式來表示。以圖解（樹）形式來描述句子語法結構關系，稱語法樹。

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

1.定義

產生式(規(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的一個候選式。當前第36頁\共有152頁\編于星期六\18點362.字匯表(符號表)

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

當前第37頁\共有152頁\編于星期六\18點37（2）分類1）非終結符號

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

2）終結符

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

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

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

當前第44頁\共有152頁\編于星期六\18點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ī)則就是一個直接推導)同樣S∷=0S1

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

<標識符>∷=<字母>|<標識符><字母>|<標識符><數字>

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

<標識符>a當前第46頁\共有152頁\編于星期六\18點46定義2

設u0,u1,u2,…,un均為V*上符號串,若w是v經過一系列直接推導得到的,即v=u0

u1

u2

…un-1

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

顯然,直接推導的長度為1,推導

+的長度≥1,而廣義推導

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

S∷=01

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

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

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

當前第58頁\共有152頁\編于星期六\18點58八、遞歸文法

1.

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

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

當前第61頁\共有152頁\編于星期六\18點61八、遞歸文法

2.說明

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

當前第62頁\共有152頁\編于星期六\18點62九、短語和簡單短語

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

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

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

定義

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

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

當前第67頁\共有152頁\編于星期六\18點67例如：設文法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當前第68頁\共有152頁\編于星期六\18點683.再談語法樹

前面我們曾利用語法樹直觀地描述句子語法結構關系，現(xiàn)在我們仍然借助于語法樹進行句型和句子的推導，同時，利用它尋找短語和簡單短語也是十分直觀和方便的。（1）語法樹形式定義設有文法G=（VN，VT，P，Z），滿足下列條件的樹即為一個語法樹

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

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

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

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

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

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

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

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

ifB1thenifB2thenCelseCifB1thenifB2thenS1elseS2

CifBCthenifBCthenelseCSSB1B2S1S2當前第101頁\共有152頁\編于星期六\18點101②CifBthenCelseCifB1thenCelseS2

ifB1thenifB2thenC

elseS2

ifB1thenifB2thenS1elseS2

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

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

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

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

1.分析基本思想2.分析方法當前第108頁\共有152頁\編于星期六\18點108一、自頂向下語法分析（導出法）

1.分析基本思想

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

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

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

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

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

當前第117頁\共有152頁\編于星期六\18點117二、自底向上語法分析1.分析基本思想

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

當前第118頁\共有152頁\編于星期六\18點118二、自底向上語法分析

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

當前第119頁\共有152頁\編于星期六\18點119歸約過程描述:

先設立一個符號棧，即將輸入串中符號逐個移進棧，當棧頂符號串形成一個句柄時，就進行一次歸約，把棧頂句柄那個符號串用相應規(guī)則左部的非終結符號來代替，接著再檢查在棧頂是否形成新的句柄，若出現(xiàn)新的句柄，那么再進行歸約；若沒有形成新句柄，則再從輸入符號串中移進新符號，……，如此繼續(xù)到整個輸入符號串處理完畢。最終，如棧底為開始符號，則輸入符號串是該文法的句子，報告成功，否則，是不合法的符號串，報告錯誤。當前第120頁\共有152頁\編于星期六\18點120為了具體實現(xiàn)方便，我們統(tǒng)一以符號“#”作為待分析符號串左右分界符，作為初始狀態(tài)，先將符號串的左分界符壓入符號棧，作為棧底符號。對符號串abbcde分析過程如下所示。步驟符號棧輸入符號串動作#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當前第121頁\共有152頁\編于星期六\18點121歸約過程描述:

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

當前第126頁\共有152頁\編于星期六\18點126例2.25設文法G=(VN,VT,P,S),其中VN={S,A,B,C,D,E}VT={a}P:①S∷=ACaB,②Ca∷=aaC③CB∷=DB,④CB∷=E⑤aD∷=Da⑥AD∷=AC⑦aE∷=Ea⑧AE∷=ε這是一個0型文法,它所產生語言為L(G)={ai|i是2的正整次方}即L(G)={aa,aaaa,aaaaaaaa,…}當前第127頁\共有152頁\編于星期六\18點1272.1型文法

若在文法G中，P中規(guī)則具有如下形式：αAβ∷=αwβ其中α,β∈V*,A∈ＶＮ,w∈Ｖ＋,則稱文法G為1型文法或上下文有關文法，也稱上下文敏感文法，簡記為CSG(ContextSensitiveGrammar)。

之所以如此命名，是因為在一個句型中，只有當