下载文档原格式
名词解析1.编译器: 一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。
2.词法分析：从左至右读源程序，识别单词符号3.语法分析：在词法分析的基础上将单词序列组合成各类语法短语4.语义分析：语义检查，收集语义信息,进行类型审查5.代码优化：对中间代码进行优化（提高时间与空间效率6.遍：对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示7.上下文无关文法:所定义的的语法单位是完全独立于这种语法单位可能出现的上下文环境的8.推导与归约：推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程9.最左/右推导：对句型最左/右非终结符进行展开10.最左/右规约：最右/左推导的逆过程，即对最左/右边的可归约串进行归约11.句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串12.句子：只包含终结符号的句型称为句子13.句柄：最左直接短语14.句子、文法、语言的二义性：如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的如果一个文法有一个句子是二义的，此文法称为二义文法如果一个语言的所有文法都是二义的，称此语言是二义的15.正规表达式：一个表示字符串格式的模式，可以用来描述单词符号的结构16.有限自动机：是具有离散输入与离散输出的一种数学模型，输入字符串，输出是、否17.不确定的有限自动机：由状态集合，输入符号集合，转换函数，开始状态，接受状态集合组成18.确定的有限自动机：没有ε边转移且一个状态面临一个输入符号时最多只转移到一个状态的NFA19.自顶向下分析：从根到叶子来建立句子的分析树或，给出句子的一个从开始符号出发的推导序列20.自底向上分析：从叶子到根来建立句子的分析树或，给出一个从句子出发到开始符号的归约序列21.综合属性：属性值是分析树中该结点的子结点的属性值的函数22.继承属性：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数23.S -属性定义：只含有综合属性的语法制导定义24.L -属性定义：是一种语法制导定义L-属性定义包含S-属性定义25.代码优化：对中间代码进行优化（提高时间与空间效率）26.基本块:·一个连续的三地址（中间）代码序列·只有一个入口语句，一个出口语句·执行时从入口语句进入，从出口语句退出27.活动记录：是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据。
编译原理_国防科技大学中国大学mooc课后章节答案期末考试题库2023年1.对于文法G(S')，该文法识别活前缀的DFA如下图，状态I5包含的项目有G(S')：(0) S' → S(1) S → iSeS(2) S → iS(3) S → a【图片】答案:S → iSeŸS_S → ŸiSeS_S → ŸiS_S → Ÿa2.(a+b)/(c-d)对应的逆波兰式(后缀式)是答案:ab+cd-/3.表达式(a+b)/c-(a+b)*d对应的间接三元式表示如下，其中三元式表中第(3)号三元式应为间接码表三元式表(1) OP ARG1 ARG2 (2) (1) + a b (1) (2) / (1)c (3) (3) (4) (4) - (2) (3)答案:( *, (1), d)4.设AS 为文法的综合属性集, AI 为继承属性集, 则对于下面的属性文法G(P)定义中，AS和AI正确描述是产生式语义规则P → xQR Q.b:=R.d R.c:=1R.e:=Q.a Q → u Q.a:=3 R → v R.d:=R.c R.f:=R.e答案:AS={ Q.a, R.d, R.f } AI={ Q.b, R.c, R.e }5.考虑下面的属性文法G（S）【图片】过程enter(name, type)用来把名字name填入到符号表中，并给出此名字的类型type。
按照该属性文法，关于语句【图片】 , 【图片】 , 【图片】:integr的语义描述准确的是答案:说明 , , 是integer变量，把 , , 三个名字填入符号表中，并在类型栏中填上integer6.考虑下面的属性文法G(S)【图片】对于输入字符串abc进行自下而上的语法分析和属性计算，设S.u的初始值为5，属性计算完成后，S.v的值为答案:187.关于属性文法，下列说法中正确的是答案:属性文法是对上下文无关文法的扩展。
编译原理练习四一、填空题1．编译过程中，常见的中间语言形式有四元式、三元式、逆波兰表示和树形表示。
2、表达式x+y≤z V a>0Λ(8+z)>3的逆波兰表示为 xy+z≤a0>8z+3>ΛV。
3、在编译程序中安排中间代码生成的目的是便于代码优化和便于目标程序的移植。
4、根据所涉及程序的范围，优化可分为局部优化、循环优化和全局优化三种。
5、编译程序进行数据流分析的目的是为了进行全局优化。
6．局部优化是局限与一个基本块范围内的一种优化。
7．基本块内可进行的优化有：删除公共子表达式、删除无用代码、合并已知常量等。
8．从词法分析器到中间代码生成与被编译的源代码有关，称之为编译器的前端，而目标代码生成主要与目标机有关，称之为编译器的后端。
9．编译器通常按需要把寄存器分为三组使用：可分配寄存器、保留寄存器和零用寄存器。
10．释放寄存器的总的原则是释放代价最小的寄存器。
二、选择题1．表达式-a+b*(-c+d)的逆波兰式是 d 。
a.ab+-cd+-*b.a-b+c-d+*c.a-bc+-d+*d.a-bc-d+*+2．在编译程序中安排中间代码生成的目的是 b d 。
a.便于进行存储空间的组织b.有利于目标代码的优化c.有利于编译程序的移植d.有利于目标代码的移植e.有利于提高目标代码的质量3．-a-(b*c/(c-d)+(-b)*a)的逆波兰表示是 c 。
a.abc*cd-b-a*+/--b.a-bc*cd-b-a*+/-c.a-bc*cd-/b-a*+-d.a-bc*/cd-b-a*+-4.赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示是 c 。
a.Xab+cd-/-bc*a+-:=b. Xab+/cd-bc*a+--:=c. Xab+-cd-/abc*+-:=d. Xab+cd-/abc*+--:=5.对任何一个编译程序来说，产生中间代码是 b .a.不可缺少的b. 不一定必要的6．逆波兰表达式ab+cd+*所代表的中缀形式的表达式是 b 。
1计算机系统组成运算器：算术/逻辑运算单元ALU、累加器ACC、寄存器组、多路转换器、数据总线组成。
控制器：计数器PC、时序产生器、微操作信号发生器，指令寄存器、指令译码器。
CPU的功能：程序控制、操作控制、时间控制、数据处理（最根本的）。
CACHE高速缓存的地址映像方法：直接地址映像（主存分区，区分块）、全相联映像（主存分块）、组相联映像（主存分区，区分块、块成组，CACHE 分块成组）。
替换算法：随机、先进先出、近期最少用、优化替换算法。
性能分析：H为CACHE命中率，t c为Cache存取时间、t m为主存访问时间，Cache等效访问时间t a＝H t c+(1-H) t m提高了t m/t a倍。
虚拟存储器由主存、辅存、存储管理单元和操作系统软件组成。
相联存储器是按内容访问的，用于高速缓冲存储器、在虚拟存储器中用来作段表页表或快表存储器、在数据库和知识库中。
RISC精简指令集：指令种类少、长度固定、寻址方式少、最少的访内指令、CPU内有大量寄存器、适合流水线操作。
内存与接口统一编址：都在一个公共的地址空间里，独立使用各自的地址空间。
优点是内存指令可用于接口，缺点内存地址不连续，读程序要根据参数判断访内还是访接口。
廉价冗余磁盘阵列RAID：0级不具备容错能力但提高了传输率N倍、1级镜像容错技术、2级汉明码作错误检测、3级只用一个检测盘、4级是独立地对组内各磁盘进行读写的阵列，用一个检测盘、5级无专门检测盘。
中断方式处理方法：多中断信号线法、中断软件查询法、菊花链法（硬件）、总线仲裁法、中断向量表法（保存各中断源的中断服务程序的入口地址）。
直接存储器存取DMA：内存与IO设备直接成块传送，无需CPU干涉。
根据占据总线方法不同分为CPU停止法、总线周期分时法、总线周期挪用法。
输入输出处理机用于大型机：数据传送方式有字节多路方式、选择传送方式、数组多路方式。
指令流水线：操作周期是最慢的操作的时间。
中间代码基本块的划分
任务要求
在理解代码优化原理的基础上，实现将中间代码序列划分基本块的程序
1．理解编译过程中代码优化的定义
2．掌握各种代码优化的方法
3．定义程序流图中的基本块
4．明确程序流图的形式及功能
5．程序设计及调试
一．原理阐述
1.代码优化的定义：
代码优化的实质就是提高代码质量从而加快代码执行速度的一种技术。
根据代码优化是否涉及具体的计算机，又将代码优化分为⑴与机器有关的优化（即窥孔优化），一般在目标代码上进行；⑵与机器无关的优化，常在中间代码上进行。
又根据优化范围分成局部优化、循环优化、全局优化。
2.代码优化的方法：
1)删除公共子表达式
2)代码外提
3)强度削弱
4)删除归纳变量5)合并已知量
6)复写传播
7)删除无用赋值
3.基本块和划分基本块的定义和方法：
定义：基本块就是代码序列中一组顺序执行的语句序列，只有一个入口和一个出口。
而划分
基本块的实质就是定义入口和出口语句。
划分基本块的方法：
1)定义入口语句
①四元式的第一个语句；
②由条件转移语句或无条件转移语句能转到的语句；
③紧跟在条件转移语句后面的语句。
2)定义出口语句
①下一个入口语句的前导语句；
②转移语句（包括转移语句本身）；
③停语句（包括停语句本身）。
构造基本块，删除不属于任何基本块的语句
二．流程示意图
按四元式序列，给出如下程序流图
⑴read x；⑵read y；⑶L1:c=c+1；
⑷if c=0 goto L2；⑸x=y；⑹y=c；
⑺goto L1；⑻L2: write y；⑼halt（以“~ ”表示）
三．部分代码：
入口条件1
int i=0,j=-1,back_i=0,in_num=0,out_num=0;
char g[200];
cout<<"请输入要进行基本块划分的四元式（按回车表示四元式输入完毕）:"<<endl; for(i=0;i<200;i++)
{g[i]=' ';c[i]=' ';} //g[]（局部）,c[]（全局）,清零
gets(g); //输入四元式
for(i=0;i<200;i++) {c[i]=g[i];} //将输入的四元式备份到c[]
in[in_num++]='1'; //首句为入口语句，将语句序号放入in[]
for(i=0;*(g+i)!='~';i++) //由条件转移语句或无条件转移语句能转到的语句为入口语句
{
if(*(g+i)==':') //找到转移语句能转到的语句
{
back_i=i; //i是指针，back_i记录当前位置，用于搜索语句序号
for (;*(g+back_i)!=')';back_i--)
{continue;}
in[in_num++]=*(g+back_i-1); //得到入口语句序号，将其放入in[]
出口条件1
out[out_num++]=(char)((int)*(g+back_i-1)-1);break;
//入口语句的上一句是出口语句，将其序号放入out[] }
}
cout<<"_______________________________"<<endl<<endl;
cout<<"判定输出语句/输入语句过程（输出语句—>输入语句）:"<<endl<<endl;
for(;j!=0;j++)
{cout<<"sentence ("<<out[out_num-1]<<") --> ("<<in[in_num-1]<<")"<<endl;}
for(i=0;*(g+i)!='~';i++) //紧跟在条件语句后面的语句为入口语句
{
if(*(g+i)=='i'&&*(g+i+1)=='f') //找到条件语句关键字if
{
back_i=i;
for(;*(g+back_i)!='(';back_i++) //找到条件语句的下一句，即入口语句
{continue;}
in[in_num++]=*(g+back_i+1); //将入口语句序号放入in[] }
}
出口条件2
for(i=0;*(g+i)!='~';i++) //转移语句为出口语句
{
if(*(g+i)=='g'&&*(g+i+1)=='o') //找到转移语句的关键字goto
{
back_i=i;
for(;*(g+back_i)!=')';back_i--)
{continue;}
out[out_num++]=*(g+back_i-1); //将语句序号放入out[]
in[in_num++]=(char)((int)*(g+back_i-1)+1);
//其下一句是入口语句，将语句序号放入in[]
for(;j<1;j++)
{cout<<"sentence ("<<out[out_num-1]<<") --> ("<<in[in_num-1]<<")"<<endl;}
for(;*(g+back_i)!='L';back_i++) //找到转移语句能够转到的语句序号
{continue;}
for(;*(c+ch)!='~';ch++)
{
for(;*(c+ch)!='L';ch++) {continue;}
if(*(g+back_i+1)==*(c+ch+1)&&back_i!=ch)
//根据语句序号找到相应的语句
{
back_ch=ch;
for(;*(c+back_ch)!=')';back_ch--)
{continue;}
cout<<"sentence ("<<out[out_num-1]<<")--> ("<<*(c+back_ch-1)<<")"<<endl;
break; //输出转移
}
}
ch=0;
}
}
出口条件3
for(i=0;*(g+i)!='~';i++) //停语句为出口语句，找到停语句{continue;}
back_i=i;
for(;*(g+back_i)!=')';back_i--)
{continue;}
out[out_num++]=*(g+back_i-1); //将语句序号放入out[] cout<<"_______________________________"<<endl<<endl;
cout<<"划分好的代码块："<<endl;
for(i=0;i<4;i++)
{cout<<"Block[ "<<i+1<<" ]: ("<<in[i]<<") -- ("<<out[i]<<")"<<endl;}
//输出各基本块内的语句四．程序运行结果
1. 运行输入的四元式：
2. 输出结果：划分好的基本代码块
五．总结
这次我主要负责中间代码基本块的划分。
有了上次词法分析器的程序设计的经验，我以书中的实例为参考模型，进行编程，这样就避免了由空想带来的不必要的麻烦。
整个设计还是以c＋＋中的模块化设计为主。
特别是在语句类型判断上，在编写代码时，虽然只要遵守判断规则，但仍然遇上了不困难，为了能方便的分块，使程序能更加简便、易
懂，我还自行将语句按规则分为三类。
同时在这次设计过程中，也加强了我们的团队合作力，大家互相帮助，在交流过程中，也学习到不少他人在思考过程中的长处，弥补了自己不少欠考虑的地方，受益良多。
最后非常感谢卜老师给予的指导。
THANKS !!!
致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求
欢迎您的下载，资料仅供参考。
