南信大编译原理考题.docx

注：加粗表示可能考简答题简答题(每小题 5 分，共 20 分) 论述题(每小题 10 分，共 20 分) 计算(每小题 12 分 ，共 60 分)1、编译程序的构成：源程序词法分析语法分析语义分析和优化目标代码生成第二章 文法与语言1、一些概念性的东西（1）推导：句型句子，自顶向下。（2）归约：句子句型，自底向上。（2）句型：一个文法经过N（N=1）步推导后得到的结果（含有非终结符号）（3）句子：一个文法经过N（N=1）步推导后得到的结果（仅含有终结符号）（4）句柄：一个句型的最左简单短语。（树的最下面）（5）VN：文法的非终结符号集合（6）VT：文法的终结符号集合（7）P：文法的规则的集合（8）S：文法的识别符号或开始符号（9）短语：由树的各个树叶节点组成的符号组，有相对于XX的区别。（10）简单短语：也叫直接短语，有非终结符一步退出的短语。2、Chomsky文法分类0型文法：短语结构文法 图灵机（TM，Turing Machine）1型文法（CSG）：上下文有关文法 线性界限自动机（LBA，Linear bounded automata）2型文法（CFG）：上下文无关文法 下推自动机（PDA，Push Down automata）3型文法（RG）：正则文法 有穷状态自动机（FA，Finite automata）文法的判断：3型文法：左边必须只有一个字符，且必须是非终结符； 其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。 对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。2型文法：左边必须有且仅有一个非终结符。 2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。1型文法：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。 与2型文法第二点相同。3、文法压缩，消除左递归4、已知文法，证明某符号串是该文法的句子5、文法压缩：P506、消除文法左递归：P537、文法四要素：VN（非终结符），VT（终结符），P（重写规则），Z（识别符号）第三章 词法分析1、词法分析的任务（1）读入源程序，（2）识别开单词（符号）并转换为内部表示,（3）做力所能及的工作（删除无效字符、预处理）。2、正则表达式。3、对简单的正则表达式，能画出状态转换图（自动机）4、NFA确定化为DFA（难） ，二者的异同。5、正则表达式引进的必要性易理解正被定义的是什么符号集合。更容易构造高效识别程序有利于自动地构造识别程序可用于其他各种信息流的处理6、文法压缩的基本思想若一个符号不能出现在文法的任何句型中，则该符号是无用的若一个非终结符号不能推导出终结符号串，该非终结符号是无用的第四章 语法分析自顶向下分析技术1、递归下降分析技术是无回溯的自顶向下分析技术。2、递归下降分析器是一个不带回溯的自顶向下分析程序，该程序是由一组递归函数或过程组成的。其函数名应该是终结符，函数体是根据重写规则右部符号串的结构编写。3、求First，Follow集合。第一步，压缩文法，消除左递归，消除回溯。第二步，求First集合第三步，求Follow集合4、递归下降分析程序构造的基本思想：每个函数名应该是非终结符号当遇到终结符时，读入下一个符号当遇到非终结符号时，调用该终结符的相应函数当遇到空时，返回第五章 语法分析自底向上分析技术1、移进-归约技术2、算符优先分析基本思想，优先函数的构造3、求文法的LR(0)项集规范族，绘制对应自动机4、题型可见以前布置的练习题5、算符文法：没有连续2个非终结符同时出现的情况，即两个非终结符中间必然有一个或几个终结符（算符）。6、质短语：句型中至少包含一个终结符号，且除它自身外不再包含其他质短语的短语。7、求算符优先矩阵（P151-153）：等于号（=）：形如Z：=aXb，则a=b小于号（）：第一步，求各个非终结符的LastTeam集合（非终结符推导出的最后一个终结符，可能为空）；第二步，若有X：=xxxY的情况，则将Y的LastTeam放入X的LastTeam里；第三步：根据文法，若存在X：=A+B，则A的LastTeam的每一个元素都大于+。8、LR(k)基本思想：向前看k个符号，能一点都不回溯地识别给定的符号串。SLR(k)的实现思想：可不向前看就不看，否则至多看k个符号。9、算符优先函数的基本思想：以数值的比较代替算符优先关系的比较10、移入归约的基本思想：使符号从左到右逐个进栈，每当栈顶形成一个“可归约子串”，就把该子串归约成一个非终结符号，即把该子串从栈顶弹出，再把归约成的子串入栈，如此反复进行。第六章 语义分析与中间代码的生成1、属性文法的概念属性文法是扩充的压缩了的上下文无关文法，往往以语法制导定义或翻译方案的形式出现语义规则：同一条产生式规则中符号的属性之间的计算法则综合属性：由语法分析树的子结点计算而得，是自下而上传递的。继承属性：由语法分析树的父结点和兄弟结点计算而得，是自上而下传递的。2、赋值语句和If语句逆波兰式的翻译逆波兰式又称后缀表示法，其特点是无括号。例一：a+b*c/(d+e) 逆波兰表示为：abc*de+/+例二：t=(a+b)*c/(d-e)逆波兰式为：tab+c*de-/=例三：if (ab)max=b;else max=a;逆波兰表示为：ab 11 GOF max b = 14 GO max a =ab11GOFmaxb=14GOmaxa=12345678910111213143、赋值语句翻译成四元式形式: ( op , arg1 , arg2 , result )。 其中：op是运算符， arg1和arg2是操作对象， result存放最终结果。若op是单目运算符，则arg2可以省略。例：赋值语句:x=12+a*(b-10)/c; 写出其四元式序列。从100号单元开始存放四元式。OPArg1Arg2Result100-b10T1101*aT1T2102/T2cT3103+12T3T4104:=T4x第八章 代码优化1、基本块划分和构造流图基本块：从第一个四元式进入, 从最后一个四元式离开, 其间没有停止也无分支的连续的四元式序列。流图是一种有向图，它由把控制流信息加到基本块集合而形成。流图中的结点是基本块，流图中的有向边指明了控制流向。2、DAG图画法3、基本块优化（种类） 合并常量计算 消除公共子表达式 削减计算强度 删除无用代码基本块的定义：程序的第一