编译原理知识点回顾 林奕 西北工业大学 2011年6月7日 西北工业大学林奕 1
西北工业大学 林奕 1 编译原理知识点回顾 林奕 西北工业大学 2011年6月7日
要点概述 ▣要点分类： ■基本概念 ■ 编译器结构和组织知识点 ·算法、模型和机制 执行过程的理解 ■ 结果表示 西北工业大学林奕
西北工业大学 林奕 2 要点概述 要点分类： ◼ 基本概念 ◼ 编译器结构和组织知识点 ◼ 算法、模型和机制 ◼ 执行过程的理解 ◼ 结果表示
要点概述（续1） ▣重要定义和基本概念的辨析和掌握 ■基本定义、概念 ■算法相关的基本定义和概念 ▣着重掌握各种算法、模型和机制 西北工业大学林奕 3
西北工业大学 林奕 3 要点概述（续1） 重要定义和基本概念的辨析和掌握 ◼ 基本定义、概念 ◼ 算法相关的基本定义和概念 着重掌握各种算法、模型和机制
第1章绪论 口低级语言、高级语言等的概念 ▣语言的处理方式：编译，解释 ▣编译器组织结构 ■以此为线索，理清各章算法和数据结构 西北工业大学林奕
西北工业大学 林奕 4 第1章 绪论 低级语言、高级语言等的概念 语言的处理方式：编译，解释 编译器组织结构 ◼ 以此为线索，理清各章算法和数据结构
掌握阶段划分和各阶段主要完成的任务 信息表管理程序 源程序 词法分析程序 语法分析程序 语义分析 中间代码生成 代码优化 目标代码生成 目标代码 10 0 错误检查和处理程序 西北工业大学林奕
西北工业大学 林奕 5 掌握阶段划分和各阶段主要完成的任务 词 法 分 析 程 序 语 法 分 析 程 序 语 义 分 析 程 序 中 间 代 码 生 成 代 码 优 化 程 序 目 标 代 码 生 成 信息表管理程序 错误检查和处理程序 源 程 序 目 标 代 码
第2章要点概述 ▣第2章的概念、算法和模型 ■ 基本概念：文法、语言、二义性及判定、语言 等价条件、推导、归约、规范推导与归约、短 语、直接短语、句柄等 ■给定语言、文法的相互转化 ■推导归约的机制 ■文法化简算法 语言、文法的分类模型及其包含关系 西北工业大学林奕 6
西北工业大学 林奕 6 第2章要点概述 第2章的概念、算法和模型 ◼ 基本概念：文法、语言、二义性及判定、语言 等价条件、推导、归约、规范推导与归约、短 语、直接短语、句柄等 ◼ 给定语言、文法的相互转化 ◼ 推导/归约的机制 ◼ 文法化简算法 ◼ 语言、文法的分类模型及其包含关系
第2章要点概述：文法分类 ▣文法分类 ■每类的定义，对应的语言，自动机 ■后 文法和语法、词法分析的关系： 口3型文法：正规文法→词法表示 ▣2型文法：前后文无关文法→语法表示 ■其他 口递归文法和无限语言 ■后面章节有递归的消除算法 西北工业大学林奕 7
西北工业大学 林奕 7 第2章要点概述：文法分类 文法分类 ◼ 每类的定义，对应的语言，自动机 ◼ 文法和语法、词法分析的关系： 3型文法：正规文法➔词法表示 2型文法：前后文无关文法➔语法表示 ◼ 其他 递归文法和无限语言 ◼ 后面章节有递归的消除算法
第2章要点概述：推导、归约 口推导和归约（规范推导和规范归约） ■最左推导 ■最左归约和最右推导 口语法树 ■给定句子/句型：能够通过最左推导/最右推导/最左归约 绘制语法树 口二义性和语法树、推导、归约的关系 ■语法树不唯 ■存在至少两个不同的最左推导/归约序列殊途同归 二义性的充分条件：文法既存在左递归，又存在右递归 西北工业大学林奕
西北工业大学 林奕 8 第2章要点概述：推导、归约 推导和归约（规范推导和规范归约） ◼ 最左推导 ◼ 最左归约和最右推导 语法树 ◼ 给定句子/句型：能够通过最左推导/最右推导/最左归约 绘制语法树 二义性和语法树、推导、归约的关系 ◼ 语法树不唯一 ◼ 存在至少两个不同的最左推导/归约序列殊途同归 ◼ 二义性的充分条件：文法既存在左递归，又存在右递归
第2章要点概述：推导、归约（续） ▣短语和句柄(2.3.3节) ■ 短语：通过语法树找短语较为方便。 ■ 直接短语： ■ 句柄：最左直接短语。最右推导每步被推导的 部分即可看出句柄。 西北工业大学林奕
西北工业大学 林奕 9 第2章要点概述：推导、归约（续） 短语和句柄（2.3.3节） ◼ 短语：通过语法树找短语较为方便。 ◼ 直接短语： ◼ 句柄：最左直接短语。最右推导每步被推导的 部分即可看出句柄
第2章要点概述：文法化简 口文法的化简和改造的算法必须掌握 口思路： ■先看有无ε产生式：若有则删除，若无则做其他化简。 (1)消除无用符号和无用产生式（有始有终） ■A→A的无效产生式必须删除。 ■ 算法2.1（有终）：从直接得到终结符的产生式开始，逆向推 理。剔除得不到终结符的产生式和符号。 算法2.2（有始）：对算法2.1的结果，从开始符S正向推理。 提出不能从S推出的符号和产生式。 ■算法执行顺序：算法2.1→算法2.2，并删除A→A (2)-产生式的消除 ■两类，语言含ε和语言不含ε ■ 算法2.4是ε产生式展开的算法；算法2.5处理 西北工业大学林奕 10
西北工业大学 林奕 10 第2章要点概述：文法化简 文法的化简和改造的算法必须掌握 思路： ◼ 先看有无-产生式：若有则删除，若无则做其他化简。 （1）消除无用符号和无用产生式（有始有终） ◼ A→A的无效产生式必须删除。 ◼ 算法2.1（有终）：从直接得到终结符的产生式开始，逆向推 理。剔除得不到终结符的产生式和符号。 ◼ 算法2.2（有始）：对算法2.1的结果，从开始符S正向推理。 提出不能从S推出的符号和产生式。 ◼ 算法执行顺序：算法2.1→算法2.2，并删除A→A （2）-产生式的消除 ◼ 两类，语言含和语言不含 ◼ 算法2.4是 产生式展开的算法；算法2.5处理
