《编译原理样题（含答案）》由会员分享，可在线阅读，更多相关《编译原理样题（含答案）（8页珍藏版）》请在金锄头文库上搜索。
1、编译原理试题计算机学院_级 班 学号 姓名 题号 一二三四五六七八九十总分满分得分一 选择题 1、编译原理各阶段工作都涉及 (第 1 章)： A.词法分析 B.表格管理 C.语法分析 D.语义分析 2、正则表达式 R1 和 R2 等价是指 (第 4 章) A.R1 和 R2 都是定义在一个字母表上的正则表达式 B.R1 和 R2 中使用的运算符相同 C.R1 和 R2 代表同一正则集 D.R1 和 R2 代表不同正则集 3、在以下的语法分析中， 特别适合于表达式的分析。(第 5，6，7 章) A.LR 分析 B.LL(1)分析 C.递归下降分析 D.算符优先分析 4、与（a|b）*(a|b)等
2、价的正规式是 。(第 4 章) A.a*| b* B.(ab)*(a|b) C.（a|b） （a|b）* D.（a|b）* 5、在语法制导翻译中不采用拉链回填技术的语句是 。(第 8 章) A.跳转语句 B.赋值语句 C.条件语句 D.循环语句 6、在属性文法中，终结符只具有 属性。(第 8 章) A.传递 B.继承 C.抽象 D.综合 7、过程的 Display 表中记录了_ _。(第 10 章) A. 过程的连结数据 B. 过程的嵌套层数 C. 过程的返回地址 D. 过程的入口地址二 判断题 1、最左归约也称为规范归约。(第 3 章) 2、逆波兰法表示的表达式把运算对象放在运算符的后面。(
3、第 8 章) 3、同心集的合并有可能产生“归约/归约”冲突。(第 7 章) 4、DFA 可以通过多条路径识别一个符号串。(第 4 章) 5、动态数组的存储空间在编译时就可完全确定。(第 10 章)三 填空题 1、词法分析所依循的是语言的 ；而中间代码生成所依循的是 。(第 4，8 章) +2、在 LR(0)分析法中，若,V*且 a则称“S .A”为 TV项目，称“S .a”为 项目。(第 7 章) 3、规范规约每次规约的是句型的_。 (第 6 章) 4、无符号常数的识别和计算该常数的工作，通常在_阶段完成的。 (第 4 章)四、设字母表为a,b的语言 L 的句子是满足下述条件的串：每个 a 都
4、有 b 直接 跟在右边。构造该语言的正则式。 （第 4 章）五、将下图的 NFA 确定化为 DFA,图中初态为 X，终态为 Y。(第 4 章)六、写一个 2 型文法 G，使得 L(G)=ai+2bi|i=0aibi+2|i=0。(第 3 章)七、设文法 G（S）：(第 5 章)S SaF|aF|aFF *aF|*a （1）消除左递归和左因子； （2）构造相应的 FIRST 和 FOLLOW 集合； （3）构造预测分析表。八、对文法 GS:S aSb | P (第 6 章) P bPc | bQc Q Qa | a 请构造简单优先关系表，该文法是否是简单优先文法？ 九、设有以下程序段(第 10
5、章) program main; var a,b:integer; procedure p(x,y,z:integer);begin y:=y*2;z:=z+xend;begina:=5; b:=2; p(a*b,a,a); write(a) end. 对于下列参数传递方式，分别写出执行程序后 a 的输出值。 （1）传值； （2）传地址； （3）值结果； （4）传名。十、文法 GS及其 LR 分析表如下，请给出对串 dada#的分析过程。(第 7 章) GS: 1) S VdB 2) V e3) V 4) B a 5) B Bda 6) B ACTIONGOTO状态dea#SBV 0r3 S3
6、 1 2 1 acc 2S4 3r2 4r6 S5r6 6 5r4 r4 6S7 r1 7 S8 8r5 r5 十一、试将下述程序段翻译成三地址形式的中间代码表示。(第 8 章) while ( a+b100 goto L2 halt L2: F:=F-1 goto L1十三、对 PL/0 语言扩充单词-=和-: (第 2 章) 请完成下列识别单词- ， -和- （设单词内码分别为 MINUS，MINUSBECOME 和 MINUSMINUS）的词法分析算法：if ( CH=- ) ;if ( ) SYM=MINUSBECOME; GetCh(); else if ( CH=- ) else
7、答案 一 选择题 b,c,d,c,b,d,b二 判断题 三 填空题 1、文法 语义 2、待约项目 移进项目 3、句柄 4、词法四 (b|ab)*五 解：用子集法确定化如下表 IIaIb状态 X,0,1,3 0,1,3. 2,3,Y. 1,3. 2,Y. Y.0,1,3 0,1,3 1,31,32,3,Y 2,3,Y Y. 2,Y. Y.-X 1 +2 3 +4 +Y确定化后如下图六 解：文法 G（S）：S aSbS aaS bb七 解：（1） （消除左递归，提公因左因子）SaFS|aFSSaFS|F*aFFF|（2）FIRST（S）a，十 FOLLOW（S）FIRST（50）， FOLLOW（
8、S）FIRST（F）* FOLLOW（F）（，）FIRST（F）*， FOLLOW（，（3） 八 Head(S)=a,P,b Head(P)=b Head(Q)=Q,aTail(S)=b,P,c Tail(P)=c Tail(Q)=a （1） “=”关系： a=S S=b b=P P=c b=Q Q=c Q=a （2） “”关系： Tail(S)b Tail(P)c Tail(Q)a 简单优先关系矩阵如下： SabPQc S=a=b= = Q= c由于矩阵中有元素存在多种优先关系，故不是简单优先文法。九 （1）5； （2）20； （3）15； （4）30。十 对输入串 dada#的分析过程 步
9、骤状态栈文法符号栈剩余输入符号动作 1 2 30 02 024# #V #Vddada# dada# ada#用 V 归约 移进 移进4 5 6 7 8 90245 0246 02467 024678 0246 01#Vda #VdB #VdBd #VdBda #VdB #Sda# da# a# # # #用 B a 归约 移进 移进 用 B Bda 归约 用 S VdB 归约 接受十一 解：三地址代码如下： 100:t:=a+b 101:if t100 goto L2halt B4 L2: F:=F-1 B5 goto L1 十三 GetCh(); CH=SYM=MINUSMINUSSYM=MINUS
