北方工业大学编译原理习题集

编译原理课后习题（修订版）第二章高级语言及其语法描述3、何谓“标识符”，何谓“名字”，两者的区别是什么？解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。4、令＋、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值：（1）、优先顺序（从高至低）为＋、*和↑，同级优先采用左结合。（2）、优先顺序为↑、＋、*，同级优先采用右结合。解：（1）、1＋1*2↑*1↑2=2*2↑*1↑2=4↑*1↑2=4↑↑2=（2）、1＋1*2↑*1↑2=6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9（1）、G6的语言L(G6)是什么？（2）、给出句子0127、34和568的最左推导和最右推导。分析：根据产生式N→D∣ND可以看出，N最终可推导出1个或多个（可以是无穷多个）D，根据产生式D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9可以看出，每个D可以推导出0至9中的某一个数字。因此，N最终推导出的是由0到9这10个数字组成的字符串。解：（1）、L(G6)是由0到9这10个数字组成的字符串。（2）、句子0127、34和568的最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127N=ND=DD=3D=34N=ND=NDD=DDD=5DD=56D=568句子0127、34和568的最右推导：N=ND=N7=ND7=N27=ND27=N127=D127=0127N=ND=N4=D4=34N=ND=N8=ND8=N68=D68=5687、写一个文法，使其语言是奇数集，且每个奇数不以0开头。分析：本题要构造一个文法，由它产生的句子是奇数，且不以0开头。也就是说它的每个句子都以1、3、5、7、9中某数结尾。如果数字只有一位，则满足要求；如果有多位，则要求第一位不能是0；而中间有多少位，每位是什么数字则没有要求。因此我们可以把这个文法分3部分完成，分别用3个非终结符来产生句子的第一位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1到9中的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。解：G(S)：A→2∣4∣6∣8∣DB→A∣0C→CB∣AD→1∣3∣5∣7∣9S→CD∣D8、令文法为E→T∣E+T∣E-TT→F∣T*F∣T/FF→(E)∣i（1）给出i+i*i、i*(i+i)的最左推导和最右推导；（2）给出i+i+i、i+i*i和i-i-i的语法树。解：（1）最左推导为：E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*iE=T=T*F=F*F=i*F=i*(E)=i*(E+T)=i*(T+T)=i*(F+T)=i*(i+T)=i*(i+F)=i*(i+i)最右推导为：E=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*iE=T=T*F=F*F=F*(E)=F*(E+T)=F*(E+F)=F*(E+i)=F*(T+i)=F*(F+i)=F*(i+i)=i*(i+i)（2）语法树：9、证明下面的文法是二义的：S→iSeS∣iS∣i分析：根据文法二义性定义，如果要证明该文法是二义的，必须找到一个句子，使该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个TE+EFi+TFiiE+TEFi*TFiTFiEE-TEFiTFi-FiETF文法，根据我们对程序语言的了解，不难发现这个文法应该是用来表示if…else…结构的（用“i”表示“if”或语句集，用e代表else）。因此我们就要到if…else…结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。解：考虑句子iiiei，存在如下两个最右推导：S=iSeS=iSei=iiSei=iiieiS=iS=iiSeS=iiSei=iiiei由此该文法是二义的。10、把下面文法改为无二义的：S→SS∣(S)∣()分析：本题给出的文法是二义的，关键在于S→SS是产生二义性的根源。我们将该产生式改造成等价的递归结构，消除二义性。解：S→TS∣T，T→(S)∣()11、给出下面语言的相应文法：L1={anbnci∣n≥1，i≥0}，L2={aibncn∣n≥1，i≥0}L3={anbnambm∣n，m≥0}L4={1n0m1m0n∣n，m≥0}分析：语言L1要求a和b的个数一样多，且至少为一个；c的个数为0个以上。因此我们可用一个非终结符去生成anbn串，用另外一个非终结符去生成ci。语言L2要求b和c的个数一样多，因此可用一个非终结符去生成bncn，而使用另外一个非终结符去生成ai。因此可以模仿L1生成L2。对于L3，可将anbnambm分两段考虑，即anbn和ambm，然后用两个非终结符分别去产生他们。L4不能采用分段处理的方式，它要求中间的0和1的个数相同，而且一前一后的0和1的个数相同。对于这种题型我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个0和n个1。解：L1的文法：S→AC；A→aAb∣ab；C→cC∣εL2的文法：S→AB；A→aA∣ε；B→bBc∣bcL3的文法：S→AB；A→aAb∣ε；B→aBb∣εL4的文法：S→1S0∣A；A→0A1∣ε；第三章词法分析1、编写一个对于Pascal源程序的预处理程序。该程序的作用是，每次被调用时都将下一个完整的语句送进扫描缓冲区，去掉注释行，同时要对源程序列表打印。2、请给出以下C++程序段中的单词符号及其属性值。intCInt：：nMulDiv（intn1，intn2）{if（n3==0）return0；elsereturn（n1*n2）/n3；}3、用类似C或Pascal的语言编写过程GetChar，GetBC和Concat。4、用某种高级语言编写并调试一个完整的词法分析器。5、证明3.3.1中关于正规式的交换律、结合律等五个关系。6、令A、B和C是任意正规式，证明以下关系成立：A∣A=A(A*)*=A*A*=ε∣AA*(AB)*A=A(BA)*(A∣B)*=(A*B*)*=(A*∣B*)*A=b∣aA当且仅当A=a*b证明：（1）、A∣A=AL(A∣A)=L(A)∪L(A)=L(A)，所以有A∣A=A。（2）、(A*)*=A*（3）、A*=ε∣AA*通过证明两个正规式所表示的语言相同来证明两个正规式相等。L(ε∣AA*)=L(ε)∪L(A)L(A*)=L(ε)∪L(A)(L(A))*=L(ε)∪L(A)((L(A))0∪(L(A))1∪(L(A))2∪(L(A))3∪…)=L(ε)∪(L(A))1∪(L(A))2∪(L(A))3∪(L(A))4∪…=(L(A))*=L(A*)即：L(ε∣AA*)=L(A*)，所以有：A*=ε∣AA*（4）、(AB)*A=A(BA)*利用正规式的分配率和结合律直接推导。(AB)*A=((AB)0∣(AB)1∣(AB)2∣(AB)3∣…)A=εA∣(AB)1A∣(AB)2A∣(AB)3A∣…=Aε∣A(BA)1∣A(BA)2∣A(BA)3∣…=A(ε∣(BA)1∣(BA)2∣(BA)3∣…)=A(BA)*即：(AB)*A=A(BA)*（5）、(A∣B)*=(A*B*)*=(A*∣B*)*证明:先证(A∣B)*=(A*B*)*因为L(A)L(A)*L(B)*,L(B)L(A)*L(B)*故:L(A)∪L(B)L(A)*L(B)*于是由本题第二小题结论可知(L(A)∪L(B))*(L(A)*L(B)*)*①又L(A)L(A)∪L(B),L(B)L(A)∪L(B)故:L(A)*(L(A)∪L(B))*L(B)*(L(A)∪L(B))*因此有:L(A)*L(B)*(L(A)∪L(B))*(L(A)∪L(B))*=((L(A)∪L(B))*)2故(L(A)*L(B)*)*((L(A)∪L(B))*)*由本题第二小题得:((L(A)∪L(B))*)*=(L(A)∪L(B))*故得:(L(A)*L(B)*)*(L(A)∪L(B))*②则由①②得:(L(A)∪L(B))*=(L(A)*L(B)*)*由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*即有(L(A)∪L(B))*=L((A*B*))*③而(A|B)*对应的语言为(L(A)∪L(B))*,且(A*B*)*对应的语言为L((A*B*))*则根据③得(A|B)*=(A*B*)*再证:(A*|B*)*=(A*B*)*因为:A,B是任意正规式,由以上结论得:(A*|B*)*=((A*)*(B*)*)*又由本题第二小题目的结论可得：（A*）*=A*，（B*）*=B*因此，（A*|B*）*=（A*B*）*综合上述两种结论，最后得：(A∣B)*=(A*B*)*=(A*∣B*)*（6）、A=b∣aA当且仅当A=a*b7、构造下列正规式相应的DFA1(0∣1)*1011(1010*∣1(010)*1)*00*10*10*10*(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*解：(1)、1(0∣1)*101第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y：再对该转换图进行分解，得到分解后的NFA如下图：第二步：对NFA进行确定化，获得状态转换矩阵：状态01{X}Ø{1，2，3}{1，2，3}{2，3}{2，3，4}{2，3}{2，3}{2，3，4}{2，3，4}{2，3，5}{2，3，4}{2，3，5}{2，3}{2，3，4，Y}{2，3，4，Y}{2，3，5}{2，3，4}根据转换矩阵获得相应的DFA：第三步：化简该DFA，获得最简的DFA即为所求。首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。{0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5}因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行进一步的划分，检查其中的所有状态。状态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}。01234100010111501X1(0∣1)*101YX12345Y1ε101ε01检查集合{1，2}，{1，2}0={2}，{1，2}1=3，不需要进行进一步划分。所以最终划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。所以，最终所求DFA如下图示：（2）、1(1010*∣1(010)*1)*0（3）、0*10*10*10*（4）、(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*8、给出下面正规表达式：（1）以01结尾的二进制数串；（2）能被5整除的十进制整数；（3）包含奇数个