#编译原理# 概论(一)

  • 2019 年 10 月 3 日
  • 筆記

概论

编译原理笔记第一部分,内容参考:北航软院教师邵兵课堂课件及内容、张莉著《编译原理及编译程序构造》、国防工业出版社的《编译原理——学习指导与典型题解析》、AlvinZH的学习笔记以及个人理解

目前是包含了全部内容的版本,后续会推出精简版和复习知识点版

如有建议或错误错误欢迎在评论中指出或联系我:QQ:847590417

阅读目录

1.1 编译的一些基本概念

1.2 编译的全过程

1.3 编译程序的构造

1.4 编译程序的前后处理器

1.5 编译技术的应用

 

1.1 编译的一些基本概念

低级语言(Low level language)

– 字位码、机器语言、汇编语言

– 特点:与特定的机器有关,功效高,但使用复杂、繁 琐、费时、易出错。

高级语言

– Fortran、Pascal、C语言等

– 特点:不依赖具体机器,移植性好,对用户要求低,易使用,易维护等。

源程序:用编译语言或高级语言编写的程序

目标程序(目标代码):用目标语言所表示的程序,目标语言:没有硬性规定,可以是某种机器的汇编语言、机器语言,也可以是介于源语言和机器语言之间的“中间语言”。

翻译程序:将源程序转换为目标程序的程序成为翻译程序。它是指各种语言的翻译器,是汇编程序、编译程序以及各种变换程序的总称

三者关系:源程序是翻译程序的输入,目标程序是翻译程序的输出

汇编程序:

源程序用汇编语言书写,经过翻译程序得到用机器语言表示的程序吗,这时的翻译程序就称之为汇编程序,这种翻译过程称为“汇编”

编译程序:

源程序用高级语言书写,加工后得到目标程序,这种翻译过程称为“编译”

汇编程序和编译程序都是翻译程序,只是就爱共对象不同,汇编语言格式件单和机器语言有一一对应关系,所以汇编程序要做的翻译工作比编译程序简单得多。

 

从源程序到真正使用程序有两个阶段:编译、运行

编译或汇编阶段即源程序通过编译程序、汇编程序等翻译程序变为目标程序

运行阶段即通过向目标程序和其运行子程序之中输入数据然后得到输出数据

 

解释程序:对源程序进行解释执行的程序,对变异的道德中间语言进行解释执行的程序。源程序转化为解释程序:

 

1.2 编译的全过程

将高级语言程序翻译成等价的目标程序的过程,一般分为五个基本阶段:

词法分析,语法分析,语义分析和生成中间代码,代码优化,生成目标程序

1.词法分析:

分析和识别单词

即扫描源程序(字符串),根据语言的此法规则分析并识别单词,并以某种编码形式输出。

单词:是语言的基本语法单位,一般语言有四大类单词:语言定义的关键字或保留字,标识符(变量名字),常数(常量),分界符(运算符、特殊符号)。词即最小的有意义的单词。

该赋值语句便可识别出9个单词

 

2.语法分析:

根据相应语言的文法,分析并识别出各种语法成分,如表达式、各种说明、语句、过程、函数等,并进行语法正确性检查。

利用这种文法,语法分析便可根据其将<>中的内容给识别出来,并进行语法检查,如有错误则会输出错误信息。

 

3.语义分析、生成中间代码:

对识别出的各种语法成分进行语义分析,并产生相应的中间代码

中间代码时一种介于源语言和目标语言之间的中间语言形式,生成的目的:1.便于做优化处理,2.便于编译程序的移植(不必依赖于目标计算机,便于转换成其他形式)

中间代码的形式:编译程序设计者可以自己设计,常用的有四元式、三元式、逆波兰表示等。

例如:

首先识别出是赋值语句,然后分析与以上的正确性,正确后生成中间代码

四元式(三地址指令):

 

 

4.代码优化:

从四元式形式的中间代码可知,第一句是常量的计算,所以为了进行优化可以在编译时计算出结果放在工作单元中,这样不必每次都生成目标指令计算。

 

然后还可以对临时工作单元的数量进行优化:T2变为T1,此时便可减少一个单元的使用。

 

5.生成目标程序:

生成中间代码后,便很容易生成目标程序(地址指令序列)了,这部分工作和机器关系很密切,所以需要根据具体机器进行。在这部分工作需要注意充分利用累加器,生成时也可进行优化处理。(该过程需要保持语义的等价性)

 

1.3 编译程序的构造

1.3.1 逻辑结构

根据逻辑功能不同,可将编译过程划分为五个基本阶段,相对应可以将实现整个编译过程的编译程序划分为五个逻辑阶段:

 

五个阶段都要做两件事:建表和查表和出错处理,即编译程序中都要包括表格管理和出错处理两部分

表格管理(建表和查表):

即及时的把源程序中的信息和编译过程中所产生的信息登记在表格中,而在随后的编译过程中同时又要不断地查找这些表中的信息,编译过程贯穿着建表和查表的工作。

出错处理:

规模较大的源程序难免有多种错误,编译程序必须要有出错处理的工作,即能诊断出错误,并向用户报告错误性质和位置,以便用户修改源程序。出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。

如上便是典型编译程序的七个逻辑部分,五个逻辑阶段加上两个一直需要进行的工作。

 

1.3.2 遍(pass)

遍:对源程序(包括源程序的中间形式)从头到尾扫描一次,并作有关的加工处理,生成新的源程序中间形式或目标程序,通常称之为一遍:

一次遍就是完成五个基本阶段的工作,需要经过几次扫描处理

一次扫描就可完成整个编译工作的称为“一遍扫描编译程序”,一遍扫描的编译程序以语法分析程序为核心。

分遍可为编译程序的移植创造条件,主要缺点是增加了不少的重复性工作。

其结构为:

 

start pass到over pass(SP,OP大概是这个意思)

 

1.3.3 前端和后端

根据编译程序各部分的功能可将编译程序分成前端和后端

前端:和源程序、源语言有关的这一部分、包括词法分析、语法分析、语义分析、中间代码生成、代码优化这些分析部分

后端:和目标机有关的部分,包括目标程序生成,和目标机有关的优化这些综合部分

划分的原因:

这是一种传统方法,可以实现采用同一个编译程序的前端,金改写后端便可生成不同目标机上的相同源语言的编译程序,并且还可以前后端并行进行工作。

 

1.4 编译程序的前后处理器

左为前,右为后

源程序:多文件、宏定义和红调用,包括文件

目标程序:一般为汇编程序或可重定位的机器代码

 

 

1.5 编译技术的应用

语法制导的结构化编译器,程序格式化工具,软件测试工具,程序理解工具,高级语言的翻译工具等等。