复习提纲
第一部分 绪论
第二部分 前后文无关文法和语言
第三部分 词法分析
第四部分 语法分析
第五部分 语法制导翻译和中间代码生成
第六部分 符号表
第七部分 存储组织与分配
第八部分 目标代码生成
第一部分 绪论
? 了解什么是编译程序和解释程序
? 掌握编译程序的逻辑结构以及各部分的主要
功能
? 理解编译程序的组织：多边扫描和单边扫描
第二部分 前后文无关文法和语言
? 能写出符号串的前缀、后缀、子串；会计算
符号串的连接、方幂；会计算符号表和符号
串集合的和、积,方幂与闭包。
? 理解文法、句型、句子、语言、递归文法的
概念
? 知道文法与语言的对应关系
? 掌握符号串的推导和归约过程（包括规范推
导、规范归约）
? 会构造给定句型的语法树
? 能根据语法树确定短语、直接短语和句柄
? 文法的化简与改造：无用符号和无用产生式
的删除,?-产生式的消除、单产生式的消除
? 能根据文法和语言的 Chomsky分类，确定给定
文法属于那种类型（ 0型,1型,2型,3型），
其语言用什么机制来识别。
第三部分 词法分析
? 理解词法分析的主要任务
? 正规文法 ? 状态转换图 ? 状态转换矩阵
会描述状态转换图识别的语言
? 正规文法 ? DFA和 NFA； NFA（可能具有 ?动
作）的确定化； DFA状态数的最小化
? 正规文法 ? 正规式 ? FA
第四部分 语法分析
? 掌握自顶向下语法分析 的基本过程
? 会消除文法的左递归，能改写非 LL(1)文法
? 会构造 FIRST集和 FOLLOW集，并在此基础上构造
预测分析表,会用 预测分析表进行语法分析
自底向上语法分析
? 掌握自底向上语法分析的基本过程
? 掌握简单优先关系和算符优先关系矩阵的基本步
骤
? 根据给定的简单优先关系和算符优先关系矩阵，
能进行相应的语法分析
? 能通过语法树找出句型的最左素短语
? 会构造优先关系矩阵的优先函数,有向图法、
Floyd方法
LR分析法
? 根据给出的 LR分析表，能写出 LR分析过程
? 写出所有的 LR(0)项目集，构造识别全部活
前缀的 DFA，并在此基础上构造 LR（ 0）分析
表和 SLR(1)分析表（求 Follow集）
? 写出所有的 LR(1)项目集，构造识别全部活
前缀的 DFA，并在此基础上构造 LR（ 1）分析
表和 LALR(1)分析表（合并同心集）
第五部分 语法制导翻译和中间代码
生成
? 理解语法制导翻译的基本思想
? 会写出语句的逆波兰表示、三元式、四元式和
树形结构
? 能将算术表达式、赋值语句、布尔表达式（拉
链与回填）,FOR（ While）循环语句、语句标
号及 GOTO语句、情况（ CASE）语句等翻译成中
间代码（四元式）
第六部分 符号表
? 理解分程序结构语言 符号表的组织结构和生成过程
? 理解非 分程序结构语言 符号表的组织结构
第七部分 运行时的存储组织与分配
? 了解活动记录的组成和各部分的含义
? 理解运行时的两种分配策略：静态和动态
? 掌握数据区的静态优化分配方案
第八部分 目标代码生成
? 能对给定程序划分出基本块
? 掌握常用指令以及常用四元式的目标代码
? 会生成引用信息与活跃信息链
? 会对 DAG中结点进行重构
? 会用全局寄存器分配策略
第一部分 绪论
第二部分 前后文无关文法和语言
第三部分 词法分析
第四部分 语法分析
第五部分 语法制导翻译和中间代码生成
第六部分 符号表
第七部分 存储组织与分配
第八部分 目标代码生成
第一部分 绪论
? 了解什么是编译程序和解释程序
? 掌握编译程序的逻辑结构以及各部分的主要
功能
? 理解编译程序的组织：多边扫描和单边扫描
第二部分 前后文无关文法和语言
? 能写出符号串的前缀、后缀、子串；会计算
符号串的连接、方幂；会计算符号表和符号
串集合的和、积,方幂与闭包。
? 理解文法、句型、句子、语言、递归文法的
概念
? 知道文法与语言的对应关系
? 掌握符号串的推导和归约过程（包括规范推
导、规范归约）
? 会构造给定句型的语法树
? 能根据语法树确定短语、直接短语和句柄
? 文法的化简与改造：无用符号和无用产生式
的删除,?-产生式的消除、单产生式的消除
? 能根据文法和语言的 Chomsky分类，确定给定
文法属于那种类型（ 0型,1型,2型,3型），
其语言用什么机制来识别。
第三部分 词法分析
? 理解词法分析的主要任务
? 正规文法 ? 状态转换图 ? 状态转换矩阵
会描述状态转换图识别的语言
? 正规文法 ? DFA和 NFA； NFA（可能具有 ?动
作）的确定化； DFA状态数的最小化
? 正规文法 ? 正规式 ? FA
第四部分 语法分析
? 掌握自顶向下语法分析 的基本过程
? 会消除文法的左递归，能改写非 LL(1)文法
? 会构造 FIRST集和 FOLLOW集，并在此基础上构造
预测分析表,会用 预测分析表进行语法分析
自底向上语法分析
? 掌握自底向上语法分析的基本过程
? 掌握简单优先关系和算符优先关系矩阵的基本步
骤
? 根据给定的简单优先关系和算符优先关系矩阵，
能进行相应的语法分析
? 能通过语法树找出句型的最左素短语
? 会构造优先关系矩阵的优先函数,有向图法、
Floyd方法
LR分析法
? 根据给出的 LR分析表，能写出 LR分析过程
? 写出所有的 LR(0)项目集，构造识别全部活
前缀的 DFA，并在此基础上构造 LR（ 0）分析
表和 SLR(1)分析表（求 Follow集）
? 写出所有的 LR(1)项目集，构造识别全部活
前缀的 DFA，并在此基础上构造 LR（ 1）分析
表和 LALR(1)分析表（合并同心集）
第五部分 语法制导翻译和中间代码
生成
? 理解语法制导翻译的基本思想
? 会写出语句的逆波兰表示、三元式、四元式和
树形结构
? 能将算术表达式、赋值语句、布尔表达式（拉
链与回填）,FOR（ While）循环语句、语句标
号及 GOTO语句、情况（ CASE）语句等翻译成中
间代码（四元式）
第六部分 符号表
? 理解分程序结构语言 符号表的组织结构和生成过程
? 理解非 分程序结构语言 符号表的组织结构
第七部分 运行时的存储组织与分配
? 了解活动记录的组成和各部分的含义
? 理解运行时的两种分配策略：静态和动态
? 掌握数据区的静态优化分配方案
第八部分 目标代码生成
? 能对给定程序划分出基本块
? 掌握常用指令以及常用四元式的目标代码
? 会生成引用信息与活跃信息链
? 会对 DAG中结点进行重构
? 会用全局寄存器分配策略
