复习题软件.docx
- 文档编号:11488396
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:17
- 大小:102.32KB
复习题软件.docx
《复习题软件.docx》由会员分享,可在线阅读,更多相关《复习题软件.docx(17页珍藏版)》请在冰点文库上搜索。
复习题软件
一.令文法为
(1)给出i+i*i、i*(i+i)的最左推导和最右推导;
(2)给出i+i+i、i+i*i、i-i-i的语法树。
最左推导:
最右推导:
语法树:
i+i+ii+i*ii-i-i
考虑文法G(E):
E→E+T|T
T→T*F|F
F→(E)|i
(1)给出句型E+F*F的语法树;
(2)给出以上句型的的短语、直接短语、句柄。
E=>E+T=>E+T*F=>E+F*F
由上图知:
短语:
F,F*F,E+F*F
直接短语:
F
句柄:
F
二.构造下列正规式相应的NFA。
1求1(0|1)*00的状态最少的DFA。
解:
1)得到NFA
2)NFA转换成DFA
状态转换矩阵为:
I
I0
I1
{X}
---
{1}
{1}
{1,2}
{1}
{1,2}
{1,2,Y}
{1}
{1,2,Y}
{1,2,Y}
{1}
重新命名后为:
表格1
S
0
1
0
--
1
1
2
1
2
3
1
3
3
1
3)DFA的化简
例如:
将下图最小化。
bba
ab
a
ab
ba
aa
最小化:
bba
ab
五.令文法G1为:
E->E+T|T
T->T*F|F
F->(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
解:
短语:
E+T*F,T*F,
直接短语:
T*F
句柄:
T*F
E->E+T|T
T->T*F|F
F->(E)|i
句型(E+T)*i+F指出这个句型的所有短语、直接短语和句柄、素短语、最左素短语
短语:
E+T(E+T)i(E+T)*i(E+T)*i+FF
直接短语:
E+TiF素短语:
iE+T最左素短语:
E+T
1、名词解释:
句柄:
一个句型的最左直接短语称为这个句型的句柄。
最左素短语:
包括至少一个终结符号,且除自身之外不包含其它素短语的短语称作素短语。
某句型最左边的那个素短语,称为最左素短语。
六.给出下面表达式的逆波兰表示(后缀式)
七.将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。
三元式序列:
(1)+,a,b
(2)@,
(1),-
(3)+,c,d
(4)*,
(2),(3)
(5)+,a,b
(6)+,(5),c
(7)-,(4),(6)
间接三元式序列:
三元式表:
(1)+,a,b
(2)@,
(1),-
(3)+,c,d
(4)*,
(2),(3)
(5)+,
(1),c
(6)-,(4),(5)
间接码表:
(1)
(2)
(3)
(4)
(1)
(5)
(6)
四元式序列:
(1)+,a,b,
(2)@,
-,
(3)+,c,d,
(4)*,
(5)+,a,b,
(6)+,
c,
(7)-,
八.按照表7.3产生三地址代码的属性文法,自下而上把赋值句A:
=B*(-C+D)翻译成四元式。
步骤输入串栈PLACE四元式
(1)A:
=B*(-C+D)
(2):
=B*(-C+D)iA
(3)B*(-C+D)i:
=A-
(4)*(-C+D)i:
=iA-B
(5)*(-C+D)i:
=EA-B
(6)*(-C+D)i:
=EA-B
(7)(-C+D)i:
=E*A-B-
(8)-C+D)i:
=E*(A-B--
(9)C+D)i:
=E*(-A-B---
(10)+D)i:
=E*(-iA-B---C
(11)+D)i:
=E*(-EA-B---C(@,C,-,
)
(12)+D)i:
=E*(EA-B--
(13)D)i:
=E*(E+A-B--
-
(14))i:
=E*(E+iA-B--
-D
(15))i:
=E*(E+EA-B--
-D(+,
D,
)
(16))i:
=E(EA-B--
(17)i:
=E*(E)A-B--
-
(18)i:
=E+EA-B-
(*,B,
)
(19)i:
=EA-
(:
=,
-,A)
(20)A
产生的四元式:
(@,C,-,
)
(+,
D,
)
(*,B,
)
(:
=,
-,A)
备注:
本类题目不需要写出详细过程,只要会用抽象语法树写出四元式即可。
九.试把以下程序划分为基本块并作出其程序流图。
1、划分基本块的算法:
(1)先求出四元式程序中各个基本块的入口:
程序的第一条语句;
能由条件转移语句或无条件转移语句转移到的语句;
紧跟在条件转移语句后面的语句。
(2)对以上求出的每一入口语句,构造其所属的基本块。
它是由该入口语句到另一入口语句,或到一转移语句,或到一停语句之间的语句序列组成的。
(3)凡未被纳入某一基本块中的语句,都是程序中控制流程无法到达的语句,从而也是不会被执行到的语句,可把它们从程序中删除。
ReadC
A:
=0
B:
=1
L1:
A:
=A+B
IfB≥CgotoL2
B:
=B+1
GotoL1
L2:
writeA
halt
十.调用R0和R1是两个可使用的寄存器,T4是基本块出口之后的活跃变量。
将下面基本块的中间代码序列生成目标代码。
T1:
=A+B
T2:
=C+D
T3:
=E-T2
T4:
=T1-T3
1.首先画出DAG图,对DAG图节点执行顺序进行排序,调整语句执行顺序
T2:
=C+D
T3:
=E-T2
T1:
=A+B
T4:
=T1-T3
2.然后进行翻译,目标代码序列为:
LDR0,C
ADDR0,D
LDR1,E
SUBR1,R0
LDR0,A
ADDR0,B
SUBR0,R1
STR0,T4
注意寄存器的选择要求利用变量的待用信息来决定。
选择题:
1.将编译程序分成若干个“遍”是为了。
a.提高程序的执行效率
b.使程序的结构更加清晰
c.利用有限的机器内存并提高机器的执行效率
d.利用有限的机器内存但降低了机器的执行效率
2.构造编译程序应掌握。
a.源程序b.目标语言
c.编译方法d.以上三项都是
3、变量应当。
a.持有左值b.持有右值
c.既持有左值又持有右值d.既不持有左值也不持有右值
4、编译程序绝大多数时间花在上。
a.出错处理b.词法分析
c.目标代码生成d.管理表格
5、不可能是目标代码。
a.汇编指令代码b.可重定位指令代码
c.绝对指令代码d.中间代码
6、使用可以定义一个程序的意义。
a.语义规则b.词法规则
c.产生规则d.词法规则
7、词法分析器的输入是。
a.单词符号串b.源程序
c.语法单位d.目标程序
8、中间代码生成时所遵循的是-。
a.语法规则b.词法规则
c.语义规则d.等价变换规则
9、编译程序是对。
a.汇编程序的翻译b.高级语言程序的解释执行
c.机器语言的执行d.高级语言的翻译
10、编译程序各阶段的工作都涉及到。
a.语法分析b.表格管理c.出错处理
d.语义分析e.词法分析
11、编译程序工作时,通常有阶段。
a.词法分析b.语法分析c.中间代码生成
d.语义检查e.目标代码生成
12、文法G:
S→xSx|y所识别的语言是。
a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*
13、文法G描述的语言L(G)是指。
a.L(G)={α|S+⇒α,α∈VT*}b.L(G)={α|S*⇒α,α∈VT*}
c.L(G)={α|S*⇒α,α∈(VT∪VN*)}d.L(G)={α|S+⇒α,α∈(VT∪VN*)}
14、有限状态自动机能识别。
a.上下文无关文法b.上下文有关文法
c.正规文法d.短语文法
15、设G为算符优先文法,G的任意终结符对a、b有以下关系成立。
a.若f(a)>g(b),则a>bb.若f(a) c.a~b都不一定成立d.a~b一定成立 16、如果文法G是无二义的,则它的任何句子α。 a.最左推导和最右推导对应的语法树必定相同 b.最左推导和最右推导对应的语法树可能不同 c.最左推导和最右推导必定相同 d.可能存在两个不同的最左推导,但它们对应的语法树相同 17、由文法的开始符经0步或多步推导产生的文法符号序列是。 a.短语b.句柄c.句型d.句子 18、文法G: E→E+T|T T→T*P|P P→(E)|i 则句型P+T+i的句柄和最左素短语为。 a.P+T和ib.P和P+Tc.i和P+T+id.P和T 19、文法G: S→b|∧(T) T→T,S|S 则FIRSTVT(T)。 a.{b,∧,(}b.{b,∧,)}c.{b,∧,(,,}d.{b,∧,),,} 20、产生正规语言的文法为。 a.0型b.1型c.2型d.3型 21、采用自上而下分析,必须。 a.消除左递归b.消除右递归c.消除回溯d.提取公共左因子 22、在规范归约中,用来刻画可归约串。 a.直接短语b.句柄c.最左素短语d.素短语 23、有文法G: E→E*T|T T→T+i|i E E*T TT+i T+ii6 i28 1 句子1+2*8+6按该文法G归约,其值为。 a.23B.42c.30d.17 24、规范归约指。 a.最左推导的逆过程b.最右推导的逆过程 c.规范推导d.最左归约的逆过程 25.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位是_______。 A字符B单词C句子D句型 26.编译程序前三个阶段完成的工作是________。 A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析 C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化 27.对应Chomsky四种文法的四种语言之间的关系是 AL0L1L2L3BL3L2L1L0 CL3=L2L1L0DL0L1L2=L3 28.给定文法G: A→Ab|cc,试问在下面的符号中,为该文法句子的是______. AccbbBbcbccCbccbccDcbbcc 29.属于自上而下分析法的是() ALL (1)BLR(0)CSLRD算符优先 30.在自下而上的语法分析中,应从开始分析。 A最左素短语B句子C文法的开始符号D句柄 二、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段,分别是词法分析、语法分析、中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中,第一段输入是源程序,最后阶段的输出为目标代码程序。 4、编译程序是指将高级语言源程序翻译成等价的低级语言程序的程序。 5、编译程序是一种常用的_翻译软件。 6、如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段_____、_____、_____。 7、文法G产生的一切句子的全体是该文法描述的语言。 8、最右推导亦称为____。 9、语法分析方法大致上可分为两大类____和____。 递归子程序方法属于____。 10、表达式—a+b*(—c+d)的逆波兰式为____。 11、自顶向下语法分析方法会遇到的主要问题有_____和_____。 12、LL (1)分析法中,第一个L的含义是_____,第二个L的含义是_____,“1” 的含义是_____。 13.确定的有穷自动机是一个五元组、,通常表示为DFA=(K,∑,M,S,Z)。 14.所谓最右推导是任何一步都是对最右非终结符进行替。 15.语法分析器的任务是分析一个文法的句子结构。 16.如果一个文法的任何产生式的右部都不含有相邻的非终结符,则这种文法称为算符文法。 17.进行确定的自上而下语法分析要求语言的文法是无左递归、公共左因子 18.根据优化对象所涉及的程序范围,代码优化分局部优化、循环优化、全局优化 1.给出下述文法对应的正规式 (7分) S→0A|1B A→1S|1 B→0S|0 2.已知文法G(E): E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*F是该文法的一个句型,并指出该句型的所有短语、直接短语和句柄。 (8分) 3.设有文法G[S]: SaBc|bAB AaAb|b Bb|ε 构造其LL (1)分析表, First(S)={a,b} First(A)={a,b} First(B)={b,ε} Follow(S)={#} Follow(B)={#,c} Follow(A)={b} a b c # S S->aBc S->bAB A A->aAb A->b B B->b B->ε B->ε 表中空白表示出错 并分析符号串baabbb是否是该文法的句子. (10分) S->bAB->baAbB->baaAbbB->baabbbB->baabbb所以baabbb是该文法的句子 4.假设可用寄存器为R0和R1,试写出下列四元式序列对应的目标代码。 (10分) T1=B-C T2=A*T1 T3=D+1 T4=E-F T5=T3*T4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复习题 软件