第一章 编译程序概述
1.1 什么是编译程序
编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。
1.2编译过程概述和编译程序的结构
编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。图1.3表示了编译的各个阶段。
| 图1.3 编译的各个阶段 |
|
|
1.3 高级语言解释系统
为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。右面的图示意了它的工作机理
第二章：PL/0编译程序
问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。
答: PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。
问答第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; end (p); begin (main) call p; end (main).
答 ： 程序执行到赋值语句b∶=10时运行栈的布局示意图为：
|
|
问答第3题
写出题2中当程序编译到r的过程体时的名字表table的内容。
| name |
kind |
level/val |
adr |
size |
|
|
|
|
|
|
答 题2中当程序编译到r的过程体时的名字表table的内容为：
| name |
kind |
level/val |
adr |
size |
|
| x |
variable |
0 |
dx |
|
|
| y |
variable |
0 |
dx+1 |
|
|
| p |
procedure |
0 |
过程p的入口（待填） |
5 |
|
| a |
variable |
1 |
dx |
|
|
| q |
procedure |
1 |
过程q的入口 |
4 |
|
| s |
procedure |
1 |
过程s的入口（待填） |
5 |
|
| c |
variable |
2 |
dx |
|
|
| d |
variable |
2 |
dx |
|
|
| r |
procedure |
2 |
过程r的入口 |
5 |
|
| e |
variable |
3 |
dx |
|
|
| f |
variable |
3 |
dx+1 |
|
|
注意：q和s是并列的过程，所以q定义的变量b被覆盖。
问答第4题
指出栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途。
答 ： 栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途说明如下：
T： 栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。
B：基址寄存器，指向每个过程被调用时，在数据区S中给它分配的数据段起始 地址，也称基地址。
SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。
DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。
RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。
在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL， RA。
问答第5题
PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。
· INT 0 A
· OPR 0 0
· CAL L A
答： PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操作说明如下：
INT 0 A
在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。
OPR 0 0
在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。
CAL L A
调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。
问答第6题
给出对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述。
(1) 扩充条件语句的功能使其为：
if〈条件〉then〈语句〉[else〈语句〉]
(2) 扩充repeat语句为：
repeat〈语句〉{；〈语句〉}until〈条件〉
答 ： 对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述如下：
(1) 扩充条件语句的语法图为：
EBNF的语法描述为： 〈条件语句〉::= if〈条件〉then〈语句〉[else〈语句〉]
(2) 扩充repeat语句的语法图为：
EBNF的语法描述为： 〈 重复语句〉::= repeat〈语句〉{；〈语句〉}until〈条件〉
第三章：词法分析程序
问答第1题
构造正规式1(0|1)*101相应的DFA.
答：先构造NFA：
用子集法将NFA确定化
| . |
0 |
1 |
| X |
. |
A |
| A |
A |
AB |
| AB |
AC |
AB |
| AC |
A |
ABY |
| ABY |
AC |
AB |
除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。
| . |
0 |
1 |
| X |
. |
A |
| A |
A |
B |
| B |
C |
B |
| C |
A |
D |
| D |
C |
B |
DFA的状态图：:
问答第2题
将下图确定化：
解：
用子集法将NFA确定化：
| . |
0 |
1 |
| S |
VQ |
QU |
| VQ |
VZ |
QU |
| QU |
V |
QUZ |
| VZ |
Z |
Z |
| V |
Z |
. |
| QUZ |
VZ |
QUZ |
| Z |
Z |
Z |
重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。
| . |
0 |
1 |
| S |
A |
B |
| A |
C |
B |
| B |
D |
E |
| C |
F |
F |
| D |
F |
. |
| E |
C |
E |
| F |
F |
F |
DFA的状态图：
问答第3题
将下图的（a）和（b）分别确定化和最小化：
解：
初始分划得
Π0：终态组{0}，非终态组{1,2,3,4,5}
对非终态组进行审查：
{1,2,3,4,5}a
而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}
∵{4} a
Π1：{0}，{4}，{1,2,3,5}
对{1,2,3,5}进行审查：
∵{1,5} b
{2,3} b
Π2：{0}，{4}，{1, 5}，{2,3}
{1, 5} a
{2,3} a
Π3：{0}，{2}，{3}，{4}，{1, 5}
这是最后分划了
最小DFA：
问答第4题
构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。
解：按题意相应的正规表达式是(0*10)*0*，或0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为
用子集法确定化：
| I |
I0 |
I1 |
| {X,0,1,3,Y} |
{0,1,3,Y} |
{2} |
重新命名状态集：
| S |
0 |
1 |
| 1 |
2 |
3 |
DFA的状态图：
可将该DFA最小化：
终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以1,2,4为等价状态，可合并。
第四章 文法和语言
问答第1题
写一文法，使其语言是偶正整数的集合。 要求：
(1) 允许0打头；
(2)不允许0打头。
答 ：(1)允许0开头的偶正整数集合的文法
E→NT|D
T→NT|D
N→D|1|3|5|7|9
D→0|2|4|6|8
(2)不允许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题
证明下述文法G[〈表达式〉]是二义的。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉
〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/
答：可为句子a+a*a构造两个不同的最右推导:
最右推导1 〈表达式〉
最右推导2 〈表达式〉
问答第3题
令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答 ： 因为存在推导序列: E
句型 E+T*F的
短语有:E+T*F,T*F
直接短语有:T*F
句柄为:T*F
问答第4题
给出生成下述语言的上下文无关文法：
（1）{ anbnambm| n，m>=0}
（2） { 1n0m 1m0n| n，m>=0}
答： (1) S→AA
A→aAb|ε
(2)
S→1S0|A
A→0A1|ε
问答第5题
给出生成下述语言的三型文法：
(1) { anbm|n,m>=1 }
(2){anbmck|n,m,k>=0 }
答： (1) S→aA
A→aA|B
B→bB|b
(2) A→aA|B
B→bB|C
C→cC|ε
问答第6题
给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
答： R = (01 | 10) ( 01 | 10 )*
第五章 自顶向下语法分析方法
问答第1题
对文法G[S]
S→a|∧|(T)
T→T,S|S
(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。
(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。
答：文法
S→a|∧|(T)
T→T,S|S
(1) 对(a,(a,a)的最左推导为：
S
对(((a,a),∧,(a)),a) 的最左推导为：
S
(2) 改写文法为：
0) S→a
1) S→∧
2) S→( T )
3) T→S N
4) N→, S N
5) N→ε
| 非终结符 |
FIRST集 |
FOLLOW集 |
| S |
{a,∧,(} |
{#,,,)} |
| T |
{a,∧,(} |
{)}.... |
| N |
{,,ε}. |
{)}.... |
对左部为N的产生式可知：
FIRST （→, S N）={，}
FIRST （→ε）={ε}
FOLLOW （N）={)}
由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
|
|
a |
∧ |
( |
) |
, |
# |
| S |
→a |
→∧ |
→(T) |
|
|
|
| T |
→S N |
→S N |
→S N |
|
|
|
| N |
|
|
|
→ε |
→, S N |
|
也可由预测分析表中无多重入口判定文法是LL(1)的。
(3) 对输入串（a,a）#的分析过程为：
| 栈（STACK） |
当前输入符（CUR_CHAR） |
剩余输入符（INOUT_STRING） |
所用产生式（OPERATION） |
| #S |
( |
a,a)#... |
.. |
可见输入串（a,a）#是文法的句子。
问答第2题
已知文法G[S]：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
判断G是否是LL(1)文法，如果是，构造LL(1)分析表。
答：文法：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
展开为：
0） S→M H
1） S→a
2） H→L S o
3） H→ε
4） K→d M L
5） K→ε
6） L→e H f
7） M→K
8） M→b L M
| 非终结符 |
FIRST集 |
FOLLOW集 |
| S |
{a,d,b,ε,e} |
{#,o}........ |
| M |
{d,ε,b}.... |
{e,#,o}...... |
| H |
{ε,e}...... |
{#,f,o}...... |
| L |
{e}......... |
{a,d,b,e,o,#} |
| K |
{d,ε}...... |
{e,#,o}...... |
对相同左部的产生式可知：
SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }=
SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }=
SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }=
SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
|
|
a |
o |
d |
e |
f |
b |
# |
| S |
→a |
→MH |
→MH |
→MH |
|
→MH |
→MH |
| M |
|
→K |
→K |
→K |
|
→bLM |
→K |
| H |
|
→ε |
|
→LSo |
→ε |
|
→ε |
| L |
|
|
|
→eHf |
|
|
|
| K |
|
→ε |
→dML |
→ε |
|
|
→ε |
由预测分析表中无多重入口也可判定文法是LL(1)的。
问答第3题
对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。
(1) A→aABe|a
B→Bb|d
(3) S→Aa|b
A→SB
B→ab
答：（1） 文法：
A→aABe|a
B→Bb|d
提取左公共因子和消除左递归后文法变为：
0) A→a N
1) N→A B e
2) N→ε
3) B→d N1
4) N1→b N1
5) N1→ε
| 非终结符 |
FIRST集 |
FOLLOW集 |
| A |
{a}... |
{#,d} |
| B |
{d}... |
{e}.. |
| N |
{a,ε} |
{#,d} |
| N1 |
{b,ε} |
{e}.. |
对相同左部的产生式可知：
SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }=
SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
|
|
a |
e |
b |
d |
# |
| A |
→a N |
|
|
|
|
| B |
|
|
|
→d N1 |
|
| N1 |
|
→ε |
→b N1 |
|
|
| N |
→ABe |
|
|
→ε |
→ε |
也可由预测分析表中无多重入口判定文法是LL(1)的。
（2）文法：
S→Aa|b
A→SB
B→ab
第1种改写：
用A的产生式右部代替S的产生式右部的A得：
S→SBa|b
B→ab
消除左递归后文法变为：
0) S→b N
1) N→B a N
2) N→ε
3) B→a b
| 非终结符 |
FIRST集 |
FOLLOW集 |
| S |
{b}... |
{#} |
| B |
{a}... |
{a} |
| N |
{ε,a} |
{#} |
对相同左部的产生式可知：
SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }=
所以文法是LL(1)的。
预测分析表（Predicting Analysis Table）
|
|
a |
b |
# |
| S |
|
→b N |
|
| B |
→a b |
|
|
| N |
→B a N |
|
→ε |
也可由预测分析表中无多重入口判定文法是LL(1)的。
第2种改写：
用S的产生式右部代替A的产生式右部的S得：
S→Aa|b
A→AaB|bB
B→ab
消除左递归后文法变为：
0) S→A a
1) S→b
2) A→b B N
3) N→a B N
4) N→ε
5) B→a b
| 非终结符 |
FIRST集 |
FOLLOW集 |
| S |
{b}... |
{#} |
| A |
{b}... |
{a} |
| B |
{a}... |
{a} |
| N |
{a,ε} |
{a} |
对相同左部的产生式可知：
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠
SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠
所以文法不是LL(1)的。
预测分析表（Predicting Analysis Table）
|
|
a |
b |
# |
| S |
|
→A a.. |
|
|
|
|
→b.... |
|
| A |
|
→b B N |
|
| B |
→a b.. |
|
|
| N |
→a B N |
|
|
|
|
→ε... |
|
|
也可由预测分析表中含有多重入口判定文法不是LL(1)的。
第六章 算符优先分析法
问答第1题
已知文法G[S]为：
S→a|∧|(T)
T→T,S|S
(1) 计算G[S]的FIRSTVT和LASTVT。
(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
(3) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。
答：文法：
S→a|∧|(T)
T→T,S|S
展开为：
S→a
S→∧
S→(T)
T→T,S
T→S
(1) FIRSTVT -- LASTVT表
| 非终结符 |
FIRSTVT集 |
LASTVT集 |
| S |
{ a ∧ ( }.. |
{ a ∧ ) }.. |
| T |
{ a ∧ ( , } |
{ a ∧ ) , } |
(2) 算符优先关系表（OPERATER PRIORITY RELATION TABLE）
|
|
a |
∧ |
( |
) |
, |
# |
| a |
. |
. |
. |
|
|
|
表中无多重人口所以是算符优先（OPG）文法。
（3）对输入串（a,a）#的算符优先分析过程为
| 栈（STACK） |
当前输入字符（CHAR） |
剩余输入串（INPUT_STRING） |
动作（ACTION） |
| # |
( |
a,a)#... |
Move in |
Success!
对输入串（a,(a,a)）# 的算符优先分析过程为：
| 栈 （STACK） |
当前字符（CHAR） |
剩余输入串 |
动作（ACTION） |
| # |
( |
a,(a,a))#... |
Move in |
Success!
问答第2题
对题1的G[S]
(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。
(2) 将(1)和题1中的(3)进行比较给出算符优先归约和规范归约的区别。
答：文法：
S→a|∧|(T)
T→T,S|S
对(a,a）和（a,(a,a)）的最右推导：
(a,a）的最右推导过程为：
S
（a,(a,a)）的最右推导过程为:
S
对输入串(a,a）# 的规范归约过程为：
| 栈（stack） |
剩余输入串 |
动作（action） |
| # |
(a,a)#... |
Shift |
Success!
(4) 对输入串（a,(a,a)）# 的规范归约过程为：
| 栈（stack） |
剩余输入串 |
动作（action） |
| # |
(a,(a,a))#... |
Shift |
Success!
第七章 LR分析法
问答第1题
已知文法
A→aAd|aAb|ε
判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。
答：文法：
A→aAd|aAb|ε
拓广文法为G′，增加产生式S′→A
若产生式排序为：
0 S' →A
1 A →aAd
2 A →aAb
3 A →ε
由产生式知：
First (S' ) = {ε,a}
First (A ) = {ε,a}
Follow(S' ) = {#}
Follow(A ) = {d,b,#}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
在I0中：
A →.aAd和A →.aAb为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。
在I0、I2中：
Follow(A) ∩{a}= {d，b，#} ∩{a}=
所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。
构造的SLR(1)分析表如下：
题目1的SLR(1)分析表
| 状态（State） |
Action |
Goto |
|
|
a d b # |
A |
| 0 |
S2 r3 r3 r3 |
1 |
题目1对输入串ab#的分析过程
| 状态栈（state stack） |
文法符号栈 |
剩余输入串 |
动作（action） |
| 0 |
# |
ab#.... |
Shift |
分析成功，说明输入串ab是题目1文法的句子
问答第2题
若有定义二进制数的文法如下：
S→L.L|L
L→LB|B
B→0|1
(1) 试为该文法构造LR分析表，并说明属哪类LR分析表。
(2) 给出输入串101.110的分析过程。
答：文法：
S→L.L|L
L→LB|B
B→0|1
拓广文法为G′，增加产生式S′→S
若产生式排序为：
0 S' →S
1 S →L.L
2 S →L
3 L →LB
4 L →B
5 B →0
6 B →1
由产生式知：
First (S' ) = {0,1}
First (S ) = {0,1}
First (L ) = {0,1}
First (B ) = {0,1}
Follow(S' ) = {#}
Follow(S ) = {#}
Follow(L ) = {.,0,1,#}
Follow(B ) = {.,0,1,#}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
在I2中：
B →.0和 B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。
在I2、I8中：
Follow(s) ∩{0，1}= { #} ∩{0，1}=
所以在I2 、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。
构造的SLR(1)分析表如下：
题目2的SLR(1)分析表
| 状态（State） |
Action |
Goto |
|
|
· 0 1 # |
S L B |
| 0 |
S4 S5 |
1 2 3 |
题目2对输入串101.110#的分析过程
| 状态栈（state stack） |
文法符号栈 |
剩余输入串 |
动作（action） |
| 0 |
# |
101.110#.... |
Shift |
分析成功，说明输入串101.110是题目2文法的句子。
问答第3题
文法G=({U,T,S},{a,b,c,d,e},P,S)
其中P为：
S→UTa|Tb
T→S|Sc|d
U→US|e
(1) 判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。
(2) 构造相应的分析表。
答：文法：
S→UTa|Tb
T→S|Sc|d
U→US|e
拓广文法为G'，增加产生式S'→S
若产生式排序为：
0 S' →S
1 S →UTa
2 S →Tb
3 T →S
4 T →Sc
5 T →d
6 U →US
7 U →e
由产生式知：
First (S' ) = {d,e}
First (S ) = {d,e}
First (U ) = {e}
First (T ) = {d,e}
Follow(S' ) = {#}
Follow(S ) = {a,b,c,d,e,#}
Follow(U ) = {d,e}
Follow(T ) = {a,b}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
在I1中：
S' →S.为接受项目，T →S. 为归约项目，T →S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。
在I1中：
Follow(S') ∩ Follow(T)= { #} ∩{a ，b}=
Follow(T) ∩{ c}= { a ，b} ∩{c}=
在I8中：
Follow(U) ∩ Follow(T) ∩{ c}={d,e}∩{ a ，b} ∩{c}=
所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。
构造的SLR(1)分析表如下：
题目3的SLR(1)分析表
| 状态（State） |
Action |
Goto |
|
|
a b c d e # |
S U T |
| 0 |
S5 S4 |
1 2 3 |
问答第4题
证明文法：
S→A$
A→BaBb|DbDa
B→ε
D→ε
是LR(1)但不是SLR(1)。(其中'$'相当于'#')
答：文法：
A→BaBb|DbDa
B→ε
D→ε
拓广文法为G′，增加产生式S′→A
若产生式排序为：
0 S'→A
1 A →BaBb
2 A →DbDa
3 B →ε
4 D →ε
由产生式知：
First (S' ) = {a,b}
First (A ) = {a,b}
First (B ) = {ε}
First (D ) = {ε}
Follow(S' ) = {#}
Follow(A ) = {#}
Follow(B ) = {a,b}
Follow(D ) = {a,b}
G′的LR(1)项目集族及识别活前缀的DFA如下图所示：
在I0中：
B →.,a和T →.，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B →ε归约，为b时用产生式D →ε归约，所以该文法是LR(1)文法。
若不看搜索符，在I0中项目B →.和T →.为归约-归约冲突，而
Follow(B ) ∩Follow(D ) = {a,b} ∩{a,b}≠
构造的LR(1)分析表如下：
题目4的LR(1)分析表
| State |
Action |
Goto |
|
|
a . b . # |
A B D |
| 0 |
r3 r4...... |
1 2 3 |
问答第5题
给定文法：
S→do S or S|do S|S;S|act
(1) 构造识别该文法活前缀的DFA。
(2) 该文法是LR(0)吗?是SLR(1)吗?说明理由。
(3) 若对一些终结符的优先级以及算符的结合规则规定如下：
a) or 优先性大于 do;
b) ;服从左结合；
c) ;优先性大于 do ；
d) ;优先性大于 or ；
请构造该文法的LR分析表,并说明LR(0)项目集中是否存在冲突和冲突如何解决的。
答 ：首先化简文法,用d代替do;用o代替 or;用a代替 act;文法可写成：
S→dSoS|dS|S;S|a
拓广文法为G'，增加产生式S′→S
若产生式排序为：
0 S' →S
1 S →dSoS
2 S →dS
3 S →S;S
4 S →a
由产生式知：
First (S' ) = {d,a}
First (S ) = {d,a}
Follow(S' ) = {#}
Follow(S ) = {o,;,#}
(1)识别该文法活前缀的DFA如下图。
(2) 该文法不是LR(0)也不是SLR(1)因为：
在I5、I6、和I8中存在移进-归约冲突，因此所给文法不是LR(0)文法。
又由于Follow(S ) = {o, ; ,#}
在I6、和I8中：
Follow(S ) ∩{ ; }={o, ; ,#} ∩{ ; }={;}≠
在I5中：
Follow(S ) ∩{ ; , o }={o , ; ,#} ∩{ ; , o }={; , o }≠
所以该文法也不是SLR(1) 文法。
此外很容易证明所给文法是二义性的，因此该文法不可能满足LR文法，
(3) 若对一些终结符的优先级以及算符的结合规则规定如下：
a) or 优先性大于 do;
b) ;服从左结合；
c) ;优先性大于 do ；
d) ;优先性大于 or ；
则在I5中："or 和;优先性都大于 do"，所以遇输入符o和; 移进；遇#号归约。
在I6中："; 号服从左结合"所以遇输入符属于Follow(S )的都应归约。
在I8中："; 号优先性大于 or " 所以遇输入符为;号 移进；遇o和#号归约。
此外，在I1中：接受和移进可以不看成冲突，因为接受只有遇#号。
由以上分析，所有存在的移进-归约冲突可用规定的终结符优先级以及算符的结合规则解决，
所构造的LR分析表如下：
题目5文法的LR分析表
| State |
Action |
Goto |
|
|
d o ; a # |
S |
| 0 |
S2 S3...... |
1 |
第八章 语法制导翻译和中间代码生成
问答第1题
给出下面表达式的逆波兰表示(后缀式)：
(1)a*(-b+c)
(2) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c
答：给出下面表达式的逆波兰表示(后缀式)：
(1) a*(-b+c)
答案：ab-c+*
(2) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c
答案：xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）
问答第2题
请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。
答：请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。
答案：三元式
(1) (+ a, b)
(2) (+ c, d)
(3) (* (1), (2))
(4) (- (3), /)
(5) (+ a, b)
(6) (- (4), (5))
间接三元式
间接三元式序列 间接码表
(1) (+ a, b) (1)
(2) (+ c, d) (2)
(3) (* (1), (2)) (3)
(4) (- (3), /) (4)
(5) (- (4), (1)) (1)
(5)
四元式
(1) (+, a, b, t1)
(2) (+, c, d, t2)
(3) (*, t1, t2, t3)
(4) (-, t3, /, t4)
(5) (+, a, b, t5)
(6) (-, t4, t5, t6)
问答第3题
采用语法制导翻译思想，表达式E的"值"的描述如下：
产生式 语义动作
(0) S′→E {print E.VAL}
(1) E→E1+E2 {E.VAL∶=E1.VAL+E2.VAL}
(2) E→E1*E2 {E.VAL∶=E1.VAL*E2.VAL}
(3) E→(E1) {E.VAL∶=E1.VAL}
(4) E→n {E.VAL∶=n.LEXVAL}
假如终结符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加"类型匹配检查"，请给出相应的语义描述。
答：采用语法制导翻译思想，表达式E的"值"的描述如下：
产生式 语义动作
(0) S′→E {print E.VAL}
(1) E→E1+E2 {E.VAL∶=E1.VAL+E2.VAL}
(2) E→E1*E2 {E.VAL∶=E1.VAL*E2.VAL}
(3) E→(E1) {E.VAL∶=E1.VAL}
(4) E→n {E.VAL∶=n.LEXVAL}
假如终结符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加"类型匹配检查"，请给出相应的语义描述。
答案：
(0) S′→E { if error≠1 then print E.VAL}
(1) E→E1+E2 { if E1.TYPE=int AND E2.TYPE=int then
begin
E.VAL:=E1.VAL + E2.VAL;
E.YTPE:=int;
end
else if E1.TYPE=real AND E2.TYPE=real then
begin
E.VAL:=E1.VAL + E2.VAL;
E.YTPE:=real;
end
else error=1
}
(2) E→E1*E2 { if E1.TYPE=int AND E2.TYPE=int then
begin
E.VAL:=E1.VAL * E2.VAL;;
E.YTPE:=int;
end
else if E1.TYPE=real AND E2.TYPE=real then
begin
E.VAL:=E1.VAL * E2.VAL;;
E.YTPE:=real;
end
else error=1
}
(3) E→(E1) { E.VAL:=E1.VAL;
E.TYPE:=E1.TYPE }
(4) E→n { E.VAL:=n.LEXVAL;
E.TYPE:=n.LEXTYPE }
问答第4题
请将下列语句
while (A<B do if (C>D) then X:=Y+Z
翻译成四元式
答：请将下列语句
while (A<B do if (C>D) then X:=Y+Z
翻译成四元式
答案:
假定翻译的四元式序列从（100）开始：
（100） if A<B goto （102）
（101） goto （107）
（102） if C<D got （104）
（103） goto （100）
（104） T∶=Y+Z
（105） X∶=T
（106） goto （100）
（107）
第九章 符号表
问答第1题
根据你所了解的某个FORTRAN语言的实现版本，该语言的名字作用域有哪几种?
解答: FORTRAN中，名字作用域有四种：
<1>在BLOCK DATA块中定义的标识符，其作用域是整个程序。
<2>在COMMON块中定义的标识符，其作用域是声明了该COMMON块的所有例程（包括函数和过程）。
<3>在例程中定义的标识符（包括哑变量），其作用域是声明该标识符的例程。
<4>在例程中用SAVE定义的标识符，其作用域是声明该标识符的例程，且在退出该例程时，该标识符的值仍保留（即内部静态量）。
问答第2题
C语言中规定变量标识符的定义可分为extern,extern static,auto,local static和register五种存储类：
(1) 对五种存储类所定义的每种变量，分别说明其作用域。
(2) 试给出适合上述存储类变量的内存分配方式。
(3) 符号表中登录的存储类属性，在编译过程中支持什么样的语义检查。
解答: (1) . extern定义的变量，其作用域是整个C语言程序；
. extern static定义的变量，其作用域是该定义所在的C程序文件；
. auto定义的变量，其作用域是该定义所在的例程；
. local static定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。
. register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。
(2) · 对extern变量，设置一个全局的静态公共区进行分配。
. 对extern static变量，为每个C程序文件，分别设置一个局部静态公共区进行分配。
. 对auto和register变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。
. 对local static变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。
(3) 实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。
问答第3题
对分程序结构的语言，为其符号表建立重名动态下推链的目的是什么?概述编译过程中重名动态下推链的工作原理。
解答: 重名动态下推链的目的是，保证在合法重名定义情况下，提供完整确切的符号表项，从而保证引用变量的上下文合法性检查和非法重名定义检查。
其工作原理是：当发生合法重名定义时，将上层重名表项下推到链中，而在符号标中原重名表项处登录当前重名定义的符号属性；在退出本层时，将最近一次下推的表项，回推登录到符号表中原重名表项处。
问答第4题
某《BASIC》语言的变量名字表示为字母开头的字母或数字两个字节的标识符，该语言的符号表拟采用杂凑法组织，请为其设计实现一个有效散列的杂凑算法，并为解决散列冲突，设计实现一个再散列算法。
解答: 可采用下列散列杂凑算法（设表长为N）散列地址=MOD（（<第一字节值>+<第二字节值>），N）发生冲突时再散列的方法：在该冲突处开始，向下寻找第一个空表项，若找到则该表项地址为再散列地址；若找不到空表项，则循环到表头开始，向下寻找第一个空表项，一直到发生冲突处为止，若找到空表项则该表项地址为再散列地址，否则表示符号表已满，编译系统给出符号表溢出信息，终止编译。
第十章 目标程序运行时的存储组织
问答第1题
下面的程序执行时输出的a分别是什么?若
(1) 参数的传递办法为"传值"；
(2) 参数的传递办法为"传地址"。
program main (input,output);
procedure p(x,y,z);
begin
y∶=y+1;
z∶=z+x;
end;
begin
a∶=2;
b∶=3;
p(a+b,a,a);
print a
end.
解答： (1) 参数的传递办法为"传值"时，a 为 2。
(2) 参数的传递办法为"传地址"，a 为 7。
问答第2题
过程参数的传递方式有几种?简述"传地址"和"传值"的实现原理。
解答：参数的传递方式有下述几种：
"传值" -- Call by Value
"传地址"-- Call by Address
"换名" -- Call by Name
"得结果"-- Value-result
"传值"方式，这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：
1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。
2.调用过程计算实参的值，并将它们的右值（r-value）放在为形式单元开辟的空间中。
3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。
"传地址"方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。
1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去。
2.如实参是一个表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。
3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。
问答第3题
下面是一个Pascal程序
program PP(input,output)
var K:integer;
function F(N:integer):integer
begin
if N< =0 then F:=1
else F:=N * F(N-1);
end;
begin
K:=F(10);
...
end;
当第二次（递归地）进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？
解答：
问答第4题
对如下的Pascal程序，画出程序执行到（1）和（2）点时的运行栈。
program Tr(input,output);
var i:integer; d:integer;
procedure A(k:real);
var p:char;
procedure B;
var c:char;
begin
...(1)...
end; {B}
procedure C;
var t:real;
begin
...(2)...
end;{C}
begin
.....
B;
C;
.....
end;{A}
begin{main}
...
A(d);
...
end.
解答：
程序执行到（1）点时的流程是：
①主程序激活A
②A激活B
程序执行到（2）点时的流程是：
① 主程序激活A
② A激活B
③ B执行结束返回A
④ A激活C
问答第5题
有如下示意的Pascal源程序
program main;
var a,b,c:integer;
procedure X(i,j:integer);
var d,e:real;
procedure Y;
var f,g:real;
begin
...
end;{Y}
procedure Z(k:integer);
var h,i,j:real;
begin
...
end;{Z}
begin
.....
10:Y;
.....
11:Z;
.....
end;{X}
begin
.....
X(a,b);
.....
end.{main}
并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和DISPLAY的内容。
（1）已开始而尚未执行完毕的标号为10的语句。
（2）已开始而尚未执行完毕的标号为11的语句。
解答：程序结构：
（1）
（2）
第十一章 代码优化
问答第1题
图11.17是图11.16的C代码的部分四元式代码序列?
(1) 请将图11.17的四元式代码序列划分为基本块并做出其流图?
(2) 将每个基本块的公共子表达式删除?
(3) 找出流图中的循环,将循环不变量计算移出循环外?
| 图11.16 |
| void quicksort(m,n) |
| 图11.17 |
||
|
解答：
（1） 基本块
流图
（2）
B5中（14）和（16）是公共子表达式、（17）和（20）是公共子表达式，B5变为
（14） t6:=4*I
（15）
（16） t7:=t6
（17） t8:=4*J
…
（20） t10:=t8
（21）
（22）
B6中（23）和（25）是公共子表达式、（26）和（29）是公共子表达式，B6变为
（23） t11:=4*I
（24）
（25） t12:=t11
（26） t13:=4*n
…
（29） t15:=t13
（3）
循环
① {B2}
② {B3}
③ {B2，B3，B4，B5}
问答第2题
如下程序流图(图11.18)中，B3中的i∶=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?
图11.18
解答：不能。因为B3不是循环出口B4的必经结点。
问答第3题
对图11.19的流图：
(1) 求出流图中各结点n的必经结点集D(n)；
(2) 求出流图中的回边；
(3) 求出流图中的循环。
图11.19
解答：
（1）
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,3,4}
D(5)={1,2,3,5}
D(6)={1,2,3,6}
D(7)={1,2,7}
D(8)={1,2,7,8}
（2）回边 7 2
（3）循环 {2，3，4，5，6，7}
第十二章 代码生成
问答第1题
一个编译程序的代码生成要着重考虑哪些问题?
解答：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。
问答第2题
决定目标代码的因素有哪些？
解答：决定目标代码的因素主要取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。又由于目标代码的执行效率在很大程度上依赖于寄存器的使用，所以目标代码与寄存器的分配算法也有关。
问答第3题
为什么在代码生成时要考虑充分利用寄存器？
解答：因为当变量值存在寄存器时，引用的变量值可直接从寄存器中取，减少对内存的存取次数，这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。
问答第4题
寄存器分配的原则是什么？
解答：寄存器分配的原则是：
(1) 当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配时为止。
(2) 当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。
(3) 对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。对基本块的划分可按基本块的划分算法(见
第十三章 编译程序实现的途径
问答第1题
如何用T型图 表示一个编译程序的实现？
解答：用T型图 表示编译程序的实现
问答第2题
如何用自展方式在PC机上实现C语言的编译程序？请用T型图表示。
解答：用自展方式在PC机上实现C语言的编译程序，首先把C划分成真包含的子集C1和C2，然后分3步实现。
问答第3题
什么叫做软件移植？
解答：通常把某个机器(称为宿主机)上已有的软件移植到另一台机器(称为目标机)
问答第4题
什么叫做交叉编译？
解答：交叉编译是指把一个源语言在宿主机上经过编译产生目标机的汇编语言或机器语言。
问答第5题
编译程序的实现应考虑的问题有那些？
解答：编译程序的实现 应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。
问答第6题
编译程序的实现途径有那些？
解答：编译程序的实现途径可有：
- 手工构造：用机器语言、汇编语言或高级程序设计语言书写。
- 自动构造工具：Lex,Yacc。 Lex ,Yacc分别是词法和语法分析器的生成器。
- 移植方式：目标程序用中间语言
- 自展方式：用T型图表示