当前位置：文档库 › 第三章编译原理典型习题

第三章编译原理典型习题

例题3.1 是非题

1．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）

2．对任何正则表达式e，都存在一个NFA M，满足L(M)=L(e) （）

（北京航天航空大学2000年研究生入学试题）

3．对任何正则表达式e，都存在一个DFA M，满足L(M)=L(e) （）

（北京航天航空大学2000年研究生入学试题）

分析

1．转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符或字符串）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符串。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。由上述转换图的定义知道，转换图只能有一个初态，但至少要有一个终态，这说明转换图可以有多个终态，因此本题错。

2．正规式和有限自动机的等价性：：⑴对任何FA M，都存在一个正规式r，使得L(r)=L(M)；⑵对任何正规式r，都存在一个FA M，使得L(M)=L(r)。

因此对任何正则表达式e，都存在一个NFA M，满足L(M)=L(e)。

所以本题正确。

3．根据上题以及确定有限自动机和非确定有限自动机之间的等价性，可以知道本题正确。

例题3.2 填空题

1．词法分析器输出的单词符号常常表示成如下二元式：（）。

2．一张转换图只包含有限个状态，其中有一个被认为是（）态，而且实际上至少要有一个（）态。

3．词法分析器的任务是（）。

解答

1．词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）

2．一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是（初）态，而且实际上至少要有一个（终）态（用双圈表示）

3．词法分析器的功能是（输入源程序，输出单词符号）。

例题3.3 简答题

1．何谓扫描器？扫描器的功能是什么？

（国防科大研究生院2001年硕士生入学考试）

2．试简述有穷状态自动机与正则表达式的等价性概念。

（南京大学2000年硕士研究生入学考试）

3．给出有限状态自动机的严格定义。

（浙江大学1998年硕士研究生入学考试试题）

解答

1．扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。

一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。

词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。

2．∑上的非确定有限自动机M所能识别字的全体L（M）是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L（M）。

3．有限状态自动机分为确定有限状态自动机和非确定有限状态自动机两类，确定有限自动机是非确定有限自动机的特例，但它们具有相同的表示能力。给出有限状态自动机的定义实际上只需要给出非确定有限状态自动机的定义就可以了：

一个有限状态自动机（NFA）M是一个五元式

M=(S, ∑, δ, S

, F)

其中

1. S是一个有限集，它的每个元素称为一个状态；

2. ∑是一个有穷字母表，它的每个元素称为一个输入字符；

3. δ是一个从S×∑*到S的子集的映照，即

δ：S×∑*→2S

4. S

?S，是一个非空初态集；

5. F?S，是一个终态集（可空）。

例题3.4 选择题

1．______不是NFA的成分。

A.有穷字母表

B.初始状态集合

C.终止状态集合

D.有限状态集合

（北京航天航空大学2000年研究生入学考试试题）

2．______不是编译程序的组成部分。

A.词法分析程序

B.代码生成程序

C.设备管理程

序 D.语法分析程序（北京航天航空大学2000年研究生入学考试试题）

分析

1．分析NFA的5个组成部分：S是一个有限状态集合，∑是一个有穷字母表，δ

?S是一个非空初态集，是一个从S×∑*到S的子集的映照，即δ：S×∑*→2S，S

F?S是一个终态集（可空）。从字面上看，似乎A、B、C、D四个选项都是NFA 的组成部分，但仔细分析，就会发现B：初始状态集合和NFA中定义的S

有区别，

是非空初态集，而初始状态集合却只是一个集合，可以是一个可空的集合。另0

外三个选项都和NFA中的定义一致，因此本题的选择为B。

2．查看编译程序的结构图，编译程序由以下7个部分组成：词法分析器、语义分析器、语义分析及中间代码生成器、优化段、目标代码生成器以及表格管理模块和出错处理模块。由此可以看出A、B、D所描述的都是编译程序的一个部分，但C设备管理程序，它所描述的是操作系统的一部分，在操作系统中负责各种外设的管理，和编译程序没有关系，因此本题的答案是C。

编译原理(清华大学第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．

短语：直接短语：句柄： 13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法：S → ABS S → Aa S →ε A → a B → b (3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语： a1 , b1 , b2, a2 , , 句柄：a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

编译原理作业集第七章

第七章语义分析和中间代码产生本章要点 1. 中间语言，各种常见中间语言形式； 2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译； 3. 过程调用的处理； 4. 类型检查；本章目标掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。本章重点 1．中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示； 3．赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式； 4．各种控制流语句的翻译及其中间代码格式； 5．过程调用的中间代码格式； 6．类型检查；本章难点 1. 各种语句的翻译； 2. 类型系统和类型检查；作业题一、单项选择题： 1. 布尔表达式计算时可以采用某种优化措施，比如A and B用if-then-else可解释为_______。 a. if A then true else B； b. if A then B else false； c. if A then false else true； d. if A then true else false； 2. 为了便于优化处理，三地址代码可以表示成________。 a. 三元式 b. 四元式 c. 后缀式 d. 间接三元式 3. 使用三元式是为了________：

a. 便于代码优化处理 b. 避免把临时变量填入符号表 c. 节省存储代码的空间 d. 提高访问代码的速度 4. 表达式-a+b*(-c+d)的逆波兰式是________。 a. ab+-cd+-*； b. a-b+c-d+*； c. a-b+c-d+*； d. a-bc-d+*+； 5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。 a. xab+cd-/-bc*a+-:=；a. xab+/cd-bc*a+--:=；a. xab+-cd-/abc*+-:=；a. xab+cd-/abc*+--:=； 6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。 a. 抽象语法树； b. 语法规则； c. 依赖图； d. 三地址代码； 7. 按照教材中的约定，三地址语句if x relop y then L表示成四元式为。 a. (relop，x，y，L)； b. (relop，L，x，y)； c. (relop，x，L，y)； d. (L，x，y，relop)； 8. 在编译程序中，不是常见的中间语言形式。 a.波兰式； b. 三元式； c. 四元式； d. 抽象语法树； 9. 在编译程序中安排中间代码生成的目的是________。 a. 便于提高编译效率； b. 便于提高分析的正确性； c. 便于代码优化和目标程序的移植； d.便于提高编译速度； 10. 按照教材中的约定，下面不是类型表达式： a. boolean； b. type-error； c. real； d. DAG； 11. 一个Pascal函数 function f ( a, b:char ) :↑integer; …… 其作用域类型是： a. char×integer； b. char×char； c. char×pointer(integer)； d. integer×integer； 12. 因为标识符可用于多种情况，比如常量标识符、变量标识符、过程标识符等等。因此，在符号表中为了给出各个符号的标志，常给标识符引入一个属性kind，然后在相应产生式的语义动作中添加给kind属性赋值的语句。比如，在在产生式D id:T的语义动作中添加赋值语句id.kind=。 a. V AR； b. CONSTANT； c. PROC； d. FUNC； 13. 下面情况下，编译器需要创建一张新的符号表。 a. 过程调用语句； b. 标号说明语句； c. 数组说明语句； d.记录说明语句； 14. 函数function f(a,b:char):↑integer;… 所以f函数的类型表达式为： a. char×char→pointer(integer)； b. char×char→pointer； c. char×char→integer； d. char×char→integer (pointer) 15. 如果一个语言的编译器能保证编译通过的程序，在运行时不会出现类型错误，则称该语言是。 a. 静态的； b. 强类型的； c. 动态的； d. 良类型的；一．答案：1. b；2. d；3. b；4. d；5. c；6. c.；7. a；8. a；9. c；10. d；11. b；12. a；13. d； 14. a；15. b；

编译原理各章习题

第二章高级语言及其语法描述 1、设有文法G[S]： S→N N→D|ND D→0|1|2|…|9 试写出028和4321的最左推导和最右推导过程。 2、证明文法G[S]是二义性文法： S→if E then S else S |if E then S |s E→0|1 3、设有文法G[E]： E→E-T|T T→T/F|F F→i|(E) （1）试写出i/(i-i-i)的推导树。（2）试写出（F-i）/F的短语、简单短语和句柄。 4、设∑={0,1}，请给出∑上下列语言的文法（1）所有以0开头的串（2）所有以0开头，以1结尾的串 5、证明文法G1和G2等价 G1：S→0S1，S→01 G2：A→0R，A→01，R→A1 第三章有限状态自动机和词法分析 1、请用中文描述下列正规式表示的正规集（1）0(0|1)*0 （2）0*10*10*10* 2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。（2）恰含有3个1的所有符号所组成的集合。（3）集合{01，1}。

（4）所有以111结束的符号串。 3、试写出∑＝{0，1}上下述集合的正则表达式：（1）试写出非负整数集的正则表达式。（2）试写出以非5数字为头的所有非负整数集的正则表达式。 4、试将图3.1中所示的有限状态自动机M 最小化。图3.1 M 的状态转换图 5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态自动机：（1）a(a|b)*baa （2）(a|b)*bbb * 6、对于下列的状态转换矩阵：（1）分别画出相应的状态转换图。（2）用自然语言分别描述它们所识别的输入串的特征 7、将图3.2所示的非确定的有限状态自动机确定化和最小化。图3.2 非确定的有限状态自动机M 第四章自顶向下语法分析 1、从下列文法中消去左递归。

编译原理_第三版_课后答案

编译原理课后题答案第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F 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 E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:

编译原理复习题及答案

编译原理复习题及答案一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba

编译原理第1阶段练习题及答案,这是其中一个阶段共3个阶段。答案在后面

江南大学网络教育第一阶段练习题及答案，这是其中一个阶段共3个阶段。答案在后面考试科目:《编译原理》第章至第章（总分100分） __________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题 (共4题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。) 1. 若一个文法是递归的，则它所产生的语言的句子是（）。（5 分） A. 无穷多个 B. 有穷多个 C. 可枚举的 D. 个数是常量 2. 文法G[A]：A→ε A→aB B→Ab B→a是（）。（5 分） A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 3. 词法分析器的输入是（）。（5 分） A. 单词符号串 B. 源程序 C. 语法单位 D. 目标程序 4. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（）。（5 分） A. 句子 B. 句型 C. 单词 D. 产生式二填空题 (共2题，总分值10分 ) 5. 编译程序的功能可以分解为词法分析、语法分析、__________、中间代码生成、中间代码优化、目标代码生成。（5 分） 6. 微小语言Micro的单词有下面的几种：标识符、__________、实常数、保留字、__________、换行符。（5 分）

三简答题 (共2题，总分值20分 ) 7. 给出与正规式R＝1(0|1)*101等价的NFA。（10 分） 8. 写出下面程序经词法分析后的TOKEN表示。 begin var X:real; var J:integer; read(J); J:=J+(J*20); X:=J-1; Write(2*J+X) End（10 分）四综合计算题 (共2题，总分值50分 ) 9. 已知文法G(S) S→a| (T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的归约规则和句柄。（25 分）10. 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→（E）|i ①该文法的开始符号（识别符号）是什么？ ②请给出该文法的终结符号集合 Vt 和非终结符号集合 Vn 。 ③找出句型 T+T*F+i 的所有短语、简单短语和句柄。（25 分）

编译原理教程课后习题答案——第七章

第七章目标代码生成 7.1 对下列四元式序列生成目标代码： T=A-B S=C+D W=E-F U=W/T V=U*S 其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。【解答】简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。汇编语言的加法指令代码形式为 ADD R, X 其中，ADD为加法指令；R为第一操作数，第一操作数必须为寄存器类型；X为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X指令的含意是：将第一操作数R与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令： MOV R, a ADD R, b MOV T, R 第一条指令是将第一操作数a由内存取到寄存器R中；第二条指令完成加法运算；第三条指令将累加后的结果送回内存中的变量T。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点)来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下： (1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。 (2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。因此，本题所给四元式序列生成的目标代码如下： MOV R0, A SUB R0, C /*R0=T*/ MOV R1, C ADD R1, D /*R1=S*/ MOV S, R1 /*S引用点较T引用点远，故将R1的值送内存单元S*/ MOV R1, E SUB R1, F /*R1=W*/ SUB R1, R0 /*R1=U*/ MUL R1, S /*R1=V*/ 7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本

编译原理课后习题答案-清华大学-第二版

第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功

哈工大编译原理习题及答案

1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。第一章习题解答 1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。 2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。 5.略第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。

各章练习题(编译原理)

第三章复习重点：1.文法与语言的对应关系思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1 = {a x b2x c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。提示：该题实际上要求为相应语言设计上下文无关文法。一个文法设计好后，严格来说应当证明此文法是否对应于该语言。解：G[S]：S →AB A →ε | aAbb B →ε | cB 推导过程： S ? AB +? a x Ab2x B /*使用A →aAbb x次*/ ? a x b2x B /*使用A →ε一次*/ ? a x b2x c x B /*使用B →cB x次*/ ? a x b2x c x/*使用B →ε一次*/ 举一反三：已知语言L2 = {a x b2y c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。解：G[S]：S →AB A →ε | aA B →ε | bBcc 练习：14：写出下列语言对应的文法 (1).{a n b n a m b m|n,m≥0}

2. {1n 0m 0m 0n |n,m ≥0} 3. {1n 0m 0m 0n |n ≥0,m>0} 4. { a n b m c k |n,m,k ≥0} G1: S —>AA G2: S —>AB A —>aAb|ε A —>aAb|ε B —>aBb|ε G: S —>1S0 S —>A A —>0A1 A —>ε G: S →1S0|A S →1S0|0A1 A →0A1|01 A →0A1|ε 2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。 1. 令文法G ［E ］为： Z →bMb M →a|(L L →Ma ） ① 符号串b(Ma)b 是否为该文法的一个句型，并证明。 ② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。 1）（5分）证明：S=> bMb=>b(Lb=>b(Ma)b 所以，符号串b(Ma)b 是该文法的一个句型。（2）（5分）短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma) 练习：（10分）已知文法G[T]： T →T*F | F ；F →F ↑P | P ； P →(T) | i （1）用最右推导法证明β：T*P ↑(T*F) 是G[T]的一个句型；（2）画出β的语法树；（3）写出β的全部短语、直接短语和句柄。 (1) T=>T*F=>T*F ↑P=>T*F ↑(T)=> T*F ↑(T*F) =>T*P ↑(T*F) 证毕。 (2) 如图 T T * F F ↑ P P T * T F ( ) 第3题语法树（3）短语：T*P ↑(T*F) ；P ↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P

编译原理教程课后习题答案——第四章

第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {print″1″} A→(B {print″2″} A→a {print″3″} B→Aa) {print″4″} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L

编译原理第七章练习题

第7节习题一、单项选择题 1、中间代码生成所依据的是。 a.语法规则 b.词法规则 c.语义规则 d.等价变换规则 2、四元式之间的联系是通过实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 3、后缀式ab+cd+/可用表达式来表示。 a.a+b/c+d b.(a+b)/(c+d) c.a+b/(c+d) d.a+b+c/d 4、表达式（┓A∨B）∧（C∨D）的逆波兰表示为。 a. ┓AB∨∧CD∨ b. A┓B∨CD∨∧ c. AB∨┓CD∨∧ d. A┓B∨∧CD∨ 5 所对应的表达式为。 a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D) 6、四元式表示法的优点为。 a.不便于优化处理，但便于表的更动 b.不便于优化处理，但节省存储空间 c.便于优化处理，也便于表的更动 d.便于表的更动，也节省存储空间 7、终结符具有属性。 a.传递 b.继承 c.抽象 d.综合解答 1、选c。 2、四元式之间的联系是通过临时变量实现的，故选b。 3、选b。 4、选b。 5、选d。 6、四元式表示法的优点与间接三元式相同，故选c。 7、选d。二、多顶选择题 1、中间代码主要有。 a．四元式b．二元式c．三元式d．后缀式e．间接

三元式 2、下面中间代码形式中，能正确表示算术表达式a+b+c 的有。 a ．ab+c+ b ．abc++ e ．a+b+c 3、在下面的语法制导翻译中，采用拉链-回填技术。 a ．赋值语句 b ．goto 语句 c ．条件语句 d ．循环语句 4、下列中间代码形式有益于优化处理。 a ．三元式 b ．四元式 c ．间接三元式 d ．逆波兰表示法 e ．树形表示法 5、在编译程序中安排中间代码生成的目的是。 a ．便于进行存储空间的组织 b ．利于目标代码的优化 c ．利于编译程序的移植 d ．利于目标代码的移植 e ．利于提高目标代码的质量 6、下面的中间代码形式中，能正确表示算术表达式 a ．ab+c* b ．abc*+ c ．a+b*c 7、三地址代码语句具体实现通常有表示方法。 a ．逆波兰表示 b ．三元式 c ．间接三元式 d ．树形表示 e ．四元式解答 1、选a 、c 、d 、e 。 2、b 、d 的中间代码不能正确表示a+b+c ，而e 不是中间代码：故选a 、c 。 3、凡涉及到跳转的语句都需要采用拉链——回填技术，故选 b 、c 、d 。 4、选b 、c 。 5、选b 、d 。 6、选b 、e 。 7、选b 、c 、e 。

编译原理课后习题答案+清华大学出版社第二版

第 1 章引论第1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

编译原理：学习指导与典型题解析

(1)——不是NFA的成分o A．有穷字母表B．初始状态集合 c．终止状态集合D．有限状态集合 (北京航天航空大学研究生入学考试试题 (2)——不是编译程序的组成部分0 A．词法分析程序B．代码生成程序 c．设备管理程序D．语法分析程序 (北京航天航空大学研究生入学考试试题解答 (1)B，(2)C 例题2．2 给出下面描述的正规表达式 (1)以0l结尾的二进制数串； (2)能被5整除的十进制整数； (3)包含奇数个t或奇数个0的二进制数串解题思路 (1)分析题意，要求的是二进制串，即由0和1构成的串，并且必须以ot结尾，所以本题可以分两部分去完成，一部分实现由o和1构成的任意串，一部分即01，然后将它们连接到一起就可以了，所以本题的解答是：(1|0)*01 (2)分析题意，本题要求是十进制整数，也就是由o09这10个数字组成的字符串，并且不能以o开头(整数“o”除外)，要求能被5整除，则该串必须以0或者5结尾0根据我们的分析，可以把本题分成两种情况考虑：一种情况是该整数只有1位，则该整数有0 和5两种可能；另外一种情况是该整数有多位，则该整数可以分成3部分考虑，一是第l 位必须不为0，二是最后1位必须为0或5，三是中间部分可有可无，并且可以由0…9之间任意数字构或，所以本题的正规表达式为：(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5)| (0|5) (3)本题求二进制串，并且要求包含奇数个0或奇数个1，由于o和1都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得0考虑包含奇数个0的字符串：由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第1段为二进制串的开始到第1个0为止，这一段包含1个o，并且0的前面有0个或多个l，对于剩下的二进制串按照每段包含两个0的方式去划分，即以o开始，以0结尾，中间可以有0个或多个1，如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串(这些全1串在前面划分的串之间或最后)，则该二进制串就具有奇数个o，所以该二进制串可以这样描述：以第1段(1‘o)开始．后面由全1串(1‘)以及包含两个o的串(ol0o)组成，所以包含奇数个0的正规表达式为：100(1[ol’o]‘，本题的解答则是：1*0(1|01*0)*|0*1(0|10*1)*