编译原理习题.pdf

编译原理复习资料 一 填空题 1 编译程序是一种程序 能够将某一种高级语言编写的源程序改 造成另一种低级语言编写的目标程序 它们在逻辑上 等价 完成 相同 的工作 2 如果一个文法存在某个句子对应两棵不同的语法树 则称这个 文法是 二义性的 3 词法分析程序的功能是从左到右扫描源程序字符串 根据语言 的词法规则识别出各类单词符号 并以 单词符号或单词符 号表示的源程序 的形式输出 4 编译程序一般划分为词法分析 语法分析 语义分析 中间代 码生成 和 代码优化 目标代码生成六个阶段 除此以外 还有两个重要的基本工作 它们是 表格管理 和 出错处理 5 目前 语法分析方法有两大类 分别为自上向下的分析方法和 自下而上 分析方法 自上而下的分析方法是从 文法的 开始符号 出发 根据文法规则正向推导出给定句子的方 法 6 属性文法是编译技术中用来说明程序设计语言的 语义 的 工具 7 若源程序是用高级语言编写的 目标程序 是机器语 言程序或汇编程序 则其翻译程序称为 编译程序 8 扫描器 程序 的任务是从 字符串 中识别出一个个 单词符号 9 一个LR分析器包括三部分 总控程序 分析表 和分析栈 10 自顶向下的语法分析方法的基本思想是 从文法的 开始符 号 出发 根据给定的输入串并按照文法的产生式一步一 步的向下进行 正向推导 试图推导出文法的 给力句 子 使之与给定的输入串匹配 11 按Chomsky分类法 文法被分成 4 0 3型文法 类 12 局部优化是在 基本块 范围内进行的一种优化 13 编译程序是一种 翻译 程序 它将某一种高级语言编写的源 程序改造成另一种低级语言编写的目标程序 源程序和目标程 序在逻辑上等价 完成相同的工作 14 编译程序与解释程序的根本区别为 解释程序在执行中不产 生目标程序 15 语法分析的任务是识别给定的终结符号串是否为给定文法的 句子 16 编译程序一般划分为 词法 分析 语法分析 语义 分 析 中间代码生成 代码优化 和目标代码生成六个阶段 除此以外 还有两个重要的基本工作 它们是 表格管理 和 出错处理 17 局部优化是局限于一个 基本块 范围内的一种优化 18 一个上下文无关文法G包括四个组成部分 他们是 一组非终 结符号 一组终结符号 一个开始符号 以及一组 文法规 则 二 单选题 A 1 一般程序设计语言的定义都涉及到 三个方面 1 语法 2 语义 3 语用 4 程序基本符号的确定 A 1 2 3 B 1 2 4 C 1 3 4 D 2 3 4 B 2 编译程序是将高级语言程序翻译成 A 机器语言程序 B 汇编语言程 序或机器语言程序 C 汇编语言程序或高级语言程序 D 机器语言程 序或高级语言程序 D 3 文法G所描述的语言是 的集合 A 文法G的字母表 中所有符号组成的符号串 B 文法G的字母表 中的 中的所有符号串 D 由文法的开始符号推出的所有终结符号串 B 4 一个句型中的最左 称为该句型的句柄 A 短语 B 直接短语 C 素短语 D 终结符号 C 5 正规式中 符号 读作 A 并且 B 或者 C 闭包 D 连接 B 6 LL 1 文法 OPG文法和LR K 文法 二义性的 A 都是 B 都不是 C 不一定都是 D 不能确定 B 7 逆波兰表达式ab cd 所代表的中缀形式的表达式是 A a b c d B a b c d C a b c d D a b c d D 8 程序基本块是指 A 一个子程序 B 一个仅有一个入口和一个出口 的语句 D 一组顺序执行的程序段 仅有一个入口和一个出口 D 9 在编译程序采用的优化方法中 是在循环语句范围 内进行的 1 合并已知常量 2 删除多余运算 3 删除归纳变量 4 强度 削弱 5 代码外提 A 1 4 B 1 5 C 1 4 5 D 3 4 5 B 10 采用自上而下语法分析法分析文法时 必须先 A 消除回溯 B 消除左递归 C 消除右递归 D 提取公共左因子 C 11 已知一文法G S S xSxy 则其识别的语言是 A xyx B xyx C xnyxn n0 D x yx A 12 在常用的语法分析方法中 递归下降分析法属于 分析 方法 A 自顶向下 B 自左向右 C 自底向上 D 自右向左 B 13 逆波兰表达式ab cd 所代表的中缀形式的表达式是 A a b c d B a b c d C a b c d D a b c d B 14 正规式中 符号 读作 A 并且 B 或者 C 连接 D 闭包 C 15 算符优先分析法每次都是对 进行归约 A 最左短语 B 直接短语 C 最左素短语 D 素短 语 D 16 LR k 方法是 A 从左到右分析 每次走k步的一种编译方法 B 从左到右分析 共走k步的一种编译方法 C 从左到右分析 每次向前预测k步的一种编译方法 D 从左到右分析 每次向貌似句柄的符号串后看k个输入符号 的一种编译方法 D 17 代码优化后可生成 的目标代码 A 运行时间较短 B 占用存储空间较 小 C 运行时间短但占用内存空间大 D 运行时间短且占 用存储空间小 A 18 若文法 G 定义的语言是无穷集 则文法必然是 A 递归的 B 前后文无关的 C 二义性的 D 无二义性的 B 19 一个文法所描述的语言是 A 不唯一的 B 唯一的 C 可能唯一 也可能不唯一 D 都不对 B 20 若a为终结符 则A a 为 项目 A 归约 B 移进 C 接受 D 待约 C 21 词法分析程序的功能是从左到右扫描源程序字符串 根据 语言的词法规则识别 出各类单词符号 并将单词或单词序列以 的形式输出 A 单词 B 单词序列 C 二元组即种别码和自身值 D 语法树 A 22 编译程序是将高级语言程序翻译成 A 汇编语言程序或机器语言程序 B 机器语言程序 C 汇编语言程序或高级语言程序 D 机器语言程序或 高级语言程序 C 23 属性文法是编译技术中用来说明程序设计语言的 的工具 A 词法 B 语法 C 语义 D 代码优化 D 24 文法G所描述的语言是 的集合 A 文法G的字母表 中所有符号组成的符号串 B 文法G的字母表 中的 中的所有符号串 D 由文法的开始符号推出的所有终结符号串 A 25 乔姆斯基 Chomsky 把文法分为四种类型 即0型 1型 2 型和3型 其中3型文法是 A 正规文法 B 短语文法 C 上下文无关文法 D 上下文有关文法 C 26 用l代表字母 用d代表数字 l d 则定义标识符单 词的正规式为 A ld B ll C l l d D ll d B 27 LL 1 文法 OPG文法和LR K 文法 二义性的 A 都是 B 都不是 C 不一定都是 D 不能确定 A 28 中缀表达式 b c d a 所代表的逆波兰形式的表达式是 A b cd a B d a b c C b cd a D b cd a D 29 设一个文法G 若G中没有形如A BC 的规则 其中A B C为非终结符 则称文法G为 A 算符优先文法 B LL 1 文法 C LR 0 文法 D 算符文法 B 30 LR语法分析栈中存放的状态是识别文法规范句型 的 DFA状态 A 前缀 B 活前缀 C 项目 D 句柄 得分 三 判断改错题 对打 错打 并改正之 1 编译程序是一种常用的应用软件 2 设符号串x为10 则x0 1 3 在形式语言中 最右推导的逆过程称为规范归约 4 一张状态转换图中只包含有限个状态 其中有一个唯一的 初态 最多只有一个终态 5 算符优先分析法是一种规范归约分析法 每次归约的可归约 串是句柄 6 在编译程序中安排中间代码生成的目的是利于目标代码优 化和便于编译程序的移植 7 转移语句是基本块的入口语句 8 若某符号串是一个文法的句子 则该符号串一定是该文法 的句型 9 一个语言所对应的文法是唯一的 10 正规文法和正规式是描述程序语言单词符号的两种不同 的形式化形式 11 若OPG文法存在一张算符优先关系表 则一定存在对应 的优先函数 12 LL 1 文法一定是无左递归和无二义性的文法 13 所谓语法制导翻译法是指在语法分析过程中 随着分析的 逐步进行 根据相应文法的每一个产生式所对应的词法子程序进 行翻译 14 自顶向下的语法分析方法的关键是如何选择候选式的问 题 15 一个句型中的最左短语称为该句型的句柄 16 递归下降语法分析方法不允许任一非终结符是直接左递 归的 17 LR语法分析法是一种规范归约分析法 每次归约的可归 约串是句柄 18 一张状态转换图中只包含有限个状态 其中有一个唯一的 初态 最多只有一个终态 四 综合题 本题中各小题均需要有详细求解计算过程 否则不得分 1 已知文法G Z Z 0U 1V U 1Z 1 V 0Z 0 1 请写出此文法描述的只含有 个符号的全部句子 2 G Z 产生的语言是什么 3 该文法在Chomsky文法分类中属于几型文法 2 已知文法G S S TB 请求出G S 每个非终结符的FIRST和FOLLOW集合 并判断该文法是否 是LL 1 的 请说明理由 T Ba B Db eT D d 解答 计算文法的FIRST和FOLLOW集合 4分 FIRST M a b e d FIRST T a b e d FIRST B b e d FIRST D d FOLLOW M FOLLOW T a b e d FOLLOW B a FOLLOW D b 3 已知文法G E E T E T E T T F T F T F F E i 求符号串T i F i 的短语 素短语 直接短语和句柄 句型T T F I的短语为i T F 第一个T T T F i 简单短语为i T F 第一个T 句柄为第一个T 4 考虑简单赋值语句的文法G S S id E E E E E E E E id 1 试构造识别该文法所有规范句型活前缀的有穷自动机 2 判断该文法是否为LR 0 文法 必须说明理由 解 1 I0 S S S id E I1 S S I2 S id E I3 S id E E E E E E E E id I4 S id E E E E E E E I5 E id I6 E E E 2 由于I4 I8 I9均有移进 归约 冲突 E E E E E E 故该文法不是LR 0 文 法 E id I7 E E E E E E E E E E id I8 E E E E E E E E E I9 E E E E E E E E E 5 构造正规式 ba b a bab相应的DFA 6 已知文法G E E Tc aF T ab F bc 证明该文法是 二义性文法 7 写一个文法 使其语言是偶数的集合 且每个偶数不以0开 头 8 已知文法G S S 1A 请求出G S 所对应的正规式 A 0A 1B 1 B 1A 9 已知文法G S S L a LS L 1 构造文法G S 的预测分析表 2 若输入串为 请给出语法分析过程 10 已知文法G Z Z HZ a H ZH b 判断该文法是否为LR 0 SLR 1 LR 1 LALR 1 文法 并说 明理由 11 给出表达式 a b c d 的三元式和四元式两种中间代码表示 形式 12 已知文法G S S 1S0 10 求该文法G S 所描述的语言L 13 已知文法G E E Tc aF T ab F bc 证明该文法是 二义性文法 14 已知表达式为 a b c d e 求该表达式的三元式 四元式和 树形表示式 15 已知文法G A A AaB B 请按要求完成以下内容 1 改写文法以消除左递归 2分 2 并求改写后的文法G A 每个非终结符的FIRST集和FOLLOW集 4 分 3 判断G A 是否是LL 1 的 4分 B BbC C C eD D D A i 16 已知文法G S S aA bB 求该文法的LR 0 项目及分析表 A cA d B cB d 17 已知文法G S S a T T T S S 判断该文法消除左递归即改写后的G S 是否为LL 1 文法 请按要求完成以下内容 1 求文法G S 每个非终结符的FIRSTVT集 和LASTVT集 4分 2 构造该文法的算符优先关系表 6分 18 8 文法G S S G G R aPbR R d P aPbRcR P d P d 构造该文法的算符优先关系表 19 已知文法G S S L R