编译原理复习题.doc

编译原理复习题1. 设G=（VN，VT，P，）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？答：一般形式为a，VN，a(VNVT)*。若G是正则文法，则一般形式为a或a，、VN，aVT（或a，a）。2. 何谓二义性文法？试举一例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。例子：给定文法G：*|a|b考察句子ab*，它有两棵不同的推导树，如下所示：3. 试正确消除下述传递图的e弧，使其接收的语言不变。1e-Se11110e，100ee+ABCDEFG答：4. 试将下述程序段翻译成三地址形式的中间代码表示。5+6 （a + b）;答: 100: t1:=a+b101: t2:=6*t1102: t3:=5+t2A（B （C D）;答: 200:if A goto 202 201:goto T 202:if B goto 204 203:goto F 204:if C goto T 205:goto 206 206:if D goto T 207:goto Ffor j:=1 to 10 do aj + j:=0;答:300:j:=1301:if j10 goto NEXT302:i:=j+j303:ai:=0304:goto 301while ( a+bc OR a=b )while ( a5 AND b10 ) a=a+1; b=b+1;答：三地址代码如下：100:t:=a+b101:if tc goto 105102:goto 103103:if a=b goto 105104:goto 0105:if a5 goto 107106:goto 100107:if b y then x:=10 else x:= x + y;答:400:if xy goto 402401:goto 404402:x:=10403:goto 405404:x:=x+y405:5. 试判定下述文法G是否是LR（1）文法？为什么？aa答：1）因为对文法G存在的句子aaa，有两棵不同的推导树，如图4.5所示。图4.5 两棵不同的推导树所以该文法是二义性文法，G不是LR(1)文法。2）可构造文法G的状态集，考虑增广文法G，如表4.29所示。表4.29 文法G的LR(1)状态集状 态 T项 目 集输入符号下一状态0,1,2a,a2a,aa31,Accept2,a,aa4a,a /a, a /a43a,aa#34a,aa#2a,a /a /#3到此不用继续计算，因为状态T4是不适定状态，对输入符a出现了“归约归约”冲突，因此文法G不是LR(1)文法。6. 对给定正则表达式b*（d | ad）（b | ab）+ 构造其NFA M。答: 7. 证明下面文法是SLR(1)文法，并构造其SLR分析表。EE + T | TTT F | FFF* | a | b答：分析表如下所示：状 态 T项 目 集输入符号下一状态0* E E E1 E E+ T E1 E T T2 T T F T2 T F F3 F F* F3 Fa a4 Fb b51* E EAccept* E E+ T+62* E T/+#2* T T F F7 F F* F7 Fa a4 Fb b53* T F /+/a/b#4* F F* *84* Fa #65* Fb #76* E E+ T T9 T T F T9 T F F3 F F* F3 Fa a4 Fb b57* T T F /+/a/b#3* F F* *88* F F* #59* E E+ T/+#1* T T F F7 F F* F7 Fa a4 Fb b58. 构造下列正则表达式的确定性的有限状态自动机。aba(a|b)*a答： 9. 文法GE的产生式为： EE + T | TTT * E | FF I |（E）给出（I+I）* I的最左推导、最右推导及相应的推导树；列出句型F + T * F的所有短语、简单短语和句柄。答：a)最左推导：ETT*EF*E(E)*E(E+T)*E(T+T)*E(F+T)*E(I+T)*E(I+F)*E(I+I)*E(I+I)*T(I+I)*F(I+I)*I最右推导：ETT*ET*TT*FT*IF*I(E)*I(E+T)*I(E+F)*I(E+I)*I(T+I)*I(F+I)*I(I+I)*I推导树如下：b)所有短语：F(2个)、T*F、F + T * F简单短语：F(2个)句 柄：F10. 条件语句可形式定义为： IF THEN 1 ELSE 2其中带有属性1.type 值为“boolean” 表示是布尔类型2.true 和.false 值为中真和假的尚待回填的出口的链首指针条件语句的语义可描述为：t:=e;if not t then goto L1; 1;goto L2;L1: 2;L2:其中 e 为的值。试用句法制导翻译的方法写出符合上述要求的条件语句的翻译方案。答：条件语句的属性翻译文法为：ifCheckBool(.type);TLT:=NewTL;GEN(LABEL,TLT);Backpatch(.true,TLT);.false:=.false; then 1 .TL:=NewTL;GEN(BR, .TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(.false,TLF); else 2GEN(LABEL,.TL);11. 适合采用静态存储分配的程序设计语言应有哪些限制？答：数据实体所需空间在编译时能确定运行时每个数据对象只能有一个实例数组的上下界是常量过程调用不允许递归不能动态建立数据实体12. 一个基本块内通常可实现哪些优化？答：合并已知量 删除公共子表达式 删除无用代码 复写传播1、编译原理是对（C）。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行2、词法分析器的输出结果是（D）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值3、文法：G：SxSx | y所识别的语言是（D）。A、xyxB、（xyx）*C、x*yx*D、xnyxn（n0）4、采用自上而下分析，必须（A）。A、消除回溯B、消除左递归C、消除右递归D、提取公共左因子5、有一语法制