编译原理PPT总结.doc

编译原理PPT总结1. 正规文法到正规式的转换: (1) 将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。(2) 依照求解规则：若 x = x | (或 x = x + ) 则解为 x = *;若 x = x | (或 x = x + ) 则解为 x = * 以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解。例1 设有正规文法G：Z 0AA 0A | 0BB 1A | 试给出该文法生成语言的正规式。分析 首先给出相应的正规式方程组(方程组中用“”代替正规式中的“ | ” )如下： Z=0A (1)A = 0A + 0B (2)B=1A+ (3)将(3)代入(2)中的B得A=0A+01A+0 (4) 对(4)利用分配律得A=(0+01)A+0 (5) 对(5)使用求解规则得A=(0+01)*0 (6) 将(6)代入(1)式中的A，得Z = 0 (0 + 01)* 0 即正规文法GZ所生成语言的正规式是:R = 0 (0 | 01)* 0 例2 设有正规文法G：A aB | bBB aC | a | bC aB 试给出该文法生成语言的正规式。分析 首先给出相应的正规式方程组(方程组中用“”代替正规式中的“ | ” )如下： A = aB + bB (1) B = aC + a + b (2)C = aB (3) 将(3)代入(2)中的C得B=aaB + a + b (4) 对(4)使用求解规则得B=(aa)*(a+b) (5) (5)代入(1)中的B得A = (a + b)(aa)*(a + b)即正规文法GA所生成语言的正规式是:R = (a | b)(aa)*(a | b)2. 正规式到正规文法的转换:(1) 令 VT= (2) 对任何正规式R选择一个非终结符Z生成规则ZR并令SZ。(3) 若a和b都是正规式，对形如 Aab 的规则转换成 AaB 和 Bb 两规则，其中B是新增的非终结符。(4) 对已转换的文法中, 形如Aa*b 的规则，进一步转换成 A aA | b 。 (5) 不断利用规则(3)和(4)进行变换，直到每条规则最多含有一个终结符为止。例1 将 R=(a | b)(aa)*(a | b) 转换成相应的正规文法。 解：令A是文法开始符号，根据规则(2)变换为：A (a | b)(aa)*(a | b)根据规则(3)变换为： A (a | b)BB (aa)*(a | b)对B根据规则(4)变换为 A aB | bBB aaB | a | b根据规则(3)变换为A aB | bBB aC | a | bC aB 3. 确定有限自动机(DFA)的定义：确定的有限自动机DFA M是一个五元式M =（S， ，s0 ，F )(1) S 是一个非空有限集，它的每个元素称为一个状态(2) 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表(3)是状态转换函数，是在SS上的单值映射。（s,a）=s意味着：当先行状态为s、输入字符为a时，将转到下一状态s。我们称s为s的一个后继状态。(4) s0S，是唯一的一个初态(5) F S，是一个终态集（可空）,终态也称可接受状态或结束状态。例如有DFA M=（0,1,2,3,a,b，,0,3）其中定义为：（0，a）=1 （0，b）=2 （1，a）=3 （1，b）=2 （2，a）=1 （2，b）=3（3，a）=3 （3，b）=3其它表示形式：状态转换矩阵和状态转换图NFA和DFA的不同在于：1) 的值域是S的子集2) 开始状态有不止一个3) 在NFA中每个结点可射出若干条弧与别的结点相连接,每条弧用中的一个正规式做标记。例如NFA M =(0,1,2,3,4,a,b,0,1,2)其中：(0,a)=0,3 (0,b)=0,4 (1,a)=1 (1,b)=1(2,a)=2 (2,b)=2 (3,a)=1 (3,b)= (4,a)= (4,b)=2 状态转换矩阵和状态转换图：012ab340,30,4112212例1 试构造识别语言R = (a | b)*abb 的NFA N, 使L(N)=L(R)。首先将R表示成如下拓广转换图 4. 从NFA M构造正规式r举例从NFA M构造正规式r举例：5. 由NFA确定DFA：将NFA确定化为DFA的原因： 使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该NFA接受 如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA例1 构造下述文法GZ的有穷自动机。Z0AA0A | 0BB1A | 解：f(Z,0)=A f(Z,1)= f(z, )= f(A,0)=A,B f(A,0)=A,B f(A,1)= f(A, )=f(B,0)= ff(B,0)= f(B,1)=A f(B, )=D例4. 设字母表=a,b，给出上的正规式 R= b*ab(b|ab)* 1. 试构造状态最小化的DFA M，使得L(M)=L(R)。2. 求右线性文法G，使L(G)=L(M)。 解：对正规式R=b*ab(b|ab)*采用分列法构造NFA，见下图。 对NFA采用子集法构造其等价的DFA的状态转换矩阵对DFA采用分化的方法得到状态最小化的DFA消去文法GS的左递归求非终结符A的Follow集的算法 1.如果A是开始符号，Follow(A)2.若有产生式BAa,aVT，则把a加入到Follow(A)中； 3.若有产生式BAX，XVN，则把First(X)中非元素加入Follow(A)中；4.若BA 或 BA， =，则把Follow(B)加入到Follow(A)中；5.连续使用上述规则，直到Follow(A)不再增大。设文法G(S)： S(L) | aS | aLL，S | S(1) 消除左递归和回溯；(2)计算每个非终结符的First和Follow集； (3) 构造预测分析表。练习1：文法GV： VN|NE EV|V+E Ni 是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而GV中含有回溯，所以先消除回溯得到文法GV： GV： VNV V|E EVE E|+E Ni由LL(1)文法的充要条件可证GV是LL(1)文法。练习2：有文法Gs: SBA ABS|d BaA|bS|c(1)证明文法G是LL(1)文法。(2)构造LL(1)分析表。(3)写出句子abccd的分析过程解：（1）对于文法Gs: SBA ABS|d BaA|bS|c其FIRST集如下： FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c。其FOLLOW集如下：首先， FOLLOW(S)=#;对SBA有： FIRST(A)加入FOLLOW(B), 即FOLLOW(B)=a, b, c, d ;对ABS有：FIRST(S)加入FOLLOW(B), 即FOLLOW(B)=a, b, c, d ;对BaA有：FOLLOW(B)加入FOLLOW(A), 即FOLLOW(A)=a, b, c, d ;对BbS有：FOLLOW(B)加入FOLLOW(S), 即FOLLOW(S)=#, a, b, c, d ;由ABS|d得：FIRST(BS) FIRST(d) = a, b, c d = ;由BaA|bS|c得： FIRST(aA) FIRST(bS) FIRST(c) =a b c= 。由于文法Gs不存在形如 的产生式，故无需求解形如FIRST()FOLLOW(A)的值。也即，文法GS是一个LL(1)文法。(2) 由Gs:SBA ABS|d BaA|bS|c的FIRST(B)=a, b, c; FOLLOW(B)=a, b, c, d ; FIRST(A)=a, b, c, d; FOLLOW(A)=a, b, c, d ;FIRST(S)=a, b, c。 FOLLOW(S)=#, a, b, c, d 可构造LL(1)预测分析表如下：6. 自下而上分析基本思想 ：从输入串出发，逐步进行归约，直至归约 到文法的开始符号，那么输入串是文法的 句子，否则输入串有语法错误或者说，从语法树的末端开始，步步向上 归约，修剪语法树，直到只剩根结点归约用产生式的左部替代右部关键寻找每步句型中可归约串寻找方式不同，分析方法不同效率更高，对语法限制更少直接短语（P85） 若* 且 A ，则称是句 相对于非终结符号A的直接短语一个句型的最左直接短语称为该句型的句柄素短语(1)是一个短语 (2)至少包含一个终结符(3)且除自身外不再包含其它素短语FIRSTVT和LASTVT集合的定义 关于文法G中的每个非终结符P：FIRSTVT(P)=a| P+a，或者P+Qa，aVT且QVN 含义：由P往下推导所有可能出现的首个终结符 例如：有F(E)|i ，则(，iFIRSTVT(F) 有EE+T，则EE+T，+FIRSTVT(E)LASTVT(P)=a|P+a，或者P+aQ, aVT且Q VN 含义：由P往下推导所有可能出现的最后一个终结符 例如：有 F(E)|i ，则)，iLASTVT(F) 有EE+T，则EE+T，+LASTVT(E)连续使用下面两条规则，直到FIRSTVT(P)不再扩大为止若有 Pa或PQa ,则aFIRSTVT(P)若aFIRSTVT(Q)，且有PQ，则aFIRSTVT(P) 即FIRSTVT(Q)加入FIRSTVT(P)连续使用下面两条规则，直到LASTVT(P)不再扩大为止若有 Pa或PaQ ,则aLASTVT(P)若aLASTVT(Q)，且有 PQ ，则aLASTVT(P) 即把LASTVT(Q)中加入LASTVT(P)中确定算符的优先关系，构造文法的算符优先表若有Aab或 AaPb，则a=b若有AaP,对b FIRSTVT(P),则ab1.可归前缀是指 A 。A 规范句型的（可归）前缀 B 活前缀 C 含有句柄的活前缀 D 句柄2. 若a为终结符,则A .a为 A 项目。A 移进 B 待约 C 规约 D 接受3. LR分析器核心部分是一张分析表,该表由 组成。（D）A ACTION表 B GOTO 表C LL(1)分析表 D ACTION表和GOTO 表4.算符优先分析法每次都是对 进行规约。（B）A 短语 B 最左素短语 C 素短语 D 句柄5 自下而上语法分析的基本思想是：从待输入的符号串出发，利用文法的产生式步步向上 规约，试图