北方工业大学编译原理第1、2章习题.pdf

考核办法考核办法 平时作业完成情况占平时作业完成情况占 10 实验作业完成情况占实验作业完成情况占 20 期末考试成绩期末考试成绩占占 70 教材教材 陈火旺等 陈火旺等 程序设计语言编译原理程序设计语言编译原理 国防国防 工业工业出版社出版社 第一章 第二章习题第一章 第二章习题 第一章第一章 引论引论 作业 作业 1 1 1 2 1 1 请给出编译程序的总体结构图 并简述请给出编译程序的总体结构图 并简述各个部分各个部分 的主要功能的主要功能 解 解 词法分析器 词法分析器 输入源程序 识别出单词符号 把需要存放的单词输入源程序 识别出单词符号 把需要存放的单词 放到符号表中 如变量名等 放到符号表中 如变量名等 语法分析器 语法分析器 在词法分析的基础上 根据语言的语法规则的要求把单在词法分析的基础上 根据语言的语法规则的要求把单 词符号串组合成各类语法单位 词符号串组合成各类语法单位 语义分析与中间代码产生器 语义分析与中间代码产生器 对每种语法范畴对每种语法范畴进行语义分析 将语法进行语义分析 将语法 分析器得到的语法单位根据分析器得到的语法单位根据语义语义规则翻译成中间代码 规则翻译成中间代码 优化器 优化器 对前阶段产生的中间代码对前阶段产生的中间代码进行优化处理 以产生更为进行优化处理 以产生更为高效的高效的 目标代码目标代码 目标代码生成器 目标代码生成器 把把中间代码翻译成目标程序 中间代码翻译成目标程序 表格管理程序 表格管理程序 负责建立 填写和查找等一系列表格工作 表格的作负责建立 填写和查找等一系列表格工作 表格的作 用是记录源程序的各类信息和编译各阶段的进展情况 编译的每个阶用是记录源程序的各类信息和编译各阶段的进展情况 编译的每个阶 段所需信息多数都从表格中读取 产生的中间结果都记录在相应的表段所需信息多数都从表格中读取 产生的中间结果都记录在相应的表 格中 格中 错误处理程序 错误处理程序 处理和校正源程序中存在的词法 语法和语义错误 处理和校正源程序中存在的词法 语法和语义错误 当编译程序发现源程序中的错误时 错误处理程序负责报告出错的位当编译程序发现源程序中的错误时 错误处理程序负责报告出错的位 置和错误性质等信息 同时对发现的错误进行适当的校正 修复 置和错误性质等信息 同时对发现的错误进行适当的校正 修复 目的是使编译程序能够继续向下进行分析和处理 目的是使编译程序能够继续向下进行分析和处理 1 2 何谓源程序 目标程序 翻译程序 何谓源程序 目标程序 翻译程序 编译程序编译程序和解释程序和解释程序 它们它们之间可能有何种关系之间可能有何种关系 解 解 源程序 源程序 是是指以某种程序设计语言所编写的程序指以某种程序设计语言所编写的程序 目标程序 目标程序 目标语言书写的程序称为目标程序 目标语言书写的程序称为目标程序 翻译程序 翻译程序 是将源程序转换为与其等价的目标程序 是将源程序转换为与其等价的目标程序 编译程序与解释编译程序与解释 程序均为翻译程序 但二者工作方法不同 程序均为翻译程序 但二者工作方法不同 编译程序 编译程序 源语言为高级语言 源语言为高级语言 目标程序为目标程序为汇编语言或汇编语言或机器语言程序 机器语言程序 解释程序 解释程序 源语言程序作为输入 但不产生目标程序 而是边解释边源语言程序作为输入 但不产生目标程序 而是边解释边 执行源程序本身执行源程序本身 编译程序与解释程序最主要的区别是 编译程序与解释程序最主要的区别是 是否生成目标程序 是否生成目标程序 广义上讲 广义上讲 编译程序和解释程序都属于翻译程序 但它们的翻译方式不同 解释编译程序和解释程序都属于翻译程序 但它们的翻译方式不同 解释 程序是边翻译 解释 边执行 不产生目标代码 输出源程序的运行程序是边翻译 解释 边执行 不产生目标代码 输出源程序的运行 结果 而编译程序只负责把源程序翻译成目标程序 输出与源程序等结果 而编译程序只负责把源程序翻译成目标程序 输出与源程序等 价的目标程序 而目标程序的执行任务由操作系统来完成 即只翻译价的目标程序 而目标程序的执行任务由操作系统来完成 即只翻译 不执行 不执行 作业 作业 2 1 2 6 2 7 2 8 2 9 第二章第二章 高级语言及其语法描述高级语言及其语法描述 2 1 设有文法设有文法G A A bA cc 判断符号串判断符号串bbc bbbcc bbA bbAc是否是是否是G A 的句型或的句型或 句子 句子 解 解 由于由于A bA bbA bbbA bbbcc 所以所以 bbA是是G A 的的句型 句型 bbbcc是是G A 的的句子 句子 而而 bbAc和和bbc不能由文法不能由文法 G A 的开始符号推导出来的开始符号推导出来 所以 所以 bbAc不是不是G A 的的句型 句型 bbc不是不是G A 的句子 的句子 2 6 令文法令文法G6为为 N D ND D 0 1 2 3 4 5 6 7 8 9 解 解 1 G6的语言的语言L G6 是什么 是什么 L G6 为由为由0到到9这这10个数字组成个数字组成的的 长度 长度大于大于0的的字符串 字符串 或者 或者 可以以可以以0开头的开头的 非负整数集合非负整数集合 2 给出句子 给出句子0127 34和和568的最左推导和最右推导 的最左推导和最右推导 0127的最左推导 的最左推导 N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 最右推导 最右推导 N ND N7 ND7 N27 ND27 N127 D127 0127 34的最左推的最左推导导 N ND DD 3D 34 最右推最右推导导 N ND N4 D4 34 568的最左推的最左推导导 N ND NDD DDD 5DD 56D 568 最右推最右推导导 N ND N8 ND8 N68 D68 568 解 解 1 不允许 不允许0 开头的偶正整数集合的文法开头的偶正整数集合的文法 E NT D T FT G N D 1 3 5 7 9 D 2 4 6 8 F N 0 G D 0 2 允许 允许0 开头的偶正整数集合的文法开头的偶正整数集合的文法 E NT D T NT D N D 1 3 5 7 9 D 0 2 4 6 8 2 7 写一个文法 使其语言是偶正整数的集合 要求 写一个文法 使其语言是偶正整数的集合 要求 1 不允许 不允许0 打头 打头 2 允许 允许0 打头 打头 2 8 令文法为令文法为 E T E T E T T F T F T F F E i 1 给出 给出i i i i i i 的最左推导和最右推导的最左推导和最右推导 解 解 i i i最左推导 最左推导 E E T T T F T i T i T F i F F i i F i i i 最右推导 最右推导 E E T E T F E T i E F i E i i T i i F i i i i i i i i 最左推导 最左推导 E T T F F F i F i E i E T i T T i F T i i T i i F i i i 最右推导 最右推导 E T T F T E T E T T E F T E i T T i T F i T i i F i i i i i 2 给出 给出i i i i i i和和i i i的语法树 的语法树 解 解 E E T ET F T i F i Fi E T ET F T i F i F i E E T ET F T i F i Fi i i i语法树语法树i i i语法树语法树i i i语法树语法树 2 9 证明下面的文法证明下面的文法G S 是二义的 是二义的 S Ac aB A ab B bc 证明证明 二义性定义二义性定义 如果一个文法存在某个句子 如果一个文法存在某个句子对应两棵对应两棵 不同的