编译原理简单复习

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:=