编译原理 清华大学出版社 习题参考答案 ppt课件

❖ 知识就是财富 ❖ 丰富你的人生
71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚持意志伟大的事业需要始终不渝的精神。——伏尔泰 74、路漫漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非
编译原理 清华大学出版社 习题参考答案
56、死去何所道，托体同山阿。 57、春秋多佳日，登高赋新诗。 58、种豆南山下，草盛豆苗稀。晨兴 理荒秽 ，带月 荷锄归 。道狭 草木长 ，夕露 沾我衣 。衣沾 不足惜 ，但使 愿无违 。 59、相见无杂言，但道桑麻长。 60、迢迢新秋夕，亭亭月将圆。

谢谢你的阅读

37、我们唯一不会改正的缺点是软弱。——拉罗什福科
xiexie! 38、我这个人走得很慢，但是我从不后退。——亚伯拉罕·林肯
39、勿问成功的秘诀为何，且尽全力做你应该做的事吧。——美华纳
40、学而不思则罔，思而不学则殆。——孔子
编译原理 清华大学出版社 习题参考
•
26、我们像鹰一样，生来就是自由的 ，但是 为了生 存，我 们不得 不为自 己编织 一个笼 子，然 后把自 己关在 里面。 ——博 莱索
•
27、法律如果不讲道理，即使延续时 间再长 ，也还 是没有 制约力 的。— —爱·科 克
•
28、好法律是由坏风俗创造出来的。 ——马 克罗维 乌斯
•
29、在一切能够接受法律支配的人类 的状态 中，哪 里没有 法律， 那里就 没有自 由。— —洛克
•
30、风俗可以造就法律，也可以废除 法律。 ——塞·约翰逊里。——西班牙

第5题
PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。
（１）INT 0 A
（２）OPR 0 0
（３）CAL L A
答案：
PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操作说明如下：
或者：允许0开头的非负整数？
第３题
为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：
G[S]:
S->S+D|S-D|D
D->0|1|2|3|4|5|6|7|8|9
第4题
已知文法G[Z]：
Z→aZb|ab
写出L(G[Z])的全部元素。
答案：
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
第6题
已知文法G：
<表达式>::=<项>｜<表达式>＋<项>
<项>::=<因子>｜<项>*<因子>
<因子>::=（<表达式>）｜i
试给出下述表达式的推导及语法树。
（５）i+(i+i)
（６）i+i*i
答案：
(5) <表达式>
=><表达式>＋<项>
n n
L(G[Z])={a b |n>=1}
第5题写一文法，使其语言是偶正整数的集合。要求：

• •
7
第 16题
• • 给出生成下述语言的三型文法： • (3){anbmck|n,m,k>=0 } • • 答案： • • (3) • A→aA|B • B→bB|C • C→cC|ε •
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
• 为只包含数字、加号和减号的表达式，例 如9-2＋5，3-1，７等构造一个文法。
•
•
•
ห้องสมุดไป่ตู้
•
•
•
•
1
2
3
第 11 题
•
• 令文法 G[E]为：
• E→T|E+T|E-T
• T→F|T*F|T/F
• F→(E)|i
• 证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
•
• 答案：
•
• 此句型对应语法树如右，故为此文法一个句型。
• 或者：因为存在推导序列: E=>E+T=>E+T*F，所
• 以 E+T*F句型
• 此句型相对于 E 的短语有:E+T*F； 相对于 T 的短语
• 有 T*F
• 直接短语为：T*F
•
句柄为：T*F
•
•
•
•
4
5
6
第 14题
• • 给出生成下述语言的上下文无关文法： • （1）{ anbnambm| n，m>=0} • • 答案： • （１） • S→AA • A→aAb|ε

答案： PL/0 语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储
管理。（数组 CODE 存放的只读目标程序，它在运行时不改变。）运行时的数据区 S 是由解 释程序定义的一维整型数组，解释执行时对数据空间 S 的管理遵循后进先出规则，当每个 过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。 应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。
RA 的用途说明如下： T： 栈顶寄存器 T 指出了当前栈中最新分配的单元(T 也是数组 S 的下标)。 B：基址寄存器，指向每个过程被调用时，在数据区 S 中给它分配的数据段起 始 地址，
也称基地址。 SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，
用以引用非局部（包围它的过程）变量时，寻找该变量的地址。 DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放
广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是 边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源 程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来 完成，即只翻译不执行。
）
第4题
对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代 码生成）报告的。 （1） else 没有匹配的 if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符
CAL L A 调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址 寄存器 B 中，目标程序的入口地址 A 的值送指令地址寄存器 P 中，使指令从 A 开始执 行。 第6题

( *， y，
( +， x，
20
10.0， t1 )
t1， A )
目标代码生成
•任务：把中间代码变换成特定机器上 的绝对指令代码或可重定位的指令代 码或汇编指令代码。
•特点：与硬件系统结构和指令含义有 关，涉及到硬件系统功能部件的运用、 机器指令的选择、各种数据类型变量 的存储空间分配以及寄存器和后缓寄 存器的调度等。
21
A := x + y * 10 ( *， y， 10.0， t1 )
( +， x， MOVF
MULF MOVF
t1， y,
10.0, x,
A ) R2
R2 R1
ADDF
MOV
R1,
R1,
R2
A
22
符号表管理 • 符号表用来记录源程序中出现的标识符， 并收集每个标识符的各种属性信息。 • 符号表是由若干记录组成的数据结构，每 个标识符在表中有一条记录，每条记录有 多个域，每个域记载标识符的一个属性。
高级语言：使用便于理解的自然语言。
6
语言处理程序
• 解释程序（器）：接受某种语言源程序，然后直接解释执行 源程序。
源程序 (高级语言 ) 初始数据
解释程序 计算结果 计算机
解释程序解释执行过程的示意图
7
•编译程序（器）：接受某种语言的源语言程序后，
将它改造成另一种逻辑上等价的目标语言程序。
高级语言程序 (源程序 )
17
中间代码生成
将源程序生成一种内部表示形式，这种内部表 示形式叫中间代码。 中间代码：一种结构简单、含义明确的记号系统。 原则：
•容易生成；
•容易将它翻译成目标代码。
如四元式：

第６题
计算机执行用高级语言编写的程序有哪些途径它们之间的主要区别是什么
答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。 像 Basic 之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语
言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一 条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反 复。
第2题
若 PL/0 编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分 别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句 b∶ =10 时运行 栈的布局示意图。 var x,y; procedure p; var a; procedure q; var b; begin (q) b∶ =10; end (q); procedure s; var c,d; procedure r; var e,f; begin (r) call q; end (r); begin (s) call r; end (s); begin (p) call s;
（2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符
答案： （1） 语法分析 （2） 语义分析 （3） 语法分析 （4） 词法分析
第5题
编译程序大致有哪几种开发技术
答案：
（1） 自编译：用某一高级语言书写其本身的编译程序。 （2） 交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。 （3） 自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的
第6题
给出对 PL/0 语言作如下功能扩充时的语法图和 EBNF 的语法描述。 (1) 扩充条件语句的功能使其为： if〈条件〉then〈语句〉[else〈语句〉] (2) 扩充 repeat 语句为： repeat〈语句〉{；〈语句〉}until〈条件〉

(a) 请指出此文法的终结符号, 非终结符号和开始符号. 终结符号: or, and, not, (, ), true, false 非终结符号: bexpr, bterm, bfactor 开始符号: bexpr
10
(b) 试对于句子 not ( true or false) 构造一棵分析树.
bexpr bterm bfactor not bfactor
a S b S
(d) 此文法产生的语言是什么?
由相同个数的a和b组成的字符串.
9
1.3 考虑文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | ( bfactor ) | true | false
(a) 0 ( 0 | 1)* 0 由0和1组成且以0开始和结束的符号串全体.
(b) ( ( | 0 ) 1* ) * 由0和1组成的符号串全体.
(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1) 由0和1组成且以000,001,010或011结束的符号串全体. 长度大于等于3且倒数第3个字符为0的01符号串全体.
16
3.4 对于下列语言分别写出它们的正规表达式:
(a) 英文字母组成的所有符号串, 要求符号串中顺序包含 五个元音字母. 令letter={非元音的英文字母} letter* (a|A) letter* (e|E) letter* (i|I) letter* (o|O) letter* (u|U) letter*
18
(e) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个0和1的由0和1组成的符号串全体. 即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E1E|E0E1E0E

它是源程序的一种内部表示形式。 设计中间代码的原则：一是容易生成，二是
容易翻译成目标代码。 常用的中间代码有三地址码、四元式、三元
式、间接三元式、逆波兰表示（后缀式）、 树形表示等。
14
中间代码：四元式
例： id1:=id2+id3*10
sum:=first+count*10 翻译为四元式中间代码的形式：
5
1.2 编译程序的工作过程与结构
一个编译程序的整个工作过程是划分成阶段 进行的，每个阶段将源程序从一种表示形式 转换成另一种表示形式。
编译阶段的典型划分方法是划分为5个基本阶 段：词法分析、语法分析、语义分析产生中 间代码、代码优化、代码生成。
掌握编译过程的5个基本阶段，是学习编译原 理课程的基本内容。
29
自编译：T形图表示
PASCAL2
A代码
PASCAL2
A代码
PASCAL1 PASCAL1
A代码 A代码
用PASCAL1语言 编写的功能更
强的PASCAL2语 言编译程序的
Ａ代码
已有的PASCAL1 语言的编译程序
自编译得到
功能更强的
PASCAL2语言 的编译程序
源程序
注意：T形图的组合规则：① ②
Java语言的操作平台无关性的实现就是如此。
26
1.3 编译程序的开发
构造编译程序，可以：
1. 使用机器语言或汇编语言作工具构造 2. 使用高级语言作工具构造 3. 使用机器语言或汇编语言构造编译程序的核心
部分，使用高级语言构造编译程序的扩充部分 4. 使用编译程序自动生成工具构造
使用高级语言作工具构造编译程序可以大大节 省程序设计的时间，并且编译程序易于阅读、 维护和移植。

自底向上的语法分析是从输入的字符串出发，逐步将其归约为文法的起始符号。
自底向上的语法分析通常采用LR(0)、SLR(1)、LALR(2)等算法。
自底向上的语法分析可以检测出输入的字符串是否符合语言的语法规则，并生成相应的语法结构。
01
02
03
自底向上的语法分析
语法分析的算法和数据结构
语法分析的算法包括预测分析法、移位/归约法、LR(0)、SLR(1)、LALR(2)等。
三地址代码的生成
对三地址代码进行优化可以提高目标代码的执行效率，常见的优化技术包括常量折叠、死代码删除、循环展开等。
三地址代码的优化
循环优化
循环是程序中常见的结构之一，对循环进行优化可以提高程序的执行效率。常见的循环优化技术包括循环展开、循环合并、循环剪枝等。
要点一
要点二
死代码删除
死代码是指程序中永远不会被执行的代码，删除这些死代码可以减小目标代码的大小并提高程序的执行效率。
习题及答案解析
词法分析习题及答案解析
题目
给定一个字符串，判断它是否是合法的标识符。
答案解析
合法的标识符必须以字母或下划线开头，后面可以跟字母、数字或下划线。
题目
给定一个字符串，判断它是否是关键字。
答案解析
关键字是编程语言中预定义的保留字，不能用作标识符。例如，在C语言中，关键字包括`int`, `float`, `if`, `else`等。
答案解析
上下文无关文法是一种形式文法，它的产生式右部不依赖于左部的任何符号。这意味着产生式右部是一个终结符或一个非终结符的序列。
题目
给定一个抽象语法树，判断它是否是二叉树。
答案解析
抽象语法树是源代码的树形表示，每个节点表示源代码中的一个结构。如果一个抽象语法树中的每个节点最多有两个子节点，则它是二叉树。