广工编译原理复习例题有客观题的答案.pdf_第1页
广工编译原理复习例题有客观题的答案.pdf_第2页
广工编译原理复习例题有客观题的答案.pdf_第3页
广工编译原理复习例题有客观题的答案.pdf_第4页
广工编译原理复习例题有客观题的答案.pdf_第5页
已阅读5页,还剩11页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

编译原理复习例题 一 选择题 1编译的各阶段工作都涉及 B 。 A词法分析 B表格管理 C语法分析 D 语义分析 2 D 型文法也称为正规文法。 A 0 B 1 C 2 D 3 3 D 文法不是LL(1)的。 A递归 B右递归 C2型 D含有公 共左因子的 4文法EE+E|E*E|i的句子i*i+i*i有 C 棵不同的语法 树。 A 1 B 3 C 5 D 7 5文法 SaaS|abc 定义的语言是 C 。 Aa2kbc|k0 Bakbc|k0 Ca2k-1bc|k0 Dakakbc|k0 6若B为非终结符,则 A.B 为 D 。 A移进项目 B归约项目 C接受项目 D待约项目 7同心集合并可能会产生新的 D 冲突。 A二义 B移进/移进 C移进/归约 D归约/归 约 8代码优化时所依据的是 C 。 A语法规则 B词法规则 C等价变换规则 D语义规则 9表达式a-(-b)*c的逆波兰表示(为单目减)为 B 。 Aa-bc* Babc*- Cab- Dabc-* 10过程的DISPLAY表是用于存取过程的 B 。 A非局部变量 B嵌套层次 C返回地址 D入口地址 b 0 1 - a a 2 + + b a b 11. 已知右图所示自动机M,请问下列哪个字符串不是M所能识别的。D A bbaa B abba C abab D aabb 12. 若状态k含有项目“A.”,且仅当输入符号aFOLLOW(A)时, 才用规则“A”归约的语法分析方法是 D 。 A LALR分析法 B LR(0)分析法 C LR(1)分析法 D SLR(1)分析法 13. 有一语法制导翻译如下所示:(第8章) S-bAb print “1” A-(B print “2” A-a print “3” B-Aa) print “4” 若输入序列为b(aa)a)a)b,则采用自下而上的分析方法,则输出是 B 。 A 32224441 B 34242421 C 12424243 D 34442212 14. 局部优化是对 D 进行的优化。 A 表达式 B 部分代码 C 循环体 D 基本块 15. 削减运算强度是对 D 的一种优化。 A 表达式 B 过程 C 基本 块 D 循环 二 填空题 1词法分析阶段的任务式从左到右扫描 源程序 ,从而逐个 识别 单词 。 2对于文法GE:ET|E+T TF|T*F FPF|P P(E)|i,句 型T+T*F+i的句柄是 T 。 3最右推导的逆过程称为 最左规约 ,也称为 规范规约 。 4符号表的信息栏中登记了每个名字的有关属性,如 符号名 、符号的类型、符号的存储类别和符号的作用域及可视性等。 5. 一个确定有穷自动机由五部分组成: 有穷状态集 、 有穷字母 表 、 转换函数 、初态和 终态集 。 6. 最常用的两类语法分析方法是 自顶向下 和 自底向 上 分析法。 7. 单词的三种描述工具: 正规文法 、 正规式 和 有穷自动机 互相之间具有等价性。 8. 在PL/0的目标代码解释执行时,寄存器B总是指向当前执行 过程活动记录的 起始地址 ,而寄存器T总是指向 栈顶 。 9LR(0)分析法的名字中”L”表示 自左向右扫描输入符号串 ,”R”表示 最右推导的逆过程 ,“0”表示 向前看的输入符号的个数 。 10. 两种常用的动态存储分配办法是 栈式动态分配和堆式 动态分配。 三 判断题(认为正确的填“T”,错的填“F”) 【 T 】1同心集的合并有可能产生“归约/归 约”冲突。 【 T 】2一个文法所有句子的集合构成该文法定 义的语言。 【 F 】3非终结符可以有综合属性,但不能有继 承属性。 【 T 】4逆波兰表示法表示表达式时无需使用括 号。 【 F 】5一个确定有穷自动机有且只有一个终 态。 【 F 】6若过程p第k次被调用,则p的DISPLAY表中就有k+1个元 素。 四 解答题 1给定文法G和句型(T+F)*i+T, G: EE+T | T TT*F | F F(E) | i (1)画出句型的语法树; (2)写出句型的全部短语、简单短语和句柄。 解:(略) 2设有文法G:SS+S|S*S|i|(S)。 (1)对于输入串i+i*i 给出一个最左推导; (2)该文法是否是二义性文法?请证明你的结论。 解:(1)i+i*i的最左推导: S = S+S = i+S = i+S*S = i+i*S = i+i*i (2)该文法是二义性的。因为对于句子i+i*i 可以画出两棵语法树(语法树略)。 3给出语言ambmcn|m1,n0的上下文无关文法(2型)。 解: G: SAB|A AaAb|ab BcB|c 4给出语言akbmcn|k,m,n1的正规文法(3型)。 解: G: AaA|aB BbB|bC CcC|c 5将文法G改写成等价的正规文法(3型)。 G: SdAB AaA|a BbB|b 解: G: SdA AaA|aB BbB|b 6设有字母表a,b上的正规式R=(ab|a)*。 (1)构造R的相应有限自动机; 解: 0 1 2 3 b a a - + (2)构造R的相应确定有限自动机; 解:将(1)所得的非确定有限自动机确定化 IaIb - +013 123 +12312313 +13123 0 1 2 a a b a -+ + + (3)构造R的相应最小确定有限自动机; 解:对(2)得到的DFA化简,合并状态0和2 为状态2: 1 2 a a b -+ + (4)构造与R等价的正规文法 解:令状态1和2分别对应非终结符B和A G: AaB|a| BaB|bA|a|b| 可化简为: G: AaB| BaB|bA| 7已知正规文法GS: S aS | bA | a A aS (1)构造与之等价的自动机NFA M (2)将NFA M确定化为DFA M IIaIb -0SSZA +1SZSZA 2AS 8. 有穷自动机M接受字母表0,1上所有满足下述条件的串:串中 至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。 解:(0|1)*(00|11)(0|1)* 9对右图所示的有限自动机 (1)若是确定的,则写出其转换矩阵;若不是,则将其确定化; (2)最小化。 (注:确定化和最小化均应给出转换矩阵和图示)。 解: (1) 符号 状态 ab -123 214 +325 +416 555 666 (2)首先将状态按终态和非终态分成两个集合1,2,5,6和3,4 检查子集1,2,5,6,由于f(1,a)=2,f(2,a)=1, f(5,a)=4,f(6,a)=3,所以子集1,2,5,6可进一步划分为1,2 和5,6 检查子集3,4,由于f(3,a)=2,f(4,a)=1以及f(3,b)=5, f(4,b)=6,所以不用进一步划分了。 检查子集1,2,由于f(1,a)=2,f(2,a)=2以及f(1,b)=3, f(2,b)=4,所以不用进一步划分了。 检查子集5,6,由于f(5,a)=4,f(6,a)=3以及f(5,b)= , f(6,b)= ,所以不需要进一步划分了。 因此最终划分的结果是1,2、3,4和5,6,重新命名状态, 令1,2为1,3,4为3和5,6为5,则得到化简后的DFA为 符号 状态 ab -113 +315 555 10写出在a,b上,不以a开头,但以aa结尾的字符串集合的正规式 (并构造与之等价的最简DFA)。 解:依题意,“不以a开头”,则必以b开头,又要“以 aa结尾”,故正规式为:b(a|b)*aa (构造与之等价的最简DFA,此略) 11写一个LL(1)文法G,使其语言是 L(G)= ambnc2n | m=0,n0 并证明文法是LL(1)。 解:文法G(S):S aS | E E bE E Ecc | cc Select(S aS)Select (S E)= Select(E Ecc)Select (E cc) = 故文法为LL(1)的 12将文法G改写成等价的LL(1)文法,并构造预测分 析表。 G:SS*aT|aT|*aT T+aT|+a (编写递归下降子程序) 解:消除左递归后的文法G: SaTS|*aTS S*aTS| T+aT|+a 提取左公因子得文法G:SaTS|*aTS S*aTS| T+aT TT| Select(SaTS)=a Select(S*aTS)=* Select(SaTS)Select(S*aTS)= Select(S*aTS)=* Select(S)=Follow(s)=# Select(S*aTS)Select(S)= Select(T+aT)=+ Select(TT)=First(T) =+ Select(T )=Follow(T)=*,# Select(TT)Select(T)= 所以该文法是LL(1)文法。 预测分析表: *+a# SSTa, N TST, N SSTa, N , P T Ta, N T, PT, P , P a , N # OK (递归下降子程序,略) 13对文法GS: S aSb | P P bPc | bQc Q Qa | a 构造简单优先关系表。该文法是否是简单优先文法? 解:简单优先关系矩阵如下: SabPQc S = a= b 由于矩阵中有元素存在多种优先关系,故不是简单优先文法。 14考虑文法 G: S AS | b A SA | a (1)构造文法的可归前缀图(活前缀的DFA); (2)判断文法是否是LR(0)文法,并说明理由。 解:(1)可归前缀图 (2)因为存在冲突,所以不是LR(0)文法。 15已知文法GS:S Uta | Tb T S | Sc | d U US | e (1) 试判断G是LR(0),SLR(1),LALR(1)还是LR(1),说明理 由。 (2) 构造相应的分析表。 解: (1) 首先拓广文法为G,增加产生式SS (0) SS (1) SUTa (2) STb (3) TS (4) TSc (5) Td (6) UUS (7) U e G的LR(0)项目集族及识别活前缀的DFA如下图所示: (2)在I1中: S S.为接受项目,T S. 为归约项目,T S.c为移进项目,存 在接受-归约和移进-归约冲突,因此所给文法不是LR(0)文法。 在I1中: Follow(S) Follow(T)= # a ,b= Follow(T) c= a ,b c= 在I8中: Follow(U) Follow(T) c=d,e a ,b c= 所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归 约-归约冲突可以由Follow集解决,所以G是SLR(1)文法。 构造的SLR(1)分析表如下: 状态 (State) ActionGoto a b c d e #S U T 0 1 2 3 4 5 S5 S4 r3 r3 S6 Acc S5 S4 S9 r7 r7 r5 r5 r4 r4. 1 2 3 . 8 2 7 6 7 8 9 10 S10 S9. r3 r3. S6 r6 r6 r2 r2. r2 r2 r2 r2 r1 r1. r1 r1 r1 r1 16文法G及其LR分析表如下,请给出对串dada#的分析过程。 G: S VdB V e V B a B Bda B 状态 ACTIONGOTO dea#SBV 0r3S3 1 2 1 acc 2S4 3r2 4r6 S5r6 6 5r4 r4 6S7 r1 7 S8 8r5 r5 解:对输入串dada#的分析过程 步骤 状态栈符号栈 剩余输入符 号 动作 1 2 3 4 5 6 7 8 9 0 02 024 0245 0246 02467 024678 0246 01 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# dada# ada# da# da# a# # # # 用V 归约 移进 移进 用B a归约 移进 移进 用B Bda 归约 用S VdB 归约 接受 17对以下文法,请写出关于配对括号数目ps的属性文法。 文法规则语 义 规 则 S(T) Si TT,S TS 解:h表示配对括号数目 (1)S.h = T.h + 1 (2)S.h = 0 (3)T.h = T.h+S.h (4)T.h = S.h 18把下列语句 if x0 and y0 then z:xy else x:x2 翻译成四元式序列。 解:略 19对传值、传地址和传名3种参数传递方法分别写出下列程 序的输出: void p(int x, int y, int z) y *= 3; z += x; void main() int a=5, b=2; p(a*b,a,a); printf(“%dn”, a); 这些参数传递机制如何实现? 解:(1)传值 5; (2)传地址 25; (3)传名 45 (参数传递机制,略) 20将下面程序划分为基本块,并画出其程序流图。 b := 1 b := 2 if w = x goto L2 e := b goto L2 L1:goto L3 L2:c := 3 b := 4 c := 6 L3:if y = z goto L4 halt L4:g := g + 1 h := 8 goto L1 解:(1)基

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论