软考软件设计师专题讲义：程序语言部分

　　2.4代码优化

　　优化是对程序进行等价(指不改变程序的运行结果)变换，经变换后的程序能生成更有效(运行时间更短、占用空间更小)的目标代码。

　　根据优化所涉及的程序范围，可分为局部优化、循环优化和全局优化三个不同的级别

　　编译原理重点难点归纳：

　　了解编译程序工作的大致过程，要清楚编译程序是如何生成的。请大家记忆并理解以下概念：编译程序，解释程序，翻译程序，扫描器，分析器，编译前端与后端，符号表。

　　要掌握的几个重量级概念：上下文无关文法，语法分析树和二义性，同时也引出了与此紧密联系的其它概念：推导，句型，句子，最左推导，最右推导等。

　　最后给出了另一个常考点：乔姆斯基的方法分类。

　　1.上下文无关文法的定义，判断和转化，以及与上下文无关文法密切相关的概念。

　　首先，应该掌握上下文无关文法的四个构成要素;

　　其次，应该清楚对于上下文无关文法，其每个产生式的左部和右部必须满足的条件。

　　在有关上下文无关文法的考点中，有这样几种考查方式：

　　n 给出某语言的自然语言描述方式，要求写该语言的上下文无关文法表述形式;

　　n 给出某语言的上下文无关文法，要求用自然语言描述该语言;

　　n 给出某语言的上下文无法方法，要求证明该文法是否二义;

　　n 给出某语言的上下文无关文法，要求给出指定句子的最左或最右推导;

　　n 给出某语言的上下文无关文法，要求给出指定句子的语法分析树;

　　n 给出一个具有二义性的上下文无关文法，要求将其转换成非二义性的。

　　2.乔姆斯基的文法分类：

　　首先，应该非常清楚乔姆斯基对于四种文法分类的定义，并能理解其含义。几种文法中，最基本的是0型文法，读者可以将它理解为其它所有文法的基础，它是可以表示任何语言的文法。后面的1，2,3三种文法，是分别对于0型文法产生式的两边作了不同的限制之后，形成了新的文法。比如：规定0型文法的每个产生式中，其左边字符集长度小于右边字符集长度并且同时规定开始符号只可出现于产生式的左边，不能出现在任何产生式的右边，这样，就成为了1型文法(即上下文有关文法)。其它与此类似，在1型文法的基础上，进一步规定该文法的任意产生式，其左部只允许有一个字符且必须为非终结符，这样就构成了上下文无关文法;再在上下文无关文法的基础上进行限制：规定除了左部有且只有一个非终结符外，还特别规定右部最多只允许有两个字符，当为两上字符时必须一个为非终结符，另一个为终结符，而当只有一个字符时，必须为终结符，这样的文法就成了正规文法。这样一层套一层的限制，就形成了从0型到3型文法的定义体制，每一层都是在前一层基础上进行定义的，所以说前一层一定比该层表示的范围要广，因为其受的限制要少。

　　那么，我们在判断一个文法时应该以什么规则来判断呢?这个规则当然是：3->2->1->0.也就是说，我们判断是从高到低来判断的，比如：一旦判断其属于正规文法之后就没必要再判断其是否属于上下文无关的了(因为它必定属于上下文无关，我们应该以最高规则来判定其属于的文法类型)，其它情况与此类推。只有当我们判断不属于3型文法时，我们才向下判断，其是不是属于2型的，若不属于2型的，则依此类推再向下判断。最终的结果如果不属于3，2和1三种类型，那就只有属于0型了。

　　“给定一个文法，要求判断其属于何种文法”是一个重要考点，其出题形式可能是填空，选择等多种题型。

　　正规式和有限自动机，对于词法分析一章的考点，可以说80%到90%以上集中在这一节的内容上。针对于这一节的知识点介绍和考点分析：

　　1) 词法分析器的功能：输入的是源程序，输出的是分析完成的单词符号;

　　2) 状态转换图：是一张有向图，用于标识在特定的输入下词法分析器应该选择的分析方向。

　　对于考点1)，作为选择进行考查，而对于考点2)，多数是与有限自动机一些考查，要求给出以“状态图”表示的确定有限自动机，或者是要求直接给出针对于某正规式的状态转换图，大家记住一句话：状态转换图，就是一张当输入不同的内容时，选择不同分析路径的有向图。

　　下面，我们重点看一下有关“正规式与有限自动机”这一考点的各种可能考查形式：

　　a.题目给定一正规式，要求给出其NFA，DFA或最简DFA形式。

　　b.题目给定一用状态图表示的NFA，要求给出其对应的DFA或最简DFA形式。

　　c.题目给定一NFA，DFA或最简DFA，要求给出其对应的正规式。

　　d.题目给定一正规集，要求给出其相应的DFA。

　　e.题目给定一用自然语言描述的正规集，要求给出其相应的正规式表示形式。

　　这些考点，综合起来看，是在正规式，正规集，NFA和DFA之间作各种可能的转换，当然这种转换正确与否的判断标准就是转换之后的内容是不是与转换之前的内容等价，如果等价，我们就认为转换是正确的。