编译原理

复习第一章引论•1.编译程序分几个阶段，每个阶段的任务是什么？•2.表格管理和出错处理•3.前端、后端•4.遍•5.“运算符与运算对象类型不符”属于语义错误•6.算法逻辑上的错误属于语义错误•1.程序语言是由语法和语义两方面定义的。•2.上下文无关文法的定义：四个组成部分：一组终结符号、一组非终结符号、一个开始符号、一组产生式。•3.推导、最左推导、最右推导•4.语法树•在编译中产生语法树是为了语法分析。第二章高级语言及其语法描述•5、什么是句型？什么是句子？什么是语言？•假定G是一个文法，S是它的开始符号。如果Sα，则称α是一个句型。•仅含终结符的句型是一个句子。•文法G所产生的句子的全体是一个语言。第二章高级语言及其语法描述•6.乔姆斯基把文法分成4种类型，即0型文法、1型文法、2型文法和3型文法。•0型文法也称为短语文法。•1型文法也称为上下文有关文法。•2型文法也称为上下文无关文法。•3型文法也称为正规文法。•与程序语言语法有关的文法是上下文无关文法第二章高级语言及其语法描述第三章词法分析•1.状态转换图：使用状态转换图是设计词法分析程序的一种好途径，状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。•一个状态转换图可用于识别（或接受）一定的字符串。•2.确定的有限自动机（DFA）、非确定有限自动机（NFA）。五元式：有限状态集合、有穷字母表、转换函数、唯一的初始状态、终止状态集合。•3.设有确定的有限自动机DFAM=({0,1,2,3},{a,b},δ,0,{3})，•其中δ为:δ(0,a)=1δ(0,b)=2•δ(1,a)=3δ(1,b)=2•δ(2,a)=1δ(2,b)=3•δ(3,a)=3δ(3,b)=3•请画出状态转换矩阵和状态转化图。第三章词法分析•相应的状态转换矩阵如下表：•对应的状态转换图状态ab0121322133333012aaa，babbb第三章词法分析•4.设计一个DFA,要求能够识别∑={0,1}上能被5整除的二进制数。第三章词法分析0123开始开始41001010101•5.词法分析的流程第三章词法分析第四章语法分析——自上而下分析•1.语法分析器的功能•2.自上而下语法分析方法会遇到的主要问题是回溯和左递归。•3.把一个文法改造成任何非终结符的所有候选式首符集两两不相交的方法是提取公共左因子。•4.LL（1）分析法中，第一个L表示从左到右扫描输入串，第二个L表示最左推导。1表示分析时每步只需向前看一个符号。•5.LL（1）文法的条件是什么？•LL（1）文法的条件是：•（1）文法不含左递归。•（2）FIRST(α）∩FIRST(β)=φ。•（3）对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）=Φ。第四章语法分析——自上而下分析•6.对于下面的文法，计算每个非终结符的FIRST集合和FOLLOW集合。•E→TE’•E’→+E|ε•T→FT’•T’→T|ε•F→PF’•F’→*F’|ε•P→(E)|a|b|∧第四章语法分析——自上而下分析•First(E)=First(T)=First(F)={(,a,b,∧}•First(E’)={+,ε}•First(T’)={(,a,b,∧,ε}•First(F’)={*,ε}•Follow(E)=Follow(E’)={#,)}•Follow(T)=Follow(T’)={+,#,)}•Follow(F)=Follow(F’)={(,a,b,∧,+,),#}•Follow(P)={*,(,a,b,∧,+,),#}第四章语法分析——自上而下分析•7.两种实现方法：递归下降分析法、预测分析程序。第四章语法分析——自上而下分析•1.简述自下而上的语法分析方法。•所谓自下而上语法分析方法就是从输入串开始，逐步进行“规约”，直至规约到文法的开始符号；或者说从语法树的树叶开始，逐步向上规约，直至规约到根节点。•2.一个句型的句柄是该句型的最左直接短语。•3.规范规约是指最右推导的逆过程。•.第五章语法分析——自下而上分析•4.算符优先分析法•（1）特别适应于表达式分析的方法。•（2）算符优先分析法中，优先表中存储的是优先关系。•（3）算符优先分析法的可规约串是句型的最左素短语。第五章语法分析——自下而上分析•5.LR分析法•（1）LR（K）文法是从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。•（2）四种分析表•（3）LR(0)项目的含义•（4）例给定文法：S→AS|b•A→SA|a•要求列出这个文法的所有LR(0)项目。第五章语法分析——自下而上分析•S→.ASS→A.SS→AS.•S→.bS→b.•A→.SAA→S.AA→SA.•A→.aA→a.第五章语法分析——自下而上分析•（5）写出LR(0)分析表的构造步骤。•①确定G的LR(0)项目；•②以LR(0)项目为状态,构造一个能识别文法G的所有活前缀的NFA；•③利用子集法,将NFA确定化,成为以项目集合为状态的DFA根据；•④利用上述DFA可直接构造出LR分析表。第五章语法分析——自下而上分析•（6）比较LR(0)、SLR（1）、LR（1）、LALR（1）分析表的优缺点。•这4种分析表都能识别对应文法的全部句子，其共同特征就是用规范规约的方法寻找句柄进行规约。在这4种方法中，LR（0）分析表对文法的要求较高，其构造方法是其它表构造方法的基础；SLR（1）分析表对文法的要求有所降低，容易实现，因而很有实用价值；LR（1）分析表对文法的要求最低，适用于一大类文法，故其分析能力最强，但其实现代价过高；LALR（1）分析表的分析能力介于SLR（1）和LR（1）之间，实现代价比LR（1）低。第五章语法分析——自下而上分析第六章属性文法和语法制导定义•1.什么是语法制导翻译法？•语法制导翻译法就是在语法分析的过程中,随分析的过程,根据为每个产生式添加的语义动作进行翻译的方法。•2.写出产生式、语义规则和语义子程序之间的关系。•①产生式:一个产生式描述了一个语法单位,但它只说明了该语法单位能产生的符号串,并未指明所产生的符号串有什么实际意义,即该符号串究竟要做什么。•②语义规则:一个产生式的语义规则描述了该产生式的具体的动作意义,即该产生式产生的符号串要做什么。•③语义子程序:按照产生式的语义规则生成某种中间代码,实现相应的动作。第六章属性文法和语法制导定义•3.对于文法的每个产生式都配备了一组属性的计算规则，称为属性。•4.文法符号的属性有两种，一种称为综合属性，一种称为继承属性。•综合属性传递信息的方向是自下而上。•继承属性传递信息的方向是自上而下。第六章属性文法和语法制导定义•5.在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的。•一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。第六章属性文法和语法制导定义第六章属性文法和语法制导定义•6.为文法•S→(L)|a•L→L,S|S•写一个语法制导定义，它输出括号的对数。•S’→Sprint(S.num)•S→(L)S.num:=L.num+1•S→aS.num:=0•L→L1,SL.num:=max{L1.num,S.num}•L→SL.num:=S.num第六章属性文法和语法制导定义•7.为文法•S→(L)|a•L→L,S|S•写一个翻译方案，它输出每个a的嵌套深度。例如，对于(a,(a,a))，输出的结果是122。第六章属性文法和语法制导定义•S’→{S.depth:=0}S•S→{L.depth:=S.depth+1}(L)•S→a{print(S.depth)}•L→{L1.depth:=L.depth}L1,{S.depth:=L.depth}S•L→{S.depth:=L.depth}S第六章属性文法和语法制导定义•8.S-属性文法•L-属性文法第六章属性文法和语法制导定义第七章语义分析和中间代码产生•1.常用的中间代码的形式：后缀式（逆波兰式）、三地址码（三元式、四元式、间接三元式）。•2.会用后缀式表示。•3.已知A是一个10×20的数组(每维下界均为1)，每个元素占1个单元，且按行存放，要求写出：赋值语句X=A[I,J]的四元式序列。•100(*，I，20，T1)/*d2=20*/•101(+，J，T1，T1)/*得到20I+J*/•102(−，A，21，T2)/*得到A−21*/•103(=[ ]，T2[T1]，_，T3)/*T2[T1]即为A[I, J]，即T3=T2[1]*/•104(=，T3，_，X)第七章语义分析和中间代码产生第十章优化•1．为了获得更优化的程序，可以从哪些层次上对程序进行优化？•为了获得更优化的程序，可以从各个环节着手：•在源代码级，可以选择适当的算法和安排适当的实现语句来提高程序的效率。•在语义动作的设计上，考虑产生更高效的中间代码，并为优化阶段做准备。•在中间代码级，安排专门的优化阶段，进行各种等价变换，以改进代码的效率。•在目标代码级，考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等。2.常用的优化方法局部优化:删除公共子表达式、复写传播、删除无用代码循环优化：代码外提、强度削弱、删除归纳变量3.程序基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口。4.基本块的入口、基本块的划分、流图第十章优化•5.已知如下中间代码序列：•（1）readX•（2）readY•（3）R:=XmodY•（4）ifR=0goto(8)•（5）X:=Y•（6）Y:=R•（7）goto(3)•（8）writeY•（9）halt•要求：（1）写出基本块的入口语句。•（2）为其划分基本块。•（3）为其构造流图。第十章优化•①入口语句：1、3、5、8•②基本块和流图（3）R:=XmodY（4）ifR=0goto(8)（1）readX（2）readY（5）X:=Y（6）Y:=R（7）goto(3)（8）writeY（9）halt第十一章目标代码生成•1.目标代码的形式•2.要考虑的问题•（1）指令选择（2）寄存器分配（3）计算顺序选择SDL•1.SDL把应用领域分为两部分SDL系统和环境。•2.SDL中，系统与环境之间的通信可以通过什么来通信交换信号。•3.SDL系统由系统、功能块和进程3个层次的实体组成。•4.SDL中每个系统可以划分为多个功能块。•5.SDL系统中的功能块最终都需要定义为进程。•6.在SDL系统中的基本单位是进程实例。•SDL•7.SDL描述系统行为的基础是扩展的有限状态自动机。•8SDL的每个进程实例就是有限状态自动机。•9.SDL中，进程规定了系统的动态结构。•Block代表了系统的静态结构。