黑大编译原理考试复习

黑大编译原理考试复习 本资源摘要信息是关于黑大编译原理考试复习的相关知识点总结，涵盖了编译原理的基础概念、词法分析、语法分析、文法、有限自动机、正规式、状态转换图等方面的知识点。 一、编译原理基础概念 * 一个典型的编译程序，它一般包括八个方面的内容：词法分析程序、语法分析程序、语义分析程序、中间代码生成、代码优化程序、目标代码生成、错误检查处理、信息表管理。 * 编译执行和解释执行的区别在于：是否产生目标代码。 二、词法分析 * 词法分析的任务就在于依次扫描输入串中的各个字符并从其中识别出一系具有独立意义的单词，我们通常把构成各个单词的字符串称为该单词的词文。 * 一般来说各类单词的语法都能用相应的正规（3 型）文法来描述。 * 通常构造词法分析程序的两种途径是：手工方式编程、借助工具自动生成。 三、语法分析 * 一个文法通常可表示成一个四元式 G[S] = (VN, VT, P, S)。 * 一个递归文法所产生的句子，其个数必然是无穷个。 * 设 G[S]为一文法，由文法的开始符号 S 推导出的符号串称为 G 的句型。 * 一个句型的最左直接短语（即规范分析中，最先被规约的子串）称为该句型的句柄。 四、文法和语言 * Chomsky 定义了四类基本的文法，分别称之为：0 型方法（短语结构）、1 型方法（前后文有关）、2 型方法（前后文无关）、3 型方法（正规）。 * 正规文法、正规式，在描述语言的意义下是等价的。 * 状态转换图、状态矩阵、有限自动机，在识别语言的意义下是等价的。 五、有限自动机 * 我们通常把一个有限自动机表示为 M = (K, ∑, ∮, S0, Z)。 * 引入具有 ε 动作的 NFA 主要目的是把识别各类单词的有限自动机用 ε 失线连接起来，组成一个单一的 NFA，然后把所得的 NFA 确定化后再据此设计编译程序的词法分析器。 六、状态转换图 * 状态转换图中初态结点没有射入矢线，终态结点没有射出矢线。 * 状态转换图是用于描述有限自动机的状态转换关系的图形表示。 七、编译原理应用 * 编译原理在计算机科学和软件工程中的应用非常广泛，例如编译器、解释器、语法检查器、代码优化器等。 * 编译原理也广泛应用于自然语言处理、模式识别、人工智能等领域。 八、考试题 * 文法和语言之间是一一对应关系吗？（ × ） * 设 G1 和 G2 为两个文法，若它们所产生的语言相等，即 L(G1) = L(G2)，则称 G1 和 G2 等价。（ √ ） * 每棵语法树的叶从左到右排列组成一个句型。（ √ ） * ...