编译原理精华总结--计算题.pptVIP

* 课堂练习 求回边 7→4 组成的循环。 解：首先，确定循环出口为7，然后求7的前驱是5和6，它们都不是4，再分别求5的前驱(=4)，6的前驱(=4)，此时算法终止，得到循环{7，6，5，4}。 由回边求循环 1 2 3 4 5 6 7 * * * * * 在程序流图中，对任意结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为 m DOM n；流图中结点n的所有必经结点的集合称为n的必经结点集，记为D(n)。 * 回边：设 a→b 是流图中的一条有向边，如果 b DOM a，则称 a→b 是流图中的一条回边。 * 由回边 n→d 组成的循环的基本思想是： 该循环以d为其唯一入口，n是循环的一个出口，只要n不同时是循环入口d，那么n的所有前驱就应该属于循环。在求出n的所有前驱之后，只要它们不是循环入口d，就应再继续求出它们的前驱，而这些新求出的所有前驱也应属于循环，然后再对新求出的所有前驱重复上述过程，直到所求出的前驱都是d为止。 * * 练习：给出i+i*i的规范推导，并画出语法树。 i Ｅ ＋ i Ｅ ＊ i Ｅ Ｅ Ｅ 最左推导过程：E=E + E =i + E =i + E * E =i + i * E =i + i * i 文法G[E]如下： E→E+E E→E*E E→( E ) E→i 课堂练习 * （1）转换函数； （3）状态转换图 DFA三种表示的转换 （2）状态转换矩阵； DFA M=({0,1,2,3},{a,b},f,0,{3}) f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=2 f(2,b)=3 f(3,a)=2 f(3,b)=1 a b 0 1 2 0 1 3 2 0 2 2 3 0 3 2 1 1 ? a 1 0 3 2 a a b b b b a * 课堂练习 4 f 3 5 6 2 1 i ? ? ? ? a a a a b b b b start NFA转变为DFA * 等价的DFA a C D B A E F S b a a a a a b b b b b a b F start NFA转变为DFA * DFA最小化 课堂练习：把下图最小化 * （1）将所有状态分成两个子集：终态集｛0｝和非终态集｛1,2,3,4,5｝； （2）当输入a时可判断｛1,2,3,4,5｝可再拆分，拆分后：｛4｝｛1,2,3, 5｝； （3）当输入b时可判断｛1,2,3,5｝可再拆分，拆分后：｛1, 5｝｛2,3｝； （4）当输入a时可判断｛2,3｝可再拆分，拆分后：｛2｝｛3｝； ｛1, 5｝在输入a或b时指向相同，不可再拆。 得：最小DNF为： DFA最小化 课堂练习 构造a(b*c|c*b)的NFA a(b*c|c*b) S Z S A Z a b*c|c*b S A Z a c*b b*c B S A Z a b b c C ε ε c 正规式构造NFA 课堂练习 4 3 5 2 1 ? ? a a a a b b b b 求以下NFA的正规式 第一步 6 4 a a z 3 5 2 1 s ? ? ? ? a a b b b b 6 NFA构造正规式 第二步 第三步 第四步 z s (a|b)*(aa|bb)(a|b)* aa|bb z 5 2 s （a|b）* （a|b）* aa z 5 2 1 s ? ? ? ? a|b a|b bb 6 NFA构造正规式 例:给出如图NFA等价的正规文法G A B C D a a a b b b b G=（{A，B，C，D}，{a，b}，P，A） 其中P：A → aB A → bD B → bC C → aA C → bD C → ε D → aB D → bD D → ε NFA构造正规文法 课堂练习 求G[S]:S→aS|bS|aA|bB A→aC|a, B→bC|b C→aC|bC的等价的NFA B A S a a a a b b b b C 正规文法构造NFA * 课堂练习 文法G[E]：E→E+T| E-T|T T→T*F| T/F|F F→(E)|I 消除方法左递归 E→TE E→+TE‘|-TE|? T→FT T→*FT| /FT| ? F→(E)|i 消除左递归