編譯原理第二章(2).ppt

1、1,2、推導(dǎo)的形式定義 (1) 直接推導(dǎo)：如果Uu是G中的一條規(guī)則， x，yV*， 則將規(guī)則Uu用于符號(hào)串r=xUy上 得到符號(hào)串w =xuy 記為： xUy = xuy (r=w) 稱符號(hào)串w是符號(hào)串r的直接推導(dǎo),或符號(hào)串 r直接產(chǎn)生了符號(hào)串w,也稱w直接歸約到r.,2,例:上述文法GS可進(jìn)行的直接推導(dǎo), S=aB,(規(guī)則S aB ),文法BNF表示為 GS: S aB | bA A a | aS | bAA B b | bS | aBB,U =u (規(guī)則U u , x,y均為 ), abS=abbA,(規(guī)則S bA),xU =xu (規(guī)則U u , x為ab,y為 ), aB=aaBB (

2、規(guī)則B aBB) xU =xu (規(guī)則U u , x為aaB,y為 ),3,例:上述文法GS可進(jìn)行的系列直接推導(dǎo) 推導(dǎo)過程 使用規(guī)則 S=aB S aB =abS B bS =abbA S bA =abbbAA A bAA =abbbaA A a =abbbaa A a,只要符號(hào)串中存在非終結(jié)符號(hào),推導(dǎo)就能繼續(xù),直至符號(hào) 串全由終結(jié)符號(hào)組成,這也是為什么稱終結(jié)符和非終結(jié) 符的原因,文法BNF表示為 GS: S aB | bA A a | aS | bAA B b | bS | aBB,4,(2)推導(dǎo)(長度為n): 設(shè)u0,u1,un(n0)均V*,且有 r=u0=u1=u n-1=un=w 記

3、為r =+w 則稱以上序列為長度n的推導(dǎo), 也稱r產(chǎn)生w(w歸約為r) 特例:如果r= + w(一步或一步以上）或r=w(0步) 記為 r=*w,5,3、語言的形式定義 (1)句型:設(shè)有文法GZ,如果有Z=*x , x V*, 則稱x是文法G的一個(gè)句型. 凡是由開始符號(hào)（識(shí)別符號(hào)）推導(dǎo)出來的字匯表V上的終結(jié)和非終結(jié)符號(hào)組成的符號(hào)串叫做句型. (2)句子:如有Z=+x（或Z=*x）且xVt*, 則稱x是文法G的一個(gè)句子. 由Z推導(dǎo)的終結(jié)符號(hào)組成的符號(hào)串為句子。,6,(3)語言L(GZ):文法GZ產(chǎn)生的所有句子的集合, 稱文法GZ所定義的語言 L(GZ)=x|xVt*且Z=+x 例:G | | a

4、|b|z|A|Z 0|1|2|9 問題:符號(hào)串“a4y”是不是文法的句子?,7,推導(dǎo)過程1 y y 4y 4y a4y,推導(dǎo)過程2 = a a4 a4y,例:G | | a|b|z|A|Z 0|1|2|9,結(jié)論： a4y是文法的合法句子,8,例:G=(Vn,Vt,P,E) 其中:Vn=E,T,F Vt=+,*,(,),i E:文法的開始符號(hào) P: EE+T|T TT*F|F F(E)|i,GE:EE+T|T TT*F|F F(E)|i,E代表 表達(dá)式 T代表 項(xiàng) F代表 因子 i代表 標(biāo)識(shí)符（變量）,i*(i+i)是不是文法合法的句子？,9,例:G1A:ABb Ba L(G1)=ab G2A:

5、Aab L(G2)=ab G1G2但L(G1)=L(G2) 稱G1和G2為等價(jià)文法 (不同文法,相同語言). 給定文法后,可以確定它的語言,但由語言寫出的文法是比較難的,這里形式語言理論可以證明:,10,1給定一文法,就能從結(jié)構(gòu)上唯一確定其語言. 即 G 唯一確定 L(G) 2給定一語言,能確定其文法,但這種文法不是 唯 一的。 即L 確定 G1,或G2 3設(shè)G=(Vn,Vt,P,S)為一文法, 并設(shè)UxVy,是P中一產(chǎn)生式, 且V1|2|3|n 是P中V的全部產(chǎn)生式 又設(shè)G1=(Vn,Vt,P1,S)是其中P1從P中刪去UxVy, 加入U(xiǎn)x1y, Ux2y,， Uxny, 則L(G1)=L(

6、G),11,G3S:S A | S-A A a | b | c G4S:S A | A-S A a | b | c 符號(hào)串a(chǎn)-b-c是G3S 、G4S合法句子，但語義不同。,G3解釋為（a-b）-c G4解釋為 a-（b-c）,12,223 遞歸規(guī)則與遞歸文法 -用有窮的規(guī)則刻劃無窮的語言 1、遞歸規(guī)則 形如UxUy UVn, x,yV* 左右具有相同的非終結(jié)符號(hào)的規(guī)則 特別:UUy (x=)左遞歸規(guī)則 UxU (y=)右遞歸規(guī)則 UxUy (x,y)自嵌入遞歸規(guī)則 遞歸規(guī)則是對(duì)其左部的非終結(jié)符號(hào)進(jìn)行遞歸定義,13,2.文法的遞歸性 1)直接遞歸性:文法中至少包含一條遞歸規(guī)則 2)間接遞歸性:

7、文法的任一非終結(jié)符號(hào)經(jīng)一步 以上推導(dǎo)產(chǎn)生的遞歸性。 3)文法的遞歸性原則:文法具有直接遞歸性或 間接遞歸性,否則,文法無遞歸性。 例1：GZ：ZaZbab 具有直接遞歸性 例2：GZ：U Vx V Uy z 具有間接遞歸性 原因：U=Vx=Uyx,GE:EE+T|T TT*F|F F(E)|i,14,2.3 句型的分析 2.3.1 規(guī)范推導(dǎo)和歸約 1、最左(右)推導(dǎo):在任一步推導(dǎo)V=w中，都是 對(duì)符號(hào)串V的最左(右）非終結(jié)符號(hào)進(jìn)行替換, 稱最左（右）推導(dǎo)。 2、規(guī)范推導(dǎo):即最右推導(dǎo) 3、規(guī)范句型：由規(guī)范推導(dǎo)所得的句型. 4、規(guī)范歸約：規(guī)范推導(dǎo)的逆過程，稱規(guī)范歸約或 最左歸約。,15,例:G | | a|b|z|A|Z 0|1|2|9 問題:給出句子a4y的規(guī)范推導(dǎo)