《编译原理复习》PPT课件.ppt

复习 2011 4 26 第一章要点 编译器的概念 其输入和输出 机器语言 汇编语言 高级语言 乔姆斯基分层结构 0型 无限制文法1型 上下文相关文法2型 上下文无关文法3型 正则文法 第一章要点 相关程序和概念解释器编辑器交互式开发环境 IDE 调试程序分析和综合前端和后端遍 编译器的翻译过程 第一章2009 编译器各处理阶段的正确顺序是 A 词法分析 语法分析 语义分析 代码生成 B 语法分析 词法分析 语义分析 代码生成 C 语义分析 语法分析 词法分析 代码生成 D 以上都不对 编译器中语法分析的输入和输出分别是 A 字符串 记号串B 记号串 注释树C 记号串 语法树D 语法树 注释树什么是编译器 请简述编译器的功能及其输入输出 第一章2008 以下对编译器 compiler 描述错误的是 A编译器的输入是由源语言编写的源程序 输出是由目标语言编写的目标程序 B编译器是一个执行程序而不是一个转换程序 C编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境 IDE 中 D按照编译器扫描的遍数 可把编译器分为一遍扫描和多遍扫描的编译器 把汇编语言程序翻译成机器可执行的目标程序的工作是由 完成的 A 编译器B 解释器C 汇编器D 预处理器 第一章2008 编译器的工作可分为多个阶段 词法分析 语法分析 语义分析阶段的结果分别是 A分析树 语法树 语义树 B分析树 语法树 注释树 C记号序列 语法树 语义树 D记号序列 分析树 注释树 文法根据限定条件分为四种文法 0型文法 1型文法 2型文法 3型文法 其中2型文法又叫做 文法 3型文法又叫做 文法 高级程序设计语言源程序有两种执行方式 即 和 什么是编译器 什么是遍 什么是扫描器 扫描器的功能是什么 第一章2010 以下对编译器 compiler 描述错误的是 A 编译器是将一种语言翻译成另一种语言的计算机部件 包括软件部分和硬件部分 B 输入编译器的源语言通常是高级语言 如C语言 输出编译器的目标语言通常是低级语言 如01代码 C 词法分析是编译器的一个处理阶段 D 编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境 IDE 中 第一章2010 汇编语言与机器语言相比 其主要优点在于 A 汇编语言机器依赖性强 B 汇编程序的可执行程序的长度可以大幅下降 C 汇编语言的符号形式更易理解 也提高了编写程序的准确性 D 以上都不对 第一章2010 一般的编译器中 语法分析的结果是生成源程序的 A 记号序列 B 分析树 C 语法树 D 注释树 编译程序和解释程序有哪些区别 第一章2011 下列程序中没有翻译功能的是 A汇编器B解释器C编译器D编辑器判断 如果编译器的源语言发生了改变 那么其前端操作无需修改 什么是语义分析程序 请解释其功能及其输入和输出 第二章要点 扫描程序的功能及其输入输出 正则表达式什么是由r生成的语言 字母表 元符号三种基本操作有限自动机定义DFANFA 第二章要点 正则表达式 NFA DFA 程序RE NFAThompson sconstructionNFA DFA子集构造法DFA的化简DFA 程序三种方式 Lex 第二章2011 以下对扫描器 scanner 描述正确的是 A扫描器是编译器的一个功能模块 其功能是进行语义分析 B扫描器的输入是语法树 输出是注释树 C扫描器需要分析哪些字符组成了 词 D扫描器无需提示任何错误 而是由其它编译器模块来完成 第二章2011 下面不属于正则表达式 regularexpression 的基本操作的是 A递归B并置C选择D闭包 第二章2011 下面的NFA中 对状态或状态集合的 闭包描述正确的是 A状态1的 闭包是 2 4 B状态 2 3 的 闭包是 2 3 4 C状态3的 闭包是 2 4 D状态4的 闭包是空集 第二章2011 7 正则表达式 a b 生成的语言 以下描述正确的是 AL a b 由a和b组成的任意字符串 BL a b 由a组成的字符串或由b组成的字符串 CL a b 由a组成的字符串和由b组成的字符串 D以上都不对 第二章2011 请解释下面各正则表达式的含义 并分别列出其生成语言的实例 a a zA Z 0 9 a zA Z b AA n AA nc 0 9 0 9 d b ab ab 第二章2011 15分 已知正则表达式 aa b a a b 1 利用Thompson构造法 Thompson sconstruction 将该正规表达式 regularexpression 转化为NFA 2 将1中得到的NFA转化为DFA 3 将2中得到的DFA进行化简 以得到状态数最少的DFA 下面的DFA中 可以合并 A 状态1和状态2 B 状态2和状态3 C 状态1和状态3 D 以上都不对 第二章2010 第二章2010 请写出下面各个字符串的正规表达式 regularexpression a 十六进制的数字串 b 含有偶数个2的数字串 c 不以AA开头的大写字母串 第二章2010 15分 已知正则表达式 a b a b 1 利用Thompson构造法 Thompson sconstruction 将该正规表达式 regularexpression 转化为NFA 2 将1中得到的NFA转化为DFA 3 将2中得到的DFA进行化简 以得到状态数最少的DFA 第二章2009 表示 由a或b组成的含有偶数个b的字符串 的正则表达式是 A a ba ba B a ba ba C abab D 以上都不对请写出下面各个字符串的正则表达式所有整数的数字串 包括负数 字符串中至多含有一个A的大写字母串请简述有限自动机的组成元素并解释DFA和NFA的区别 第二章2009 以下不是有限自动机的组成元素的是 A 开始状态B 结束状态C 正则表达式D 状态转换函数已知正则表达式 ab a b 1 构造该正则表达式所对应的NFA 2 由NFA构造DFA 3 对DFA进行最小化 第二章2008 以下对有穷自动机的图形表示描述错误的是 用带箭头的线表示一个状态到另一个状态的转换 用圆圈表示状态 用双线边界的圆圈表示接受状态 一个有穷自动机里只能有唯一的一个接受状态 对于给定的一个非确定性有限自动机 NFA 以下正确的是 不存在与之等价的DFA 存在一个唯一等价的DFA 存在一个唯一的具有最少状态数的等价DFA 存在等价DFA 但具有最少状态数的DFA不唯一 第二章2008 请写出下面各个字符串的正则表达式 以a开头或者以b结尾的小写字母串 以字母开头 后面是数字或字母的符号串 即标识符 已知正则表达式a ba 1 构造该正则表达式所对应的NFA 2 由NFA构造DFA 3 对DFA进行最小化 第三章要点 分析程序的功能及其输入输出 常见的高级语言的文法 上下文无关文法 表示方式 BNF 以及其特点 包含递归 推导分析给定文法的 终结符 非终结符 生成的语言 对某个串的推导 二义性文法概念及消除二义性的方法 1 2 常见产生原因及消除的方法 第三章2011 在一般的编译器中 语法分析基于 文法进行 即识别的单词串是该类文法的句子 分析器 parser 的主要功能是进行 第三章2011 以下对于文法二义性的描述正确的是 ALL 1 文法是无二义性文法 B二义性文法会对所有的符号串产生多个语法树 C通过相应算法可以判断文法的二义性 D在语法分析中 二义性文法是不被允许的 必须通过修改文法来消除 第三章2011 判断 一个文法所描述的语言是唯一的 描述一个语言的文法是不唯一的 考虑下列文法G D D TVT int floatV id V id请给出intid id id进行的最右推导过程 并画出其分析树或语法树 第三章2010 判断 一个文法所描述的语言是不唯一的 描述一个语言的文法是唯一的 分析器 parser 的主要功能是进行 分析器的输入是 输出是 第三章2010 请写出下面文法对于表达式 进行的最左推导过程 并画出其分析树或语法树 A A A 试描述由下列文法所产生的语言 S aSS a 第三章2009 在文法中可能引起二义性的原因有 A 运算的优先级B 运算的结合性C else的悬挂问题D 以上都有可能 第三章2008 以下对于语法二义性的描述正确的是 A如果文法G的某个句子存在两棵或者两棵以上的语法树 或分析树 则称该文法是存在二义性的 B如果文法G的某个文法存在两个或者两个以上的句子符合该文法规则 则称该文法是存在二义性的 C消除文法二义性只能对文法进行修改 别无他法 D能够通过算法判别文法是否存在二义性 编译过程中 语法分析器的任务是 分析单词是怎样构成的 分析单词串是如何构成语句和说明的 分析语句和说明是如何构成程序的 分析程序的结构A 和 B C D 第三章2008 已知文法G S S a T T T S S给出句子 a a a 的最左推导并画出语法树 第四章要点 语法分析的分类 自顶向下 自底向上自顶向下分析方法 递归下降 LL 1 分析LL 1 基本方法 三种动作 生成 匹配 接受 判断文法是否是LL 1 文法First集和Follow集左递归和左因子的消除构造分析表 第四章2011 对下面文法中非终结符First集合描述正确的是 E L a L EL EAFirst E a BFirst L a CFirst E a DFirst L a 第四章2011 考虑下列文法G S S PSk PP a S S为开始符号 请计算S和P的First集合和Follow集合 判断文法G S 是否是LL 1 文法并说明理由 第四章2011 20分 已知文法G S 为S SAT TA T S k1 通过消除左递归和提取左因子 回溯 给出与G S 等价的文法G S 2 计算文法G S 非终结符的First集合和Follow集合 3 判断文法G S 是否为LL 1 文法 4 如果文法G S 是LL 1 文法 构造G A 的分析表 5 给出输入串k k k 的分析过程 第四章2010 对于文法G S S Q S Q SQ a S S为开始符号 请计算S和Q的First集合和Follow集合 第四章2010 已知文法G A 为A a B b P P A Ak通过消除左递归和提取左因子 回溯 给出与G A 等价的文法G A 计算文法G A 非终结符的First集合和Follow集合 判断文法G A 是否为LL 1 文法 如果文法G A 是LL 1 文法 构造G A 的分析表 给出输入串的分析过程 第四章2009 设有文法G S S XS X aSb S c计算文法G S 非终结符的First集合和Follow集合 若采用自顶向下分析方法 对此文法来说 在分析过程中能否避免二义性 为什么 分析符号串aababb是否为此文法的句子 第四章2009 已知文法G A 为A L A x L L s k通过消除左递归和提取左因子 回溯 给出与G A 等价的文法G A 计算文法G A 非终结符的First集合和Follow集合 判断文法G A 是否为LL 1 文法 如果文法G A 是LL 1 文法 构造G A 的分析表 给出输入串 k s s x 的分析过程 第四章2008 高级语言编译程序常用的语法分析方法中 递归下降分析法属于 分析方法 A 自左至右B 自顶向下C 自底向上D 自右向左LL 1 分析方法是这样得名的 第一个 L 指的是 第二个 L 指的是 括号中的数字1指的是 第四章2008 10分 设有文法G Z Z A A a bBB Aab 1 若采用自顶向下分析方法 对此文法来说 在分析过程中能否避免二义性 为什么 2 分析符号串 bbaabab 是否为此文法的句子 20分 已知文法G A 为A aABe aB Bb d 1 通过消除左递归和提取左因子 回溯 给出与G A 等价的文法G A 2 计算文法G A 非终结符的FIRST集合和FOLLOW集合 3 判断文法G A 是否为LL 1 文法 4 如果文法G A 是LL 1 文法 构造G A 的分析表 5 给出输入串aade的分析过程 第五章要点 什么是自底向上的分析方法基本操作 移入 归约方法及能力 LR 0 SLR 1 SLR k LR 0 SLR 1 LR 1 LR K LR 0 项构造DFA移入归约冲突 归约归约冲突分析过程 第五章2006 LR 0 分析中的分析动作包括 和 第五章2006 对于文法 E L qL EL Ea 为这个文法构造LR 0 项目的DFAb 构造SLR 1 分析表c 对输入串 qq 进行分析 15分 第六章要点 属性文法概念 联编联编时间静态语义和动态语义常见的静态语义符号表的作用 内容符号表存储的属性 第六章2008 2011 下面不属于语义属性的是 A 变量的数据类型B 表达式的值C 变量对应的内存地址D 源程序文件名判断 为了提高查找及存取速度 符号表都采用有序表的形式 第七章要点 概念运行时环境过程活动记录调用序列和返回序列几种运行时环境及其特点 举例 完全静态的运行时环境基于栈的运行时环境 第七章2008 2011 在编译方法中 动态存储分配的含义是 A 在运行阶段对源程序中的量进行分配B 在编译阶段对源程序中的量进行分配C 在编译阶段对源程序中的量进行分配 在运行时这些量的地址可以根据需要改变D 以上都不正确对于数据空间的存贮