《编译原理样题5(有答案.docx》由会员分享，可在线阅读，更多相关《编译原理样题5(有答案.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理试题计算机学院 级 班学号 姓名题号 一 三eg五七八九十总分满分得分-选择题1.词法分析器的输入是。A.符号串 B.源程序 C.语法单位D.目标程序【2.两个有穷自动机等价是指它们的 oA.状态数相等B.有向弧数相等C.所识别的语言相等D.状态数和有向弧数相等【3.文法G： S xSx|y所识别的语言是 oA. xy*xB. (xyx)* C. xx*yxx* D. x*yx*14.设a, b,c为文法的终结符，且有优先关系a三b和b三c,则。A. 必有a=cB. 必有c=aC.必有b三aD.选项A、B和C都不一定成立【15.若状态k含有项目“A-Q. ”，且仅当输入符号aWFOLL
2、OW(A)时，才用规则“A- a ”归约的语法分析方法是 oA. LALR分析法B. LR (0)分析法C. LR分析法D. SLR分析法二判断题1、一个LL(1)文法一定是无二义的。2、逆波兰法表示的表达式亦称前缀式。3、算符优先关系表不一定存在对应的优先函数。4、同心集的合并有可能产生“移进/归约”冲突。5、若主程序为。层，过程p层次为k,则p的DISPLAY表中就有k+1个元素。三填空题1、词法分析的任务是从 中识别出一个个 o2、在LR(0)分析法中，若a,代V*且则称“S fa.A”为 项目，称“Sa.ap 为 项 目o3、规范规约每次规约的是句型的 o算符优先分析法每次规约的是当前
3、句型的 O四写一个文法，使其语言是奇数集，且每个奇数不以0开头。五已知文法G (S)：S-a|(T)T一T, 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)：SS + aF|aF| + aFF 一*aF|*a(1)消除左递归和左因子；(2)构造相应的FIRST和Follow集合；(3)构造预测分析表。八设有以下程序段program main;var a,b:integer
4、;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)文法？若是，请构造相应的分析表。若不是，请说明理由。 SSablbR R-S|a十文法Sf (L)|aL 3 L, S | S(a)给出句子(a, (a, a), (a, a)的一个最右推导；(b)按照(a)的最右推导，给出移进一归约分析器的工作步骤。十一对PL/0语言扩充单词：+= + +请完成下列识别
5、单词 +=和 + + (设单词内码分别为PLUS, PLUSDECOME和PLUSPLUS)的词法分析算法：if ( CH=+ ) ；if ( ) SYM=PLUSBECOME;GetCh(); else if ( CH=1+1 ) else答案（2）短语：（2分）(T, S), a)最 4s导C S S )，S= q S )a ,( S 9 S )5,( a，$)1)语法树*(2-选择题b, C, D, D, C二判断题三填空题源程序 单词符号待约项目移进项目句柄最左素短语四解:文法G (S)：S-AB|B|AOAAD|CB 一 2|4|6|8C 一 1|3|5|7|9|BDO|C五I Q、
6、(T, S), a(T, S)T, Sa直接短语：（1分）T,a句柄：(1分)T, S 解：(j0, x, 0, 3) (2) (j, , , 8)(3) (j, y, 0, 5)(4) (j, 1, 1, 8)(5) ( + , x, y, Tl)(6) (： =, Tl, z)(7) (j, 1, 1, 12)(8) ( + , x, 2, T2)(9) (： =, T2, 一, x)(10) ( + , y, 3, T3)(11) (： =, T3, y)七.解：（1）（消除左递归，提公因左因子）S 一 aFS，| + aFSS一+ aFS|F 一*aFFF|e(2)FIRST (S)
7、= a,十FIRST (50) = + ,FIRST (F) = *FIRST (F) = *,sFOLLOW (S) = #FOLLOW (S) = #FOLLoW (F) = ( + , # FOLLOW ( + , # )八九.该文法的拓广文法G，为:(0)S3 S (l)s 9 Sab(2) S 1 bR (3) R 9 S(4) R f a其LR(0)项目集规范族如下：10 : S少 S 13 : S f Sa b14 : S 9 bR 15 : R S S 玲 S abS S ab17 : S Sab 12 : S 9 b R R 3 SR 3 a S 9 Sab S 9 bR文法
8、G，的识别活前缀的DFA如下所示:状态actiongotoab$SR0S211S3acc2S6S2543S74r2r25r3/S3r36r4r47rlrlFOLLOW(S) = FOLLOW = a, $构造的SLR分析表如下:观察左表，对状态5,可 归纳又可移进，即存在为重 定义的入口。所以，该文法不是 SLR文法。十.(a) S ”工L1 ”(US)今(L, O -(L, (L, S)-(L, (LJU)-(L, (L, (L, S)今(L, (L, (L, a) (L, (L,a) (L, (L, (a, a)今(L,(a, a)今(L, (O (a, a)今(L, (US), (a,
9、a)-(L, (L, a), (a, a)今(L,(a), (a, a) 今(L, (a, a), (a, a)今(a, a), (a, a) - (a, (a, a), (a, a)(注：下划线部分为句柄)步骤栈输入动作1$(a, (a, a), (a, a)$移进2$(a, (a, a), (a, a)$移进3$(a,(a, a), (a, a)$归约，S3a4$(S,(a, a), (a, a)$归约，L3S5$(L,(a, a), (a, a)$移进6$(L,(a, a), (a, a)$移进7$(L (a, a), (a, a)$移进8$(L (a, a), (a, a)$移进9$(
10、L, (a,a), (a, a)$归约，S玲a10$(L (S，a), (a, a)$归约，LfS11$(L, (L,a), (a, a)$移进12$(L, (L,a), (a, a)$移进13$(L, (L, a),(a, a)$归约，STa14$(L, (L, S),(a, a)$归约，LJL,S15$(L, (L),(a, a)$移进16$(L, (L),(a, a)$归约，S9(L)17$(L, (S,(a, a)$归约，LTS18$(L, (L，(a, a)$移进19$(L, (L,(a, a)$移进20$(L, (L,(a, a)$移进21$(L, (L, (a,a)$归约，Sa22$(L, (L, (S,a)$归约，L3S23$(L, (L, (L,a)$移进24$(L, (L, (L,a)$移进25$(L, (L, (L, a)$归约，Sa26$(L, (L, (L, S)$归约，LTL,S27$(L, (L, (L)$移进28$(L, (L, (L)$归约，Sf(L)29$(L, (L, S)$归约，LJL,S30$(L, (L)$移进31$(U (L)$归约，ST(L)32$(L,S)$归约，LfL,S33$(L)$移进34$(L)$归约,S3(L)35$S$接受