编译原理样题3讲义.doc

*编译原理 样题 一 选择题 【 】1．____型文法也称为正规文法。 　　　[A] 0 [B] 1 [C] 2 [D] 3 【 】2．____文法不是LL(1)的。 　　 [A] 递归 [B] 右递归 [C] 2型 [D] 含有公共左因子的 【 】3． 文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。 　　　[A]1 [B]3 [C]5 [D]7 【 】4．四元式之间的联系是通过 实现。 [A]临时变量 [B]指示器 [C]符号表 [D]程序变量 【 】5．同心集合并可能会产生的新冲突为 。 [A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约 【 】6．代码优化时所依据的是 。 [A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则 【 】7．表达式a-(-b)*c的逆波兰表示为 。 [A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* （注：@为单目减运算符） 【 】8．过程的DISPLAY表记录了 。 [A]过程的连接数据 [B]过程的嵌套层次 [C]过程的返回地址 [D]过程的入口地址 二 填空题．　　 、语义分析、　　 代码优化和目标代码生成。 2．词法分析阶段的任务式从左到右扫描 　　 ，从而识别 　．　　 ，则称文法G1和G2是等价的。 4．对于文法G[E]：E→T|E+T T→F|T*F F→PF|P P→(E)|i，句型T+T*F+i的句柄是　　 　　　 　。 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。所谓最左素短语是指处于句型最左边的那个素短语。P*P和i是句型P*P+i的素短语，而P*P是它的最左素短语。 ．最右推导的逆过程称为 ，也称 。 ． ，算符优先分析中的可规约串是 。 7．（A∨ B）∧（C∨ ?D∧ E） 。 8．　　 和　　 。 9．符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表是 的依据。 ．　　 的DISPLAY表的内容加上　　 。 三 有穷自动机M接受字母表(＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。 ab)*a 与正规式a(ba)*等价 用构造他们的最小的DFA方法。写一个文法，使其语言是L ＝ { 1n0m1m0n | m,n≥0 } 对文法G[S] 　 S → aSb | P P → bPc | bQc Q → Qa | a 它是否是算符优先文法？请构造算符优先关系表 文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请证实。 已知文法G为: S′→ S S → aAd S → bAc S → aec S → bed A → e 试构造它的LR（1）项目集LR（1）分析表 prod:=0; i:=1; while i≤20 do begin prod:=prod+a[i]*b[i]; i:=i+1 end; 试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。 程序 文法规则 语 义 规 则 S→(T) S→i T→T,S T→S 十一 对PL/0语言的while语句 while 条件B DO 语句S 的编译程序， 请在空缺处填空，完成该语句的编译算法： switch (SYM) { …… case WHILESYM: ; GetSym(); CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX); ; GEN(JPC,0,0); if (SYM==DOSYM) ; else Error(18); S