讲稿第9章-编译原理习题课.pptVIP

1 期末考试 考试时间：2016-05-29 上午9:00-11:00 考试地点：东环101 答疑时间：2016-05-27 下午13:00-16:00 2016-05-28 下午13:00-17:00 答疑地点：工科楼E1110 复习习题课 2 3 编译原理总复习 形式化方法 词法的描述——三型文法、正规式 语法的描述——二型文法 语义处理的描述——属性文法 文法的概念 形式定义（四元组） 句子、句型、推导、分析树 文法分类 4 编译系统结构 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 表格管理 错误处理 5 词法分析 正规式 正规文法 有限自动机 DFA：确定的有限自动机 知识点： 语言、自动机、正规式和正规文法的关系 自动机和识别过程的关系 6 主要计算题型 正规语言、正规文法、正规式、自动机的互换 有限自动机的生成和DFA的构造 NFA的确定化 DFA的最小化 7 一、词法分析 设有正规式1(0|1)*101 1. 试构造与该正规式等价的NFA，并对其进行确定化、最小化； 2. 写出与最小化以后的DFA等价的正规文法； 3. 写出其识别的正规集(即对应的正规语言)。 8 正规式1(0|1)*101 构造与该正规式等价的NFA NFA确定化 9 正规式1(0|1)*101 DFA最小化 与最小化以后的DFA等价的正规文法 G[S]：S → 1A A → 0A | 1B B → 0C | 1B C → 0A | 1Z D → 0B | 1B | ε 10 正规式1(0|1)*101 3. 写出其识别的正规集(即对应的正规语言) 以1开头，以101结尾的二进制数 11 语法分析 自顶向下分析 递归子程序法 LL(1)分析法（预测分析） 自底向上分析（移进归约分析） 简单优先分析 算符优先分析 LR分析：LR(0)、SLR(1)、LR(1)、LALR(1) 12 语法分析 自顶向下分析 递归子程序法 LL(1)分析法（预测分析） 自底向上分析（移进归约分析） 简单优先分析 算符优先分析 LR分析：LR(0)、SLR(1)、LR(1)、LALR(1) 13 自顶向下分析 消除左递归、提取左因子 计算FIRST集、FOLLOW集、 SELECT集 递归子程序法(了解) 判断是不是LL(1)文法 设计子程序 LL(1) 分析法（预测分析法） 填写预测分析表 分析某个符号串是否为句子 14 自顶向下分析常见题型 消除左递归（直接、间接） 消除左因子(提左公因子) 求 FIRST 集 求 FOLLOW 集 求 SELECT 集 编制递归子程序（了解） 计算预测分析表(LL(1)分析表) 跟踪预测分析过程 15 LL分析的概念 根据当前输入符号，唯一地确定采用哪个产生式进行推导 LL(1) 文法 何时改写文法 适用范围 左递归、左因子、FIRST、FOLLOW集和SELECT 集的概念 16 二、LL(1)文法 1、计算该文法的每个非终结符的FIRST集和FOLLOW集； 2、求每个产生式的SELECT集； 3、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判断G[S]是否为LL(1)文法； 4、若G[S]是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列： 步骤 分析栈 输入串 使用产生式 G[S]：S → aH H → aMd | d M → Ab | ε A → aM | e 17 1、计算该文法的每个非终结符的FIRST集和FOLLOW集； G[S]：S → aH H → aMd | d M → Ab | ε A → aM | e 非终结符 FIRST集 FOLLOW集 S {a} {#} H {a, d} {#} M {a, e, ε} {d, b} A {a, e} {b} 2、求每个产生式的SELECT集； 产生式 SELECT集 S → aH {a} H → aMd {a} H → d {d} M → Ab {a, e} M → ε {d, b} A → aM {a} A → e {e} 18 3、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判断G[S]是否为LL(1)文法； a d b e # S aH H aMd D M Ab ε ε Ab A aM e 产生式 SELECT集 S → aH {a} H → aMd {a} H → d {d} M → Ab {a, e} M → ε {d, b} A → aM