編譯原理簡單復習

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

2、歸式： （1）單個符號的遞歸式：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=anbmambn|n0,m 0的文法 例：設計定義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ù)的文法 例：設計定義

3、L=anbn+1|n0 的文法 例：設計定義L=a nbm| nm0的文法 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)生式的右部 句柄：F E E - T T F ( + E T F ) E T F

4、i T F * () E ET 第三章 詞法分析 單詞結(jié)構(gòu)描述機制 有窮自動機（識別機制），正規(guī)文法，正規(guī)式 a.三者之間的轉(zhuǎ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)

5、換規(guī)則 分劃法 子集法 確定化： AB 0,1 0,1 1 0 1 A A A,B A,B A,B A,B A A B B B B 0 1 AB 0,1 0 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|1A|1，AA0|0 (2)正規(guī)文法到正規(guī)式轉(zhuǎn)換 關鍵式：關鍵式：AxA|y A= x*y 例：例：SaA|a寫成:S=aA+a（1） A aA|dA|a|d寫成:A

6、=aA+dA+a+d（2） 將（2）式簡化為：A=(a+d)A+(a+d) 使用求解規(guī)則：A=(a|d)*(a|d) （3） 將（3)的A代入（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|

7、1，B0B|1B|0|1 求：最小化DFA 第四章自頂向下的語法分析 主 要 內(nèi) 容 兩種分析方法： LL(1) (預測分析法)方法 遞歸子程序方法 主要問題：回溯問題。 主要練習：LL(1)文法判定與改寫 LL(1)分析表的構(gòu)造 1.LL(1)文法判定與改寫 LL(1)文法判定： SELECT(U:=xi)SELECT(U:=xj)= 求： FIRST和FOLLOW兩個集合 改寫后的文法也要判定。 到LL(1)文法的改寫：分別用消除左遞歸和提取左公共因子 的方 法。 （1）提取左公共因子一般形式）提取左公共因子一般形式 A:= 1|2|n (為左公共因子) 提取左公共因子： A:= (1|2

8、 | |n) 去掉括號，引進非終結(jié)符A: A:= A A := 1|2|n （2）消除左遞歸消除左遞歸 如：AAa|b 改寫：AbA A aA| 例：已知文法G： A:=aABl | a .(1) B:=Bb | d .(2) 試給出與G等價的LL(1)文法G。 解：消除左遞歸和回溯 消除（1）式的回溯，改寫（1）式為：A:=aA A:=ABl | 消除(2)式的左遞歸，改寫(2)式為:B:=dB B:=bBI 改寫后G為： A:=aA A:=ABlI B:=dB B:=bBI 判G為LL(1)文法： SELECT(A:=ABl )SELECT(A:=) =FIRET(ABl)(FOLLOW(

9、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:=aA ” 對于： 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:=dB B:=dB B:=