【Compiler】-1-编译原理概述

title: 【Compiler】-1-编译原理概述
author: lthero
comments: true
date: 2022-05-27 19:56:57
tags: [编译原理,compiler]
cover: 
categories: [编译原理,compiler]

程序设计语言的转换

翻译

  • 是指能把某种语言的源程序,在不改变语义的条件下,转换成另一种语言程序———目标语言程序。

编译型

如 c,c++

  • 专指由高级语言转换成低级语言,将整个源程序翻译成低级语言

解释型

如 python,basic

  • 接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句。逐个语句的翻译并执行

  • 特点:效率低,不产生目标程序

编译的转换过程

  • 两个阶段:编译、运行

  • 三个阶段:编译、汇编、运行

目标代码可能是obj文件,不一定为exe文件,obj文件运行前需要link动作,如一些include需要link来实现

编译程序概述

编译程序的五个阶段

  • 词法分析,

  • 语法分析,

  • 语义分析与中间代码产生

  • 优化

  • 目标代码生成

其中的语义分析器会和语法分析器中间代码生成结合

词法分析

词法分析任务

  • 对程序内的字符串进行扫描和分解,识别出单词符号,如:基本字、标识符、常数、数字……

  • 续:识别出来后,需要转换成统一规格,给语法分析使用。

转换

  • 对基本字,运算符,界限符的转换(按预设)

  • 对标识符的转换,用户自定义的符号

  • 常数的转换

  • 转换后的格式:类号+内码

描述词法规则的工具

正规式&有限自动机

语法分析

语法分析任务:

  • 在词法分析的基础上,根据语言的语法规则,把单词符号分解成各类语法单位。如短语,子句,句子,程序段,程序等。

语法规则:

又称为文法,规定单词如何构成短语,语句、过程、程序

语法规则的表示:

  • BNF: A::=B|C

  • 如,<句子>::=<主><谓><宾> 表示:句子定义为主+谓+宾 而<主>::=<定><名>

赋值语句的语法规则:

  • 赋值号左边:

  • 赋值号右边:可以是个表达式(混合运算)

  • E定义为算法运算

  • T定义为乘法运算

  • F定义为标识符或常数

语法分析的文法

  • 分为推导 归约 ,而且推导的逆过程就是归约

推导

  • 分为:最左推导、最右推导

最右推导---最左归约

每次将式子中,最右的终结符号替换成其它值,并且最终要尽量变成x=a+b*50

  1. E变成E+T 产生式:V=E+T 现在最右边是T,再去推T

  2. T变成T*F 产生式:V=E+T*F现在最右边是F,再去推F

  3. F变成C 产生式:V=E+T*C C是常数,因为式子里面x=a+b\*50 是50 V=E+T*50

  4. T变成F 为什么上面的T变成T * F,这里变成F??要根据x=a+b*50这个式子,T现在所在位置只能放一个F,不能再变成一个T * F这样式子 产生式:V=E+F*50

  5. F变成V 变成标识符b,理由同上 产生式:V=E+b*50

  6. E变成T 产生式:V=T+b*50

  7. T变成F 产生式:V=F+b*50

  8. F变成V 产生式:V=V+b*50

  9. V变成x=a+b\*50的a 产生式:V=a+b*50

  10. V变成x=a+b\*50的x 产生式:x=a+b*50

归约

  • 最右归约、最左归约

刚刚看了最右推导(对应最左归约),现在看最左推导(对应最右归约)

最左推导---最右归约

每次替换最左边的终结符

序号 替换 产生式
1 原式子V=E
2 将V替换成x x=E
3 将E替换成E+T x=E+T
4 将E替换成T x=T+T
5 将左边T替换成F x=F+T
6 将F替换成V x=V+T

省略……

最右归约呢,要从x=a+b*50这个式子的右开始出发

替换说明 产生式
原式子:x=a+b*50
将50替换成C x=a+b*C
将C替换成F x=a+b*F
F不能再变成T,因为规则中没有:某个符号*T
所以b变成V x=a+V*F
V变成F x=a+F*F
F变成T x=a+T*F
T*F变成T x=a+T
a变成V x=V+T
V变成F x=F+T
F变成T,T再变成E x=E+T
E+T变成E x=E
x变成V V=E

最终x=a+b*50,向左逐个变成了V=E

推导与归约的应用

像上面用最右推导,无法得到对应的公式,所以有错误

语法树

语法分析过程也可以用一颗树表示

如,下面这个公式对应的语法树就无法构建,所以有错误

语义分析与中间代码

任务:

对语法分析识别出的各类语法范畴,公析其含义,进行和初步翻译,产生介于源代码和目标代码之间的一种代码。

两个阶段的工作:

  • 对每种语法范畴进行静态语义检查

  • 若语义正确,就进行中间代码的翻译,如:蚂蚁吃大象,就是无意义的

中间代码的形式

  • 四元式

  • 三元式

  • 逆波兰式

比如将x=a+b*50 变成中间代码,这个就是四元式(算符、左操作数、右操作数、结果)

比如将下面代码转换成中间代码

i=33,j=44;
for(k=1;k<=100;k++){
    m=i+10*k;
    n=j+10*k;
}

初步换成中间代码,发现有代码可以再被替换

再优化后,发现,原来的m=i+10*k;里面的乘法被替换成m=m+10,减少了乘法的次数,提升了效率

因为高级语言可能看不出来什么优化空间,但从底层逻辑来看,还是可以再次优化

优化

任务

  • 对前面产生的中间代码进行加工变换,以期在最后阶段能产生更为高效的目标代码。

原则

  • 等价变换(功能不变)

优化的主要方面

  • 公共子表达式的提取(直接查表)、合并已知量、删除无用语句、循环优化等

目标代码生成

任务

  • 把经过优化的中间代码转化成特定机器上的低级语言代码

目标代码形式

  • 绝对指令代码:可立即执行的目标代码。如exe文件

  • 汇编指令代码:汇编语言程序,需要通过汇编程序汇编后才能运行。

  • 可重定位指令代码:先将各目标模块连接(link)起来,确定变量、常数在主存中的位置,装入主存后才能成为可以运行的绝对指令代码。

现在绝对指令代码起来越少了,因为不同机器上的绝对指令代码不同,那么不同机器生成的程序不一定通用

如果是汇编指令代码,则生成的内容,只要重新汇编后,就能在不同机器上运行

表格管理

表格的作用

  • 用来记录源程序的各种信息以及编译过程中的各种状况。

作用阶段

  • 符号表、常数表、标号表、分程序入口表、中间代码表等。

符号表

  • 用来登记源程序中的常量名、变量名、数组名、过程名等,记录它们的性质、定义和引用情况。

比如:

void main(){
    int m,n,k
}

通过查表,就能知道不同的变量的类型,存储地址,占用内存的大小等

常数表

  • 每种类型记录对应一张表,如整数型,浮点型……

标号表

  • 登记标号的定义与应用,当扫描器识别出一个(标识符)后,把对应名字填写到标号表,但它的各种属性需要在后续阶段才能填入。比如:名字的类型需要在语义分析时才能确定

出错处理

任务

  • 如果源程序有错误,编译程序应设法发现错误,并报告给用户。

错误类型

  • 语法错误: 在词法(第一阶段)分析和语法(第二阶段)分析阶段能检测出来。比如:单词写错

  • 语义错误: 一般在语义分析(第三阶段)阶段检测。语义上的不可达,某些功能无法实现,可以报错,比如:除以了0

逻辑错误是查不出来的,所以在编译过程中,不处理逻辑错误

  • 指对源程序或源程序的中间结果从头到尾扫描一次,并做有关的加工处理,生成新的中间结果或目标代码。

  • 遍与阶段的含义毫无关系,可以是一遍覆盖所有阶段,也可以是一个阶段重复好几遍

多遍扫描

第一遍扫描源程序,第二遍扫描第一遍产生的结果(词法分析),第三遍扫描中间代码结果……

  • 优点:节省内存空间,提高目标代码质量,使编译的逻辑结构清晰。

  • 缺点:编译时间较长。

  • 注:在内存许可情况下,还是遍数尽可能少些为好。

一遍扫描

以语法分析为中心

主程序是“语法分析程序”

主程序调用“扫描器”取单词,“扫描器”返回类号、内码。

主程序调用“语义子程序”进行归约过程

编译程序生成

  • 1.直接用机器语言编写编译程序(01代码)

  • 2.用汇编语言编写编译程序

    • 注:编译程序核心部分常用汇编语言编写

    • 源代码需要经过编译得到目标程序

    • 编译.exe又是通过汇编语言写的代码产生的

    • 编译的源代码需要经过汇编得到编译.exe

  • 3.用高级语言编写编译程序

    • 注:这是普遍采用的方法

    • 源代码需要经过编译得到目标程序

    • 编译.exe又是通过C语言写的代码产生的

    • 编译的源代码需要经过C语言编译得到编译.exe

  • 4.编译工具:LEX(词法分析)与YACC(自动产生语法分析)

  • 5.移植:同种语言的编译程序在不同类型机器移植

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录