第二章-文法與語(yǔ)言

編譯原理

CompilerPrinciples2013年9月閆雷鳴第二章文法與語(yǔ)言討論問題：文法和語(yǔ)言的概念和定義文法和語(yǔ)言的分類文法等價(jià)變換句型分析簡(jiǎn)單回顧對(duì)程序的理解程序是計(jì)算機(jī)執(zhí)行的一系列指令；程序是計(jì)算任務(wù)的處理對(duì)象和處理規(guī)則的描述。

?對(duì)程序設(shè)計(jì)語(yǔ)言的理解程序設(shè)計(jì)語(yǔ)言是程序的書寫規(guī)范；程序設(shè)計(jì)語(yǔ)言的要素：一組記號(hào)(符號(hào))和一組規(guī)則。程序設(shè)計(jì)語(yǔ)言程序是程序設(shè)計(jì)語(yǔ)言之符號(hào)集合上的、按一定規(guī)則組成的符號(hào)串。?語(yǔ)言是一切句子的集合；程序設(shè)計(jì)語(yǔ)言是一切程序的集合；把程序看做程序設(shè)計(jì)語(yǔ)言的句子。?程序是(程序設(shè)計(jì)）語(yǔ)言的句子?如何系統(tǒng)地構(gòu)造程序？或者，一般地，如何為一個(gè)(程序設(shè)計(jì))語(yǔ)言生成句子？

2.1符號(hào)串與符號(hào)串集合語(yǔ)言實(shí)際上是一個(gè)符號(hào)串集合；文法規(guī)定語(yǔ)言中句子的構(gòu)造規(guī)則。句子是一個(gè)語(yǔ)言之字母表上按一定規(guī)則構(gòu)造的符號(hào)串。2.1.1字母表字母表:有窮非空的符號(hào)集合。例A={a,b,c}∑={0,1}C語(yǔ)言字母表={字母，數(shù)字，界限符}

不同的語(yǔ)言有不同的字母表。字母表上的元素（即符號(hào)）組成符號(hào)串。2.1.2

符號(hào)串:1.符號(hào)串及其長(zhǎng)度

符號(hào)串:由字母表上的符號(hào)所組成的有窮序列。字母表A={a,b,c}上的符號(hào)串：

a,b,c,ab,ba,aaa,aab,baa,abcab,ε(空串)

注意：順序是重要的,ab≠baC語(yǔ)言字母表上的符號(hào)串？長(zhǎng)度：|aabcaca|=7|ε|=02.子符號(hào)串若u=xvy，其中|v|≠0（|u|>=|v|）則v是u中的子符號(hào)串。（非空符號(hào)串）例a+(b-c)/d中的子符號(hào)串3.符號(hào)串的頭與尾（前綴、后綴）

abc的頭：a,ab,abc,?x=t…

abc的尾：c,bc,abc,?x=…t

4.對(duì)符號(hào)串的運(yùn)算聯(lián)結(jié)（或并置）：

x=aby=baxy=abbayx=baab

對(duì)任何符號(hào)串x，有x=x=x。

方冪：xn=xx…x(x自身聯(lián)結(jié)n次)xn=xn-1x=xxn-1

x0=?

x3=(ab)3=ababab|xy|=|x|+|y||xn|=n|x||x0|=02.1.3

符號(hào)串集合（語(yǔ)言）1.符號(hào)串集合的定義1)它是一切元素都是某字母表上的符號(hào)串的集合。

2)表示法枚舉法{1，11，111，1111}

省略法{1，11，111，1111，┅}

描述法{1i|i≥1}或{x|x全由1組成,|x|≥1}

注意：一定不能涉及含義,如{x|x=∑10i}。字母表∑上的一個(gè)語(yǔ)言就是∑上的一些符號(hào)串組成的集合。

空集ф

是一個(gè)語(yǔ)言，僅含一個(gè)空符號(hào)串集合{ф}也是一個(gè)語(yǔ)言。特別需要指出的是，?和{?}是不同的語(yǔ)言。2.對(duì)符號(hào)串集合的運(yùn)算乘積：AB={xy|x∈A且y∈B}{1,0}{a,b,c}=?

對(duì)任何符號(hào)串x有x=x=x，A0={ε}因此，{}A=A{}=A，但?A=A?=?。

方冪：An=AA…A(n個(gè)A乘積）

An=An-1A=AAn-1

特例，字母表A的方冪，x∈An,|x|=n{1,0}3=?{1,0}n=?3.字母表的閉包與正閉包閉包A*=A0∪A1∪┅∪An∪┅{0，1，2}*

正閉包A+=A1∪┅∪An∪┅=A*-{}{0，1，2}+

x∈A+,則|x|>=1

x∈A*,則|x|>=0

任何一個(gè)語(yǔ)言是其字母表之正閉包的真子集。如何找出此真子集？或說(shuō)，如何找出其句子？2.2文法與語(yǔ)言的形式定義2.2.1文法的形式定義1.重寫規(guī)則（產(chǎn)生式規(guī)則）定義：有序?qū)Γ║，u)或U::=u

A→α（或A::=α）其中，A是一個(gè)符號(hào)，稱為產(chǎn)生式規(guī)則的左部，而α是有窮非空符號(hào)串，稱為產(chǎn)生式規(guī)則的右部，“→

”和“::=”表示“定義為”或“由……組合成的”或“生成”，其含義是左部符號(hào)用右部的符號(hào)串定義或左部符號(hào)生成右部符號(hào)串。產(chǎn)生式規(guī)則可合寫，如：A→α和A→β可寫為A→α|β

1.重寫規(guī)則（產(chǎn)生式規(guī)則）規(guī)則表示法：通常的E::=E+TE::=T

或E::=E+T|T

擴(kuò)充的E::=T{+T}

術(shù)語(yǔ)：非終結(jié)符號(hào)，非終結(jié)符號(hào)集VN

終結(jié)符號(hào)，（不會(huì)出現(xiàn)在規(guī)則左部）終結(jié)符號(hào)集VT

（

VN∩VT=?V=

VN∪VT）單規(guī)則：右部是單個(gè)非終結(jié)符{}用于指定重復(fù)次數(shù)<標(biāo)識(shí)符>::=<字母>{<字母數(shù)字>}05[]內(nèi)中符號(hào)至多出現(xiàn)一次<整數(shù)>::=[+|-]<數(shù)字>{<數(shù)字>}()提公因子E::=E+T|E-T可改寫為E::=E(+|-)T16規(guī)則構(gòu)造的例子C語(yǔ)言標(biāo)識(shí)符的規(guī)則：<標(biāo)識(shí)符>::=<字母下劃線><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><字母下劃線><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><數(shù)字><字母下劃線>::=A|…|Z<字母下劃線>::=a|…|z<字母下劃線>::=_<數(shù)字>::=0|…|917用規(guī)則產(chǎn)生句子的例子如：用標(biāo)識(shí)符產(chǎn)生式規(guī)則產(chǎn)生句子area.<標(biāo)識(shí)符><標(biāo)識(shí)符><字母下劃線><標(biāo)識(shí)符>a

<標(biāo)識(shí)符><字母下劃線>a <標(biāo)識(shí)符>ea <標(biāo)識(shí)符><字母下劃線>ea <標(biāo)識(shí)符>rea<字母下劃線>rea

area其中，“=>”為推導(dǎo)。2.文法的定義文法G[Z]是非空有窮的重寫規(guī)則集合，其中Z是識(shí)別符號(hào)（或稱開始符號(hào)），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T|TT::=T*F|FF::=(E)F::=iG[E]：E::=T{+T}T::=F{*F}F::=(E)|i文法的四要素：VN，VT，P，ZP有窮非空的重寫規(guī)則集，識(shí)別符號(hào)ZVN3.

應(yīng)用文法產(chǎn)生語(yǔ)言的句子

G[<句子>]:1.<句子>::=<主語(yǔ)><謂語(yǔ)><狀語(yǔ)>2.<主語(yǔ)>::=<名詞>3.<謂語(yǔ)>::=<動(dòng)詞>4.<狀語(yǔ)>::=<介詞><名詞>5.<名詞>::=Peter6.<名詞>::=Berry7.<名詞>::=river8.<動(dòng)詞>::=swims9.<介詞>::=in例試以文法G[<句子>]為例考察如何應(yīng)用文法來(lái)生成句子。

替換為?句子?=>?主語(yǔ)??謂語(yǔ)??狀語(yǔ)?

(規(guī)則1)

=>?名詞?

?謂語(yǔ)?

?狀語(yǔ)?(規(guī)則2)=>Peter?謂語(yǔ)??狀語(yǔ)?

(規(guī)則5)=>Peter?動(dòng)詞?

?狀語(yǔ)?(規(guī)則3)=>Peterswims

?狀語(yǔ)?(規(guī)則8)=>Peterswims?介詞??名詞?

(規(guī)則4)=>Peterswims

in

?名詞?(規(guī)則9)=>Peterswimsinriver(規(guī)則7)應(yīng)用文法生成句子的步驟：步驟1以識(shí)別符號(hào)為當(dāng)前符號(hào)串；步驟2對(duì)當(dāng)前符號(hào)串中的一個(gè)非終結(jié)符號(hào)進(jìn)行替換，把它替換為以此非終結(jié)符號(hào)為左部的規(guī)則之右部符號(hào)串，生成新的當(dāng)前符號(hào)串；步驟3重復(fù)步驟2,直到當(dāng)前符號(hào)串中不包含非終結(jié)符號(hào)，最終不包含非終結(jié)符號(hào)的符號(hào)串就是所生成的句子。說(shuō)明：每步的當(dāng)前符號(hào)串將稱為句型，最終的終結(jié)符號(hào)串稱為句子。

按上述步驟應(yīng)用各個(gè)規(guī)則，可生成：

Berryswimsinriver

甚至可生成：riverswimsinPeter

表明：語(yǔ)法上的正確性不能保證語(yǔ)義上的正確性。

對(duì)當(dāng)前句型中任一非終結(jié)符號(hào)進(jìn)行替換，都將生成新的句型，最終生成句子。但宜用系統(tǒng)的方式進(jìn)行推導(dǎo)，如，每步對(duì)最左的或最右的非終結(jié)符號(hào)進(jìn)行替換。這時(shí)，分別稱為最左推導(dǎo)與最右推導(dǎo)。引進(jìn)句子生成中的兩個(gè)重要概念：推導(dǎo)與歸約。直接推導(dǎo)：=>xUy=>xuy

?句子?=>?主語(yǔ)??謂語(yǔ)??狀語(yǔ)?

?主語(yǔ)??謂語(yǔ)??狀語(yǔ)?=>?名詞??謂語(yǔ)??狀語(yǔ)?

?名詞??謂語(yǔ)??狀語(yǔ)?=>Peter?謂語(yǔ)??狀語(yǔ)?Peter?謂語(yǔ)??狀語(yǔ)?=>Peter?動(dòng)詞??狀語(yǔ)?Peter?動(dòng)詞??狀語(yǔ)?=>Peterswims?狀語(yǔ)?Peterswims?狀語(yǔ)?=>Peterswims?介詞??名詞?Peterswims?介詞??名詞?=>Peterswimsin?名詞?Peterswimsin?名詞?=>Peterswimsinriver

直接推導(dǎo)時(shí)，給定v=xUy,

找到規(guī)則U::=u，把u代替U，

得到w=xuy稱v直接推導(dǎo)到w，記為：v=>w或xUy=>xuy推導(dǎo)（直接推導(dǎo)序列）：=>+<句子>

=>?主語(yǔ)??謂語(yǔ)??狀語(yǔ)?=>?名詞??謂語(yǔ)??狀語(yǔ)?=>Peter?謂語(yǔ)??狀語(yǔ)?=>Peter?動(dòng)詞??狀語(yǔ)?=>Peterswims?狀語(yǔ)?=>Peterswims?介詞??名詞?=>Peterswimsin?名詞?=>Peterswimsinriver

推導(dǎo)時(shí)，給定符號(hào)串v,

找到v=>u1=>u2=>…=>un-1=>w,

得到符號(hào)串w,稱v推導(dǎo)到w，記為：v=>+w。一般，從識(shí)別符號(hào)開始推導(dǎo)，例如，

<句子>=>+Peter?謂語(yǔ)??狀語(yǔ)?<句子>=>+Peterswimsinriver

推導(dǎo)長(zhǎng)度：直接推導(dǎo)的步數(shù)。直接推導(dǎo)

:=>

直接推導(dǎo)時(shí)，給定v=xUy，在其中找出U，應(yīng)用規(guī)則U::=u,

得到w=xuy，稱v直接推導(dǎo)到w,或w直接歸約到v,記為v=>w

一般，總有：U::=uxUy=>xuy推導(dǎo):=>+

推導(dǎo)時(shí)，給定符號(hào)串v,找出直接推導(dǎo)序列：

v=>u1=>u2=>…=>un-1=>w得到符號(hào)串w,稱v推導(dǎo)到w,或w歸約到v,記為:v=>+wn稱為推導(dǎo)的長(zhǎng)度。

廣義推導(dǎo)：=>*

若v=>+w或v=w，則稱v廣義推導(dǎo)到w,或廣義歸約到v。對(duì)照：直接推導(dǎo)v=>w(U::=uv=xUyw=xuy)(推導(dǎo)長(zhǎng)度=1)

推導(dǎo)v=>+w(v=>u1=>…=>un-1=>w)(推導(dǎo)長(zhǎng)度1)

廣義推導(dǎo)v=>*w(v=>+w或v=w)(推導(dǎo)長(zhǎng)度0)通常考慮的都是從識(shí)別符號(hào)出發(fā)的推導(dǎo)：

Z=>*xx∈(VN

∪VT)+

直接歸約：v=>ww直接歸約為v

歸約:v=>+ww歸約為v

廣義歸約:v=>*ww廣義歸約為v

請(qǐng)對(duì)照比較推導(dǎo)與歸約這兩個(gè)概念。重要概念：句型、句子句型：Z=>*x,x∈(VN∪VT)+

句子：Z=>*x,x∈VT+

例Peterswimsinriver注意：句子和<句子>在概念上的區(qū)別注意：應(yīng)用文法生成句子僅是形式上的。例riverswimsinPeter注：句子也是句型，但句型不一定是句子。文法產(chǎn)生句型和句子的例子【例】設(shè)有文法G[Z]:Z::=aZb|?有推導(dǎo)：Z=>*?Z=>*aZb=>aaZbb=>*aaabbb可見，符號(hào)串

ε，aZb，aaZbb和aaabbb都是文法G[Z]的句型，而

ε

和aaabbb才是文法G[Z]的句子。30文法產(chǎn)生句型和句子的例子

【例】設(shè)有文法G[E]:

E::=E+T|E-T|TT::=T*F|T/F|FF::=(E)|i

試證明i+i*i是它的一個(gè)句子。

分析：只有證明i+i*i可由文法G從開始符號(hào)E推導(dǎo)出，即可證明i+i*i是它的一個(gè)句子。

證明：

EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i

即有E

*i+i*i

又因i+i*i中的每個(gè)符號(hào)均為終結(jié)符號(hào)，故i+i*i是它的一個(gè)句子。思考設(shè)計(jì)編程語(yǔ)言時(shí)，是先設(shè)計(jì)語(yǔ)言形式，還是先設(shè)計(jì)BNF形式的文法？例如要表示形如i+i,i+i*i的表達(dá)式建議：學(xué)習(xí)時(shí)注意積累，何種典型文法可以得到某種典型的語(yǔ)言形式考試考查：能夠由文法寫出語(yǔ)言，也能由語(yǔ)言設(shè)計(jì)出文法為什么有窮規(guī)則集合的文法能定義無(wú)窮的語(yǔ)言？文法G[<無(wú)正負(fù)號(hào)整數(shù)>]：

1）<無(wú)正負(fù)號(hào)整數(shù)>::=<數(shù)字序列>2）<數(shù)字序列>::=<數(shù)字序列><數(shù)字>3）<數(shù)字序列>::=<數(shù)字>4）<數(shù)字>::=05)<數(shù)字>::=16）<數(shù)字>::=27)<數(shù)字>::=38)<數(shù)字>::=49)<數(shù)字>::=510)<數(shù)字>::=611)<數(shù)字>::=711)<數(shù)字>::=812)<數(shù)字>::=9VN={<無(wú)正負(fù)號(hào)整數(shù)>,<數(shù)字序列>,<數(shù)字>}VT={0,1,2,3,4,5,6,7,8,9}<無(wú)正負(fù)號(hào)整數(shù)>=><數(shù)字序列>=><數(shù)字序列><數(shù)字>=><數(shù)字序列><數(shù)字><數(shù)字>=><數(shù)字><數(shù)字><數(shù)字>=>1<數(shù)字><數(shù)字>=>12<數(shù)字>=>123<無(wú)正負(fù)號(hào)整數(shù)>=><數(shù)字序列>=><數(shù)字序列><數(shù)字>=><數(shù)字序列><數(shù)字><數(shù)字>=><數(shù)字序列><數(shù)字><數(shù)字><數(shù)字>=>…

遞歸地定義規(guī)則，即，U::=U…,使得有窮個(gè)規(guī)則可能定義潛在地?zé)o窮的語(yǔ)言。重要概念：短語(yǔ)、簡(jiǎn)單短語(yǔ)

已知w=xuy是文法G的句型,

短語(yǔ)

u:Z=>*xUyU∈VN

U=>+u

簡(jiǎn)單短語(yǔ)

u:Z=>*xUyU∈VN

U=>u

理解：句型w=xuy中

⑴可(直接)歸約且

⑵(直接)歸約后所得新符號(hào)串仍為句型

的子符號(hào)串u。

例句子123中,1、2、3都是簡(jiǎn)單短語(yǔ)。

1、12、123、2、3都是短語(yǔ)。

句型<數(shù)字序列>1<數(shù)字>2

中：

簡(jiǎn)單短語(yǔ)有：1、2

短語(yǔ)有：<數(shù)字序列>1、1、<數(shù)字序列>1<數(shù)字>、2

句柄

:句型中最左的簡(jiǎn)單短語(yǔ)。句柄是重要概念之一。歸約是自底向上的語(yǔ)法分析關(guān)鍵，何時(shí)進(jìn)行歸約則必須依賴句柄。分析句型時(shí)，要搞清楚哪些符號(hào)串能構(gòu)成短語(yǔ)和直接短語(yǔ)。36求短語(yǔ)、直接短語(yǔ)和句柄的例子

【例】設(shè)有文法G[E]:

求出句型(F+i)－T*(E－T)的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。

分析：從句型的推導(dǎo)過程中找出其全部短語(yǔ)、直接短語(yǔ)和句柄。37

可以看出：

句型(F+i)－T*(E－T)包含以下短語(yǔ)：

F，i，F(xiàn)+i，(F+i)，E－T，(E－T)，T*(E－T)，(F+i)－T*(E－T)；簡(jiǎn)單短語(yǔ)有：F，i，E－T；句柄為F。注意：選擇符號(hào)串判斷是否短語(yǔ)時(shí)，必須同時(shí)滿足兩個(gè)條件：1）可歸約；2）歸約后仍是句型（即可由識(shí)別符號(hào)推導(dǎo)出）概括文法G:有窮非空的重寫規(guī)則集合四要素：VN，VT，P，Z句型：Z=>*t,t∈(VN∪VT)+句子：Z=>*t,t∈VT+概念：推導(dǎo)，歸約簡(jiǎn)單短語(yǔ)，短語(yǔ)，句柄4.文法句子之生成的實(shí)現(xiàn)實(shí)質(zhì)是推導(dǎo)的構(gòu)造。要點(diǎn)是推導(dǎo)在計(jì)算機(jī)內(nèi)的存儲(chǔ)表示。文法符號(hào)序號(hào)

后繼符號(hào)結(jié)點(diǎn)指針其中包含兩類結(jié)點(diǎn)，一類結(jié)點(diǎn)結(jié)構(gòu)形如：另一類結(jié)點(diǎn)結(jié)構(gòu)形如：這易于用C語(yǔ)言結(jié)構(gòu)類型實(shí)現(xiàn)，例如，對(duì)第一類，

typedefstruct直接推導(dǎo)鏈?zhǔn)捉Y(jié)點(diǎn){struct符號(hào)結(jié)點(diǎn)*句型首符號(hào)結(jié)點(diǎn)指針；

struct直接推導(dǎo)鏈?zhǔn)捉Y(jié)點(diǎn)*下一直接推導(dǎo)鏈頭指針；}直接推導(dǎo)鏈?zhǔn)捉Y(jié)點(diǎn)類型；

句型首符號(hào)結(jié)點(diǎn)指針

下一直接推導(dǎo)鏈頭指針顯然每一“列”（垂直鏈）中各結(jié)點(diǎn)相應(yīng)的符號(hào)組成一個(gè)句型。這易于用C語(yǔ)言結(jié)構(gòu)類型實(shí)現(xiàn)。以最左推導(dǎo)的建立為例，程序控制流程示意圖如下。

建立最左推導(dǎo)

置初值

把識(shí)別符號(hào)置為當(dāng)前句型,

建立一“列”結(jié)點(diǎn)

當(dāng)前句型中包含

N

非終結(jié)符號(hào)

Y

復(fù)制當(dāng)前句型一“列”結(jié)點(diǎn)，把所復(fù)制的作為當(dāng)前句型，并建立與原有當(dāng)前句型的鏈接

取到當(dāng)前句型的最左非終結(jié)符號(hào)U相應(yīng)的結(jié)點(diǎn)

以U為左部的Y

規(guī)則僅一個(gè)

N

顯示以U為左部的各規(guī)則

用戶選擇一個(gè)規(guī)則，

k=規(guī)則序號(hào)

關(guān)于規(guī)則k的右部生成結(jié)點(diǎn)鏈，代替U相應(yīng)的結(jié)點(diǎn)出口k=規(guī)則序號(hào)

由于推導(dǎo)過程中，進(jìn)行替換的非終結(jié)符號(hào)可能作為多個(gè)規(guī)則的左部，在尚未討論分析技術(shù)的情況下，宜于采用交互方式由用戶自己選擇進(jìn)行直接推導(dǎo)的規(guī)則。這涉及到文法規(guī)則在計(jì)算機(jī)內(nèi)的存放。文法的存儲(chǔ)表示：

?一種是數(shù)組表示

?一種是鏈表表示

例G[E]：

E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i?數(shù)組表示：左部右部符號(hào)串右部長(zhǎng)度C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)定義：typedefstruct{符號(hào)左部符號(hào)；符號(hào)右部符號(hào)串[MaxRightPartLength+1];int右部長(zhǎng)度；}規(guī)則;規(guī)則

文法[MaxRuleNum+1];其中，typedefchar符號(hào)[MaxLength+1]；符號(hào)

非終結(jié)符號(hào)集[MaxVnNum+1];

符號(hào)

終結(jié)符號(hào)集[MaxVtNum+1];

為便于處理，以符號(hào)的序號(hào)代替符號(hào)本身：typedefstruct{int左部符號(hào)序號(hào)；

int右部符號(hào)串[MaxRightPartLength+1];int右部長(zhǎng)度；}規(guī)則;規(guī)則

文法[MaxRuleNum+1];為區(qū)分非終結(jié)符與終結(jié)符，將非終結(jié)符的序號(hào)+100文法[1]中的規(guī)則E::=E+T,在計(jì)算機(jī)內(nèi)的存儲(chǔ)表示:

文法[1]：

{101，

{0，101，

1，

102}，

3}文法[2]中的規(guī)則E::=T，在計(jì)算機(jī)內(nèi)的存儲(chǔ)表示：文法[2]：

{101，

{0，102}，

1}T∈VT：T在VT中的序號(hào)

U∈VN：U在VN中的序號(hào)+100

注意：C語(yǔ)言數(shù)組元素的下標(biāo)值從0開始，已把0號(hào)元素棄之不用。文法的鏈?zhǔn)奖硎荆何姆℅[E]的數(shù)據(jù)結(jié)構(gòu)G[E]：E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i2.2.2語(yǔ)言的定義程序設(shè)計(jì)語(yǔ)言L是一切程序P的集合。

PL

L∑+

（∑=VT

）語(yǔ)言是相應(yīng)文法一切句子的集合。

L(G[Z])={x|Z=>*x,x∈VT+

}

一個(gè)文法確定唯一的語(yǔ)言。反之？

L(G[<程序>])={P|<程序>=>*P,P∈VT+

}

語(yǔ)言可能是有窮的，也可能是無(wú)窮的。重要概念：遞歸規(guī)則遞歸規(guī)則左遞歸：U::=U…

一般遞歸：U::=…U…

規(guī)則右遞歸：U::=…U文法遞歸文法左遞歸:U=>+U…

一般遞歸：U=>+…U…

文法右遞歸：U=>+…U遞歸，使有窮多個(gè)規(guī)則定義的語(yǔ)言可以是無(wú)窮的。C語(yǔ)言中的規(guī)則遞歸和文法遞歸規(guī)則左遞歸有：

<整型常量>::=<整型常量><數(shù)字>

規(guī)則右遞歸有：

<因式>::=!<因式>

文法右遞歸于<語(yǔ)句>：

<語(yǔ)句>::=<控制語(yǔ)句><控制語(yǔ)句>::=<條件語(yǔ)句><條件語(yǔ)句>::=if(<表達(dá)式>)<語(yǔ)句>else<語(yǔ)句>

因此，

<語(yǔ)句>=>+…<語(yǔ)句>

也可以說(shuō)，C語(yǔ)言文法遞歸于<語(yǔ)句><語(yǔ)句>=>+…<語(yǔ)句>…為語(yǔ)言構(gòu)造文法

L1={aibjck|i,j,k≥1}aa…aabb…bbcc…ccABCABCABCSG1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|c

aa…aabb…bbcc…ccAAABBSSG1’[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a注：同一種語(yǔ)言可設(shè)計(jì)出不同的文法；注意擴(kuò)展！L2={aibick|i,k≥1}

a…aabb…bcc…cAAASSG2[S]:S::=Sc|AcA::=aAb|ab

L3={aibici|i≥1}G3[S]:S::=abC|aSBCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL4={a2i|i≥1}G4[S]:S::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=ε56文法產(chǎn)生語(yǔ)言的例子【例1】設(shè)有文法G[Z]:Z::=aaZbb|ab求該文法所描述的語(yǔ)言。

分析：語(yǔ)言：57文法產(chǎn)生語(yǔ)言的例子【例2】設(shè)有文法G[Z]:求該文法所描述的語(yǔ)言。

分析：由括號(hào)組成的終結(jié)符號(hào)，且左右括號(hào)匹配。

【例3】設(shè)有文法G[Z]:求該文法所描述的語(yǔ)言。

分析：1后面緊跟的符號(hào)必為0或?yàn)榭?，即該文法產(chǎn)生的是不包括兩個(gè)相鄰1的所有0、1串。

語(yǔ)言：

概括1.程序設(shè)計(jì)語(yǔ)言是一切程序的集合；程序是在程序設(shè)計(jì)語(yǔ)言字母表上按一定規(guī)則構(gòu)造的符號(hào)串；程序設(shè)計(jì)語(yǔ)言是其字母表正閉包的真子集。2.文法是重寫規(guī)則的集合文法四要素：VN、VT、P、Z

文法的句型：由識(shí)別符號(hào)推導(dǎo)所得的符號(hào)串。文法的句子：全由終結(jié)符號(hào)組成的句型。3.語(yǔ)言是一切句子的集合；文法確定，則語(yǔ)言確定，語(yǔ)言給定，但可為該語(yǔ)言構(gòu)造若干文法。遞歸，使有窮多個(gè)規(guī)則能定義無(wú)窮的語(yǔ)言。4.重要概念句型、句子推導(dǎo)、歸約短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄遞歸（規(guī)則遞歸、文法遞歸）應(yīng)用文法生成句子的步驟：步驟1以識(shí)別符號(hào)為當(dāng)前句型步驟2對(duì)當(dāng)前句型進(jìn)行直接推導(dǎo)（把其中一個(gè)非終結(jié)符號(hào)替換為以其為左部的規(guī)則之右部符號(hào)串）步驟3重復(fù)步驟2，直到無(wú)非終結(jié)符號(hào)可被替換。通常應(yīng)以系統(tǒng)的有規(guī)則的方式進(jìn)行替換

·對(duì)最左的非終結(jié)符號(hào)進(jìn)行替換（最左推導(dǎo)）

·對(duì)最右的非終結(jié)符號(hào)進(jìn)行替換（最右推導(dǎo)）2.3.1Chomsky文法類和語(yǔ)言類1.Chomsky分類法對(duì)文法四要素概括與抽象。定義：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a2.3語(yǔ)言的分類2.3.1Chomsky文法類和語(yǔ)言類1.Chomsky分類法對(duì)文法四要素概括與抽象。定義：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a

G1=（VN,VT,P1,S1)VN={S1,A,B}VT={a,b,c}P1:S1::=S1c|BcB::=Bb|AbA::=Aa|aL(G1)={aibjck|i,j,k≥1}G2=（{S2,A},{a,b,c},P2,S2)P2:S2::=S2c|AcA::=aAb|abL(G2)={aibick|i,k≥1}G3=({S3,B,C,D},{a,b,c},P3,S3)P3:S3::=abC|aS3BCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL(G3)={aibici|i≥1}G4=({S4,A,B,C,D,E},{a},P4,S4)P4:S4::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=εL(G4)={a2i

|i≥1}分類：按規(guī)則的定義形式對(duì)文法分類

0型文法（短語(yǔ)結(jié)構(gòu)文法PSG）：

u::=v

u∈(VN∪VT)+,v∈(VN∪VT)*1型文法（上下文有關(guān)文法CSG）：

xUy::=xuyU∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+2型文法（上下文無(wú)關(guān)文法CFG）：

U::=xuy

U∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+3型文法（正則文法RG）：

U::=VT

或U::=T

U,V∈VN,T∈VT

相應(yīng)地有4類Chomsky語(yǔ)言：

0型語(yǔ)言（短語(yǔ)結(jié)構(gòu)語(yǔ)言PSL）

1型語(yǔ)言（上下文有關(guān)語(yǔ)言CSL）

2型語(yǔ)言（上下文無(wú)關(guān)語(yǔ)言CFL）

3型語(yǔ)言（正則語(yǔ)言RL）注意：有時(shí)對(duì)2型文法，擴(kuò)充有ε規(guī)則與ε句子

ε規(guī)則：U::=εε句子：Z=>*ε2.3.2*

形式語(yǔ)言與自動(dòng)機(jī)Chomsky語(yǔ)言類和自動(dòng)機(jī)的對(duì)應(yīng)關(guān)系：

3型語(yǔ)言~有窮狀態(tài)自動(dòng)機(jī)

FA2型語(yǔ)言~下推自動(dòng)機(jī)PDA1型語(yǔ)言~線性界限自動(dòng)機(jī)LBA0型語(yǔ)言~圖靈機(jī)TM

2.3.3形式語(yǔ)言的分類與程序設(shè)計(jì)語(yǔ)言

1.程序設(shè)計(jì)語(yǔ)言一般用上下文無(wú)關(guān)文法定義：

U::=u2.但語(yǔ)言一般是上下文有關(guān)的

(1)<標(biāo)號(hào)>::=<標(biāo)識(shí)符><變量>::=<標(biāo)識(shí)符>goto<標(biāo)號(hào)>::=goto<標(biāo)識(shí)符>

<標(biāo)號(hào)>:<語(yǔ)句>::=<標(biāo)識(shí)符>:<語(yǔ)句>

(標(biāo)識(shí)符由所在上下文確定是否標(biāo)號(hào))(2)<函數(shù)標(biāo)識(shí)符>'('<實(shí)在參數(shù)表>')

'

<數(shù)組變量>'['<下標(biāo)表達(dá)式表>']

'<變量>=<表達(dá)式>(標(biāo)識(shí)符由后跟符號(hào)確定是函數(shù)標(biāo)識(shí)符、數(shù)組變量還是變量)3.通常：詞法正則文法語(yǔ)法上下文無(wú)關(guān)文法語(yǔ)義口語(yǔ)2.3.4對(duì)上下文無(wú)關(guān)文法的進(jìn)一步討論1*.上下文無(wú)關(guān)文法的自嵌套特性如果一個(gè)上下文無(wú)關(guān)文法G中存在具有下列特性的非終結(jié)符號(hào)U：

U=>*xUy其中x,y∈V+，則稱U為自嵌套的非終結(jié)符號(hào)，包含自嵌套非終結(jié)符號(hào)的文法G稱為自嵌套的上下文無(wú)關(guān)文法。

若一個(gè)上下文無(wú)關(guān)文法G不是自嵌套的，則L(G)是一個(gè)正則語(yǔ)言。

對(duì)任何一個(gè)正則語(yǔ)言，必定可構(gòu)造不是自嵌套的文法。一個(gè)嚴(yán)格的上下文無(wú)關(guān)語(yǔ)言，必不能構(gòu)造非自嵌套的文法。自嵌套特性把正則語(yǔ)言與嚴(yán)格的上下文無(wú)關(guān)語(yǔ)言區(qū)別開來(lái)。

2.與推導(dǎo)有關(guān)的特性⑴對(duì)于CFG，若存在句型x=x1x2…xn,有

x1x2…xn=>*y,

則必存在y1,y2,…,yn，使得

xi=>*yi(i=1,2,…,n),Z

且y=y1y2…yn。⑵設(shè)x=>*y,若x的首符號(hào)∈VT,X1X2…Xn

則y的首符號(hào)也∈VT

。反之，y的首符號(hào)∈VN,則y1y2…yn

x的首符號(hào)也∈VN

。3.ε規(guī)則

ε規(guī)則：U::=ε

Chomsky2型文法U::=u中，u∈VT+,

不包含ε規(guī)則，但有時(shí)讓u∈VT*,

例如進(jìn)行文法等價(jià)變換，便引進(jìn)ε規(guī)則。引進(jìn)ε規(guī)則，便可能產(chǎn)生ε句子：

Z=>*ε

對(duì)于所有非0型的語(yǔ)言，包括上下文無(wú)關(guān)語(yǔ)言，刪去或添加一個(gè)ε句子，不改變?cè)瓉?lái)的語(yǔ)言類。4*.上下文無(wú)關(guān)語(yǔ)言的可判定性對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，重要的是能機(jī)械且高效地在有限的時(shí)間內(nèi)判定一個(gè)符號(hào)串是否是語(yǔ)法上正確的程序，換句話說(shuō)，就是判定一個(gè)符號(hào)串是否是屬于該(程序設(shè)計(jì))語(yǔ)言的句子。這就是可判定性問題。一般地，可判定性問題可以這樣描述：設(shè)集合L是集合S的一個(gè)子集，而x是S的一個(gè)任意元素,問:是否可能機(jī)械而高效地判定x是否L的一個(gè)成員?

對(duì)于上下文無(wú)關(guān)語(yǔ)言，這問題的答案是肯定的。

2.4文法等價(jià)和等價(jià)變換2.4.1文法等價(jià)的概念文法G1與G2等價(jià)，若L(G1)=L(G2)。1.例L1={aibjck|i,j,k≥1}G1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|cG1'[S]:S::=Sc|BcB::=Bb|AbA::=Aa|aG1與G1'等價(jià)。2.文法等價(jià)變換的必要性文法等價(jià)變換的概念：對(duì)文法進(jìn)行變換，使得變換后的文法滿足某種要求，并且與原文法等價(jià)，這種變換稱為文法的等價(jià)變換。文法等價(jià)變換的必要性

?使文法類與語(yǔ)言類一致

?消去二義性

?使文法適用于某種分析技術(shù)

?特殊需要文法等價(jià)變換的種類：

?壓縮文法等價(jià)變換

?消去左遞歸文法等價(jià)變換

?消除單規(guī)則文法等價(jià)變換

?增廣文法等價(jià)變換

2.4.2壓縮文法等價(jià)變換1.壓縮了的文法目的：使文法中任一規(guī)則都能用來(lái)生成文法的句子，使文法中無(wú)多余規(guī)則。多余規(guī)則：U::=U形規(guī)則不滿足下列條件的規(guī)則Ｕ::=u：條件１Ｚ=>*…U…(U出現(xiàn)在句型中）條件２u=>*tt∈VT+(可推導(dǎo)到終結(jié)符號(hào)串）概念：若文法中任一規(guī)則都滿足上述條件１和條件2,則稱壓縮了的文法。

Z=>*xUy=>xuy=>*tt∈VT+,即，t是句子。76文法壓縮（化簡(jiǎn)）的基本思想條件1）若一符號(hào)不能出現(xiàn)在文法的任何句型中，則該符號(hào)是無(wú)用的。

條件2）若一個(gè)非終結(jié)符不能推導(dǎo)出終結(jié)符號(hào)串，則該非終結(jié)符是無(wú)用的。

從識(shí)別符號(hào)開始或從終結(jié)符號(hào)開始。刪除這些規(guī)則，不會(huì)改變文法描述的語(yǔ)言2.無(wú)用規(guī)則的判別算法

算法步驟如下:

步驟１規(guī)則展開成非縮寫形式并刪除U::=U形規(guī)則;

步驟２判別條件１，刪除不滿足條件１的規(guī)則;

步驟３判別條件２，刪除不滿足條件２的規(guī)則;

步驟４重復(fù)步驟２和步驟３，直到無(wú)規(guī)則被刪除。實(shí)現(xiàn)：采用加標(biāo)記的算法。

采用加標(biāo)記的算法。對(duì)條件1：U::=xVy中，若規(guī)則左部U加過標(biāo)記，則對(duì)右部非終結(jié)符號(hào)V加標(biāo)記。對(duì)條件2：U::=xVy,若規(guī)則右部全由終結(jié)符號(hào)和加過標(biāo)記的非終結(jié)符號(hào)組成,則對(duì)左部非終結(jié)符號(hào)加標(biāo)記。對(duì)于文法G[Z]：

Z∷=BeA∷=Ae｜A｜eB∷=Ce｜AfC∷=CfD∷=f

步驟1展開并刪除U::=U形規(guī)則成：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=CfD∷=f步驟2判條件1，加標(biāo)記：

*******

Z∷=BeA∷=AeA∷=eB∷=Ce

****

B∷=AfC∷=CfD∷=f規(guī)則D∷=f是多余的,應(yīng)刪除。從而得到文法

G'[Z]：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=Cf

步驟3判條件2，加標(biāo)記：

*****

Z∷=BeA∷=AeA∷=e

*

*

B∷=CeB∷=AfC∷=Cf

規(guī)則B∷=Ce與C∷=Cf是多余的，應(yīng)刪除。

重復(fù)判條件1與2，最終得到與文法G[Z]等價(jià)的壓縮了的文法G″[Z]:Z∷=BeA∷=AeA∷=eB∷=Af

壓縮文法等價(jià)變換的規(guī)范步驟：步驟１規(guī)則展開成非縮寫形式并刪除U::=U形規(guī)則;步驟２判別條件１，刪除不滿足條件１的規(guī)則;步驟３判別條件２，刪除不滿足條件２的規(guī)則;步驟４重復(fù)步驟２和步驟３，直到無(wú)規(guī)則被刪除。3.*

實(shí)現(xiàn)之考慮2.4.3消去左遞歸的文法等價(jià)變換左遞歸的存在將導(dǎo)致自頂向下語(yǔ)法分析失敗自頂向下：即從識(shí)別符號(hào)出發(fā)，使用不同規(guī)則進(jìn)行推導(dǎo)。左遞歸可使分析陷入無(wú)窮循環(huán)，導(dǎo)致棧溢出U=>Ux=>Uxx=>Uxxx=>…=>因此，對(duì)自頂向下分析技術(shù)，需要消除左遞歸。2.4.3消去左遞歸的文法等價(jià)變換1.規(guī)則左遞歸的消去(U::=Ux|y)U=>Ux=>Uxx=>Uxxx=>…=>yxx…xx例G[E]：E::=E+T|TU'T::=T*F|FF::=(E)|iE=>E+T=>E+T+T=>…U'=>T+T+T…+T+TU'a.改成右遞歸T+T+T…+T+TU::=Ux|y→U::=yU'U'::=xU'|εE'例E::=TE'E'::=+TE'|?E'T::=FT'T'::=*FT'|?E'一般情況下，U::=Ux1|Ux2|…|Uxm|y1|y2|…|ynU::=Ux1|Ux2|…|Uxm|y1|y2|…|yn→U::=U(x1|x2|…|xm)|(y1|y2|…|yn)→U::=(y1|y2|…|ym)U'U’::=(x1|x2|…|xn)U'|ε

b.用擴(kuò)充表示法

U::=Ux|y→U::=y{x}一般情況下，

U::=Ux1|Ux2|…|Uxn|y1|y2|…|ym→U::=U(x1|x2|…|xn)|(y1|y2|…|ym)→U::=(y1|y2|…|ym){x1|x2|…|xn}2.文法左遞歸的消去（間接的規(guī)則左遞歸）基本思想:對(duì)非終結(jié)符號(hào)排序成U1、U2、…、Un后文法等價(jià)變換成呈下形:U1::=Ui1…(或U1::=T…)i1>1U2::=Ui2…(或U2::=T…)i2>2…Uj::=Uij…(或Uj::=T…)ij>j…Un-1::=Un…(或Un-1::=T…)Un::=T…T∈VT一般地，對(duì)于Ui::=Uj…必有：j>i,從而不可能產(chǎn)生U=>+U…U->…->Ua文法左遞歸消去文法左遞歸的算法步驟:

步驟１把非終結(jié)符號(hào)排序成U1,U2,…,Un

步驟２以上列順序執(zhí)行下列程序：

for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ui::=Ujr的規(guī)則改寫成:Ui::=xj1r|xj2r|…|xjkr

其中Uj::=xj1|xj2|…|xjk是對(duì)于Uj的一切規(guī)則

}

消除關(guān)于Ui的規(guī)則左遞歸;}消去文法左遞歸等價(jià)變換的解題規(guī)范：步驟1識(shí)別是規(guī)則左遞歸還是文法左遞歸步驟2進(jìn)行相應(yīng)的文法等價(jià)變換步驟3給出消去了左遞歸的等價(jià)文法例設(shè)有文法G[S]：

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh

試消去其文法左遞歸。

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh解:步驟1排序：U1=SU2=T(n=2)

步驟2執(zhí)行循環(huán)：

i=1，j=1：j＞i－1，不執(zhí)行關(guān)于j的循環(huán)，消去關(guān)于U1=S的規(guī)則左遞歸（改寫成右遞歸）：

S∷=(Tbc|Td)S'S'∷=aS'|εi=2，j=1：有規(guī)則T∷=Se|gh，呈U2::=U1…形，把S∷=(Tbc|Td)S'代入，得

T∷=(Tbc|Td)S'e|gh因此,T∷=T((bc|d)S'e)|gh

消去關(guān)于U2=T的規(guī)則左遞歸如下:T∷=ghT'T'∷=(bc|d)S'eT'|ε最后得到文法G[S]：

G[S]：S∷=Sa｜Tbc｜TdT∷=Se｜gh消去了左遞歸的等價(jià)文法G'[S]：

S∷=T(bc｜d)S'S'∷=aS'|εT∷=ghT'T'∷=(bc|d)S'eT'|ε例設(shè)有文法G[A]：

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah

試消去該文法的左遞歸。

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah解：首先判別知，該文法存在文法左遞歸。步驟1排序成：U1=A，U2=B,U3=C；步驟2執(zhí)行循環(huán)：

i=1,j=1:j＞i－1，不執(zhí)行關(guān)于j的循環(huán)，且關(guān)于U1=A不存在規(guī)則左遞歸。

i=2,j=1:有規(guī)則B∷=Ae|dA|f，呈U2::=U1…形，把規(guī)則A∷=Ba|Cb|c代入，得

B∷=(Ba|Cb|c)e|dA|f或B∷=Bae｜Cbe｜c(diǎn)e｜dA｜f消去關(guān)于U2=B的規(guī)則左遞歸，所以,B∷=(Cbe|ce|dA|f)B'B'::=aeB'|ε

i=3,j=1:有規(guī)則C::=Ah|Bg，呈U3::=U1…形，把規(guī)則A::=Ba|Cb|c代入,C::=(Ba|Cb|c)h|Bg或C::=B(ah|g)|(Cb|c)hi=3,j=2:由規(guī)則C∷=B(ah|g)|(Cb|c)h,呈U3::=U2…形，把規(guī)則B∷=(Cbe|ce|dA|f)B'代入，得

C::=(Cbe|ce|dA|f)B'(ah|g)|(Cb|c)h或C::=C(beB'(ah|g)|bh)|(ce|dA|f)B'(ah|g)|ch消去關(guān)于U3=C的規(guī)則左遞歸，得到

C∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε最后得到消去了左遞歸的等價(jià)文法

G'[A]:A∷=Ba｜Cb｜c(diǎn)B∷=(Cbe|ce|dA|f)B'

B'::=aeB'|εC∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε3.*

實(shí)現(xiàn)之考慮要點(diǎn):·識(shí)別文法是規(guī)則左遞歸還是文法左遞歸

·文法在計(jì)算機(jī)內(nèi)的存儲(chǔ)表示2.5

語(yǔ)法分析樹與句型分析

2.5.1語(yǔ)法分析樹的概念1.語(yǔ)法分析樹的引進(jìn)

<句子>

術(shù)語(yǔ)：結(jié)點(diǎn)根結(jié)點(diǎn)末端結(jié)點(diǎn)

<主語(yǔ)><謂語(yǔ)><狀語(yǔ)>

邊

分支

<名詞><動(dòng)詞><介詞><名詞>

分支名字結(jié)點(diǎn)

分支結(jié)點(diǎn)

Berryswimsinriver

分支結(jié)點(diǎn)符號(hào)串子樹子樹末端結(jié)點(diǎn)符號(hào)串樹末端結(jié)點(diǎn)符號(hào)串語(yǔ)法分析樹

一個(gè)句型推導(dǎo)過程的樹形表示稱為語(yǔ)法分析樹，或簡(jiǎn)稱語(yǔ)法樹。語(yǔ)法樹的優(yōu)點(diǎn)是：它有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。語(yǔ)法樹通常表示成一棵倒立的樹，根在上，樹葉在下。

語(yǔ)法樹離不開句型，一棵語(yǔ)法樹是相對(duì)于某個(gè)句型而存在，脫離句型的語(yǔ)法樹是不存在的。句子

Berryswinsinriver的推導(dǎo)：<句子>=><主語(yǔ)><謂語(yǔ)><狀語(yǔ)>=><名詞><謂語(yǔ)><狀語(yǔ)>=>Berry<動(dòng)詞><狀語(yǔ)>=>Berryswins<狀語(yǔ)>=>Berryswins<介詞><名詞>=>Berryswinsin<名詞>

=>Berryswinsinriver如何為它構(gòu)造語(yǔ)法分析樹？2.從推導(dǎo)構(gòu)造語(yǔ)法分析樹從推導(dǎo)構(gòu)造語(yǔ)法分析樹的步驟如下.

步驟1以識(shí)別符號(hào)為根結(jié)點(diǎn)，對(duì)應(yīng)于第一個(gè)直接推導(dǎo)向下作分支。步驟2從第二個(gè)直接推導(dǎo)左邊被替換的非終結(jié)符號(hào)相應(yīng)的結(jié)點(diǎn)向下作分支,對(duì)應(yīng)于此直接推導(dǎo)。步驟3類似地對(duì)應(yīng)于每個(gè)直接推導(dǎo),從左邊被替換的非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)向下作分支,相應(yīng)于此直接推導(dǎo)。如此繼續(xù)，直到推導(dǎo)完。重要性質(zhì)：

分支的分支結(jié)點(diǎn)符號(hào)串是相應(yīng)句型中相對(duì)于分支名字結(jié)點(diǎn)的簡(jiǎn)單短語(yǔ)。

Z=>*xUy=>xuyU=>u

子樹的末端結(jié)點(diǎn)符號(hào)串是相應(yīng)句型中相對(duì)于子樹根結(jié)點(diǎn)的短語(yǔ)。

Z=>*xUy=>+xuyU=>+u利用語(yǔ)法分析樹尋找句型中的簡(jiǎn)單短語(yǔ)和短語(yǔ)。3.從語(yǔ)法分析樹構(gòu)造推導(dǎo)這是從推導(dǎo)構(gòu)造語(yǔ)法分析樹的逆過程。

EF*i+i=>i*i+iT*i+i=>F*i+i=>i*i+iE+TT*F+i=>T*i+i=>F*i+i=>i*i+i