編譯簡單復習2

1、編譯簡單復習 第二章形式語言與文法1.語言 a. 定義：L(GS)=x|S x，xVT b. 推導中的概念：推導，短語，簡單短語，素短語，句柄，最 左素短語，句子，句型等。用語法樹求解。 c.已知文法怎樣寫出定義的語言？ 基本方法是推導，綜合組成句子特點，用通式寫出。特點：句子由哪些終結(jié)符組成，它們的順序關(guān)系怎樣，個數(shù)怎樣，初始值是什么。例：GS: SAC A aAb| C Cc| L(GS)=?2. 文法 a. 概念：四元式： （VN,VT,P,S） b.分類：短語文法(0)，上下文有關(guān)文法(1)，上下文,無關(guān)文法(2),正規(guī)文法(3) c.已知語言怎樣設計文法？ *常用的遞歸式： （1）單

2、個符號的遞歸式：AA| 或者： AA| 定義的語言： L(GA)=n|n1 （2）成對符號的遞歸式：AA| 定義的語言： L(GA)=nn|n1例：求定義語言L=anbncm|n0,m 0的文法 特點：字符：a，b，c；順序：a前c后b中間；個數(shù)：a，b相同，c不同；初值：0開始的整數(shù)。例：設計定義L=a n | n為偶數(shù)的文法例：設計定義L=a n | n為奇數(shù)的文法例：設計定義L=a nbm | n為奇數(shù)，m為大于0的偶數(shù)的文法例：設計定義L=a nbmcn| n為奇數(shù)，m為大于0的偶數(shù)的文法例：設計定義L=anbn+1|n0 的文法例：設計定義L=a nbm| nm0的文法例：求定義語言

3、L=anbmambn|n0,m 0的文法3.用語法樹求解求：短語，簡單短語，素短語，句柄，最左素短語。證明：文法二義性。例：有文法GE: E:=E+T|E-T|T T:=T*F|T/F|F F:=(E)|i 求句型(F+i)-T*(E-T)的短語，簡單短語和句柄。 解：畫句型(F+i)-T*(E-T)的語法樹：短語：F, i, F+i , (F+i) , E-T, (E-T), T*(E-T), (F+i)T*(E-T).。簡單短語：F, i , E-T 。文法中某產(chǎn)生式的右部 句柄：FEE-TTF(+ETF)ETFiTF*()EET 第三章 詞法分析單詞結(jié)構(gòu)描述機制 有窮自動機（識別機制），

4、正規(guī)文法，正規(guī)式 a.三者之間的轉(zhuǎn)換關(guān)系 單詞5種。 b.概念 （1）有窮自動機：五元組： M=(S, ,f,S0,F) ; 分類：確定和非確定； 表示：函數(shù)式，狀態(tài)圖和狀態(tài)矩陣。三者等價表示。 最小化的DFA視為詞法分析程序的框圖。 練習： 確定化最小化例：已知有窮自動機M=(A,B,0,1,f,A.B),其中：f為： f(A,0)=A, f(A,1)=A,B, f(B,0)=B, f(B,1)=B.1. 求最小化的DFA。 正規(guī)式 正規(guī)式法 NFA DFA 最小化DFA 詞法分析程序 分裂法 轉(zhuǎn)換規(guī)則 分劃法 子集法 確定化：AB0,10,11A A A,B A,B A,B A,BAB0,

5、101A A BB B B0 10 1也是最小化（2）正規(guī)文法 右線性正規(guī)文法和左線性正規(guī)文法（3）正規(guī)式2. 三者之間轉(zhuǎn)換 (1)有窮自動機到正規(guī)文法或正規(guī)式轉(zhuǎn)換 上例：轉(zhuǎn)換成正規(guī)式：0*1(0|1)* 轉(zhuǎn)換成右線性正規(guī)文法：A0A|1B|1，B0B|1B|0|1 轉(zhuǎn)換成左線性正規(guī)文法：BB0|B1|A1|1，AA0|0(2)正規(guī)文法到正規(guī)式轉(zhuǎn)換關(guān)鍵式：關(guān)鍵式：AxA|y A= x*y例：例：SaA|a寫成:S=aA+a（1） A aA|dA|a|d寫成:A=aA+dA+a+d（2）將（2）式簡化為：A=(a+d)A+(a+d)使用求解規(guī)則：A=(a|d)*(a|d) （3）將（3)的A代入

6、（1)式：S=a(a|d)*(a|d)|a =a(a|d)*(a|d) |) a(a|d)*(a|d)| )= a(a|d)*即為所求的正規(guī)式。 正規(guī)式到正規(guī)文法轉(zhuǎn)換 例： S=a(a|d)* SaA ， A(a|d)*， A (a|d)A| A aA|dA| 最后： SaA ， A aA|dA| （3）有窮自動機確定化和最小化 利用最小化的自動機可以證明：兩個正規(guī)式或正規(guī)文法等價。例：已知正規(guī)式：0*1(0|1)* 或者已知正規(guī)文法： A0A|1B|1，B0B|1B|0|1 求：最小化DFAABC00,10,111XADBCY00,11由0*1(0|1)*得:由A0A|1B|1，B0B|1B

7、|0|1得: 0 1X,A,B A,B C,D,YA,B A,B C,D,YC,D,Y D,Y D,YD,Y D,Y D,Y 0 1A A B,CB,C B,C B,C 0 1 A A B B B B 0 1 S A B A A B B C C C C C由圖可見，C結(jié)點是多余的，應該去掉AB0,101SABC100,110,10最小化:S,A合并；B,C合并AB0,101 第四章自頂向下的語法分析 主 要 內(nèi) 容 兩種分析方法： LL(1) (預測分析法)方法 遞歸子程序方法 主要問題：回溯問題。 主要練習：LL(1)文法判定與改寫 LL(1)分析表的構(gòu)造( FIRST( )和FOLLOW(

8、 ) )1.LL(1)文法判定與改寫 LL(1)文法判定： SELECT(U:=xi)SELECT(U:=xj)= 求： FIRST和FOLLOW兩個集合 改寫后的文法也要判定。 到LL(1)文法的改寫：分別用消除左遞歸和提取左公共因子的方 法。（1）提取左公共因子一般形式）提取左公共因子一般形式A:= 1|2|n (為左公共因子)提取左公共因子：A:= (1|2 | |n)去掉括號，引進非終結(jié)符A:A:= AA := 1|2|n（2）消除左遞歸消除左遞歸 如：AAa|b 改寫：AbA A aA| 例：已知文法G： A:=aABl | a .(1) B:=Bb | d .(2) 試給出與G等價

9、的LL(1)文法G。解：消除左遞歸和回溯消除（1）式的回溯，改寫（1）式為：A:=aA A:=ABl |消除(2)式的左遞歸，改寫(2)式為:B:=dB B:=bB |改寫后G為： A:=aA A:=ABl | B:=dB B:=bB |判G為LL(1)文法： SELECT(A:=ABl )SELECT(A:=) =FIRET(ABl)(FOLLOW(A ) =a(,d )= SELECT(B:=bB)SELECT(B:=) =b(FOLLOW(B) =b(l)= G是LL(1)文法2. LL(1)分析表的構(gòu)造例：構(gòu)造G的分析表對于： A:=aA， FIRST(A)=a MA,a =”A:=a

10、A ”對于： A:=ABl， FIRST(A)=a MA,a =”A:=ABl ” A:=， FOLLOW(A)=d,# MA,d=”A:= ”對于：B:=dB， MB,d =”B:=dB ” MA,#=”A:= ”對于： B:=bB MB,b =”B:=bB ” 對于： B:= ， FOLLOW(B)=d,# MB,d =” B:= ” MB,# =” B:= ”ab l d # AA:=aA AA:=ABlA:= A:= B BB:=bB B:=dBB:=dB B:= 第五章第五章 算符優(yōu)先分析法算符優(yōu)先分析法 解決問題：解決問題：1.非規(guī)范非規(guī)范歸約法：最左素短語。歸約法：最左素短語。2

11、.算符文法（算符文法（OG）和算符優(yōu)先文法）和算符優(yōu)先文法(OPG)。3.素短語及最左素短語。素短語及最左素短語。4.構(gòu)造算符優(yōu)先關(guān)系矩陣構(gòu)造算符優(yōu)先關(guān)系矩陣.(FIRSTVT( )和和LASTVT( )例：例：設有文法GS:S =AA =B|AiBB =C|B+CC =)A*|(求：非終結(jié)符的求：非終結(jié)符的FIRSTVT和和LASTVT；構(gòu)造優(yōu)先關(guān)系矩陣。；構(gòu)造優(yōu)先關(guān)系矩陣。FIRSTVT(S)=i,+,),( FIRSTVT(A)=i,+,),( FIRSTVT(B)=+,),(FIRSTVT(C)=),(.LASTVT(S) =i,+,*,( LASTVT(A) =i,+,*,( LASTVT(B) =+,*,( LASTVT(C) =*,(iB: iFIRSTVT(B) i +,),( +C :+ FIRSTVT(C) + ),( )A: ) FIRSTVT(A) ) i i,+,),(i B+: LASTVT(B) + +,),( +A*: LASTVT(A) * i,+,),(* ) = *對#S#，有#=#, #FIRSTVT(S), 即： #; 即： +，(，），），i # 按行填按行填+*i()#+*i() =#=由表可見，文法不是OPG文法而是OG文法 第六章 LR分析法主要問題： 三種方法：LR(0)