编译原理样题3(有答案）.docx
编译原理样题-选择题【11.型文法也称为正规文法。A 0B 1C 2D 3【2. 文法不是LL(1)的。A递归 B右递归 C 2型 D含有公共左因子的【)3.文法E-E+E |E*E|i的句子+的不同语法分析树的总数为。AlB3C5D7【1 4.四元式之间的联系是通过 实现。A临时变量 B指示器 C符号表D程序变量【1 5.同心集合并可能会产生的新冲突为。A二义 B移进/移进C移进/归约D归约/归约【】6.代码优化时所依据的是 oA语法规则B词法规则 C等价变换规则 D语义规则【1 7.表达式a-(-b)*c的逆波兰表示为 oA a-bc* B abc*- C ab- D abc-* (注：©为单目减运算符)8.过程的DISPLAY表记录了 oA过程的连接数据B过程的嵌套层次C过程的返回地址D过程的入口地址二填空题1 .编译过程的六个阶段为：词法分析、语义分析、代码优化和目标 代码生成。2 .词法分析阶段的任务式从左到右扫描,从而逐个识别 o.对于文法G1和G2,若有,则称文法G1和G2是等价的。3 .对于文法 GE ： E-TIE+T TtF|T*F F-P人F|P P-(E)|i,句型 T+T*F+i 的句柄 是，最左素短语是 o所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短 语。所谓最左素短语是指处于句型最左边的那个素短语。如，P*P和i是句型P*P+i的素短语，而P*P 是它的最左素短语。4 .最右推导的逆过程称为,也称为 o.规范规约中的可规约串是,算符优先分析中的可规约串是 o5 . (AV B) A (CVDA E) 的逆波兰式是 o.在属性文法中文法符号的两种属性分别称为 和 o6 .符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表 是 的依据。7 . 一个过程的D工SPLAY表的内容是它的 的D工SPLAY表的内容加上。三 有穷自动机M接受字母表£=0,1上所有满足下述条件的串：每个1都有0直接跟在右 边。构造一个最小的DFA M及和M等价的正规式。四 证明正规式(ab)*a与正规式a (ba)*等价(用构造他们的最小的DFA方法)。五写一个文法，使其语言是：L = ln0mlm0n | m,nN0 六对文法GSS f aSb | P P f bPc | bQc Q f Qa I a (1)它是否是算符优先文法？请构造算符优先关系表 (2)文法GS消除左递归、提取左公因子后是否是LL (1)文法？请证实。七已知文法G为：(0) s' f S(1) S f aAd (2) S - bAc (3) S f aec (4 ) S f bed (5) A f 试构造它的LR (1)项目集、可归前缀图和LR (1)分析表。 八已知源程序如下： prod:=0;: =1;while iW20 do beginprod:=prod+ai*bi; i:=i+l end;试按语法制导翻译法将源程序翻译成四元式序列(设A是数组a的起始地址，B是数组b的起 始地址；机器按字节编址，每个数组元素占四个字节)。九设有以下程序段 procedure P(x,y,z) beginY:=y*3;Z : =X+z;end; begina:=5; b:=2;p(a*b,a,a);print(a); end若参数传递的方法分别为(1)传值、(2)传地址、(3)传名，试问结果分别什么？十对以下文法，请写出关于括号嵌套层数的属性文法。(为S,L引入属性h,用来记录输出配 对的括号个数)文法规则语义规则Sf (T)STTf T, STf S对PL/0语言的whil语句while 条件B DO 语句S的编译程序, 请在空缺处填空，完成该语句的编译算法：switch (SYM) case WHILESYM:GetSym();CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);GEN(JPC,0,0);if (SYM=DOSYM) else Error (18);STATEMENT(FSYS,LEV,TX);GEN(JMP,O,CX1);break;编译原理样题参考答案-选择题(12分)1.D2. D 3. B 4. A 5. D 6. C 7. B8. B二填空题(8分)1 .语法分析2 .源程序3.L(G1)=L(G2)4 .T5 .规范归约综合属性(次序可换)地址分配本过程的SP的地址中间代码生成单词(或G1和G2的语言相同)最左归约.最左素短语6 . A B VC DE 八".继承属性7 .信息栏.直接外层三最小的DFAM如下图所示:与M等价的正规式为：(O, |(10) ).四正规式(ab) * a对应的NFA如图:正规式a (ba) *对应的NFA如图:这两个正规式最终都可得到最简的DFA如图所示:a所以这两个正规式等价。五文法 G: S -> ISO | AA - 0A1 | s六 1 .求出GS的FIRSTVT集和LASTVT集:FIERSTVT (S) =a,bFIERSTVT(P)=bLASTBVT (S) =b,cLASTBVT (P) =cLASTBVT (Q) =aabca< ><>b< >c>>FIERSTVT(Q)=a 构造优先关系表为：由于在优先关系中同时出现了和aa以及b<b和bb,所以该文法不是算符优先文法。2.消除左递归和提取左公因子后的文法为：S 一 aSb | PP - bP'PJ Pc I QcQ - aQ'Q aQf | e求具有相同左部的两个产生式的select集的交集：Select (S->aSb) ASelect (S->P) = aJAFirst (P) = aAb=Select (PPc) ASelect (P-Qc) = First (P) DFirst (Q) = bAa=Select(QzaQz)ASelect(Qze) = aAFollow(Q) = aAc= 所以修改后的文法是LL (1)文法。七 LR(1)项目集和可归前缀图如下:构造LR(1)分析表如下:状态abcde#sA0S2S311acc2S53S74S85S9r56S107r5Sil8rl9r310r211r4八四元式序列100 prode:=0101 i:=l102 If i<20 goto 104103 goto 114104 T1:=4*I105 T2:=A-4106 T3:=T2 Tl107 T4:=4*I108 T5:=B-4109 T6:=T5T4110 T7:=T3*T6111 prod:=prod+T7112 i:=i+l113 goto 102114十(1)传值5；(2)传地址25；(3)传名45文法规则语义规则Sf (T)S.h:=T.h+l; STs.h:=0T T, ST.h:=T.h+S.h;Tf ST.h:= S.h;CX1=CXCX2=CXGtSym()CODECX2.A=CX
