编译原理 (2)

通过从左向右扫描句子，通过下一输入，决定从Si归约到Sj，并最终到达终态

SLR(1)语法分析

LR(0)文法，如果遇到在一个状态中，同时出现移进和规约的冲突，则会让LR(0)无法判断此步骤应该如何处理

S3状态，已经满足归约条件，则无论下一个字符是什么，都需要进行归约操作；但是如果下一个字符是‘，’，则应该i进行移进操作

SLR(1)为了解决移进归约冲突，则遇到冲突时向前看一个字符，来解决冲突

LR(1)语法分析

当某个状态遇到移进归约冲突，并且下一个移进的符号，与归约符号的下一个符号相同，则无法使用SLR(1)进行分析

SLR(1)通过Follow(A)来计算，而LR(1)通过First(A.next)来决定来缩小范围

LR(1)过程：

如果A->a.BM, B->r，m=First(M)，则记为B->r,m

中间代码 优点

编译程序的逻辑结构更加简单明确

利于再不同的目标机器上实现同一种语言

利于进行与机器无关的优化

可以用于解析

形式

后缀式

图表示：抽象语法树/DAG图

三地址代码：三元式/四元式/间接三元式

后缀式 a+b*(c-d)+e/(c-d) => abcd-*+ecd-/+ 抽象语法树

内部节点代表操作符，叶子节点为操作数

DAG图

把抽象语法树的公共部分进行合并，可以减少公共表达式的计算

三地址码

可以看作抽象语法树或者DAG的一种线性表示

三地址码详解 四元式 特点

占用空间多

易于优化

result = arg1 op arg2 => (op, arg1 arg2, result) 三元式 特点

占用空间少

由于临时变量跟i紧密关联，导致难以优化

result = arg1 op arg2 => (i) (op, arg1, arg2)

用i位置来保存临时结果

左值与右值 x[i]=y => (0) ([]=, x, i) (1) (assign, (0), y) y=x[i] => (0) (=[], x, i) (1) (assign, y, (0)) 间接三元式 特点

占用空间多

易于优化

数组翻译 LOC(A[i]) = base + (i-low)*w = (base-low*w) + i*w = conspart + varpart Loc(A[i][j]) = base + ((i-low1)*n2+j-low)*w = (base-(low1*n2+low2)*w)+(i*n2+j)*w

可见任意维度的数组元素的计算都可以分为不变计算和可变计算组成，在编译时首先计算出conspart，可以达到优化的目的

条件语句的翻译 文法 S -> if(E) S1|if(E) S1 else S2

拉链回填

对于E.true的未来地址，在三地址码中，先通过打标志的方式，在后续确定下地址后，再回填到标志的位置

循环语句的翻译 文法 S -> while(E) S1

符号表

存储

变长字段通过指针链接到另外的内存区存储

查找 线性查找

通过顺序查找

自适应线性表：通过新增一列，通过LRU算法，构成链表，最新访问的元素会出现在链头

二叉树

建立树索引

hash

建立hash索引

名字作用域

嵌套结构的符号表特征

由于函数的执行是先执行，后结束，所以适合用栈的方式来存储

在函数对应的符号表中指定display表，代表此函数可用符号表的首地址

在符号表中引入指针previous，来连接上一个符号的首地址

运行时存储空间组织

活动记录

用于管理函数变量的信息

栈式存储

过程进入和返回

通过变更top和sp指针，实现活动记录的栈式处理

静态链实现局部变量的访问