编译简单复习2

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=a n | n为偶数的文法例：设计定义L=a n | n为奇数的文法例：设计定义L=a nbm | n为奇数，m为大于0的偶数的文法例：设计定义L=a nbmcn| n为奇数，m为大于0的偶数的文法例：设计定义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 。文法中某产生式的右部 句柄：FEE-TTF(+ETF)ETFiTF*()EET 第三章 词法分析单词结构描述机制 有穷自动机（识别机制），

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.1. 求最小化的DFA。 正规式 正规式法 NFA DFA 最小化DFA 词法分析程序 分裂法 转换规则 分划法 子集法 确定化：AB0,10,11A A A,B A,B A,B A,BAB0,

5、101A A BB B B0 10 1也是最小化（2）正规文法 右线性正规文法和左线性正规文法（3）正规式2. 三者之间转换 (1)有穷自动机到正规文法或正规式转换 上例：转换成正规式：0*1(0|1)* 转换成右线性正规文法：A0A|1B|1，B0B|1B|0|1 转换成左线性正规文法：BB0|B1|A1|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 求：最小化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结点是多余的，应该去掉AB0,101SABC100,110,10最小化:S,A合并；B,C合并AB0,101 第四章自顶向下的语法分析 主 要 内 容 两种分析方法： LL(1) (预测分析法)方法 递归子程序方法 主要问题：回溯问题。 主要练习：LL(1)文法判定与改写 LL(1)分析表的构造( 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)去掉括号，引进非终结符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的分析表对于： 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:= 第五章第五章 算符优先分析法算符优先分析法 解决问题：解决问题：1.非规范非规范归约法：最左素短语。归约法：最左素短语。2

11、.算符文法（算符文法（OG）和算符优先文法）和算符优先文法(OPG)。3.素短语及最左素短语。素短语及最左素短语。4.构造算符优先关系矩阵构造算符优先关系矩阵.(FIRSTVT( )和和LASTVT( )例：例：设有文法GS:S =AA =B|AiBB =C|B+CC =)A*|(求：非终结符的求：非终结符的FIRSTVT和和LASTVT；构造优先关系矩阵。；构造优先关系矩阵。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)