下载文档原格式
北航《编译技术》在线作业三北航《编译技术》在线作业三单选题多选题判断题一、单选题（共14道试题，共56分。
）1.文法G产生的（）的全体是该文法描述的语言。
A.句型B.终结符集C.非终结符集D.句子-----------------选择：D2.Chomsky定义的四种形式语言文法中，2型语言文法又称为（）文法。
A.短语文法B.上下文无关文法C.上下文有关文法D.正规文法-----------------选择：B3.如果r、s是正规式，则下面（）不一定是正规式。
A.rsB.r|sC.r*D.r+s-----------------选择：D4.算符优先分析每次规约的是（）。
A.最左短语B.直接短语C.句柄D.最左素短语-----------------选择：D5.最常用的中间代码形式是（）。
A.二元式B.三元式C.四元式D.树形表示-----------------选择：C6.文法E→(E)产生的语言是（）。
A.空集B.（）C.（E）D.((((E))))-----------------选择：A7.下面哪个文法是左递归的（）。
A.E→E＋T|TB.T→F*TC.E→(E)D.E→a-----------------选择：A8.Σ={0，1}上的正规式(0|1)*表示（）。
A.0开头的串B.1开头的串C.有一个0和一个1的串D.由0、1组成的任意串-----------------选择：D9.正规式（a|b）*表示的是（）。
A.所有由字母a或b构成的串B.字符串a|bC.字符串（a|b）*D.空串-----------------选择：A10.编译器与要编译的源程序的接口阶段是（）。
A.扫描程序B.语法分析程序C.语义分析程序D.代码生成器-----------------选择：A11.有限自动机可以有（）个初始状态。
A.一个B.两个C.三个D.多个-----------------选择：A12.语法分析属于编译器的（）阶段。
北航《编译技术》复习题一一、单项选择题1、目标代码生成属于编译器的（）阶段A．词法分析B．语法分析C．分析D．综合2、算符优先分析每次规约的是（）A．最左短语B．直接短语C．句柄D．最左素短语3、简单优先分析每次规约的是（）A．最左短语B．直接短语C．句柄D．最左素短语4、若文法 G 定义的语言是无限集，则文法必然是（）A ．递归的 B. 前后文无关的C .二义性的 D. 无二义性的5、Chomsky 定义的四种形式语言文法中， 1 型文法又称为（）文法；A ．短语结构文法 B.前后文无关文法C.前后文有关文法D.正规文法6、一个文法所描述的语言是（）A ．唯一的 B. 不唯一的C .可能唯一， D.可能不唯一7、数组的内情向量中肯定不含有数组的（）的信息A．维数 B.类型C.维上下界D.各维的界差8、自顶向下的分析方法有（）。
①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析A.③④⑦B. ③④⑧C.①②⑧D.③④⑤⑥⑦9、文法 G 所描述的语言是（）的集合。
A.文法 G 的字母表 V 中所有符号组成的符号串B.文法 G 的字母表 V 的闭包 V 中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串10、乔姆斯基（Chomsky）把文法分为四种类型，即 0 型、1 型、2 型、3 型。
其中 3 型文法是（）。
A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法二、判断题11、每个基本块可用一个DAG表示。
A．对 B．错12、每个过程的活动记录的体积在编译时可静态确定。
A．对 B．错13、2型文法一定是3型文法。
BA．对 B．错14、一个句型一定是句子。
BA．对 B．错15、算符优先分析法每次都是对句柄进行归约。
A．对 B．错16、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
第七章 源程序的中间形式•• •• ••波兰表示 波兰表示 N－元表示 N－元表示 抽象机代码 抽象机代码北京航空航天大学计算机学院17.1 波兰表示一般编译程序都生成中间代码，然后再生成目 标代码，主要优点是可移植(与具体目标程序无关)， 且易于目标代码优化。
有多种中间代码形式： 波兰表示 N－元组表示 抽象机代码 波兰表示 算术表达式： 转换成波兰表示： 波兰表示： F*3.1416*R*(H+R) F3.1416*R*HR+*赋值语句： A := F * 3.1416 * R * ( H + R ) AF3.1416 * R * HR + * :=2北京航空航天大学计算机学院#a+b#ab++ 操作符栈 # #优先级最低算法： 设一个操作符栈；当读到操作数时，立即输出该操作数， 当扫描到操作符时，与栈顶操作符比较优先级，若栈顶操作 符优先级高于栈外，则输出该栈顶操作符，反之，则栈外操 作符入栈。
北京航空航天大学计算机学院 3if 语句的波兰表示label1if 语句：if <expr> then <stmt1> else <stmt2>label2波兰表示为 ：<expr><label1>BZ<stmt1><label2>BR<stmt2> BZ: 二目操作符 若<expr>的计算结果为0 (false)， 则产生一个到<label1>的转移 BR: 一目操作符 产生一个到< label2>的转移北京航空航天大学计算机学院4波兰表示为 ：<expr><label1>BZ<stmt1><label2>BR<stmt2> 由if语句的波兰表示可生成如下的目标程序框架： <expr> BZ label1 <stmt1> BR label2 label1：<stmt2> label2： 其他语言结构也很容易将其翻译成波兰表示， 使用波兰表示优化不是十分方便。
《编译技术》第二阶段导学材料（对应教材第三章、第四章、第五章）第3章语法分析⏹目标：通过本章的学习，掌握有关上下文无关文法的基本概念，理解适合于手工实现的预测分析技术，掌握自上而下分析法和自下而上分析法，掌握自动工具用的LR分析算法。
⏹主要内容：3.1 上下文无关文法3.2 语言和文法3.3 自上而下分析3.4 自下而上分析3.5 LR分析器3.6 二义文法的应用3.7 分析器的生成器⏹重点：语法、语义、文法的构造，语法分析方法。
⏹难点：LR分析法第4章词法制导的翻译⏹目标：通过本章的学习，掌握语法制导的定义，掌握自下而上、自上而下的实现方法。
了解递归计算的方法，掌握翻译方案实现方法。
⏹主要内容：介绍了语义规则和产生相联系的两种方式：语法制导的定义和翻译方案。
语法制导的定义是较抽象翻译说明，它隐藏了一些实现细节；而翻译方案陈述了一些实现细节，主要是指明了语义规则的计算次序。
讲述了语法制导的定义和翻译方案实现方法。
4.1 语法制导的定义4.2 S属性定义的自下而上计算4.3 L属性定义的自上而下计算4.4 L属性的自下而上计算4.5 递归计算⏹重点：属性翻译文法的概念，属性的正确使用和计算。
第5章类型检查⏹目标：通过本章的学习，了解类型在程序设计语言中的作用，掌握类型系统的组成与作用、类型检查的作用，了解多态函数的作用，掌握重载的概念，了解控制流检查、唯一性检查和关联名字检查的功能。
⏹主要内容：讲述了静态检查的概念，讲述了类型系统的组成与作用、类型检查的作用和多态函数的作用，介绍了重载的概念，介绍了控制流检查、唯一性检查、关联名字检查的概念和各自的功能。
5.1 类型在程序设计语言中的作用5.2 描述类型系统的语言5.3 简单类型检查器的说明5.4 多态函数5.5 类型表达式的等价5.6 函数和算符的重载⏹重点：类型系统的组成与作用，类型检查的作用，函数和算符的重载。
北航《编译技术》在线作业一一、单项选择题（共14 道试题，共56 分。
）1. LR（1）文法都是（C）。
A. 无二义性且无左递归B. 可能有二义性但无左递归C. 无二义性但可能是左递归D. 能够既有二义性又有左递归总分值：4 分2. 已知文法：S→aAa|aBb|bAb|bBaA→x B→x ，那么（A）。
A. LR(1)文法B. LALR（1）文法C. 都不是D. A和B总分值：4 分3. 语法分析程序输出（B ）。
A. 记号系列B. 分析树或语法树C. 中间代码D. 目标代码总分值：4 分4. 正规式（a|b）*表示的是（A ）。
A. 所有由字母a或b组成的串B. 字符串a|bC. 字符串（a|b）*D. 空串总分值：4 分5. （A ）的任务是从源代码中读取字符并形成由编译器的以后部份处置的逻辑单元——记号。
B. 语法分析程序C. 语义分析程序D. 源代码优化程序总分值：4 分6. 下面哪个文法是右递归的（A）A. A E→TE|TB. T→aTC. E→(E)D. E→a总分值：4 分7. 编译程序诸时期的工作往往是（D）。
A. 顺序B. 并行C. 成批D. 穿插总分值：4 分8. 在语法分析处置中，FIRST集合、FOLLOW集合、SELECT集合均是（B）。
A. 非终极符集B. 终极符集C. 字母表D. 状态集总分值：4 分9. Chomsky 概念的四种形式语言文法中，1 型文法又称为（C ）文法。
A. 短语文法B. 上下文无关文法C. 上下文有关文法总分值：4 分10. 标准规约是（A ）。
A. 最左规约B. 最右规约C. 动态规约D. 静态规约总分值：4 分11. 编译器与要编译的源程序的接口时期是（A ）。
A. 扫描程序B. 语法分析程序C. 语义分析程序D. 代码生成器总分值：4 分12. Chomsky 概念的四种形式语言文法中，2 型语言文法又称为（B ）文法。
A. 短语文法B. 上下文无关文法C. 上下文有关文法D. 正规文法总分值：4 分13. 假设文法G概念的语言是无穷集，那么文法必然是（D）。
2017秋17春北航《编译技术》在线作业一一、单选题（共14 道试题，共56 分。
）1. 下面哪个文法具有二义性（）。
A. A→AA | (A) |B. E→E＋T|TC. E→(E)D. E→a正确答案：2. Chomsky 定义的四种形式语言文法中，2 型语言文法又称为（）文法。
A. 短语文法B. 上下文无关文法C. 上下文有关文法D. 正规文法正确答案：3. 最常用的中间代码形式是（）。
A. 二元式B. 三元式C. 四元式D. 树形表示正确答案：4. 赋值语句X::=-(a+b)/(c-d)-(a+b*c)r的逆波兰表示是（）。
A. Xab+cd-/-bc*a+-:=B. Xab+/cd--bc*a+--:=C. Xab+-cd-/abc*+-:=D. Xab+cd-/abc*+--:=正确答案：5. 规范规约是（）。
A. 最左规约B. 最右规约C. 动态规约D. 静态规约正确答案：6. 如果r、s是正规式，则下面（）不一定是正规式。
A. rsB. r|sC. r*D. r+s正确答案：7. 目标代码生成属于编译器的（）阶段。
A. 词法分析B. 语法分析C. 分析D. 综合正确答案：8. 文法E→(E)产生的语言是（）。
A. 空集B. （）C. （E）D. ((((E))))正确答案：9. 编译器与要编译的源程序的接口阶段是（）。
A. 扫描程序B. 语法分析程序C. 语义分析程序D. 代码生成器正确答案：10. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。
A. 自左至右B. 自上而下C. 自下而上D. 自右向左正确答案：11. 在自下而上的语法分析方法中，分析的关键是（）。
A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式正确答案：12. 语法分析程序输出（）。
A. 记号系列B. 分析树或语法树C. 中间代码D. 目标代码正确答案：13. （）的任务是从源代码中读取字符并形成由编译器的以后部分处理的逻辑单元——记号。
在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对各位有些帮助。
一1、画出编译程序的总体结构图，简述其部分的主要功能。
[答案]编译程序的总框图见下图。
图编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。
语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间优化器对中间代码进行优化处理。
一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码目标代码生成器把中间代码翻译成目标程序。
中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。
编译程序各个阶段所产生的中间结果都记录在表格出错处理程序对出现在源程序中的错误进行处理。
如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。
编译程2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?[答案]计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。
像Basic之类的语言，属于解释型的高级语言。
它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读总而言之，是边翻译边执行。
像C，Pascal之类的语言，属于编译型的高级语言。
它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素。
[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V+。
1. 有限自动机有（）个接受状态A. 只能一个B. 只能两个C. 只能三个D. 0个、一个或多个该题参考选项是：D 满分：4 分2. 编译程序中语法分析器接收以（）为单位的输入。
A. 单词B. 表达式C. 产生式D. 句子该题参考选项是：A 满分：4 分3. 描述一个语言的文法是（）。
A. 唯一的B. 不唯一的C. 可能唯一D. 可能不唯一该题参考选项是：B 满分：4 分4. Chomsky 定义的四种形式语言文法中， 3 型文法又称为（）文法。
A. 短语文法B. 上下文无关文法C. 上下文有关文法D. 正规文法该题参考选项是：D 满分：4 分5. （）的任务是从源代码中读取字符并形成由编译器的以后部分处理的逻辑单元——记号。
A. 扫描程序B. 语法分析程序C. 语义分析程序D. 源代码优化程序该题参考选项是：A 满分：4 分6. 在编译时安排所有数据对象的存储单元的分配策略属于（）。
A. 静态分配策略B. 动态分配策略C. 栈式分配策略D. 堆分配策略该题参考选项是：A 满分：4 分7. 语法分析属于编译器的（）阶段。
A. 词法分析B. 语法分析C. 分析D. 综合该题参考选项是：C 满分：4 分8. 类型转换时，整数到实数的转换称为（）。
A. 截断B. 舍入C. 拓展D. 收缩该题参考选项是：C 满分：4 分9. 如果r、s是正规式，则下面（）不一定是正规式。
A. rsB. r|sC. r*D. r+s该题参考选项是：D 满分：4 分10. 正规式（a|b）*表示的是（）。
A. 所有由字母a或b构成的串B. 字符串a|bC. 字符串（a|b）*D. 空串该题参考选项是：A 满分：4 分11. 算符优先分析每次规约的是（）。
A. 最左短语B. 直接短语C. 句柄D. 最左素短语该题参考选项是：D 满分：4 分12. 有限自动机可以有（）个初始状态。
A. 一个B. 两个C. 三个D. 多个该题参考选项是：A 满分：4 分13. 一个文法所描述的语言是（）。
北航计算机学院编译习题讲解
习题课 (1-3章）
1、复习
2、习题讲解
北京航空航天大学计算机科学与工程系
2008年6月27日
1
第一章
概论
(介绍名词术语、了解编译系统的结构和编译过程）
北京航空航天大学计算机科学与工程系
2008年6月27日
2
1.2 编译过程
所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。
习惯上是将编译过程划分为5个基本阶段：词法分析语法分析语义分析、生成中间代码代码优化生成目标程序
北京航空航天大学计算机科学与工程系
2008年6月27日 3
典型的编译程序具有7个逻辑部分 S.P 词法分析程序符号表管理语法分析程序语义分析、生成中间代码代码优化生成目标程序 O.P 出错处理
北京航空航天大学计算机科学与工程系
2008年6月27日
4
第二章? 掌握符号串和符号串集合的运算、文法和语言的定义? 几个重要概念：递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。
? 掌握文法的表示：BNF、扩充的BNF范式、语法图。
? 了解文法和语言的分类
北京航空航天大学计算机科学与工程系
2008年6月27日 5
第三章:词法分析
3.1 词法分析的功能 3.2 词法分析程序的设计与实现
–状态图
3.3 词法分析程序的自动生成
–有穷自动机、LEX
北京航空航天大学计算机科学与工程系
2008年6月27日
6
补充
正则文法正则文法 1 2 4 NFA NFA 3 DFA DFA 最小化
北京航空航天大学计算机科学与工程系
2008年6月27日 7
5 6 正则表达式正则表达式
习题1－3章
北京航空航天大学计算机科学与工程系
2008年6月27日
8
第一章
2．典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？
北京航空航天大学计算机科学与工程系
2008年6月27日
9
1.2 编译过程
所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。
习惯上是将编译过程划分为5个基本阶段：词法分析语法分析语义分析、生成中间代码代码优化生成目标程序
北京航空航天大学计算机科学与工程系
2008年6月27日 10
典型的编译程序具有7个逻辑部分 S.P 词法分析程序符号表管理语法分析程序语义分析、生成中间代码代码优化生成目标程序 O.P 出错处理
北京航空航天大学计算机科学与工程系
2008年6月27日
11
P19：4.试证明：A+ =AA*=A*A 证：∵ A*=A0∪A+，A+=A1∪A2∪…∪An∪… 得：A*=A0∪A1∪A2∪…∪An∪… ∴ AA*=A（A0∪A1∪A2∪…∪An∪…）= AA0∪AA1∪AA2∪…∪A An∪… =A∪A2∪A3∪An +1∪… = A+ 同理可得：A*A =(A0∪A1∪A2∪…∪An∪…)A =A0 A∪A1A∪A2A∪…∪AnA∪… = A∪A2∪A3∪An+1∪… = A+ 因此： A+ =AA*=A*A
北京航空航天大学计算机科学与工程系
2008年6月27日 12
P26:1.设G[〈标识符〉]的规则是：〈标识符〉::=a|b|c| 〈标识符〉a|〈标识符〉c| 〈标识符〉0|〈标识符〉1 试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。
解：VT ={a,b,c,0,1}， VN ={〈标识符〉} (1) 不能推导出ab0,11,0a (2)〈标识符〉=>a (3)〈标识符〉=>〈标识符〉1 =>〈标识符〉01 =>〈标识符〉c01 =>〈标识符〉0c01 => a0c01 (4)〈标识符〉=>〈标识符〉a =>〈标识符〉aa =>aaa 2008年6月27日北京航空航天大学计算机科学与工程系
13
P26： 2．写一文法，其语言是偶整数的集合
常见错误： 1.终结符集中没有奇数。
2.如下定义：<偶整数> => <数字串> <偶数字>， <数字串> => <数字> | <数字串> <数字> <数字串>不能=>ε。
3.忽略负偶数。
北京航空航天大学计算机科学与工程系
2008年6月27日
14
作法一：<偶整数>::=2×<整数> <整数>::=<数字串><数字> <数字串>::=<数字> <数字>::=0|1|2|3|4|5|6|7|8|9 作法二：z=偶整数G(z)=0|2|2Z|2(Z+1)|2(Z-1) 或：G(Z)=0|2|Z+2|Z-2
北京航空航天大学计算机科学与工程系
2008年6月27日
15
解：G[<偶整数>]：<偶整数>::= <符号> <偶数字>| <符号><数字串><偶数字> <符号> ::= + | —|ε <数字串>::= <数字串><数字>|<数字> <数字> ::= <偶数字>| 1 | 3 | 5 | 7 | 9 <偶数字> ::=0 | 2 | 4 | 6 | 8
3. 写一文法，使其语言是偶整数的集合，但不允许有以0 开头的偶整数。
北京航空航天大学计算机科学与工程系
2008年6月27日
16
4.
设文法G的规则是：
〈A〉::=b| cc 试证明：cc, bcc, bbcc, bbbcc∈L[G] 证：（1）〈A〉=>cc （2）〈A〉=>b〈A〉=>bcc （3）〈A〉=>b〈A〉=>bb〈A〉=>bbcc （4）〈A〉=>b〈A〉=>bb〈A〉=>bbb〈A〉=>bbbcc 又∵cc, bcc, bbcc, bbbcc∈Vt* ∴由语言定义，cc, bcc, bbcc, bbbcc∈L[G]
北京航空航天大学计算机科学与工程系
2008年6月27日
17
5 试对如下语言构造相应文法：（1）{ a(bn)a | n=0,1,2,3,……},其中左右圆括号为终结符。
（2） { （an）（bn）| n=1,2,3,……} 解：（1）文法[G〈S〉]：S::= a(B)a B::= bB |ε ( 2 ) 文法[G〈S〉]：--错了，两个n不等 S ::= (A)(B) S ::= (B) A::= aA|a B::= aBb|a)(b B::= bB|b
北京航空航天大学计算机科学与工程系
2008年6月27日 18
7.对文法G3[〈表达式〉] 〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉〈因子〉::=（〈表达式〉）| i 列出句型〈表达式〉+〈项〉*〈因子〉的所有短语和简单短语。
<表达式> => <表达式> + <项> => <表达式> + <项> * <因子> <表达式> + <项>
<表达式>
<项> * <因子> 短语有：〈表达式〉+〈项〉*〈因子〉和〈项〉*〈因子〉简单短语是：〈项〉*〈因子〉
北京航空航天大学计算机科学与工程系
2008年6月27日 19。
