admin 管理员组文章数量: 1086019
2025年1月2日发(作者：玳瑁手镯适合年轻人戴吗)
符号表也称为环境(environment)，其作用是将标识符映射到它们的类型和存储位置。
在处理类型、变量和函数的声明时，这些标识符便与其在符号表中的“含义”相绑定。每当发现标识符的使用（非声
明性出现）时，便在符号表中查看它们的含义。
程序中的每一个局部变量都有一个作用域(scope)，该变量在此作用域中是可见的。
当语义分析到达每一个作用域的结束时，所有局部于此作用域的标识符都将被抛弃。
第六章
通常意义上的“栈”：支持压入(push)和弹出(pop)操作的数据结构。
但是，局部变量会成批压入和弹出栈，而且，当局部变量在栈中被创建时，它们一般不会被立刻初始化。最后，当向
栈中压入很多变量之后，还会需要访问压在栈顶之下较深的变量。
因此，抽象的压入和弹出模式并不适合。
可以将栈看成是一个大型数组，并带有一个特殊寄存器，即栈指针(stack pointer)。
栈中空间的划分：
超出栈指针的所有位置为自由存储空间(garbage)；
位于栈指针之前的位置为已分配存储空间(allocated)。
栈通常只在函数的入口处增长，它通过增加足以容纳该函数的所有局部变量的一片存储空间来扩大栈。栈在
函数的出口处收缩，收缩的空间就是入口时扩大的空间。
栈中用来存放一个函数的局部变量、参数、返回地址和其他临时变量的这片区域称为该函数的活动记录(activation
record)或栈帧(stack frame)。
设函数g(„)调用函数f(
a1
,
a2
, „
an
)：
g是调用者(caller)；
f是被调用者(callee)。
在进入函数f时，栈指针(Stack Pointer)指向g传递给f的第一个参数。在f的入口，f简单地使SP减去帧的长度
而分配一个新栈帧。
原来的SP则变成了当前的帧指针(Frame Pointer)。
某些栈帧布局中：
FP是一个单独的寄存器；
原来的FP保存在存储器中（栈帧内）。
当函数f退出时，需要复制FP到SP，并取回保存在存储器中的FP。
适合于栈帧大小可变或不连续的情况。
如果栈帧的大小是固定不变的，则对于每一个函数f，FP与SP所指的位置总是相差一个已知的常数：“虚”寄存器
FP=SP+栈帧大小。
将局部变量、表达式的中间结果和其他值保存在寄存器中，而不是放在栈帧中，将有助于编译生成的程序快速地运行。
算术指令可以直接访问寄存器。
假设函数f在用寄存器r保存了它的一个局部变量的同时调用过程g，而过程g也需用r完成自己的计算：
在g使用r之前先将r保护起来（将它保存在栈帧内）；
完成计算而不再需要时将r恢复（从帧栈中取回被保存的内容）。
保护和恢复该寄存器的责任：
如果由调用者f来保护和恢复，则称r为调用者保护的(caller-save)寄存器;
如果由被调用者g来保护和恢复，则称r为被调用者保护的(callee-save)寄存器;
保护和恢复寄存器的特殊情况：
如果f知道某个变量x的值在函数调用以后将不再需要，它可以把x放在一个调用者保护的寄存器中，
并且在调用过程g时不保护它。
如果f有一个局部变量i，并且在若干次函数调用之前和之后都需使用，则可以把i放在某个被调用
者保护的寄存器ri中，并且只在f的入口保护ri一次，在f的出口将ri取回一次。
这样，明智地为局部变量和临时变量选择调用者或被调用者保护的寄存器，便可以减少程序执行存储操作的次数。
第七章
中间表示(Intermediate representation, IR)：是一种抽象机器语言，它可以表示目标机的操作而不需太多地涉及
机器相关的细节且独立于源语言的细节。
前端(front end)：lexical analysis、parsing、semantic analysis，and translation to intermediate
representation.
后端(back end)：optimization of the intermediate representation and translation to machine language
一种好的中间表示(IR)应具有以下一些特点：
– 便于在语义分析阶段生成它；
– 对于希望支持的所有目标机，它必须便于转变成真实的机器语言；
– 每一种结构必须具有简单而清晰的含义，以便能够较简单地指定和实现重写中间表示的各种优化变换
(optimizing transformations)。
中间表示中的个体成分(individual components)应该只描述特别简单的事情：如单个取、存、加法、传递或转移等
操作。
表达式(T_exp)代表某个值的计算：
CONST(
i
)：整型常数
i
;
NAME(
n
)：符号常数
n
；
TEMP(
t
)：临时变量t，抽象机器中的临时变量类似于真实机器中的寄存器，但可以有无限多个临时变量。
BINOP(
o, e1, e2
)：对操作数
e1 , e2
施加二元操作符
o
表示的操作。
其中T_binOp的定义如下：
整型算数操作符：PLUS、MINUS、MUL、DIV；
整型按位逻辑操作符：AND、OR、XOR；
整型逻辑移位操作符：LSFIFT、RSHIFT；
整型算数右移操作符：ARSHIFT。
MEM(
e
)：开始于存储地址e的wordSize个字节的内容。
当MEM作为MOVE操作的左子式时，它表示对存储地址
e
的“存储”；
在其他位置都表示“读取”。
CALL(
f ,l
)过程调用：以参数表
l
调用函数
f
，子表达式
f
的计算先于参数的计算，参数的计算则从左到右。
ESEQ(
s,e
)：先计算语句
s
以形成其副作用，然后计算
e
作为此表达式的结果。
树中间语言的语句(T_stm)执行副作用和控制流：
MOVE(TEMP
t
,
e
)：计算
e
并将结果送入临时单元
t
。
MOVE(MEM(
e1
),
e2
)：计算
e1
，由它生成地址a，然后计算
e2
，并将计算结果存储在从地址a开始的wordSize
个字节的存储单元中。
EXP(
e
)：计算
e
但忽略结果。
JUMP(
e, labs
)：将控制转移到地址
e
，
目标地址
e
可以是文字标号，也可以是由其他种类的表达式计算出来的一个地址。
标号表labs指出表达式
e
可能计算出的所有目标地址。
CJUMP(
o,
e1, e2, t, f
)：依次计算
e1、e2
，生成值
a
、
b
，然后用关系操作符
o
比较
a
和
b
：
如果结果为true，则跳转到
t
；
否则，跳转到
f
。
关系操作符T_relOP的定义如下：
EQ和NE分别表示整数的相等比较和不等比较；
有符号整数的非相等比较：LT,GT,LE,GE；
无符号整数的非相等比较：ULT,UGT,ULE,UGE。
SEQ(
s1,s2
)：语句
s1
之后跟随语句
s2
。
LABEL(n)：定义名字
n
的常数值为当前机器代码的地址。
第八章
Tree语言表示的程序和机器语言程序之间存在的不匹配(mismatch)情况：
CJUMP指令，真正的机器语言的转移指令在条件为假时下降至下一条指令。
ESEQ结点会使得子树的不同计算顺序产生不同的结果。
在表达式中使用CALL结点情况类似。
当企图将参数送入固定的形参寄存器集合时，在一个CALL结点的参数表达式中使用另一个CALL结点会出现
问题。
对于任意一棵树，将它重写为等价的没有上述任何一种情况的树（简答）：
1. 重写成一列不含SEQ和ESEQ结点的规范树(canonical tree)；
2. 将这一列树分组组合成其内不含转移和标号的基本块(basic block)集合；
3. 对基本块排序并形成一组轨迹(trace)，轨迹中每一个CJUMP之后都直接跟随它的false标号。
规范树：
（1）无SEQ或ESEQ；
（2）每一个CALL的父亲不是EXP(„)，
就是MOVE ( TEMP
t
, „)。
Tree语言与大多数机器指令集不能直接等价的另一个原因是两路分支CJUMP指令。
在真实的机器中，条件转移指令或者使控制发生转移（条件为真时），或者“下降到”下一条指令。
重新安排CJUMP，使得每一个CJUMP(
cond
,
l
t,
l
f)之后直接跟随的是LABEL(
l
f )，即“false分支”。
Step1: 取一列规范树，并由它们形成基本块；
Step2: 对这些基本块排列形成一条轨迹。
Basic Blocks基本块是语句组成的一个序列，控制只能从这个序列的开始处进入并从结尾处退出：
第一个语句是一个LABEL；
最后一个语句是JUMP或者CJUMP；
没有其他的LABEL、JUMP或者CJUMP。
Traces
可以按任意顺序安排这些基本块，并且程序执行的结果仍是相同的。
利用这一点选择适当的基本块排列顺序，以满足每个CJUMP之后都跟随它的false标号这一条件。
同样可以安排基本块使得无条件转移JUMP之后直接跟随的是它们的目标标号，这样便可以删除这些JUMP，使编
译生成的程序的执行速度更快。
轨迹(trace)是在程序执行期间可能连贯执行的语句序列，它可以包含条件分支。
为了适当安排CJUMP和false标号，需要建立一组正好能覆盖整个程序的轨迹，即每一个基本块在一条且只在一
条轨迹中。
问题：如何描述程序设计语言的词法规则？用什么语言来编写词法分析器？
答案：任何合理的程序设计语言都可以用来实现特定的词法分析器。我们学习使用正则表达式的形式语言来指明词法
单词，用确定的有限自动机 (Deterministic Finite Automata, DFA)实现词法分析器，并用数学的方法将两者联系
起来。
LL与LR分析的本质区别：
LL为自上而下(up-to-down)的语法分析，即从文法的开始符号出发，向下推导，对于任何的输入串，试图用一切可
能的办法，自上而下地为输入串建立一个语法树。
LR为自下而上(down-to-up)的语法分析，其过程是最右推导的逆过程（最左归约）；即从输入串开始，朝着文法开始
符号进行归约，直至到达文法开始符号为止的过程。
具体分析树不便于在语义分析阶段直接使用：
标点符号单词中有许多是冗余的，而且不传递信息；
语法树的结构对文法的依赖程度太高！
环境是由一些绑定(binding)构成的集合，所谓绑定指的是标识符与其含义之间的一种映射关系。
用“→”表示绑定。
----------σ0
1 function f(a:int, b:int, c:int)= ----------σ1= σ0 + {a→int, b→int, c→int}
2 (print_int(a+c);
3 let var j:=a+b ----------σ2= σ1 + {j→int}
4 var a:=“hello” ----------σ3= σ2 + {a→string}
5 in print(a); print_int(j)
6 end; ----------σ1
7 print_int(b)
8 ) ----------σ0
问题：当栈帧大小是常数时，为何还讨论帧指针？
栈帧的大小要到编译处理相当晚的时候才能知道，即要到给临时变量分配的空间大小和用于保护寄存器的空间大小都
已确定时。但是，尽早知道形参与局部变量的位移量是有好处的。
问题：The transformation is done in three stages:P177
版权声明：本文标题：编译原理课件总结 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1735863449a1697957.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论