编译原理(习题课)(二).doc

编译原理 朱雪峰 博士 计算机科学与技术系 Tel:O) Email: xuefeng.zhu@cup.edu.cn 1 第六题（ P36 第11题） 解：分析L2，要求b和c的个数一样多，因此可以使用一个非 终结符去生成bncn串，而用另外一个非终结符去生成ai， 因此，可以模拟L1使用一个非终结符去生成bncn，而用 另外一个非终结符去生成ai 。 L2的文法： S→AB A→ aA | ε B→ bBc | bc 2 第六题（ P36 第11题） 解：分析L3，可以将anbnambm分成两段考虑，即anbn和ambm， 然后使用两个非终结符分别去产生它们。 L3的文法： S→AB A→ aAb | ε B→ aBb | ε 3 第六题（ P36 第11题） 解：L4不能采用分段处理的方式，它要求中间的0和1的个数 相同，而且一前一后的1和0的个数相同。对于这种文法 我们可以采用从里向外扩展的方式进行，即先用一个非 终结符生成处于中间的m个0和m个1，然后，使用另外 一个非终结符在该串的基础上扩充前后的n个1和n个0。 L4: A→0A1 | ε S →1S0 | A 4 第七题（ P64 第7题） 7. 构造下列正规式相应的DFA ① 1(0|1)*101 ② 1(1010*|1(010)*1)*0 ③ 0*10*10*10* ④ (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 5 第七题（ P64 第7题①） 6 第七题（ P64 第7题① ） 0 1 状态 ? {X} 0 {1,2,3} 1 {1,2,3} 1 {2,3} 2 {2,3,4} 3 {2,3} 2 {2,3} 2 {2,3,4} 3 {2,3,4} 3 {2,5,3} 4 {2,3,4} 3 {2,3,5} 4 {2,3} 2 {2,3,4,Y} 5 {2,3,4,Y} 5 {2,5,3} 4 {2,4,3} 3 7 0 1 状态 第七题（ P64 第7题① ） {X} 0 {1,2,3} 1 ? {2,3} 2 {1,2,3} 1 {2,3,4} 3 {2,3} 2 {2,3} 2 {2,3,4} 3 {2,3,4} 3 {2,5,3} 4 {2,3,4} 3 {2,3,5} 4 {2,3} 2 {2,3,4,Y} 5 {2,3,4,Y} 5 {2,5,3} 4 {2,4,3} 3 8 第七题（ P64 第7题①） á 初始划分：{{0,1,2,3,4},{5}}， {0,1,2,3,4}0={2,4,_}, {0,1,2,3,4}1={1,3,5}。由于0不能接受字符0，需要把状态 0划分出来；另外，只有状态4读入字符1后进入状态5， 因此将状态4划分出来，划分的结果为4个集合： {{0},{1,2,3},{4},{5}}。 á 对于集合{1,2,3}，由于{1,2,3}0={2,4}，因此需要对 {1,2,3}进一步划分，划分结果为5个集合： {{0},{1,2},{3},{4}, {5}}。检查集合{1,2}，由于 {1,2}0={2},{1,2}1={3}，不需要进一步的划分。所以最 终划分结果为5个集合： {{0},{1,2},{3},{4},{5}} 9 第七题（ P64 第7题①） 10 第七题（ P64 第7题②） 1(1010*|1(010)*1)*0 11 第七题（ P64 第7题②） 0 1 0 1 状态 状态 ? ? {1} {2} {4,7,9} {5,8,2} {2} {9} {3,6} {5,2,9} {5,2,9} {3,6} ? ? {9} {3,6,8} {4,7,6} {2} {3,6} {4,7} {2} {4,7,6} {7} {5,8,2} ? ? {4,7} {5,8,2} {7} {8} {5,8,2} {5,2,6,9} {3,6} {8} {6} ? {5,2,6,9 {5,2,7,9} {3,6,2} {6} {7} {2} {5,2,7,9 {5,2,9} {3,6,8} } {3,6,2} {4,7,9} {3,6,2} } 12 第七题（ P64 第7题②） 13 第七题（ P64 第7题③） 0*10*10*10* 14 第七题（ P64 第7题④） (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 15 第七题（ P64 第7题④） 0 1 状态 {1} {2} {3} {2} {1,4} ? {3} {1,4} ? {1,4} {2,5} {3,7} {2,5} {1,4} {6} {3,7} {6} {1,4} {6} {8,10} {9,12} {8,10} {6} {1