程序设计语言的转换

翻译

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

编译型

如 c,c++

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

解释型

如 python，basic

  • 接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。逐个语句的翻译并执行
  • 特点：效率低，不产生目标程序

编译的转换过程

  • 两个阶段：编译、运行

image-20220527200338062

image-20220527200420788

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

image-20220527201456290

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

编译程序概述

编译程序的五个阶段

  • 词法分析，
  • 语法分析，
  • 语义分析与中间代码产生
  • 优化
  • 目标代码生成

image-20220527202529532

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

词法分析

词法分析任务

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

image-20220527205221077

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

转换

  • 对基本字，运算符，界限符的转换（按预设）
  • 对标识符的转换，用户自定义的符号
  • 常数的转换
  • 转换后的格式：类号+内码

描述词法规则的工具

正规式&有限自动机

语法分析

语法分析任务：

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

语法规则：

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

语法规则的表示：

  • BNF: A::=B|C
  • 如，<句子>::=<主><谓><宾> 表示：句子定义为主+谓+宾 而<主>::=<定><名>

image-20220527210631043

赋值语句的语法规则：

  • 赋值号左边：
  • 赋值号右边：可以是个表达式（混合运算）
  • E定义为算法运算
  • T定义为乘法运算
  • F定义为标识符或常数

语法分析的文法

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

推导

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

最右推导—最左归约

image-20220527211221511

每次将式子中，最右的终结符号替换成其它值，并且最终要尽量变成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+TC ** C是常数，因为式子里面x=a+b\*50 是50 V=E+**T50

  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

归约

  • 最右归约、最左归约

刚刚看了最右推导（对应最左归约），现在看最左推导（对应最右归约）

最左推导—最右归约

image-20220527220321129

每次替换最左边的终结符

序号 替换 产生式
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

推导与归约的应用

image-20220527221828575

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

语法树

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

image-20220527221846687

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

image-20220527221945434

语义分析与中间代码

任务：

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

两个阶段的工作：

  • 对每种语法范畴进行静态语义检查
  • 若语义正确，就进行中间代码的翻译，如：蚂蚁吃大象，就是无意义的

中间代码的形式

  • 四元式
  • 三元式
  • 逆波兰式

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

image-20220527222412807

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

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

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

image-20220527223241421

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

image-20220527223645047

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

优化

任务

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

原则

  • 等价变换（功能不变）

优化的主要方面

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

目标代码生成

任务

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

目标代码形式

  • 绝对指令代码:可立即执行的目标代码。如exe文件
  • 汇编指令代码:汇编语言程序，需要通过汇编程序汇编后才能运行。
  • 可重定位指令代码:先将各目标模块连接(link)起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。

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

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

表格管理

image-20220527224250109

表格的作用

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

作用阶段

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

符号表

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

比如：

1
2
3
void main(){
	int m,n,k
}

image-20220527224435933

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

常数表

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

标号表

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

出错处理

任务

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

错误类型

  • 语法错误: 在词法（第一阶段）分析和语法（第二阶段）分析阶段能检测出来。比如：单词写错
  • 语义错误: 一般在语义分析（第三阶段）阶段检测。语义上的不可达，某些功能无法实现，可以报错，比如：除以了0

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

遍

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

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

多遍扫描

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

  • 优点:节省内存空间，提高目标代码质量，使编译的逻辑结构清晰。
  • 缺点:编译时间较长。
  • 注:在内存许可情况下，还是遍数尽可能少些为好。

一遍扫描

==以语法分析为中心==

image-20220527230211052

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

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

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

编译程序生成

  • 1.直接用机器语言编写编译程序（01代码）
  • 2.用汇编语言编写编译程序
    • image-20220528091050544
    • 注:编译程序核心部分常用汇编语言编写
    • 源代码需要经过编译得到目标程序
    • 编译.exe又是通过汇编语言写的代码产生的
    • 编译的源代码需要经过汇编得到编译.exe
  • 3.用高级语言编写编译程序
    • image-20220528092615926
    • 注:这是普遍采用的方法
    • 源代码需要经过编译得到目标程序
    • 编译.exe又是通过C语言写的代码产生的
    • 编译的源代码需要经过C语言编译得到编译.exe
  • 4.编译工具：LEX(词法分析)与YACC（自动产生语法分析）
  • 5.移植：同种语言的编译程序在不同类型机器移植