編譯原理 第 四 講

1.文法的類型通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類型：0型文法：對(duì)任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外2型文法：對(duì)任一產(chǎn)生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT文法的類型例：1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA

C→aCA

Ba→aB

C→bCB Bb→bB

AD→aD C→ε BD→bD D→ε

Aa→bD文法的類型例：2型（上下文無(wú)關(guān)）文法

文法G[S]： S→AB A→BS|0 B→SA|1

3型文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT

I→l T→lT

T→dT

T→l

T→d

2.文法之間的包含關(guān)系2型文法1型文法0型文法四種文法之間的逐級(jí)“包含”關(guān)系3型文法3.文法和語(yǔ)言0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言1型文法或上下文有關(guān)文法（CSG）產(chǎn)生的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言（CSL）2型文法或上下文無(wú)關(guān)文法（CFG）產(chǎn)生的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言（CFL）

3型文法或正則（正規(guī)）文法（RG）產(chǎn)生的語(yǔ)言稱為3型語(yǔ)言正則（正規(guī)）語(yǔ)言（RL）

上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法有足夠的能力描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)語(yǔ)法樹(shù)---句型推導(dǎo)的直觀表示描述簡(jiǎn)單算術(shù)表達(dá)式的文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P為：{E→i,E→E+E,E→E*E,E→(E)}描述一種簡(jiǎn)單賦值語(yǔ)句的產(chǎn)生式：〈賦值語(yǔ)句〉→i∶=E描述條件語(yǔ)句的產(chǎn)生式：〈條件語(yǔ)句〉→if〈條件〉then〈語(yǔ)句〉｜

if〈條件〉then〈語(yǔ)句〉else〈語(yǔ)句〉1.規(guī)范推導(dǎo)和規(guī)范歸約G[s]:①S→aAS

②A→SbA

③A→SS

④S→a

⑤A→ba

推導(dǎo)過(guò)程一：SaASaAaaSbAaaSbbaaaabbaa

推導(dǎo)過(guò)程二：SaASaSbASaabASaabbaSaabbaa

推導(dǎo)過(guò)程三：SaASaSbASaSbAaaabAaaabbaa

1.規(guī)范推導(dǎo)規(guī)范句型最左（最右）推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型規(guī)范推導(dǎo)的逆過(guò)程，稱為最左歸約，也稱為規(guī)范歸約。例：設(shè)有文法G[E]：

E→E+T|T

T→T*F|F

F→(E)|a

給出句子a+a*a的最左和最右推導(dǎo)2.語(yǔ)法樹(shù)設(shè)G=(VN,VT,P,S)為一cfg，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱作G的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(派生樹(shù)）：1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2.根的標(biāo)記是S3.若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定A∈VN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹(shù)的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之

構(gòu)造語(yǔ)法樹(shù)G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a

EE+TT

T*FF

Faa

a看不出句型中的符號(hào)被替代的順序一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?例：G[E]:

E→i E→E+E E→E*E E→(E)

EE+EE*Eiii

EE*EiE+E

ii句型i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i3.文法的二義性

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的

或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的

文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可以為無(wú)二義性尋找一組充分條件二義文法改造為無(wú)二義文法G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)規(guī)定優(yōu)先順序和結(jié)合律

句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。句型的分析算法分類分析算法可分為：自上而下分析法：

從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。自下而上分析法：

從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。

兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。自上而下方法是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串自下而上方法則是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上地構(gòu)造語(yǔ)法樹(shù)1.自上而下的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子

S S S

c A d

c A d

a

b推導(dǎo)過(guò)程：S

cAd

cAd

cabd2.自下而上的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否該文法的句子

S

A

A

cabd

ca

bd

ca

b

d

規(guī)約過(guò)程構(gòu)造的推導(dǎo)：

cAd

cabdS

cAd句型分析中的關(guān)鍵問(wèn)題1）在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個(gè)右部去替代B？2）在自下而上的分析方法中如何識(shí)別可歸約的串？ 在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”刻畫“可歸約串”文法G[S]句型的短語(yǔ)S=>*

αAδ且A

=>+

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)句型的直接短語(yǔ)若有A

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的直接短語(yǔ)句型的句柄一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄

例：i*i+i的短語(yǔ)、直接短語(yǔ)和句柄

EE

+T

T

FT*

F

i3

短語(yǔ)：i1*i2+i3，

i1*i2

，F(xiàn)

i2

i1

，

i2

，

i3。i1

直接短語(yǔ)：i1

，

i2

，

i3。句柄：

i1

G[E]：E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+i化簡(jiǎn)文法文法實(shí)用中的一些說(shuō)明文法中不含有有害規(guī)則和多余規(guī)則有害規(guī)則：形如U→U的產(chǎn)生式。會(huì)引起文法的二義性多余規(guī)則：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則文法中不含有不可到達(dá)和不可終止的非終結(jié)符1）文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達(dá)。2）文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串，該非終結(jié)符稱為不可終止。對(duì)于文法G[S]，為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個(gè)條件：

1.A必須在某句型中出現(xiàn)即有S=>*

αAβ，其中α，β屬于V*2.必須能夠從A推出終結(jié)符號(hào)串t來(lái)即A=>*

t，其中t∈VT*化簡(jiǎn)文法例：G[S]： 1)S→Be

2)B→Ce

D為不可到達(dá) 3)B→AfC為不可終止

4)A→Ae

5)A→e

6)C→Cf

7)D→f

產(chǎn)生式

2），6），7）為多余規(guī)則應(yīng)去掉。上下文無(wú)關(guān)文法中的ε規(guī)則上下文無(wú)關(guān)文法中某些規(guī)則可具有形式A→ε，稱這種規(guī)則為ε規(guī)則因?yàn)棣乓?guī)則會(huì)使得有關(guān)文法的一些討論和證明變得復(fù)雜,有時(shí)會(huì)限制這種規(guī)則的出現(xiàn)兩種定義的唯一差別是ε句子在不在語(yǔ)言中文法構(gòu)思的啟示是要找出語(yǔ)言的有窮描述，而如果語(yǔ)言L有一個(gè)有窮的描述，則L1=L∪｛ε｝也同樣有一個(gè)有窮的描述，并且可以證明，若L是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言或正規(guī)語(yǔ)言，則L∪｛ε｝和L-｛ε｝分別是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。思考本章目的為語(yǔ)言的語(yǔ)法描述尋求工具,以便：對(duì)源程序給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀）根據(jù)語(yǔ)言文法的特點(diǎn)來(lái)進(jìn)行語(yǔ)法分析從描述語(yǔ)言的文法可以自動(dòng)構(gòu)造出可用的分析程序制導(dǎo)語(yǔ)義翻譯1.什麼是文法,什麼是它的語(yǔ)言?2.我們?yōu)槭颤N關(guān)注上下文無(wú)關(guān)文法?3.語(yǔ)法分析方法的分類?[本章小結(jié)]1.本章出現(xiàn)的概念較多,應(yīng)重點(diǎn)理解文法,推導(dǎo),句型句子及語(yǔ)言的定義等概念.語(yǔ)法分析有關(guān)內(nèi)容在后面章節(jié)會(huì)詳細(xì)討論.2.文法作為程序語(yǔ)言的語(yǔ)法的描述工具,它用規(guī)則只能陳述的是:語(yǔ)言的所有句子以什麼樣的符號(hào)串能出現(xiàn).請(qǐng)記住文法和語(yǔ)言的形式定義中的“形式”的含義—只涉及語(yǔ)言的語(yǔ)法不涉及語(yǔ)言的語(yǔ)義.3.本章內(nèi)容是形式語(yǔ)言理論的一部分.形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。[本章小結(jié)]考察本章知識(shí)點(diǎn)最典型的題目是1.已知文法G[A]，寫出它定義的語(yǔ)言描述

如：G[A]:A→0B|1C

B→1|1A|0BB

C→0|0A|1CC答案:G[A]定義的語(yǔ)言由0、1符號(hào)串組成，串中0和1的個(gè)數(shù)相同.2.給出語(yǔ)言描述，構(gòu)造文法.如：構(gòu)造一文法,其定義的語(yǔ)言是由算符+,*,(,)和運(yùn)算對(duì)象a構(gòu)成的算術(shù)表達(dá)式的集合.答案1:

G[E]E→E+T|T

T→T*F|F

F→(E)|a答案2:

G[E]E→E+E|E*E|(E)|a相關(guān)術(shù)語(yǔ)的回顧（英文版）上下文無(wú)關(guān)文法Acontextfreegrammar(grammarforshort)consistsofterminals,nonterminals,astartsymbol,andproductions.Terminalsarethebasicsymbolsfromwhichstringsareformed.Nonterminalsaresyntacticvariablesthatdenotesetsofstringsthathelpdefinethelanguagegeneratedbythegrammar.Inagrammar,onenonterminalisdistinguishedasthestartsymbol,andthesetofstringsitdenotesisthelanguagedefinedbythegrammar.Theproductionsofagrammarspecifythemannerinwhichtheterminalsandnonterminalscanbecombinedtoformstring.句型句子和語(yǔ)言GivenagrammarGwithstartsymbolS,wecanusethe=>*relationtodefineL(G),thelanguagegeneratedbyG.StringsinL(G)maycontainonlyterminalsymbolsofG.WesayastringofterminalswisinL(G)ifandonlyifS=>*

w.ThestringwiscalledasentenceofG.IfS=>*α,wherαmaycontainnonterminalsthenwesaythatαisasententialformofG

驗(yàn)證文法生成的語(yǔ)言AproofthatagrammarGgeneratesalanguageLhastwoparts:wemustshowthateverystringgeneratedbyGisinL,andcoverselythateverystringinLcanindeedbegeneratedbyG.語(yǔ)法樹(shù)和推導(dǎo)Aparsetreemaybeviewedasagraphicalrepresentationforaderivationthatfiltoutthechoiceregardingreplacementorder.Theleavesoftheparsetreearelabeledbynonterminalsorterminalsand,readfromlefttoright,theyconstituteasententialform,calledtheyieldorfrontierofthetree.句型分析，語(yǔ)法分析Parsingistheprocessofdetermingifastringoftokencanbegeneratedbyagrammar.Mostparsingmethodsfallintooneoftwoclasses,calledthetop-downandbottom-upmethods.Thesetermsrefertotheorderinwhichnodesintheparsetreeareconstructed.Intheformer,constructionstartsattherootandproceedstowardstheleaves,while,inthelater,constructionstartsattheleavesandproceedstowardstheroot.二義性Agrammarthatproducesmorethanoneparsetreeforsomesetenceissaidtobeambiguous.Putanotherway,anambiguousgrammar

isone

thatproducesmorethanoneleftmostormorethanrightmostderivationforthesamesentence.Sometimesanambiguousgrammarcanberewrittentoeliminatetheambiguity.Forexmplesuitablegrammarsforexpressioncanoftenbeconstructedusingassociativityandprecedenceinformation,asintheslide74消除左遞歸規(guī)則AgrammarisleftrecursiveifithasanonterminalAsuchthatthereisaderivationA=>+Aαforsomestringα