北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）复习提纲（田凤占）

复习提纲 第一部分绪论 第二部分前后文无关文法和语言 第三部分词法分析 第四部分语法分析 第五部分语法制导翻译和中间代码生成 第六部分符号表 第七部分存储组织与分配 第八部分目标代码生成

复习提纲 第一部分 绪论 第二部分 前后文无关文法和语言 第三部分 词法分析 第四部分 语法分析 第五部分 语法制导翻译和中间代码生成 第六部分 符号表 第七部分 存储组织与分配 第八部分 目标代码生成

第一部分绪论 了解什么是编译程序和解释程序 ■掌握编译程序的逻辑结构以及各部分的主要 功能 理解编译程序的组织:多边扫描和单边扫描

第一部分 绪论 ◼ 了解什么是编译程序和解释程序 ◼ 掌握编译程序的逻辑结构以及各部分的主要 功能 ◼ 理解编译程序的组织：多边扫描和单边扫描

第二部分前后文无关文法和语言 ■能写出符号串的前缀、后缀、子串;会计算 符号串的连接、方幂;会计算符号表和符号 串集合的和、积、方幂与闭包 ■理解文法、句型、句子、语言、递归文法的 概念 ■知道文法与语言的对应关系 ■掌握符号串的推导和归约过程(包括规范推 导、规范归约)

第二部分 前后文无关文法和语言 ◼ 能写出符号串的前缀、后缀、子串；会计算 符号串的连接、方幂；会计算符号表和符号 串集合的和、积、方幂与闭包。 ◼ 理解文法、句型、句子、语言、递归文法的 概念 ◼ 知道文法与语言的对应关系 ◼ 掌握符号串的推导和归约过程（包括规范推 导、规范归约）

■会构造给定句型的语法树 ■能根据语法树确定短语、直接短语和句柄 ■文法的化简与改造:无用符号和无用产生式 的删除、ε-产生式的消除、单产生式的消除 ■能根据文法和语言的 Chomsky分类,确定给定 文法属于那种类型(0型、1型、2型、3型), 其语言用什么机制来识别

◼ 会构造给定句型的语法树 ◼ 能根据语法树确定短语、直接短语和句柄 ◼ 文法的化简与改造：无用符号和无用产生式 的删除、-产生式的消除、单产生式的消除 ◼ 能根据文法和语言的Chomsky分类，确定给定 文法属于那种类型（0型、1型、2型、3型）， 其语言用什么机制来识别

第三部分词法分析 ■理解词法分析的主要任务 正规文法状态转换图分状态转换矩阵 会描述状态转换图识别的语言 正规文法分DFA和NFA;NFA(可能具有E动 作)的确定化;DFA状态数的最小化 ■正规文法冷正规式<FA

第三部分 词法分析 ◼ 理解词法分析的主要任务 ◼ 正规文法  状态转换图  状态转换矩阵 会描述状态转换图识别的语言 ◼ 正规文法  DFA和NFA；NFA（可能具有动 作）的确定化；DFA状态数的最小化 ◼ 正规文法  正规式  FA

第四部分语法分析 ■掌握自顶向下语法分析的基本过程 ■会消除文法的左递归,能改写非L(1)文法 ■会构造 FIRST集和 FOLLOW集,并在此基础上构造 预测分析表,会用预测分析表进行语法分析

第四部分 语法分析 ◼ 掌握自顶向下语法分析的基本过程 ◼ 会消除文法的左递归，能改写非LL(1)文法 ◼ 会构造FIRST集和FOLLOW集，并在此基础上构造 预测分析表，会用预测分析表进行语法分析

自底向上语法分析 掌握自底向上语法分析的基本过程 ■掌握简单优先关系和算符优先关系矩阵的基本步 骤 ■根据给定的简单优先关系和算符优先关系矩阵, 能进行相应的语法分析 能通过语法树找出句型的最左素短语 ■会构造优先关系矩阵的优先函数:有向图法、 Foyd方法

自底向上语法分析 ◼ 掌握自底向上语法分析的基本过程 ◼ 掌握简单优先关系和算符优先关系矩阵的基本步 骤 ◼ 根据给定的简单优先关系和算符优先关系矩阵， 能进行相应的语法分析 ◼ 能通过语法树找出句型的最左素短语 ◼ 会构造优先关系矩阵的优先函数：有向图法、 Floyd方法

LR分析法 根据给出的LR分析表,能写出LR分析过程 写出所有的LR(0)项目集,构造识别全部活 前缀的DFA,并在此基础上构造LR(0)分析 表和SLR(1)分析表(求Fo11ow集) 写出所有的LR(1)项目集,构造识别全部活 前缀的DFA,并在此基础上构造LR(1)分析 表和LALR(1)分析表(合并同心集)

LR分析法 ◼ 根据给出的LR分析表，能写出LR分析过程 ◼ 写出所有的LR(0)项目集，构造识别全部活 前缀的DFA，并在此基础上构造LR（0）分析 表和SLR(1)分析表（求Follow集） ◼ 写出所有的LR(1)项目集，构造识别全部活 前缀的DFA，并在此基础上构造LR（1）分析 表和LALR(1)分析表（合并同心集）

第五部分语法制导翻译和中间代码 生成 ■理解语法制导翻译的基本思想 会写出语句的逆波兰表示、三元式、四元式和 树形结构 ■能将算术表达式、赋值语句、布尔表达式(拉 链与回填)、FOR( While)循环语句、语句标 号及GOTO语句、情况(CASE)语句等翻译成中 间代码(四元式)

第五部分 语法制导翻译和中间代码 生成 ◼ 理解语法制导翻译的基本思想 ◼ 会写出语句的逆波兰表示、三元式、四元式和 树形结构 ◼ 能将算术表达式、赋值语句、布尔表达式（拉 链与回填）、FOR（While）循环语句、语句标 号及GOTO语句、情况（CASE）语句等翻译成中 间代码（四元式）

第六部分符号表 ■理解分程序结构语言符号表的组织结构和生成过程 理解非分程序结构语言符号表的组织结构

第六部分 符号表 ◼ 理解分程序结构语言符号表的组织结构和生成过程 ◼ 理解非分程序结构语言符号表的组织结构