编译原理--04 符号表、运行时存储组织和代码优化复习(清华大学出版社第3版)...

本文主要是介绍编译原理--04 符号表、运行时存储组织和代码优化复习(清华大学出版社第3版)...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

目录
01 文法和语言、词法分析复习
02 自顶向下、自底向上的LR分析复习
03 语法制导翻译和中间代码生成复习
04 符号表、运行时存储组织和代码优化复习

第8章 静态语义分析和中间代码生成(续)

符号表

符号表需要在编译期间用到,记录符号的具体信息。本部分只讨论PL/0符号表的建立。

PL/0符号表结构

PL/0的符号表包含5个信息:

  1. NAME符号名
  2. KIND符号类型
  3. LEVEL/VAL层次/值。如果类型为CONSTANT,存放的是常量的值;如果类型为VARIABLEPROCEDURE,存放所属分程序的层次,主程序的层次为0;在主程序中定义的内容层次为1;主程序内第一层分程序中定义的内容层次为2,以此类推。
  4. ADR地址。如果为简单变量或常量,则记录的是该量在数据区所占单元的相对地址,用DX表示给本层局部变量分配的相对存储位置,每说明一个变量后DX加1;如果为过程,则存放该过程的分程序入口地址(需要返填
  5. SIZE大小。该过程内局部变量的个数,再加上过程活动记录的头3个单元(DL,SL,RA)(需要返填

例如下面的程序:

const a = 35, b = 49;
var c, d, e;
procedure p;var g;

对应的符号表为:

NAMEKINDVAL/LEVELADDSIZE
aCONSTANT35
bCONSTANT49
cVARIABLELEVDX
dVARIABLELEVDX+1
eVARIABLELEVDX+2
pPROCEDURELEVp的入口地址4
gVARIABLELEV+1DX

又例如下面的程序:

const a = 25;
var x, y;
procedure p;var z;begin...end;
procedure r;var x, s;procedure t;var v;begin...end;begin...end;
begin
...
end.

对应的符号表为:

NAMEKINDVAL/LEVELADDSIZE
aCONSTANT25
xVARIABLELEVDX
yVARIABLELEVDX+1
pPROCEDURELEVp的入口地址4
zVARIABLELEV+1DX
rPROCEDURELEVr的入口地址5
xVARIABLELEV+1DX
sVARIABLELEV+1DX+1
tPROCEDURELEV+1t的入口地址4
vVARIABLELEV+2DX

第9章 运行时存储组织

PL/0程序运行栈中的过程活动记录

PL/0程序运行时,每一次过程调用都将在运行栈增加一个过程活动记录。 其中,当前活动记录的起始单元由基址寄存器b指出,结束单元是栈顶寄存器t所指单元的前一个单元。

PL/0的过程活动记录中的头3个单元是固定的联系信息:

  1. 静态链SL:存放的是定义该过程所对应的上一层过程,最近一次运行时的活动记录的起始单元。
  2. 动态链DL:存放的是调用该过程前正在运行过程的活动记录的起始单元。过程返回时当前活动记录要被撤销,此时需要动态链信息来修改基址寄存器b的内容。
  3. 返回地址RA:记录该过程返回后应该执行的下一条指令地址,即调用该过程的指令执行时指令地址寄存器p的内容加1

这样,每当一个过程被调用,就需要在栈上先分配3个空间用来存储上述信息,然后才是分配空间存储过程的局部变量。对于主过程,SL=DL=RA=0。

这里给出一道例题。对于下列程序:

var m, n, g:integer;
function gcd(m,n:integer):integer;beginif n = 0 theng := melseg := gcd(n, m mod n)end;beginm := 24;n := 16;g := gcd(m, n)
end.

它的运行栈为:
1172605-20190619182710390-836190430.png

这一章可能要考的内容

  1. 运行栈的填写(静态链、动态链)
  2. display表(本质上是记录各个层定义的最新活动记录),建议自己看书

第10章 代码优化

优化技术简介

常用优化技术有:

  1. 删除多余运算
  2. 循环不变代码外提
  3. 强度削弱
  4. 变换循环控制条件
  5. 合并已知量
  6. 复写传播与删除无用赋值

删除多余运算

\((1)T_1:=4*I\)
\((2)T_2:=addr(A)-4\)
\((3)T_3:=T_2[T_1]\)
\((4)T_4:=4*I\)
\((5)T_5:=addr(B)-4\)
\((6)T_6:=T_5[T_4]\)

可以看到\((4)\)式做了和\((1)\)式重复的工作,可以改写成\(T_4:=T_1\)

循环不变代码外提

原代码:
块1
\((1)P:=0\)
\((2)I:=1\)
块2
\((3)T_1:=4*I\)
\((4)T_2:=addr(A)-4\)
\((5)T_3:=T_2[T_1]\)
\((6)P:=P+T_3\)
\((7)I:=I+1\)
\((8)if \;I<=20\;goto\;(3)\)

可以看到\((4)\)式在每次循环都做重复的工作,可以把它提到循环外来,记得修改跳转:
块1
\((1)P:=0\)
\((2)I:=1\)
\((3)T_2:=addr(A)-4\)
块2
\((4)T_1:=4*I\)
\((5)T_3:=T_2[T_1]\)
\((6)P:=P+T_3\)
\((7)I:=I+1\)
\((8)if \;I<=20\;goto\;(4)\)

强度削弱

把强度大的运算换成强度小的运算,比如用加法换乘法:
块1
\((1)P:=0\)
\((2)I:=1\)
\((3)T_2:=addr(A)-4\)
块2
\((4)T_1:=4*I\)
\((5)T_3:=T_2[T_1]\)
\((6)P:=P+T_3\)
\((7)I:=I+1\)
\((8)if \;I<=20\;goto\;(4)\)

\((4)\)式经过处理,并修改跳转:
块1
\((1)P:=0\)
\((2)I:=1\)
\((3)T_1:=0\)
\((4)T_2:=addr(A)-4\)
块2
\((5)T_1:=T_1+4\)
\((6)T_3:=T_2[T_1]\)
\((7)P:=P+T_3\)
\((8)I:=I+1\)
\((9)if \;I<=20\;goto\;(5)\)

变换循环控制条件

下面的代码中,\(I\)\(T_1\)保持4倍的线性关系:
块1
\((1)I:=1\)
\((2)T_1:=4*I\)
块2
\((3)P:=T_2[T_1]\)
\((4)I:=I+1\)
\((5)T_1=T_1+4\)
\((6)if\;I<=20\;goto\;(3)\)

可以把循环条件\(I<=20\)改为\(T_1<=80\),然后修改\(T_1\)的初始赋值,这样\(I\)在整个循环都没有被用上,可以剔除:
块1
\((1)T_1:=4\)
块2
\((2)P:=T_2[T_1]\)
\((3)T_1=T_1+4\)
\((4)if\;T_1<=80\;goto\;(2)\)

合并已知量

下面的代码中,在计算\(4*I\)时,\(I\)必定为1:
\((1)I:=1\)
\((2)T_1:=4*I\)

因此可以直接在编译期间算出它的值是4:
\((1)I:=1\)
\((2)T_1:=4\)

复写传播和删除无用赋值

看下面的代码:
块1
\((1)T_1:=4\)
\((2)I:=1\)
块2
\((3)T_2:=T_1\)
\(...\)
\((7)T_3:=T_4[T_2]\)
\((8)T_1:=T_1+T_3\)
\((9)I:=I+1\)
\((10)if\;T_1<=80\;goto\;(3)\)

四元式\((3)\)\(T_1\)的值写入\(T_2\)中,但\(T_2\)\(T_1\)的值在\((3)\)\((7)\)之间没有发生改变,故将\((7)\)改为\(T_3:=T_4[T_1]\)

此时\((3)\)式没有被引用,属于无用赋值,可以删掉。

然后,\((2)\),\((9)\)\(I\)赋值,但也只是自我引用,其余地方没有需要用到\(I\),属于无用赋值,故可以删掉。

最终变为:
块1
\((1)T_1:=4\)
块2
\(...\)
\((5)T_3:=T_4[T_1]\)
\((6)T_1:=T_1+T_3\)
\((7)if\;T_1<=80\;goto\;(2)\)

基本块、流图和循环

基本块

一个基本块内部是顺序执行的,故内部不能有任何停止、分支、跳转。

基本块的划分:

  1. 条件转移语句或者无条件转移语句和下一句语句之间要划分开
  2. 跳转的目标语句要和上一句语句之间划分开

例如:
\((1)\quad pi:=3.14\)
\((2)\quad ar:=0.0\)
\((3)\quad n:=16\)
\((4)\quad r:=1\)
\((5)\quad if\;n<=1\;goto\;(9)\)
\((6)\quad r:=r*n\)
\((7)\quad n:=n-1\)
\((8)\quad goto\;(5)\)
\((9)\quad ar:=2*pi\)
\((10)\quad ar:=ar*r\)
\((11)\quad print\;ar\)

经过划分后:
B1
\((1)\quad pi:=3.14\)
\((2)\quad ar:=0.0\)
\((3)\quad n:=16\)
\((4)\quad r:=1\)
/
B2
\((5)\quad if\;n<=1\;goto\;(9)\)
/
B3
\((6)\quad r:=r*n\)
\((7)\quad n:=n-1\)
\((8)\quad goto\;(5)\)
/
B4
\((9)\quad ar:=2*pi\)
\((10)\quad ar:=ar*r\)
\((11)\quad print\;ar\)

流图

流图 是在已经划分基本块的基础上,构造一个有向图。

  1. 两个相邻基本块如果上面的没有跳转,可以直接和下面的相连
  2. 如果当前基本块最后存在无条件跳转,直接和跳转的目标基本块相连
  3. 如果当前基本块存在最后有条件跳转,需要先和下面相邻的基本块相连,然后和跳转的目标基本块相连

上面的基本块集合为\(\{B1,B2,B3,B4\}\),可以用有向边集合\(\{B1\rightarrow B2, B2\rightarrow B3, B3\rightarrow B2, B2\rightarrow B4\}\),这里不画图。

循环

支配结点,指的是对任意两个结点m和n来说,如果从流图的首结点出发,到达n的任一通路都要经过m,则称m是n的支配结点,记为\(m\;DOM\;n\)

下图是某个程序的流图,其结点即程序中的基本块
1172605-20190618115453914-1997071527.png

所有结点的支配结点集D(n):
\(D(1)=\{1\}\)
\(D(2)=\{1,2\}\)
\(D(3)=\{1,2,3\}\)
\(D(4)=\{1,2,4\}\)
\(D(5)=\{1,2,4,5\}\)
\(D(6)=\{1,2,4,6\}\)
\(D(7)=\{1,2,4,7\}\)

该图的有向边集合为:\(\{1\rightarrow 2, 2\rightarrow 3, 2\rightarrow 4, 3\rightarrow 4, 4\rightarrow 2, 4\rightarrow 5, 4\rightarrow 6, 5\rightarrow 7, 6\rightarrow 6, 6\rightarrow 7, 7\rightarrow 4\}\)

回边指的是存在一条边\(A\rightarrow B\),使得\(B\in D(A)\)。故上图的回边有\(4\rightarrow 2, 6\rightarrow 6,7\rightarrow4\)

一个循环由其中的一条回边\(A\rightarrow B\)对应的两个结点\(B,A\),以及有通路到达\(A\)而不经过\(B\)的所有结点组成,并且保证\(B\)是该循环的唯一入口结点。

如包含回边\((6\rightarrow 6)\)的循环为\(\{6\}\)
包含回边\((7\rightarrow 4)\)的循环为\(\{4,5,6,7\}\)
包含回边\((4\rightarrow 2)\)的循环为\(\{2,3,4,5,6,7\}\)

这一章可能的考点

  1. 划分基本表、画出流图、求支配集、找回边、找循环
  2. 代码局部优化

PL/0编译程序

因为居然还有编程填空题这种恐怖存在,需要了解下面这些内容,不然填空都不知道怎么填。

可以用的全局变量如下:

全局变量含义
sym当前读取到的符号类型
num当前读取到的值
id当前读取到的标识符名称
cx当前中间代码将被写入时的索引
tx当前符号表将被写入的索引
code指令数组,类型为instruction

在分析控制流的函数可以用的变量如下:

变量含义
cx1,cx2分别记录条件为真/假时需要跳转的地址

instruction的结构体如下:

typedef struct
{int f; // 函数类别int l; // 层级int a; // 地址/立即数/操作类别
} instruction;

函数类别和操作类别如下:

enum opcode
{LIT,    // 取立即数OPR,    // 操作LOD,    // 读取STO,    // 保存CAL,    // 调用INT,    // 初始化空间JMP,    // 无条件跳转JPC     // 有条件跳转
};enum oprcode
{OPR_RET, OPR_NEG, OPR_ADD, OPR_MIN,OPR_MUL, OPR_DIV, OPR_ODD, OPR_EQU,OPR_NEQ, OPR_LES, OPR_LEQ, OPR_GTR,OPR_GEQ
};

符号类别如下:

enum symtype
{NUMBER,// 符号类型PLUS,MINUS,TIMES,SLASH,ODD,EQU,        // =NEQ,        // <>LES,        // <LEQ,        // <=GTR,        // >GEQ,        // >=LPAREN,     // (RPAREN,     // )COMMA,      // ,SEMICOLON,  // ;PERIOD,     // .// 关键字BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM,DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCEDURESYM
}

可以用的全局函数如下:

全局函数含义
getsym获取下一个符号的类型到sym。如果sym是number,则num将会存放值;如果sym是标识符,id将存放标识符名称
gen生成下一条指令,cx加1

处理while循环的题目

1172605-20190618155730005-294536242.png

<while语句> ::= <while><条件><do><语句>

case WHILESYM:__________;                        // 第一个空为cx1 = cx,记录JMP要跳转的位置getsym();condition(SymSetAdd(DOSYM, FSYS), LEV, TX);__________;                 // 第二个空为cx2 = cx,记录JPC指令的位置gen(JPC, 0, 0);if (__________)                 // 第三个空为sym == DOSYM,处理到dogetsym();elseerror(18);statement(fsys, lev, tx);gen(__________);                // 第四个空为jmp, 0, cx1,要知道跳转回开始判断条件的地方__________;                        // 第五个空为code[cx2].a = cx,回填JPC指令的跳转位置break;

处理if或if-else条件语句的题目

if条件语句图
1172605-20190619194243644-432480857.png

if-else条件语句图
1172605-20190618160421228-1678967094.png

<条件语句> ::= <if><条件><then><语句>[<else><语句>]

下题处理了if条件语句和if-else条件语句的情况:

case IFSYM:getsym();condition(SymSetUnion(SymSetNew(THENSYM, DOSYM), FSYS), LEV, TX);if (SYM == THENSYM)getsym();elseerror(16);________;                           // 第一个空为cx1 = cx;,记录JPC位置待回填gen(JPC, 0, 0);statement(SymSetUnion(SymSetNew(ELSESYM), FSYS), LEV, TX);if (__________)                 // 第二个空为SYM != ELSESYM,此时在分析else符号code[cx1].a = cx;else{getsym();cx2 = cx;gen(JMP, 0, 0);__________;                 // 第三个空为code[cx1].a = cx,此时在分析false部分的语句开头,回填JPC的地址statement(FSYS, LEV, TX);__________;                 // 第四个空为code[cx2].a = cx,此时为执行完true部分语句后的JMP回填跳转地址}break;

转载于:https://www.cnblogs.com/X-Jun/p/11042544.html

这篇关于编译原理--04 符号表、运行时存储组织和代码优化复习(清华大学出版社第3版)...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/389811

相关文章

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》:本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实