《编译原理》总复习-习题与试题-2010.ppt

编译原理 复习 西安电子科技大学软件工程研究所刘坚 2 课程内容 要求 希望 牢固掌握基本概念灵活使用基本方法归纳总结所学内容 一 引言二 词法分析三 语法分析四 语义分析 语法制导翻译生成中间代码 学习不能走捷径 付出多少劳动就有多少收获掌握正确的学习方法 提高自学能力 3 第一章引言 语言的翻译 不同的翻译形式 汇编 编译 转换 预编译 逆向翻译翻译方法 4 编译器的基本组成 5 编译器的分析 综合模式 编译器的扫描遍数与编译器的编写 6 第二章词法分析 构词规则与词法分析 首先规定单词形成的规则 称为构词规则 然后根据构词规则识别输入序列 称为词法分析 主要内容 记号 模式与单词记号的说明 模式的形式化描述 正规式与正规集 记号的识别 有限自动机从正规式到词法分析器 词法分析器的作用 滤掉源程序中的无用成分 处理与具体操作系统或机器有关的输入 识别记号并交给语法分析器 调用符号表管理器和出错处理器进行相关处理 7 记号 模式与单词 模式 pattern 规定单词识别的规则记号 token 按照某模式识别出的一类单词 记号种类 单词 lexeme 被识别出的字符串本身词法分析器的输出 记号 记号种类 记号属性 记号的说明 模式的形式化描述 正规式与正规集正规式与正规集的定义 基本正规式 三个运算 正规式的等价 描述相同的集合 利用正规式的等价对正规式进行化简 正规式的代数性质 用正规式形式化描述模式如何用正规式描述程序设计语言中常见的记号 如标识符 数字 运算符和分隔符等正规式的简化形式以及辅助定义与规则 8 记号的识别 有限自动机 FA NFA与DFA的定义 FA S move s0 F NFA与DFA的表示 定义表示 状态转换图 状态转换矩阵 NFA与DFA的关键区别 NFA的不确定性 有 状态转移 当前状态下 对同一字符有多于一个的下一状态转移 用NFA识别输入序列的弱点 尝试所有路径才能确定一个输入不被接收 回溯带来的问题 模拟DFA的算法 算法2 1 用DFA识别记号 从正规式到词法分析器 构造NFA的Thompson算法 算法2 2 与正规式的对应关系 模拟NFA的 并行 算法 算法2 3 从NFA构造DFA 子集法 算法2 5 smove S a 与 闭包 T 的计算 DFA的最小化 可区分的概念 所有不可区分的状态看作是一个状态 算法2 6 灵活运用各种方法构造DFA 正规式化简 状态转换图等 特别是手工构造和算法构造的区别 考虑 a b abb的NFA 10 第三章语法分析 语法分析是编译器中的重要阶段之一 可以认为是语法制导翻译模式编译器的核心 语法分析也有双重含义 根据一定的规则构成语言的各种结构 即语法规则 根据语法规则识别输入序列 记号流 中的语言结构 即语法分析 语法分析的分析对象是组成语言的句子 句子具有层次结构的特征 表征该结构的最好方法是树 从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法 主要内容程序设计语言与文法有关推导的基本概念自上而下分析自下而上分析 11 程序设计语言与文法 正规式与正规文法 正规式与正规文法用于描述线性结构 如构成句子的记号 终结符 识别正规语言的自动机是有限自动机 它们的特征是没有记忆能力 上下文无关文法 CFG N T S P CFG用于描述层次结构 如构成程序的句子 识别CFL的自动机是下推自动机 它是在有限自动机的基础上增加了一个下推栈 从而有了简单的记忆能力 文法的分类 0型 1型 2型和3型文法词法分析器与语法分析器 FA与PDA 12 有关推导的基本概念 CFG产生语言的基本方法 推导 从文法的开始符号开始 反复地用产生式的右部替换句型中的非终结符 推导的基本概念 句子 直接推导 最左推导 左句型 最右推导 右句型 定义3 2 3 3 3 4 分析树与语法树 分析树和语法树都反映了语言结构 分析树还记录了分析的过程 含有非终结符 定义3 5 3 6 文法的二义性 二义性的本质是在文法中缺少对文法符号优先级和结合性的限制 从而使得一个句子可以推导出多于一棵分析树 定义3 7 二义性的消除 改写二义文法为非二义文法 两个关键步骤 对文法符号施加优先级与结合性的限制 使得分析的每一步有唯一选择 13 自上而下分析 分析方法 推导 从上到下构造分析树 是一种预测的 试探的方法 对文法的要求 没有公共左因子和左递归左递归与直接左递归 定义3 9 消除直接左递归与左递归 算法3 1 3 2 提取公共左因子 类似于提取公因式 递归下降子程序方法 匹配终结符 展开非终结符 子程序调用 自上而下分析 续 预测分析表方法 工作方式与过程 PDA DPDA 格局 栈内容 当前剩余输入 改变格局的动作 改变格局的动作 匹配终结符 展开非终结符 接受 报错驱动器 算法3 4 预测分析表和分析表的构造 分析表的构成与意思 M A a FIRST集合与FOLLOW集合 定义3 10 3 11 FIRST与FOLLOW的计算 算法3 5 3 6 分析表的构造 算法3 7 LL 1 文法及其判别 预测分析表中没有多重定义条目 定义3 12 推论3 2 15 自下而上分析 分析方法 归约 推导的逆过程 从叶子到根构造分析树 基本概念 短语 直接短语 句柄 定义3 13 最左归约 定义3 14 归约 规范归约采用的方法 剪句柄实现方法 移进 归约 格局中的两个关键动作 关键问题 是如何确定栈顶已经形成句柄 当句柄形成时 如何判定采用哪个产生式进行规约 移进 归约分析器的工作模式 与预测分析表方法对着看 移进 匹配终结符 归约 展开非终结符 驱动器 算法3 8 自下而上分析 续1 移进 归约分析表 动作表 action 和转移表 goto LR k 文法 定义3 15 核心 识别活前缀的DFA 活前缀与LR 0 项目 NFA状态 定义3 16 3 17 一个产生式是一个识别活前缀的NFA一个LR 0 项目是NFA的一个状态 拓广文法与子集法构造DFAclosure I goto I X 定义3 18 3 19 核心项目与非核心项目 定义3 20 构造算法 算法3 9 核心是 closure goto I x 17 自下而上分析 续2 DFA如何分析输入序列有效项目 定义3 21 可移进项目 可规约项目移进 归约冲突 归约 归约冲突 解决冲突的方法 SLR 1 简单向前看一个终结符 计算归约项非终结符的FOLLOW 与可移进终结符比较 移进 归约分析表的构造 算法3 10 LR文法与LR分析 LR 0 SLR 1 LALR 1 LR 1 18 第四章语法制导翻译生成中间代码 讨论程序设计语言的静态语义分析 并且在语法分析的基础上生成中间代码 采用的基本方法是语法制导翻译 与前两章词法分析和语法分析不同的是 词法分析和语法分析的讨论侧重于理论 而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术 主要内容语法制导翻译 概念与基本方法中间代码符号表的组织声明语句的翻译可执行语句的翻译 语法制导翻译的基本概念 语法与语义语法 语言的结构 语义 附在结构上的实际意思属性与属性的计算属性 附在文法符号上的意思 如 val place等语义规则 实现属性的计算语义规则的两种表现形式语法制导定义 抽象的属性和计算表示的语义规则翻译方案 具体的属性和计算表示的语义规则 基本设计方法 与语法分析的关系 自下而上语法分析 LR分析的两点扩充 自上而下语法分析 递归下降子程序方法 语义规则的设计 设计属性 基本操作 函数或过程 语义规则 声明性语句 需要保存什么信息 这些信息有哪些特征 设计什么样的数据结构存放这些信息 以便于对它们的处理 可执行语句 语句的结构应生成什么样的中间代码序列 根据中间代码序列设计语法制导定义 根据序列的特点设计翻译方案 中间代码 为什么生成中间代码 中间代码是编译器分析综合模式前端与后端的分水岭 中间代码的特征 形式接近目标机器代码 但又与具体机器无关 便于编译器的开发移植和代码的优化 常用的中间代码形式 后缀式 树 图 三地址码 三地址码的实现 三元式 四元式中间代码之间的关系 树与后缀式的关系树与三元式和四元式的关系 符号表的组织 符号表的作用 连接声明与引用的桥梁符号表的条目与信息的存储 直接存储与间接存储作用域信息的保存静态作用域 最近嵌套原则线性表 栈结构 表上的操作散列表 每个子表是栈结构 提高表上操作的效率 声明语句的翻译 定义与声明 类型定义与变量声明 过程定义与过程声明变量声明 符号表信息的填写 简单变量和数组变量 过程声明 左值与右值 参数传递 参数传递的不同形式 各种参数传递形式的处理方式 名字的作用域 满足静态作用域与最近嵌套原则 声明中作用域信息的保存 可执行语句的翻译 简单算术表达式和赋值句的翻译 语法制导翻译的设计 类型转换 数组元素的引用 多维数组到一维存储空间的映射 数组元素地址计算的递推公式 数组元素地址计算的语法制导翻译 布尔表达式短路计算的翻译 为什么需要短路计算和短路计算的控制流 真出口与假出口 拉链 回填技术 真值链与假值链控制语句的翻译 控制语句的分类 转移与条件转移 结束 2010年5月25日 试题与习题 认真复习 重点是掌握基本概念 基本概念掌握了 相当一部分试题的解就有了 习题与试题的目的区别 习题的目的是通过反复的练习理解 掌握所学知识 会有不少繁 难 大量步骤的题 试题的目的是考察对本课程综合掌握的情况 特点是短时间内覆盖大量内容 太繁琐步骤或太难等需要耗费大量时间的题是不可能出的 大部分应该是基本概念题 但也会有一些综合性的题目 自己要会辨别什么是主要的什么是次要的 抓什么丢什么 基本概念要严谨 清楚 基本方法要灵活 总之一句话 学习方法的掌握是个人努力的结果 单纯靠别人教是学不会的 27 关于考试 题目类型 填空题 30分 简答题 20分 计算题 50分 考试范围 1 4章讲过的内容侧重考察 基本概念与基本方法的掌握 易犯的错误不认真审题 对题目的要求理解错误 意思理解错 难题想容易 容易题想难 关键问题是基本概念不清楚 所答非所问 例如 没有要求LL分析却将文法改为LL的 画蛇添足 例如 仅问有无冲突却将分析表先构造出来 偷工减料 例如 有若干问 仅回答部分或问题仅答一半 警示千万不要作弊 命运掌握在自己的手中 实际试题举例一 简答题 1 2分 有哪些方法可以去除文法的二义性 2 2分 写出 a b c d的后缀式 3 4分 试证明正规式 ab a与a ba 是等价的 1 1 改写文法 2 规定文法符号的优先级和结合性2ab c d 或ab c d 3证明 考虑L ab a 中的任意一个串ababab aba 由串连接的结合性可得 a ba ba b a ba 它恰好是L a ba 即L ab a L a ba 也可以用归纳法证明 提示 以ab重复0次 1次作为归纳基础 假设ab重复n次成立 证明ab重复n 1次也成立 二 填空题 30分 1 6分 编译程序的基本组成有 词法分析 中间代码生成 和 2 1分 正规式r和s等价说明相同 3 2分 不含子串baa的所有a b符号串的正规式是 4 4分 已知文法G定义如下 S eT RTT DR R dR D a bd则FIRST S FIRST D FIRST T FIRST R 1语法分析 语义分析 代码优化 目标代码生成 符号表管理和出错处理2r和s表示的正规集3a b ba 4FIRST S e d a b FIRST D a b FIRST T a b FIRST R d 三 计算题 1 1 13分 已知一个NFA如图 a 4分 用自然语言简要叙述该自动机所识别的语言的特点 列举两个它可识别的串 b 3分 写出与该自动机等价的正规式r c 6分 用子集法构造识别r的最小DFA 解 含有至少两个连续b的a b串 例如bb bbb等 r a b bb a b 直接用状态转换矩阵构造 初态 0 子集法得 2是终态 令 0 A 0 1 B 0 1 2 C 0 2 D得 最小化DFA得 C和D不可区分 三 计算题 2 2 15分 有文法G和G的语法制导翻译如下 E E1 T E place newtemp emit E1 place T place E place T E place T place T T1 F T place newtemp emit T1 place F place T place F T place F place F E F place E place id F place id name a 4分 求句型 T F id的短语 直接短语以及句柄 b 4分 根据语法制导翻译写出句子a b c d的中间代码 c 3分 若a 3 b 5 c 7 d 8 请给出中间代码计算结果 d 4分 将文法G简化为 E E T T T T F F F id 给出它的识别活前缀的DFA 解 a 短语 T F id T F T F id直接短语 T F id句柄 T F b a b c d的中间代码 1 b c t1 2 a t1 t2 3 t2 d t3 c 计算结果 t3 288 d 识别活前缀的DFA 34 部分习题解答 习题2 4 写出下述语言的正规式描述 1 由偶数个0和奇数个1构成的所有01串 2 所有不含子串011的01串 3 每个a后面至少紧随两个b的ab串 4 C的形如 的注释 其中 代表不含 的字符串 思路 分析题意 从最简单的例子考虑 然后找出统一规律 1 的解题步骤 1 最简单的符合要求的串 1 010 还有100 001 111等 2 所有01均为偶数的串 A 00 11 01 10 00 11 10 01 3 符合要求的所有串 A1A A0A1A0A 为什么没有后三个 结果 A1A A0A1A0A思考 识别它的DFA又应该如何构造 4 C的形如 的注释 其中 代表不含 的字符串 思路 注释中若遇到 若后边是 则结束注释否则仍然是注释步骤 1 注释串是空 2 考虑没有 的注释 3 考虑含 的注释结果 4 2 所有不含子串011的01串 1 01 0 3 每个a后面至少紧随两个b的ab串 b abb 习题2 9 用自然语言给出下述正规式所描述的语言 并构造他们的最小DFA 10 1 0 1 011 0 1 说明 所谓用自然语言描述就是解释字符串的性质 一般情况下是已经有了形式化描述 解 10 1 首尾是1中间有零或若干个0的01串 0 1 011 0 1 至少含一个011的01串 注意 是0或若干次的重复 是至少一次的重复绝对不允许用正规式表示 因为正规式是已知条件DFA 略 0 1 011 0 1 的DFA构造与考试题中计算题相似 习题2 10 有一NFA的状态转换矩阵下表 其中S为初态 D为终态 求出它的最小DFA用正规式描述DFA所接受的语言 问题 根据DFA写出对应的正规式 通常的考虑和步骤是什么 再重复一遍 正规式 DFA是从两个不同的侧面表示一个集合 即正规集 所以 根本的方法是把正规集作为桥梁 先分析清楚DFA识别出的是一个什么集合 然后再设计此集合的正规式 反之亦然 习题2 10 2 的解 该DFA从初态到终态有三条路径 b c a a c b 而且是这三条路径的至少一次重复 故正规式为 b c a a c b 习题3 7 设计一文法G 使得L G 是不以0开始的正奇数 思路 首先根据集合的描述设计几个句子 然后从句子中找出规律 或共性 把它们的性质用产生式表示出来 解 正规式 个位 13579 个位以上 0 9 最高位 1 9 三段连起来 1 9 0 9 13579 两种情况 1 9 0 9 13579 13579 产生式 S ACB BA 1 2 3 4 5 6 7 8 9B 1 3 5 7 9C 0C AC 习题3 14 下述四个文法 无需构造预测分析表 指出哪一个是LL 1 文法 并指出其他文法为什么不是LL 1 文法 解 1 不是LL 1 文法 因为它是左递归的 S Ra Sba 2 是LL 1 文法 3 不是LL 1 文法 因为对于S的两个候选项Aa和Aa FIRST aA FIRST Aa a 不满足推论3 2的条件 4 不是LL 1 文法 因为S的前两个候选项中含有左公因子iCtS 不满足推论3 2的条件 习题3 11 3 18 文法G如下 S aABeA b AbcB d 1 改写G为等价的LL 1 文法 2 求每个非终结符的FIRST集合和FOLLOW集合 1 构造识别活前缀的DFA 2 指出DFA中的冲突 如果有的话 解 3 11 1 改写后的文法 S aABeA bA A bcA B d 2 FIRST S a FOLLOW S FIRST A b FOLLOW A d FIRST A b FOLLOW A d FIRST B d FOLLOW B e 习题3 11 3 18 续 解 3 18 1 S aABeA b AbcB d的DFA如下 2 无冲突 44 Toknowhowtodosomethingwellistoenjoyit 战略上藐视敌人 战术上重视敌人 Thetreesthatareslowtogrowbearthebestfruit 认真复习 迎接考试 结束2010年5月27日 习题3 17 对于文法G3 4和它所产生的句子 id id id和 id id idE E T TT T F F G3 4 F E F id 1 构造基于LR 0 项目集的识别活前缀的DFA 2 指出DFA中所有含有冲突的项目集 并说明这些冲突可以用SLR 1 方法解决 3 构造文法G3 4的SLR 1 分析表 4 用分析表对句子 id id id和 id id id进行分析 以格局变化的方式 5 根据 4 的分析给出 id id id的分析树和剪句柄的过程解 习题3 17 解 1 构造基于LR 0 项目集的识别活前缀的DFA 2 指出DFA中所有含有冲突的项目集 并说明这些冲突可以用SLR 1 方法解决 冲突的项目集 I2 I11计算FOLLOW E 看 是否在其中 略 构造SLR 1 分析表的方法 1 可移进项直接从DFA上看 action I a sjgoto I A k2 可归约项分两步走 若在I状态中有 A 首先计算 FOLLOW A 然后填写 action I b Ri其中 b FOLLOW A 且A 是第i个产生式 习题3 6 设字母表 0 1 设计下述语言的文法 对于正规语言 可用正规式表示 1 每个0后面至少跟随一个1的字符串 2 0和1个数相等的字符串 3 0和1个数不相等的字符串 4 不以011作为子串的字符串 解 1 01 1 2 S 0S1S 1S0S 3 S A0A B1BA 0A1A 1A0A 0A 0不少于1 B 0B1B 1B0B 1B 1不少于0 4 1 0 01 习题3 22 构造SLR 1 分析表的算法3 9基于的假设是LR 0 项目集中可能有冲突 如果基于的假设是LR 0 项目集中没有冲突 则构造方法可以简化 无需计算FOLLOW集合 得到的是LR 0 分析表 试修改算法3 9成为构造LR 0 分析表的算法 1 ifDFA中有不能解决的移进 归约和归约 归约冲突thenerror elsefor每个状态转移Dtran i x jloopifx Tthenaction i x Sj elsegoto i x j endif endloop for状态i的每个可归约项A loopifS S thenaction i acc elsefor每个a FOLLOW A loopaction i a Rk endloop endif endloop endif 每个终结符a A 状态i B x 习题4 4 假定下述程序分别采用值调用 引用调用 复写 恢复和换名调用 请给出它们的打印结果 programmain inputoutput procedurep x y z beginy y 1 z z xend begina 2 b 3 p a b a a printaend 两种解题的思路 1 把自己当作计算机 按照参数传递的实现方式 运行 一遍程序 得出结果 2 找台机子把程序敲进去试试 辅助手段 困惑的是 表达式a b如何作为引用调用和复写 恢复的实参 解决方案 忽略返回值问题 其实这一思想可以推广到任何不支持某种方式的情况 放心 考试中不会有这种很困惑的问题 具体结果 略 习题4 9 设整型数组声明的形式为intA d1 d2 d3 并且假设每个整型数占据4个字节 1 试导出以列为主存储时计算c和v的递推公式 2 设计数组声明的语法制导翻译 包括语法和语义 以使得在对数组声明从左到右分析的同时 正确填写符号表和内情向量的所有信息 解 1 n 1时 addr