1、編譯簡單復習 第二章形式語言與文法1.語言 a. 定義：L(GS)=x|S x，xVT b. 推導中的概念：推導，短語，簡單短語，素短語，句柄，最 左素短語，句子，句型等。用語法樹求解。 c.已知文法怎樣寫出定義的語言？ 基本方法是推導，綜合組成句子特點，用通式寫出。特點：句子由哪些終結符組成，它們的順序關系怎樣，個數怎樣，初始 值是什么。例：GS: SAC A aAb| C Cc| L(GS)=?2. 文法 a. 概念：四元式： （VN,VT,P,S） b.分類：短語文法(0)，上下文有關文法(1)，上下文,無關文法(2),正規文法(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中間；個數：a，b相同，c不同；初值：0開始的整數。例：求定義語言L=anbmambn|n0,m 0的文法例：設計定義L=a n | n為偶數的文法例：設計定義L=a n | n為奇數的文法例：設計定義L=a nbm | n為奇數，m為大于0的偶數的文法例：設計定義L=a nbmcn| n為奇數，m為大于0的偶數的文法例：設計定義L=anbn+1|n0 的文法

3、例：設計定義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 。文法中某產生式的右部 句柄：FEE-TTF(+ETF)ETFiTF*()EET 第三章 詞法分析1.單詞結構描述機制 有窮自動機（識別機

4、制），正規文法，正規式 a.三者之間的轉換關系 單詞5種。 b.概念 （1）有窮自動機：五元組： M=(S, ,f,S0,F) ; 分類：確定和非確定； 表示：函數式，狀態圖和狀態矩陣。三者等價表示。 最小化的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. 求最小化的DFA。 正規式 正規式法 NFA DFA 最小化DFA 詞法分析程序 分裂法 轉換規則 分劃法 子集法 確定化：AB0,10,110 1A A A,B A,B A,B A,B

5、A A BB B B0 1AB0,101也是最小化（2）正規文法 右線性正規文法和左線性正規文法（3）正規式2. 三者之間轉換 (1)有窮自動機到正規文法或正規式轉換 上例：轉換成正規式：0*1(0|1)* 轉換成右線性正規文法：A0A|1B|1，B0B|1B|0|1 轉換成左線性正規文法：BB0|B1|1A|1，AA0|0(2)正規文法到正規式轉換關鍵式：關鍵式：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)使用求解規則：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)*即為所求的正規式。 正規式到正規文法轉換 例： S=a(a|d)* SaA ， A(a|d)*， A (a|d)A| A aA|dA| 最后： SaA ， A aA|dA| （3）有窮自動機確定化和最小化 利用最小化的自動機可以證明：兩個正規式或正規文法等價。例：已知正規式：0*1(0|1)* 或者已知正規文法： A0A|1B|1，B0B|1B|0|1 求：最小化DFA 第四章自頂向下的語法分析 主 要 內 容 兩種分析方法： LL(1) (預測分析法)方法 遞歸子程

7、序方法 主要問題：回溯問題。 主要練習：LL(1)文法判定與改寫 LL(1)分析表的構造1.LL(1)文法判定與改寫 LL(1)文法判定： SELECT(U:=xi)SELECT(U:=xj)= 求： FIRST和FOLLOW兩個集合 改寫后的文法也要判定。 到LL(1)文法的改寫：分別用消除左遞歸和提取左公共因子的方 法。（1）提取左公共因子一般形式）提取左公共因子一般形式A:= 1|2|n (為左公共因子)提取左公共因子：A:= (1|2 | |n)去掉括號，引進非終結符A:A:= AA := 1|2|n（2）消除左遞歸消除左遞歸 如：AAa|b 改寫：AbA A aA| 例：已知文法G：

8、 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(A) =a(,d )= SELECT(B:=bB)SELECT(B:=) =b(FOLLOW(B) =b(l)= G是LL(1)文法2. LL(1)分析表的構造例：構造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:=dBB:=dB B:=