编译原理期末试题二答案.doc

编译原理试卷二 一、 选择1.下面说法正确的是：A 一个正规式只能对应一个确定的有限状态自动机；B 一个正规语言可能对应多个正规文法； 2.算符优先分析与规范归约相比的优点是：A 归约速度快B 对文法限制少3.一个LR（1）文法合并同心集后若不是LALR（1）文法： A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突4.下面说法正确的是：A Lex是一个词法分析器的生成器B Yacc是一个语法分析器 二、 问答题问答第1题(5分) 将文法G[S] 改写为等价的G[S]，使G[S]不含左递归和左公共因子。　　G[S]： S→SAe|Ae 　　　　　 A→dAbA|dA|d 问答第2题(10分) 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。　　S→aD 　　D→STe|ε　　T→bH|H 　　H→d|ε 问答第3题(5分) 给出与正规式R＝（(ab)*|b）*（a|(ba)*）a 等价的NFA。问答第4题解：根据所给的PL/0示意程序完成下列要求。（1）(4分) 给出 当程序执行到A过程体的write(c) 语句时的栈式存储分配布局和用Display 显示表时A过程必威体育精装版活动记录的内容； （2）(2分) 说明在过程D中，当执行c:=b*a；语句时，变量c和b的存取位置是如何确定的（请填在下面的相应括号内）。　　c的存取位置=（ ） 　　b的存取位置=（ ）PL/0示意程序为：　　var c;　　procedure M; 　　　　procedure A;　　　　begin (* A *) 　　　　　write(c);　　　　end (* A *) 　　　procedure Z; 　　　　var a,b;　　　　procedure D 　　　　　begin (* D *) 　　　　　　c:=b*a；　　　　　　call A; 　　　　　end ；(* D *)　　　　begin (* Z *) 　　　　　call D; 　　　　end ；(* Z *) 　　　begin (*M *) 　　　　call Z; 　　　end ；(* M *) 　　begin (*main *) 　　　call M; 　　end. (* main *) 问答第5题（6分）试对 while (ab and ac) or a=d do S:=a;的四元式序列给出第四区段应回填的指令地址，并指出真假链和链头及回填的次序。 ? ? 应回填的值 回填的次序 ? (1) if ab goto ( 　 ) ( 　 ) 真链头 E.true= (2) goto ( 　 ) ( 　 ) 真出口链( 　 ) (3) if ac goto ( 　 ) ( 　 ) ? (4) goto ( 　 ) ( 　 ) 假链头 E.false= (5) if a=d goto ( 　 ) ( 　 ) 假出口链( 　 ) (6) goto ( 　 ) ( 　 ) ? (7) s:=a ? ? ? (8) goto ( 　 ) ( 　 ) ? (9) ? ? ? ? 问答第6题(10分) 某语言的文法G为： E → aTd|ε 　　　　　　　　　　　　 T → Eb|a 证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。 问答第7题(5分) 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。　　G[S]为： S →D;D|D　　　　　 　D →DB|B　　　　　　 B →a|b 问答第8题(5分) 文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析过程。　　G[S]: 0) S′→S 　　　1) S→dSoS　　　　　2) S →dS 　　　3) S →S;S 　　　　　4) S →a name ACTION GOTO d a ; a # S 0 S2 S3 ? S3 ? 1 1 ? ? S4 ? acc ? 2 S2 ? ? S3 ? 5 3 ? r4 r4 ? r4 ? 4 S2 ? ? S3 ? 6 5 ? S7 S4 ? r2 ? 6 ? r3 r3 ? r3 ? 7 S2 ? ? S3 ? 8 8 ? r1 S4 ? r1 ? 问答第9题（5分）文法G[S]为：　　S→V 　　V→T | ViT 　　T→F| T+F　　F→)V* |( 试给出句型ViFi( 的短语，简单(直接)短语,句柄和最左素短语。 问答第10题（5分） 下列语言或文法确切属于按乔姆斯基