编译原理样题5(有答案）.docx

《编译原理样题5(有答案）.docx》由会员分享，可在线阅读，更多相关《编译原理样题5(有答案）.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编泽原理试题计算机学院 级一班学号 姓名题号三四五六七八九十总分满分理分-选择题1 1.词法分析器的输入是 OA.符号串 B.源程序 C.语法单位D.目标程序【2.两个有穷自动机等价是指它们的 oA.状态数相等B.有向弧数相等C.所识别的语言相等D.状态数和有向弧数相等3.文法G： S - xSx | y所识别的语言是。A. xy*xB. (xyx)* C. xx*yxx* D. x*yx*4.设a, b,c为文法的终结符，且有优先关系a三b和b三c,则。A.必有a三cB.必有c三aC.必有b三aD.选项A、B和C都不一定成立5.若状态k含有项目“At a.”,且仅当输入符号a W FOLLO

2、W (A)时,才用规则“A- Q ”归约的语法分析方法是 oA. LALR分析法B. LR(O)分析法C. LR(1)分析法D. SLR(l)分析法二判断题1、一个LL( 1)文法一定是无二义的。2、逆波兰法表示的表达式亦称前缀式。3、算符优先关系表不一定存在对应的优先函数。4、同心集的合并有可能产生“移进/归约”冲突。5、若主程序为。层，过程p层次为k,则p的DISPLAY表中就有k+1个元素。三填空题1、词法分析的任务是从 中识别出一个个。2、在LR(0)分析法中，若a/wV*且aw匕则称“S ra.A”为 项目，称“Sfaap”为 项目。3、规范规约每次规约的是句型的。算符优先分析法每次

3、规约的是当前句型 的 o四写一个文法，使其语言是奇数集，且每个奇数不以0开头。五已知文法G (S)： Sia|(T)TT, S|S(1)给出句子(a, (a, a)的最左推导并画出语法树；(2)给出句型(T, S), a)的短语、直接短语、句柄。六把语句if x0 and y0 then z： =x+yelse beginx： =x+2y： =y+3end； 翻译成四元式序列。七设文法G (S)：S S+aFlaF| + aFF*aF|*a(1)消除左递归和左因子：(2)构造相应的FIRST和Follow集合;(3)构造预测分析表。八设有以下程序段program main;var a,b:in

4、teger;procedure p (x,y,z:integer);beginy:=y+l;z:=z+xend;begina:=2; b:=3; p(a+b,a,a); write(a) end.对于下列参数传递方式，分别写出执行程序后a的输出值。(1)传名；(2)传地址。九下列文法是否为SLR(l)文法？若是，请构造相应的分析表。若不是，请说明理由。 S-Sab|bR R-S|a十文法S1(L)|aL - L, S | S(a)给出句子(a, (a, a), (a, a)的一个最右推导；(b)按照的最右推导，给出移进一归约分析器的工作步骤。十一.对PL/0语言扩充单词：+= +请完成下列识别

5、单词 +=和 + + (设单词内码分别为PLUS, PLUSDECOME和PLUSPLUS)的词法分析算法：if ( CH=+ ) _；if ( ) SYM=PLUSBECOME; GetCh(); else if ( CH=1+1 ) else答案答案一选择题b, C, D, D, C二判断题三填空题源程序 单词符号待约项目移进项目句柄最左素短语四.解：文法G (S)： S-AB|B|AO A-AD|C B 一 2|4|6|8 C-1|3|5|7|9|B D-O|C五（2）短语：（2分）(T, S), a)踪左推寻2分S2S ACS, S)-i a , S?“ h 予 a 一( a ,(S

6、S )-0, x, 0, 3) (2) (j, , , 8)(3) (j, y, 0, 5)(4) (j, 一, 一, 8)(5) ( + , x, y, Tl)(6) (： =, Tl, z)(7) (j, , 一, 12)(8) ( + , x, 2, T2)(9) (： =, T2, x)(10) ( + , y, 3, T3)(11) (： =, T3, y)(12) 七解：(1)(消除左递归，提公因左因子)SaFS|+aFSS-+aFS|8F*aFF-F|e(2)HRST (S) = a,十 FOLLOW (S) = # FIRST (50) = + ,& FOLLOW (S) =

7、(# ) FIRST (F) = * FOLLOW (F) = ( + , # FIRST (F) = *, e FOLLOW ( + , # )(3)0#sS-aPS*Sr + aFSs，S V卜* a FyVfFz-c八九.该文法的拓广文法G，为:(O)STSSI SabS f bR(3) R S(4) R 今 a其LR(0)项目集规范族如下：10 : S今 S 13 : S 玲 Sa bS f Sab14 : S bR ST bRIl ：s - s I5:R-S-S - S , ab16 : R - a S 9 S ab12 : S b R17 : S Sab RI SR9 aSI ,

8、SabS bR文法G哨勺识别活前缀的DFA如下所示：状态actiongotoab$SR0S211S3acc2S6S2543S74r2r25r3/S3r36r4r47rlrlFOLLOW(S) = FOLLOW = a,$ 构造的SLR分析表如下：观察左表，对状态5,可 归纳又可移进，即存在为重 定义的入口。所以，该文法不是 SLR文法。+. (a) S(L,S) - (L,包)9(L, (L, S) 9 (L, (L,_(L)(L, (L, (L, S) (L, (L, (L, a) - (L, (L, (S, a) (L,(L,(a, a) - (L,(a, a)今(L, L), (a, a

9、) (L,(LS), (a, a) * (L, (L, a), (a, a) - (L,( a), (a, a) (L, (a, a), (a, a) (S, (a, a), (a, a) - (a, (a, a), (a, a)(注：下划线部分为句柄)(b)步骤栈输入动作1$(a, (a, a), (a, a)$移进2$(a, (a, a), (a, a)$移进3$(a(a, a), (a, a)$归约，Sa4$(S,(a, a), (a, a)$归约，L9S5$(L，(a, a), (a, a)S移进6$(L,(a, a), (a, a)$移进7$(L,(a, a), (a, a)$移进8

10、$(L,(a, a), (a, a)$移进9$(L, (a,a), (a, a)$归约,S玲a10$(L, (S,a), (a, a)$归约，LTS11$(L, (L,a), (a, a)$移进12$(L, (L,a), (a, a)$移进13$(L, (L, a),(a, a)$归约，Sa14$(L, (L, S),(a, a)$归约，L-L,S15$(L, (L),(a, a)$移进16$(L, (L),(a, a)$归约，ST(L)7$(L, (S,(a, a)$归约，L9S18$(L, (L,(a, a)$移进19$(L, (L,(a, a)$移进20$(L, (L,(a, a)$移进21$(L, (L, (a,a)$归约，STa22$(L, (L, (S,a)$归约，L9S23$(L, (L. (L,a)$移进24$(L, (L, (L,a)$移进25$(L, (L, (L, a)$归约，S-a26$(L, (L, (L, S)$归约，L-L,S27$(L, (L, (L)$移进28$(L, (L, (L)$归约，ST(L)29$(L, (L, S)$归约，LTL,S30$(L, (L)$移进31$(L, (L)$归约,Sf(L)32$(L,S)$归约，L-L,S33$(L)$移进34$(L)$归约，S(L)35$S$接受