因为复试专业课需要考编译原理，线上复试总结一些编译原理的相关题目~ （ps:只是一些面试的一些概念简答题，如果有笔试相关类型的题目要好好写）

Q1. 高级语言，汇编语言和机器语言的关系？编译器如何将他们联系起来? 翻译程序是指把用某种程序设计语言编写的程序（源程序）翻译成与之等价的另一种语言的程序（目标程序）。包括：编译程序，汇编程序和解释程序。 编译程序：能够将高级语言编写的源程序翻译成等价的机器语言/汇编语言的目标程序。 汇编程序：将汇编语言程序翻译成等价的机器语言程序（可直接在计算机上执行）。 解释程序：翻译一句执行一句，不生成目标文件，直接执行源代码文件。

Q2.简述编译程序结构，并说明每个部分的作用。 (1)词法分析：根据词法规则，对构成输入源程序的字符扫描分解，识别出一个个单词符号。 (2)语法分析：在词法分析的基础上，根据语言语法规则，把单词符号分解成各类语法单位。 (3)语义处理和中间代码生成：根据语言的语义规则来生成中间代码。 (4)代码优化：对程序和中间代码进行等价变换，从变换后的程序出发，能生成更有效的目标代码。 (5)目标代码生成：把中间代码变换成特定机器上的低级语言代码。

Q3.什么是推导，什么是规约？并简述规范推导和规范归约。 推导：把句型中的非终结符用产生式规则的右部来替代的过程。 归约：把句子中的某个子串（即句柄）用一个非终结符来替代的过程。 规范推导：也称最右推导，指对一个推导序列中的每一步直接推导α=>β，都是对阿尔法中的最左非终结符进行替换；规范推导的逆过程成为最左归约，也即规范归约。

Q4.什么是语法树，其优点是什么？ 语法树是一个句型推导的树形表示。 其优点是有助于理解一个句子语法结构的层次。

Q5.什么是文法二义性？怎样消除文法二义性？ 文法的二义性：如果一个文法存在某一个句子对应两颗不同的语法树，则称这个文法是二义的。 消除文法二义性的方法包括： （1）不改变文法，附加一些限制条件，生成确定的语法树 （2）改变文法，构造一个等价的新文法，把排除二义性规则合并到原文法中

Q6.怎样判断某个句子w是否合法？ （1）从文法的开始符号出发，逐步推导，看能否产生w。若能，则w是合法的句子； （2）从句子w出发，逐步归约，看是否能够归约到文法的开始符号。若能，则w是合法的句子。

Q7.什么是DFA，什么是NFA？简述他们的区别和联系。 DFA(确定的有限自动机)：M是一个五元组，M = ( S，Σ ，δ，S0，F ) S：有穷状态集 Σ：输入字母表，即输入符号集合。 δ：将S×Σ映射到S的转换函数。 S0：开始状态 F：终止状态集 NFA：非确定有限自动机：M是一个五元组，M = ( S，Σ ，δ，S0，F ) （状态子集确定，状态不确定） S：有穷状态集 Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素 δ：将S×Σ映射到S的转换函数。 S0：开始状态集 F：终止状态集 DFA是NFA的特例，NFA是DFA的推广。NFA能识别的语言都能被DFA识别，DFA相应的识别程序更容易实现。

Q8.简述NFA确定化为DFA的基本思路 核心思想：状态子集法 基本思路：DFA的每个状态代表NFA状态集合的某个子集，构造的DFA使用它的状态去记录NFA读入输入符号之后可能到达的所有状态的集合。

Q9.简述DFA最简化的基本思路 DFA中的有些状态是等价的。如果从状态S出发，经过任意符号串，能够到达终止状态，对于同一个串t，状态W也能终止，则状态S和W等价。两个终止状态可以不同，只要终止就可以。 不等价：找出一个串t,S出发可以终止，W出发不能到达终止状态。 将这些等价的状态进行合并，就可以简化DFA。

Q10.说明正规式，正规集和正规文法的关系。以及如何判断两个正规式等价？ 正规式：是描述程序语言单词的表达式，是一种表示正规集的工具。 正规集：正规式描述的表达式的集合。 对于任意一个正规式，存在定义同一语言的正规文法；反之，对每个正规文法，同样存在一个生成同样语言的正规式。 两个正规式等价描述的两个正规集相同（正规式=>NFA=>DFA=>最简化）

Q11.简述自顶向下的语法分析的基本思想，以及面临主要的问题。 基本思想：从文发的开始符号出发，往下推导，试图推导出句子。 语法树角度：从树根出发，不断向下生长，直至所有叶子构成的串就是句子。 面临的两个问题： （1）回溯问题 （2）左递归问题

Q12.FIRST集和FOLLOW集分别表示什么？ FIRST集：从符号x可以推导出的所有首终结符或可能的ε。 FOLLOW集：句型中，紧紧跟在符号A后面的终结符号。

Q13.如何判断有无回溯？ 定义一个SELECT集合： SELECT(x)=FIRST(x)，若ε不属于FIRST(x) / (FIRST(x)-{ε})∪FOLLOW(A) 有A->X1|X2|…|Xn，若SELECT(Xi)∩SELECT(Xj)=Ø，则无回溯

Q14.简述LL(1)分析法的工作原理。 LL(1)分析技术结构组成包括：栈，输入，输出，总控程序（表驱动），LL(1)分析表 （1）若栈顶是非终结符号，查表。空白：报错。否则，栈顶弹出，倒序入栈； （2）若栈顶是终结符号，比较。和下个单词一样：栈顶弹出，读取下一个单词。否则，报错。 （3）若栈顶是#，下个单词#，成功。否则，失效报错。

Q15.简述自底向上的语法分析的基本思想，以及面临的主要问题。 基本思想：从句子出发，不断向上归约，试图归约到文法的开始符号。 语法树角度：从叶子开始，向上生长，一直到树根。 面临的两个问题： （1）如何寻找可规约子串？ （2）找出可规约字串后，用哪一条产生式规则进行规约？

Q16.介绍移进-归约法的基本思想。 基本思想：不断将下个单词移进栈，判断在栈顶是否已构成一个可规约子串。如果已经构成则立即归约；否则继续移进栈。

Q17.什么是素短语和最左素短语？ 素短语：是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语。 最左素短语：就是句型最左边的素短语，是算符优先分析法的归约对象。

Q18.简述算符优先分析法的工作原理。 算符优先分析法从运算符之间优先级的角度作为切入点，通过算符优先关系生成算符优先关系表，就可以在移进-归约过程中，在栈的内部寻找最左素短语，一旦找到就立即进行归约。 具体过程： （1）当栈顶运算符优先关系ab时，表示已经找到了最左素短语的尾部，然后在栈内由栈顶向栈底搜索第一个出现 X1 X2 X3 …Xn相应的语义规则是b=f(a1,a2,…,ak) (1)若b是A的属性：A.b称为A的综合属性； (2)若b是Xi的属性：Xi.b称为Xi的继承属性。 综合属性依赖于子结点和自己，在自底向上语法分析时能通过一边扫描全部计算出来； 继承属性由其父结点或兄弟结点的属性值来确定，主要用于表达上下文的依赖性。

Q26.什么是S-属性文法，什么是L-属性文法？ S-属性文法：文法中的所有属性均为综合属性，适合于自底向上的语法分析； L-属性文法： （1）S-属性文法是L-属性文法 （2）若A -> X1 X2… Xk…Xn，b是Xk的继承属性，则Xk.b由A的继承属性及左边兄弟的任何属性决定 适用于自顶向下的语法分析。

Q27.简述语法制导的语义翻译的基本思想。 给文法配上语义规则，当进行语法分析，每当发生归约，则自动调用该规则所配置的语义规则。在进行语法分析的同时，自动进行语义的处理，即语义处理的时机，调用何种语义规则都是由当时进行语法分析的归约时刻决定的。

Q28.什么是翻译方案？ 把语义规则转成语义动作，放在规则右部适当位置，成为文法的一个组成部分。

Q29.怎样指导将语义动作插入到合适的位置上？ （1）继承属性：计算继承属性的动作，应放在符号左边； （2）综合属性：计算综合属性的动作，应放在这样的位置，其他属性都已经算出，通常放在最右边 （3）语义动作：一个语义动作不能引用他后边的符号的属性，语义动作通常放在它所引用的属性此时已经全部算出。

Q30.生成中间代码有什么好处？ （1）可以进行与具体机器特性无关的能反映代码本身特性的代码优化； （2）当要将编译程序移植到新的目标机器时，前端（词法分析…）几乎不变，只需要修改后端。后端是针对具体目标机器的代码生成与优化。

Q31.简述“回填”技术的思想。 当生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令都具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号。

Q32.说明C语言运行时的空间分配策略。 对于C语言程序中的全局变量，static型局部变量，采用静态分配存储策略； 对于函数中非static型局部变量，采用栈式存储分配策略； 对于指针类变量所指的空间，可以通过堆式存储分配策略来管理，需要运行库的支持。 运行时内存空间划分为代码区，静态数据去，栈，堆。静态数据区在编译时就已知大小，相对固定；栈和堆大小可变。栈向下生长，堆向上生长。

Q33.什么是活动，什么是活动记录？C语言活动记录的结构是怎样的？ 函数的一次调用执行成为一个活动。 从函数的第一条指令开始执行到函数的最后一条指令为止，这个过程为函数的一次活动的生存周期。 管理函数的活动所需要的全部信息，称为函数的活动记录。

老BP：用于运行时访问局部变量，即实参。格式：[BP+data]。

Q34.什么是优化？优化原则有什么？ 优化：对程序和中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 原则： （1）等价原则：不能改变程序运行的结果； （2）有效原则：缩短目标程序运行的时间 / 压缩程序的存储空间 （3）合算原则：代价小

Q35.什么是基本块？怎样划分基本块？ 基本块：指程序中一组顺序执行的语句序列，其中只有一个入口和一个出口。入口就是其中的第一条语句，出口就是其最后一条语句。对于一个基本块来说，执行是只能从其入口进入，从其出口退出，期间不能停止也不可能有分支。 求入口语句： （1）四元式序列的第一条语句； （2）经条件转移或无条件转移能转到的语句； （3）紧跟在条件转移语句后面的语句 对于每个入口语句，其所属的基本块，是由该入口语句到下一入口语句（不包括该入口语句）或到下一转移语句（包括该转移语句）或停语句（包括该停语句）之间的语句序列组成的。

Q36.简述局部优化和循环优化的过程。 局部优化：（1）准备操作数的结点 （2）合并已知量 （3）删除公共子表达式 （4）删除无用赋值 循环优化：（1）代码外提 （2）强度削弱 （3）归纳变量删除

Q37. 简述利用DAG图进行基本块优化的基本思想。 基本思想：首先顺序地对一个基本块内所有四元式构造一个DAG，接着按构造节点的次序将DAG还原成四元式序列。构造DAG的同时已经进行了局部优化，因此按照构造DAG结点的顺序，对每一个结点写出相应的四元式就可以实现对基本块的优化处理。

Q38.目标代码生成主要应考虑哪几方面的因素？ 目标代码可以是某种能立即执行的机器语言代码，也可以是可重定位的机器语言模块，或者是某种类型机器上的汇编语言程序。 目标代码生成主要考虑的因素包括：生成的代码要短，执行效率高（充分利用机器中的寄存器，使用指令代价小的指令等）。

只有一些网络面试问答题，如果笔试的话一定要把相关题型做透。结束！后面三章好像有点草率了~