编译技术复习资料 9页

第一章编译概述1.编译程序：所谓编译程序是指这样一个程序，它把一种语言（称做源语言）所写的程序（源程序）翻译成与之等价的另一种语言（称做目标语言）的程序（目标程序）。编译程序是一种编译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。P12.解释程序：解释程序也是一种编译程序，它将源程序作为输入并执行Z,即边解释边执行。3.编译过程的5个阶段（翻译的大致过程）：笫一阶段:词法分析対构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则,识别出一个一个具有独立意义的单词（也称单词符号，简称符号）。第二阶段:语法分析在词法分析的基础上根据语言的语法规则从单词符号串屮识别出各种语法单位（如表达式、说明、语句等）并进行语法检查，即检查各种语法单位在语法结构上的正确性。笫三阶段：语义分析及中间代码生成首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式來描述这种语义。第四阶段：代码优化对前阶段产牛:的中间代码进行等价变换或改造，以期获得更为髙效的,即省时间和空间的II标代码。第五阶段：目标代码生成将屮间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。4.编译程序结构框图p55.练习题和习题p7习题1.1什么是编译过程见上11.2编译过程的5个阶段见上313编译程序的结构框图见上4第二章文法和语言的基本知识I.符号的幕运算P92•集合的幕运算plO3.集合A的正闭包A+M闭包A*plO4.文法：文法是规则的非空有穷集合，通常表示成四元组G=（VN,VT,P,S）。设计文法p275.句子:设有文法G[S]（S是文法G的开始符号）,如果S=*>x,x^VT*z则称x是文法G⑸的句子。6.语言：文法G⑸产生的所有句子的集合称为文法G所定义的语言，记为L（G[S]）:L（G⑸）={x|s=>xJgLxeVT*}7.规范推导：对于一个推导序列屮的每一步直接推导a=>0,都是对a屮的最右非终结符进行替换，最右推导也称为规范推导。8.用规范推导推出的旬型称为规范句型。9.规范规约：规范推导的逆过程，称为最左规约也称为规范规约。10•直接短语：令G是文法的开始符号，假定。B§是文法G的一个句空，如果有S=*>aB6且A=>P,则称B是直接短语。II.句柄：一个句型的最左宜接短语称为该旬型的句柄。12.语法树：对句型的推导过程给出一种图形表示，这种表示称为语法树。具体见p2013•文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义性的。\n14.语言的分类：语言分为4大类，即0型，1型，2型和3型。划分的依据是对文法中的规则施加不同的限制。(包含关系、类型、哪种要求严格见书P24)15.本章小结设计一个文法，定义一个已知的语言；已知一个文法确定该文法所定义的语言；求句型的短语、直接短语和句柄；文法二义性的判断。P27第三章词法分析与有穷自动机1•词法分析的任务：对字符串表示的源程序从左到右地进行扫描和分解，根据语言的语法规则识别出一个一个具有独立意义的单词符号。2.语言的单词符号：p33(1)关键字(2)标识符(3)常数(4)运算符(5)届符3.词法分析程序所输出的单词符号通常表示成如下的二元式：(单词种別，单词自身的值)4.两个相邻a和两个相邻b的正则表达式。P345.冇穷自动机：具冇离散输入与输出系统的一种抽彖数学模型。6.化简：p44,p45例题3.16ppt7/列题：3.12、3.14、3.163.13、3.15、3.17第四章语法分析1.语法分析程序的功能：以词法分析器生成的单词符号序列作为输入，根据语言的语法规则,识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。2.语法分析的分类：语法分析分为两人类，即自上而下的分析方法和自下而上的分析方法。3.两种分析方法的区别：(1)口上而下的分析法是从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法。(2)口下而上的分析法是从给定的输入串开始，根据文法规则逐步规约，直至规约到文法的开始符号。4•左递归的消除：采用白上而下分析法进行语法分析需要消除文法的左递归性；对含直接左递归的规则进行等价变换，消除左递归。5.LL(1)文法：一个上下文无关文法G是LL⑴文法，当H.仅当对G中每个非终结符A的任何两个不同的规则Act|卩，满足SELECT(Aa)nSELECT(AP)=0o6.判断是否是LL⑴文法7.递归下降分析法：是确定的自上而下分析法，这种分析法要求文法是LL⑴文法。8.递归下降分析方法基木思想：对文法屮的每个终结符编写一个函数(子程序)，每个函数(或子程序)的功能是识别山该非终结符所表示的语法成分。9.递归子程序怎么写p66以后10.LL(1)分析法：预测分析法也称为LL(1)文法，两个L分别表示最左推导和从左到右分析字符串。P68考试大题11•口下而上的分析法：按照“移进■规约”法的原理建立起来的一种语法分析方法。最终若栈中剩下句子右届符“$”和文法的开始符号，则所分析的输入符号是文法的正确句子。12.算符优先分析法和LR分析法都是自下而上的分析方法。13.LR分析法：最右推导逆过程，一种自下而上进行规范规约的语法分析方法；规范规约是最左规约，每次规约的是句柄。14.LR(0)分析表:对于一个文法G的拓广文法G'的LR(O)项目集规范族中每个项目集,不存在移进项冃和规约项n同时并存或多个规约项n同时并存，则称G为LR(O)文法。\n12.冲突：p87冲突能解决的是SLR⑴文法。13.例题4.2、4.3、4.6、4.7、4.14、4.15、4.17。4.18第五章语法制导翻译技术和中间代码生成1•语法制导翻译技术用于语义分析和屮间代码生成时2.词法考点：止规文法、正规表达式、DFA/NFA3.语法考点：上下文无关文法分为白上而下和白下而上。4.语义考点：属性文法5.对语法分析后的语法单位进行语义分析，首先编译程序审查每个语法结构的静态语义，如果静态语义正确，再生成屮间代码，也有的编译程序不生成中间代码而•肓接生成实际的目标代码。较为常见的是用属性文法作为描述程序设计语言语义的工具。采用语法制导翻译法完成对语法成分的翻译工作。6.中间代码的形式：逆波兰式、三元式、树形表示、四元式等。7.属性文法:一个属性文法是在上卜-文无关文法的基础上，为每个文法规则式都定义一组属性的计算规则，称为语义规则。&属性分为两类：综合属性和继承属性。9•语法制导翻译法的基本思想:对文法中的每个产生式都附加上一个语义动作或语义子程序,在执行语法分析非过程中，每当使用一条产生式进行推导或规约时，就执行响应产生式的语义动作，从而完成预定的翻译工作。【重点背】3.逆波兰式(后缀式)中没有括号，运算对象写在而而，运算符写在后而。考试时写到赋值语句。Pill元式和三地址代码：pll4四元式:(i)(op,argl,arg2,result)三地址代码序列：⑴Tl=a*b⑵T2=c/d⑶T3=T1+T2⑷X二T312.习题5.25.5什么是属性文法见上75.6语法制导翻译的基本思想：见上9第六章符号表的组织和管理1•符号表的组成：符号表的每一项通常由两部分组成，第一部分是名字栏，另一部分是与名字冇关的信息栏。2.符号表的组织方式：一般可以分为在接方式和间接方式。3•直接方式：在符号表中直接填入源程序中定义的标识符及其相关信息。1.间接方式：单独设置一个字符串数组，其中存放所有标识符，在符号表的名字栏中设置两项内容：指针和整数，指针指向标识符在数组屮的位置，整数值表示标识符的长度。2.另一类组织方式：按标识符的种属，同一种属的标识符建立一张符号表。&根据符号表名字栏的组织特点，符号表信息栏的组织方式分为两类：固定信息内容和仅记载信息地址。2.如果名字栏屮的标识符按种属分类，由于同类标识符具有的基本特征一致，可以将这些信息一一-记录在信息栏屮；如果符号表屮名字不分种属，由于不同种属的标识符特征不一致，它们所需存储的信息也不一•致，也不容易确定一个固定长度的空间统一安排，这时可以在符号表外另设一组存储空间，在符号表信息栏中附设一个指针，指向表外存储空间的地址。\n2.符号表的作用(习题6.1)：(1)首先，当编译程序扫描到语言程序中标识符的说明部分时，根据说明语句的功能。（2）其次，符号表内容为上下语义的合法性检查提供依据。（3）最后生成目标代码时，符号表中的内容乂是编译程序分配存储地址的依据。（4）代码优化时，编译程序将利川符号表提供的信息选出恰当的代码进行优化。习题6.2符号表的组织方式冇哪儿种？见上2、5第七章代码优化1•代码优化：提高代码质量的技术常称为代码优化，依据等价变化原则。2.根据优化对彖所涉及的程序范围，又分为局部优化、循坏优化、全局优化。3.7种优化：P146-P148（1）删除公共子表达式（删除多余运算）公共子表达式是指在一个基本块内计算结果相同的子表达式。（2）代码外提代码外提是指将循环中的不变运算提到循环体前面。（3）强度削弱强度削弱是指在不改变运算结果的前捉卜，将程序屮执行时间长的运算替换成执行时间短的运算。（4）变换循环控制条件（删除归纳变量）在B2中存在变虽T与循环控制变量I保持线性关系,则可由T取代I,因此对三地址语句（12）中的循环控制条件（5）合并己知量合并己知量是指若参加运算的两个对彖在编译时都是已知量，则町以在编译时直接计算出它们的运算结果，不必牛成口标（6）复写传播复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响其运行结果的变量。（7）删除无用赋值对赋值语句X二Y,若在程序的任何地方都不引用X,这时该语句执行与否对程序运行结果没有任何作用，这种语句称为无用赋值语句，可以删除。其中（1）、（5）、（7）进行基本块优化；（2）、（3）、（4）进行循环优化【注】7个优化都要懂,重点是⑴、（2）、（3）、（5）o4.局部优化：在基本块范围内进行的优化。5.划分棊本块的方法：P1491）从四元式序列确定满足以下条件的入口语句（1）四元式序列的第一个语句。（2）由条件转义语句或无条件转移语句能转到的语句。（3）紧跟在条件转移语句后而的语句。2）确定满足以下条件的出口语句（1）下一个入口语句的前导语句。（2）转移语句（包括转义语句本身）。（3）停语句（包括停语句本身）。3）构造基木块，删去那些不属于任何基木块的语句6•循环优化：对循环体代码进行优化，分为代码外提和强度削弱与删除归纳变量。7.例题7.2、7.4图7.6、7.108.习题7.1什么是代码优化？见上1代码优化通常在什么基础上进行？答：口标代码、屮间代码、源代码9•习题7.2常用的优化技术有哪些？见上3\n10.习题7.3什么是局部优化？见上411•习题7.4什么是循环优化？见上6第八章运行时的存储组织与管理1•存储分配策略：（1）静态存储分配策略（编译时全部都分配好了）。（2）动态存储分配策略，分为栈式和堆式2.运行时环境:冃标计算机的寄存器和存储器的结构，以及用来管理存储擀并保存执行过程所需要的信息。实际上，几乎所冇的程序设计语言都使用一下三种类型的存储环境：完全静态环境、基于栈的存储环境及基于堆的存储环境中的一种或儿种。3.存储空间：编译程序还必须分配冃标程序运行时所需的存储空间，这些空间包括用户定义的各种类型的数据对象所需的存储空间、调用过程所需的连接单元和组织输入/输出所需的缓冲区及保留中间结果和传递参数所需的临时单元。4.存储管理的复杂程度取决于源语言本身，具体包括：（1）允许的数据类型的多少。（2）语言屮允许的数据项是静态确定和动态确定。（3）程序决定名字的作用域的规则和结构。5.存储空间分配的一个重要单元是过程的活动记录。过程的活动记录是一段连续的存储区,用来存放过程的一次执行所需的所有信息。&运行时存储空间的划分和过程活动记录见图8.1和8.2。P1687.最简单的运行时坏境类型是所有的数据都是静态的。在静态坏境屮所有的变量都是静态分配，每个过程只有一个在执行之丽被静态分配的活动记录，可以通过固定的地址直接访问所冇的变量。8.栈式存储分配：先调用后返回，先申请后释放。其分配策略是将整个存储空间设计成一个栈，每当调用一个过程时就将它的活动记录压入栈，在栈顶形成过程工作时的数据区，当过程结束时再将其活动记录弹出栈。9.堆式存储分配方法的基木思想：一个程序开始执行时有很人一块存储空间，运行期间如果需要就从里而申请--块存储空间，使用完毕归还。10.习题8.1.1完全静态环境、基于栈的存储环境、基于堆的存储环境8.1.2静态存储分配：如果在编译时就能确定目标程序运行时所需要的全部数据空间的大小，则编译时就能安排好冃标程序的全部数据空间，并能确定每个数据项的单冗地址、存储空间。栈式存储分配：在允许递归调用且毎次调用都要重新分配局部变量的语言中，编译程序不能静态地分配活动记录。对于这种语言应该采用栈式存储分配。堆式存储分配：一•种程序语言允许数据对象能够白由地分配和释放，这种语言通常采用堆式存储方法。第一章概述1.翻译程序是指这样一个程序，它把一种语言所写的程序翻译成与之等价的另一种语言的程序。2.编译程序是指一种翻译程序，它将高级语言所写的源程序翻译成与Z等价的机器语言或汇编语言的冃标程序。3.解释程序也是一种翻译程序，它将源程序输入并执行，即边解释边执行。它与编译程序的主要区别是解释程序的执行过程屮不产生目标程序，而是按照源语言的定义解释执行原语言本身。\n1.词法分析的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出具有独立意义的单词。2.语法分析的任务是在词法分析的基础上，根据语言的语法规则从单词符号串屮识别出各种语法单位(如表达式、说明、语句等)并进行语法检查，即检查各种语法单位的正确性。3.语义分析的任务是首先对每种语法单位进行静态的语义检杳，然示分析其含义，并用另一种语言(中间代码或直接用冃标语言)来描述这种语义。7•编译语言结构框图：P5五步：词法分析，语法分析，语义分析和中间代码生成，代码优化，冃标代码生成。辅助：表格管理程序，岀错处理程序。第二章文法和语言的基本知识1•文法是规则的非空冇穷集合，通常表示成四元组G二(Vn,Vt,P,S)oVn是规则屮非终结符号的集合Vt是规则屮终结符号的集合P是文法规则的集合S是一个非终结符号，称为文法的开始符号或文法的识別符号，它至少要在一条规则中作为左部出现。2•句型、句子、语言1)设冇文法L(G[S]),如果S~+x,xe(VnUVt)*,则称符号串x为文法L(G[S])的句型。2)Sf+x,xevt*,则称x为文法L(G[S])的句子。3)文法G⑸产生的所有句子的集合称为文法G所定义的语言，记为L(G[S])：L(G[S])={x|S-*+x且xGVt*}2.最右推导也称为规范推导，用规范推导推出的句型称为规范句型。3.递归规则是指在规则的左部和右部具有和同非终结符的规则。如果文法中有规则A->A—称为规则左递归如果文法屮有规则A->—A称为规则右递归如來文法中有规则A->~~~A~~~称为规则递归4.句柄：一个句型的最左肓•接短语称为该句型的句柄。特征:1•它是直接短语，即某规则的右部2.它具有最左性5.文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。第三章词法分析与有穷自动机(FA二NFA+DFA)1.词法分析的任务2.输入：字符串输出单词的形式：二元式(单词种别，单词自身的值)\n1.正规式与正规集P35例3.13.22.正规文法与正规式：都是描述正规集的工具3.有穷自动机是具有离散输入与输出系统的一种抽象数学模型。4.非确定有穷自动机(NFA)：五元组(Q,E,f,S,Z),特殊：多值函数，非空初态集Q：有穷状态集合刀：有穷输入字母表f：映射S：初态Z：终态5.确定冇穷自动机(NFA)：五元组(Q,工，f,S,Z),特殊：单值函数，唯一初态6.R->NFA->DFA：P40-P46,例12■例17第四章语法分析1.语法分析的功能是以词法分析生成的单词符号序列作为输入，根据语言的语法规则，识别出各种语法单位，并进行语法检杳，检杳所给单词符号序列是否是该语言的文法的一•个句子。2.语法分析的两人方法：白上而下的分析方法+自下而上的分析方法3.自上而下的分析方法是从文法的开始符号出发，根据文法规则正向推导出给定旬了的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶子的分析方法。4.自下而上的分析方法是从给定的输入串开始，根据语法规则逐步进行归约，直到归约到文法的开始符号；或者说，从语法树的末端开始，步步向上归约，直到根结点的分析方法。5.白上而下分析法：(1)文法左递归的消除：对含直接左递归的规则进行等价变换，消除左递归。P61例4.24.3(2)H溯的消除：LL(1)文法一个上下文无关文法G是LL(1)文法,当且仅当对G中每个非终结符A的任何两个不同的规则A->a|B,满足select(A->a)Clselect(A->P)=空。P64例4.6,4.76.递归下降分析法是确定的口上而下分析法，这种分析法耍求文法是LL(1)文法。基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。7.预测分析法与预测分析表的构造预测分析法也称LL(1)分析法，是确定的白上而下分析法的另一种方法，这种分析法要求文法是LL(1)文法。P69例4.108.自下而上分析法：都是按照“移进•归约”法的原理建立起来的一种语法分析方法。9.LR分析法是一种自下而上进行规范归约的语法分析方法。L：从左到右扫描输入字符串，R:构造最右推导的逆过程(最左归约)。这种分析方法是表格駅动的。示意图见P80P81例4.1410.LR(0)分析法：若对于一个文法G的拓广文法G'的LR(0)项目集规范族屮的每个项\n冃集，不存在移进项F1和归约项口同吋并存或多个归约项口同吋并存，则称G为LR(0)文法。P85例4.15ll.SLR（1）分析法：解决“移进•归约”冲突或“归约■归约”冲突P88例4.174.18P100小结可帮助搭建框架第五章语法制导翻译技术和中间代码生成1.语法制导翻译法用在语义分析和中间代码生成阶段2.常见的几种屮间代码的形式（如，逆波兰式、三元式和树形表示、四元式等）3.属性文法是用来说明程序设计语言的语义的工具描述方法很重要P107属性文法二语义规则，一个属性文法是在上下文无关文法的基础上，为每个文法规则都定义一组属性的计算规则。4.语法制导翻译法的基木思想是对文法中的每个产生式都附加上一个语义动作或语义了程序，在执行语法分析的过程屮，每当使川一条产生式进行推导或归约时，就执行相应产生式的语义动作，从而完成预定的翻译工作。5.逆波兰式Pill6.三元式和树形表示P1127.四元式和三地址代码P114第六章符号表的组织与管理1.符号表是编译程序中主要的数据结构z—,它主要用于存放程序语言中出现的冇关标识符的信息。2.符号表的每一项通常由两部分组成，第一部分是名字栏，另一部分是与名字有关的信息栏。3.符号表的作用：1）在诃法分析中，每识別到一个标识符，编译程序就耍查阅符号表，若符号表中没有该标识符的定义，就将标识符及其相关信息背录在符号表中。2）在语义分析时，符号表中的内容可以用于语义检查。3）代码优化时，编译程序将利川符号表提供的信息选出恰当的代码进行优化。4）目标代码生成时，符号表中内容是编译程序分配存储地址的依据。4.符号表的组织方式一般可以分为直接方式和间接方式。5.根据符号表名字栏的组织特点，符号表信息栏的组织方式也可以分为两类，固定信息内容和仅记载信息地址。第七章：代码优化（等价变换原则）1.提高代码质量的技术常称为代码优化。2.根据优化対象所涉及的程序范围，乂分为局部优化循环优化和全局优化。3.步骤：1删除公共了表达式2代码外提3强度削弱4变换循环控制条件（删除归纳变量）\n5合并已知量6复写传播7删除无用赋值——3删+外强合写1.局部优化定义为应川于代码的线性部分的优化，也就是代码屮没有转入或转出语句。它是基于基木块进行优化。2.划分基本块的方法：1从四元式序列确定满足以下条件的入口语句2确定满足以卜•条件的出口语句3构造基木块，删去那些不属于任何基木块的语句第八章运行时的存储组织与管理：静态存储分配策略+动态存储分配策略（栈式动态存储分配+栈式动态存储分配）1.运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。2.3种类型的存储环境：完全静态环境+基于栈的存储环境+基于堆的存储环境3.过程的活动记录是一段连续的存储区。4.静态存储分配1）条件：如果在编译时就能确定冃标程序运行中所盂要的全部数据空间的人小2）FORTRAN77釆用的是静态存储分配。3）在静态环境中所有的变量都是静态分配。4）定义：如果在编译时就能确定目标程序运行屮所需耍的全部数据空间的大小，则编译时就能安排好目标程序的全部数据空间，并能确定每个数据项的单元地址、存储空间，这种分配方式叫做静态分配。5.栈式存储分配1）条件：在允许递归调用且每次调用都耍重新分配局部变量的语言中，编译程序不能静态分配活动记录2）慕本思想：将整个存储空间设计成一个栈，每当调用一个过程时就将它的活动记录压入栈，在栈顶形成过程工作吋的数据区，当过程结束吋再将其活动记录弹出栈。6.堆式存储分配1）条件：如果一种程序语言允许数据对象能够白由的分配和释放，那么由于空间的使用不一定按照“先申请后释放”的原则，这时栈式存储分配就不适用了2）基木思想：一个程序开始执行时冇很大一块存储空间，运行期间如果需要就从里面申请一块存储空间，使用完毕归还。