模拟试题一
更新时间:2024-01-16 18:45:01 阅读量: 教育文库 文档下载
模拟试题一
一、选择题
1 .文法 G 产生的 ⑴ 的全体是该文法描述的语言。 A .句型 B. 终结符集 C. 非终结符集 D. 句子
2 .若文法 G 定义的语言是无限集,则文法必然是 ⑵ : A .递归的 B 前后文无关的 C 二义性的 D 无二义性的
3 . Chomsky 定义的四种形式语言文法中, 0 型文法又称为 ⑶ 文法; 1 型文法又称为 ⑷ 文法; 2 型语言可由 ⑸ 识别。
A .短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机
4 .一个文法所描述的语言是 ⑹ ;描述一个语言的文法是 ⑺ 。 A .唯一的 B 不唯一的 C 可能唯一,好可能不唯一 5 . 数组的内情向量中肯定不含有数组的 ⑻ 的信息 A.维数 B.类型 C.维上下界 D.各维的界差
6 .在下述的编译方法中,自底向上的方法有 ⑼ ,自顶向下的分析方法有⑽ 。 ①简单优先分析 ②算符优先分析 ③递归下降分析 ④预测分析技术 ⑤LR(K)分析 ⑥ SLR(k)分析 ⑦ LL(k)分析 ⑧LALR(K)分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧
二、简答题(每小题 5 分,共 20 分) 1 . LL ( 1 )分析法对文法有哪些要求?
2 .常见的存储分配策略有几种?它们都适合于什么性质的语言? 3 .常见循环优化都有哪些项目?
4 .什么是活动记录?它主要由哪些内容构成? 三、( 8 分)化简文法 G[S] : S → ASe | BCaD | aD | AC A → Cb | DBS C → bC | d B → Ac D → aD
四、( 12 分) 设 L í {a,b,c}* 是满足下述条件的符号串构成的语言: (1)若出现 a ,则其后至少紧跟两个 c ; (2)若出现 b ,其后至少紧跟一个 c 。
试构造识别 L 的最小化的 DFA ,并给出描述 L 的正规表达式。
五、( 12 分) 已给文法 G[S] : S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL ( 1 )文法,并给出 LL ( 1 )分析表。
六、( 12 分) 给定文法 G[S] : S → Aa|dAb|Bb|dBa A → c B → c 构造文法 G[S] 的 LR ( 1 )分析表。
七、( 8 分) 将下面的条件语句表示成逆波兰式和四元式序列: if a>b then x:=a+b*c else x:=b-a; 八、( 8 分) 给定基本块: A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F
假定出基本块后,只有 A 、 C 、 E 是活跃的,给出用 DAG 图完成优化后 的代码序列。 参考答案:
一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A
二、 1 .对于 G 中的每个产生式 A →γ 1 | γ 2 | … | γ m ,其各候选式均应满足:(1)不同的候选式不能推出以同一终结符号打头的符号串,即
FIRST( γ i ) ∩ FIRST( γ j )= φ( 1 ≤ i , j ≤ m ; i ≠ j )
(2)若有γ j ε,则其余候选式γ i 所能推出的符号串不能以 FOLLOW(A) 中的终结符号开始,即有 FIRST( γ i ) ∩ FOLLOW(A)= φ( i ≤ 1,2, … ,m ; i ≠ j ) 2 .有三种分配存储空间的方式:( 1 ) 静态分配 若在编译阶段就能确定源程序中各个数据实体的存储空间大小,则可以采用较简单的静态存储管理。 适合 静态管理 的语言应具备条件: 数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。 ( 2) 栈式分配 适用于允许递归调用的程序设计语言 ;( 3 ) 堆式分配 对于允许程序在运行时为变量 动态申请和释放存储空间 的语言 , 采用 堆式分配 是最有效的
解决方案 。
3 .不变运算外提;运算强度削弱;消除归纳变量;下标变量地址计算优化。 4 . 一个过程的一次执行所需信息的管理,是通过称为 活动记录 的连续存储块来实现的。活动记录的主要内容有:( 1) 临时变量域 存放目标程序临时变量的值;( 2 )局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等;( 3 )机器状态域 保存在调用过程前有关机器状态的信息,包括各寄存器的当前值及返回地址等;( 4 )存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址;( 5 )控制链 指向主调过程的活动记录;( 6 )实参 存放主调过程为被调用过程所提供的实
参信息;( 6 )返回值 为主调过程存放被调过程的返回值
三、化简后: S → ASe|AC A → Cb C → bC | d 四、 DFA 如图所示。相应的正规式为 (c|acc|bc)* 。
五、
改造后的文法:S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e 各候选式的 FIRST 集,各非终结符的 FOLLOW 集为
产生式 FIRST 集 FOLLOW 集 S → PS' {q} {#}
S' → aPS' {a} {#}
→ fS' {f} → e { e }
P → qP' {q} {a,f,#} P' → bP {b} {a,f,#}
→ e { e } LL(1) 分析表为
六、分析表如下图所示
七、( 1 )逆波兰式:
,其中, BLE 表示汪或等于
时的转向指令; [ … ] 表示标号。 ( 2 )四元式: (1) ( j>, a, b, (3))
(2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9)) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( … … )
八、化简后的的四元式序列为 A :=D+12 E :=E+F C:=28
模拟试题二
一、是非题(下列各题,你认为正确的,请在题干的括号内打“√”,错的打“×”。每题1分,共5分) 1、算符优先关系表不一定存在对应的优先函数。 2、数组元素的地址计算与数组的存储方式有关。
3、仅考虑一个基本块,不能确定一个赋值是否真是无用的。 4、每个文法都能改写为LL(1)文法。
5、对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。
二、填空题(每题2分,共20分) 1、从功能上说,程序语言的语句大体可分为_______语句和______语句两大类。 2、扫描器的任务是从________中识别出一个个_______。 3、所谓最右推导是指:_______。 4、语法分析最常用的两类方法是________和_________分析法。 5一个上下文无关文法所含四个组成部分是_______________。
6、所谓语法制导翻译方法是_____________________。 7、符号表中的信息栏中登记了每个名字的有关的性质,如_________等等。 8、一个过程相应的DISPLAY表的内容为________。 9、常用的两种动态存贮分配办法是_____动态分配和_____动态分配。 10、产生式是用于定义_____的一种书写规则。
三、名词解释(每题2分,共10分) 1、遍 2、无环路有向图(DAG) 3、语法分析 4、短语 5、后缀式
四、简述题(每题4分,共24分) 1、考虑下面程序 ………… Var a:integer; Procedure S(X); Var X:integer;
Begin a:=a+1; X:=a+X End; Begin a:=5; S(a); Print(a) End. 试问:若参数传递方式分别采取传名和传值时,程序执行后输出a的值是什么? 2、画出Pascal中实数(不带正负号,可带指数部分)的状态转换图。 3、写出表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。
4、已知文法G(S) S→a|∧|(T) T→T,S|S 写出句子((a,a),a)的规范归约过程及每一步的句柄。 5、何谓优化?按所涉及的程序范围可分为哪几级优化? 6、目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题?
五、计算题(共41分) 1、写一个文法,使其语言是奇数集,且每个奇数不以0开头。(5分) 2、设文法G(S): S→(L)|a S|a L→L,S|S (1)消除左递归和回溯; (2)计算每个非终结符的FIRST和FOLLOW;
(3)构造预测分析表。
3、While a>0 ∨b<0 do Begin X:=X+1; if a>0 then a:=a-1 else b:=b+1 End; 翻译成四元式序列。(
4、已知文法G(E) E→T|E+T T→F|T *F F→(E)|i (1)给出句型(T *F+i)的最右推导及画出语法树; (2)给出句型(T *F+i)的短语、素短语。
5、设布尔表达式的文法为 E →E(1)∨E(2) E →E(1)∧E(2) E →i 假定它们将用于条件控制语句中,请 (1)改写文法,使之适合进行语法制导翻译和实现回填; (2)写出改写后的短个产生式的语义动作。 6、设有基本块 T1:=2
T2:=10/T T3:=S-R T4:=S+R A:=T2 *T4 B:A T5:=S+R T6:=T3 *T5 B:=T6 (1)画出DAG图; (2)假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。 参考答案: 一、√ √ √ × ×
二、 1 执行性、 说明性 2、 源程序、 单词符号 3、 任何一步αβ都是对α中最右非终结符进行替换的 4 自上而下、 自下而上 5、 一组终结符号,一组非终结符号、一个开始符号、一组产生式 6、 为每个产生式配上一个翻译子程序,并在语法分析的同时执行这些子程序 7、 类型、种属、所占单元大小、地址 8、 现行活动记录地址和所有外层最新活动记录的地址 9、 栈式、 堆式 10、 语法范畴 三、名词解释
1.遍--指编译程序对源程序或中间代码程序从头到尾扫描一次。
2.无环路有向图(DAG)--如果有向图中任一通路都不是环路,则称庐有向图为 无环路有向图,简称DAG。
3.语法分析--按文法的产生式识别输入的符号串是否为一个句子的分析 过程。
4.短语--令G是一个文法。S划文法的开始符号,假定αβδ是文法G的一个句 型,如果有SαAδ且AB,则称β是句型αβ相对非终结符A的短语。
5.后缀式--一种把运算量写在前面,把算符写在后面的表示表达式的方法。 四、简述题 1、答:传名:a=12 传值:a=6
3、答:逆波兰表示: abc*+ab+/d- (2分) 三元式序列: ① (*,b,c) ② (+,a,①) ③ (+,a,b) ④ (/,②,③) ⑤ (-,④,d)
4、答: 句型 归约规则 句柄
((a,a),a) S→a a ((S,a),a) T→S S ((T,a),a) S→a a ((T,S),a) T→T,S T,S ((S),a) T→S S ((T),a) S→S(T) (T) (S,a) T→S S (T,a) S→a a (T,S) T→T,S T,S (T) S→(T) (T) S
5、 答:优化:对程序进行各种等价变换,使得从变换后的程序出发,能产生更有效的目标代码。 (2分) 三种级别:局部优化、循环优化、全局优化。
6、 答:目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。(2分) 应着重考虑的问题: (1)如何使生成的目标代码较短; (2)如何充分利用寄存器,以减少访问内存次数;(3)如何充分利用指仅系统的的特点。 五、计算题
1、解:文法G(N): N→AB|B
A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D
2、解:(1) S→(L)|aS' S'→S|ε L→SL' L'→SL'|ε 评分细则:消除左递归2分,提公共因子2分。
(2) FIRST)S)={(,a} FOLLOW(S)={#,,,)} FIRST(S')={,a,ε} FOLLOW(S')={#,,,)} FIRST(L)={(,a} FOLLOW(L)={ )} FIRST(L')={,,ε} FOLLOW(L'〕={ )} 3、解: (1) (j>,a,0,5)
(2) (j,-,-,3) (5) (+,×,1,T1) (6) (:=,T1,-,×)
(7) (j≥,a,0,9) (8) (j,-,-,12) (9) (-,a,1,T2) (10) (:=,T2,-,a) (11) (j,-,-,1) (12) (+,b,1, T3) (13) (:=,T3,-,b) (14) (j,-,-,1) (15)
4、解:(1) 最右推导: ETF(E)(E+T)(E+F)(E+i) (T+i)(T*F+i)
(2) 短语:(T*F+i),T*F+i,T*F,i
素短语:T*F,i
5、解:(1) E0→E(1)
E→E0E(2) EA→E(1) E→EAE(2) E→i
6、解:(1)DAG: (2) 优化后的四元式 T3:=S-R
T4:=S+R A:=5*T4 B:=T3+T4
2005年《编译原理》试卷
1、编译原理是对( )。
A、机器语言的执行 B、汇编语言的翻译
C、高级语言的翻译 D、高级语言程序的解释执行 2、词法分析器的输出结果是( )。
A、单词自身值 B、单词在符号表中的位置
C、单词的种别编码 D、单词的种别编码和自身值 3、文法:G:S→xSx | y所识别的语言是( )。 A、xyx B、(xyx)* C、x*yx* D、xyx(n≥0) 4、采用自上而下分析,必须( )。
A、消除回溯 B、消除左递归
C、消除右递归 D、提取公共左因子
n
n
5、有一语法制导翻译如下所示: T→aDa {print “1”} D→(A {print “2”} D→d {print “3”} A→Dd {print “4”}
若输入字符序列为a(((dd)d)d)a,且采用自上而下的分析方法,则输出序列为( )。
A、32224441 B、34242421 C、12424243 D、34442212 二、(15分)对给定正则表达式b*(d | ad)(b | ab)构造其NFA M 三、(20分)文法G[E]的产生式为:
E→E + T | T T→T * E | F F→ I |(E)
① 给出(I+I)* I的最左推导、最右推导及相应的推导树; ② 列出句型F + T * F的所有短语、简单短语和句柄。
四、(20分)写出下列表达式的三地址形式的中间表示。 ①5+6 ×(a + b); ②?A∨(B ∧(C ∨ D)); ③for j:=1 to 10 do a[j + j]:=0;
③ if x > y then x:=10 else x:= x + y;
五、(20分)证明下面文法是SLR(1)文法,并构造其SLR分析表。 E→E + T | T T→T F | F
F→F* | a | b
答案 二
+
三、答: a)最左推导:
E?T?T*E?F*E?(E)*E?(E+T)*E?(T+T)*E
?(F+T)*E?(I+T)*E?(I+F)*E?(I+I)*E?(I+I)*T?(I+I)*F?(I+I)*I 最右推导:
E?T?T*E?T*T?T*F?T*I?F*I?(E)*I
?(E+T)*I?(E+F)*I?(E+I)*I?(T+I)*I?(F+I)*I?(I+I)*I 推导树如下:
b)所有短语:F(2个)、T*F、F + T * F 简单短语:F(2个)
句 柄:F
四、答: ⑴ 100: t1:=a+b
101: t2:=6*t1
102: t3:=5+t2
⑵ 200: if A goto 202 201: goto T
202: if B goto 204 203: goto F 204: if C goto T 205: goto 206 206: if D goto T 207: goto F
⑶ 300: j:=1
301: if j10 goto NEXT 302: i:=j+j 303: a[i]:=0
304: goto 301 ⑷ 400: if xy goto 402 401: goto 404 402: x:=10 403: goto 405 404: x:=x+y 405:
五、答:分析表如下所示:
正在阅读:
模拟试题一01-16
2017年大学生毕业顶岗实习周记20篇02-14
湖南大学《机械原理》测试题01-25
地理上册知识点总结初一03-19
川农《旅游经济学(专科)》18年9月作业考核标准答案03-10
企业安全生产应急管理九条规定及解读02-29
侵权责任法课本整理09-30
幼儿园大班的班务制定计划10-04
XXX学小学青岛版数学五年级上册期末试卷11-06
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 模拟试题
- 铁塔组立施工组织设计方案 - 图文
- IMAP命令
- 实用常规对联
- 刘建平调研文章 - 赣州市防汛减灾对策探讨
- VB期末参考代码 大题
- 关于开展清洁化生产小改小革和合理化建议专项活动的通知
- 苦荞茶的神奇功效
- 地质灾害隐患(危险)点单点应急预案表
- 浙江省物价局关于农村住房改造建设中有关价格收费政策的若干意见
- 某工程水土保持监测总结报告
- 招聘管理复习资料
- 军事理论较为完整型
- 基于MATLAB的语音处理 语音合成
- 10kV真空环网柜技术标准 - 图文
- 北京市卫生局关于成立北京市毕业后医学教育委员会
- 米开朗琪罗和贝尼尼的大卫像之比较 - 图文
- 金融垄断资本与金融垄断资本主义及其当代启示
- 植物之间的爱和恨教学设计
- vb模拟题01-60(女)
- 物化期末复习试题 - 图文