四川大学编译原理期末复习总结

编译原理复习资料1一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）–其中Vn表示非终结符号–Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ–S是开始符号，–P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。4.局部优化有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6.什么是文法？答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。7.语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：编译原理复习资料2逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号—滤掉空格，跳过注释、换行符—追踪换行标志，指出源程序出错的行列位置—宏展开，……10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。11.什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。12.什么是基本块?答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句。13.代码优化阶段的功能是什么？答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。14.文法分哪几类？答：文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：０型文法(短文文法)：G的每个产生式αβ满足：α∈V+且α中至少含有一个非终结符,β∈V*１型文法(上下文有关文法)：如果G的每个产生式αβ均满足|β|=|α|,仅当Ｓε除外，但S不得出现在任何产生式的右部２型文法(上下文无关文法)：G的每个产生式为Aβ,A是一非终结符，β∈V*３型文法(正规文法)：G的每个产生式的形式都是：AαB或Aα，其中A,B是非终结符，α是终结符串。(右线性文法)。15.循环优化常用的技术有哪些？答：代码外提；强度削弱；删除归纳变量。16.什么是算符优先文法？答：算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有中的一种成立,则G为一算符优先文法。二、计算题（一）推导、最左推导、最右推导和语法树,复习表达式文法及相关例题。1.表达式的推导例：G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i答：表达式(i)和(i+i)*i的推导：E(E)(i)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*iEE*EE*i(E)*i(E+E)*i(E+i)*i(i+i)*i编译原理复习资料3(i+i)*i的最左推导过程：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i(i+i)*i的最右推导过程：EE*EE*i(E+E)*i(E+i)*i(i+i)*i2．语法树例：对文法G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i答：句子(i+i)*i的语法树：例：G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i答：句子(i*i+i)的语法树：(1)E(E)(E+E)(E*E+E)(i*E+E)(i*i+i)编译原理复习资料4（二）给定语言求文法编译原理复习资料5（三）逆波兰式编译原理复习资料6（四）将for语句和if语句翻译成相应的四元式序列1.if编译原理复习资料72.for(五)短语、素短语、最左素短语，FirstVT集和LastVT集的求解方法(复习第四章算符优先文法相关内容)1.短语、素短语、最左素短语编译原理复习资料82.FirstVT集和LastVT集的求解方法编译原理复习资料9例：设文法为：E'→#E#；T→F；E→E+T；F→P↑F|P；E→T；P→(E)；T→T*F；P→i；3.算符优先文法优先关系的定义:编译原理复习资料10算符优先文法的定义:编译原理复习资料11三、综合题1.NFA的确定化和最小化(参看课件第三章62页：例5)编译原理复习资料12编译原理复习资料132.自顶向下分析(参看课件第四章（1）67页：综合练习)例：求对应于下述文法的预测分析表:ETE'E'+TE'|εTFT'T'*FT'|εF(E)|i答：1）首先求first集:2）由于εFirst(E'),εFirst(T'),求E'和T'的Follow集:3）根据集合的值填表，得到:例:设文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的First和Follow集；(3)构造预测分析表。答：(1)消除左递归和回溯：(2)(3)构造预测分析表：编译原理复习资料143.LR分析方法(参看课件第四章（3）28页及30页)编译原理复习资料15(附)1.短语、直接短语、句柄例：考虑如下文法：E=T|E+TT=F|T*FF=i|(E)求句型i1*i2+i3的短语、直接短语和句柄答：E=F*i2+i3E=i1*F+i3E=i1*i2+FE=T+i3（T=T*F=i1*i2）F=iE=i1*i2+i3因此：短语有：i1,i2,i3,i1*i2,i1*i2+i3直接短语有：i1,i2,i3句柄是：i1i2+i3不是短语，因为E=i1*E（E=i2+i3）2.什么是语法制导翻译语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。语法制导翻译(Syntax-DirectedTranslations)：–一个句子的语义翻译过程与语法分析过程同时进行。在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。编译原理复习资料16翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段：1、词法分析任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。2、语法分析任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法单位。3、语义分析和中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义并进行初步翻译。4、优化任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。5、目标代码生成任务：把中间代码变换成特定机器上的低级语言代码。编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。词法规则：指单词符号的形成规则。（也就是正规式）语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。空字：不包含任何符号的序列。闭包：中所有的符号组成的集合。上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。上下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。终结符号也就是不可再分的基本符号。非终结符号是用来代表语法范畴，表示一定符号串的集合。开始符号是语言中我们最感兴趣的语法范畴。产生式是定义语法范畴的书写规则。句子：文法中从开始符号推导的终结符号串。句型：从开始符号推导的符号串语言：文法中所有句子的集合。程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。二元式表示：（种类，属性）正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。DFA怎么识别字：若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为DFA所识别。DFA怎么识别空字：若DFA的初态结点同时又是终态结点，则空字可为DFA所识别。NFA怎么识别字：若存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为NFA识别。NFA怎么识别空字：若M的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为M所识别。语言的语法结构是用上下文无关文法描述的。语法分析分为两类：自上而下分析法，自下而上分析法。自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错的确切位置。5.效率低，代价高为什么消除左递归？因为含有左递归的文法将自上而下分析的过程陷入无限循环。为什么消除回溯？因为回溯统一做一大堆无效的工作。自下而上分析法：从输入串开始，逐步进行归约，知道归约到文法的开始符号。短语：符号串推导过程中某非终结符推导的部分。编译原理复习资料17直接短语：符号串推导过程中某非终结符一步推导的部分。句柄：一个句型的最左直接短语。最左归约是最有推导的逆过程。中间语言形式：后缀式，三元式，四元式，间接三元式。中间语言的好处：1.便于进行与机器无关的代码优化工作。2.使编译程序改变目标机更容易。3.使编译程序的结构在逻辑上更为简单，以中间语言为界面，编译前端和后端的借口更清晰