编译原理样题5(有答案）.docx
编泽原理试题计算机学院 级一班学号 姓名题号三四五六七八九十总分满分理分-选择题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 FOLLOW (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、规范规约每次规约的是句型的。算符优先分析法每次规约的是当前句型 的 o四写一个文法，使其语言是奇数集，且每个奇数不以0开头。五已知文法G (S)： Sia|(T)TT, S|S(1)给出句子(a, (a, a)的最左推导并画出语法树；(2)给出句型(T, S), a)的短语、直接短语、句柄。六把语句if x>0 and y>0 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:integer;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语言扩充单词：+= +请完成下列识别单词' +='和' + + '(设单词内码分别为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 > <S* S > > 一( a ,(S S >)-><。/ R，S )*><J)动法忸4 «二分)(T, S), a（T, S）T, Sa直接短语：（I分）T, Sa句柄：（1分）T, S/解：(1) (j>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'|+aFS'S'->+aFS'|8F*aF'F'->F|e(2)HRST (S) = a,十 FOLLOW (S) = # FIRST (50) = + ,& FOLLOW (S') = (# ) FIRST (F) = * FOLLOW (F) = ( + , # FIRST (F) = *, e FOLLOW ( + , # )(3)0#sS-»aPS*Sr + aFS's，S' V卜* a FyVfFz->c八九.该文法的拓广文法G，为:(O)S'TSSI 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 , 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) » (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$(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$接受
