编译原理 简答题
简答题
1. 什么是上、下文无关文法？它是由几部分组成的？
答：上、下文无关文法所定义的语法范畴，是完全独立于这种范畴可能出现的环境的。它由四部分组成：一组终结符号，一组非终结符号，一个开始符号和一组产生式。
2. 简述正规式和有限自动机的关系。
答： 上的非确定有限自动机M 所能识别字的全体L （M ）是 上的一个正规集。对于 上的每个正规集V ，存在一个 上的确定有限自动机M ，使得V=L（M ）。
3. 简述NFA 和DFA 的区别。
答：①DFA 初态是唯一的，NFA 可以有多个初态。
②DNF 是单值函数，NFA 是多值函数。
③DFA 每个弧线用 中一个不同输入字符做标记，而NFA 每条弧用 中的一个字做标记。
4. 何为递归下降分析法。
答：在不含左递归和每个非终结符的所有的首符集都两两不想交的条件下。我们就可以构造一个不带回溯的的自上而下的分析程序。该程序是由一组递归过程组成的。每个过程对应文法的一个非终结符。这种语法分析的方法称为文法递归下降分析法。
5. 什么叫做递归下降分析器？
答：当一个文法满足 LL（1）条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符，这样的一个分析程序称为递归下降分析器。
6．语法分析方法如何分类，它们面对的主要问题是什么？
答：语法分析方法分为自下而上的分析法和自上而下的分析法。自上而下分析法的主要问题是：消除文法的左递归以及由文法开始符号出发推导句子的过程中如何避免回溯。自下而上 分析法的主要问题是：在由输入串出发向文法的开始符号规约的过程中。如何确定可规约子串。
7. 何为中间语言，简述它的作用。
答：中间语言是一种面向语法。其复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间。是一种易于翻译成目标代码的代码形式。它的作用在于利用它作为中间环节。不仅可以较快的实现源程序的翻译过程而且可以在此基础上应用优化方法将源程序翻译成运行时间短，占用内存少的目标程序。
8. 优化的原则，优化的分类，优化有哪些具体方法。
答：①优化的原则：等价原则、有效原则、合算原则。
②优化分为：局部优化、循环优化、全局优化。
③具体方法有：删除公共子表示式，复写传播，删除无用代码，代码外提，强度削弱，删除归纳变量。
9. 什么是LL （1）文法？
答：①文法不含左递归 ②对于文法中每一个非终结符A 的各个产生式的候选首符集两两不相交 ③对文法中的每个非终结符A, 若它存在某个候选首符集包含 。