【编译原理】Chapter1概述

课程主要内容：程序设计语言编译程序构造的基本原理和基本实现技术

什么是编译程序

翻译程序(Translator)
把一种语言程序（源语言程序）等价地转换成另一种语言程序（目标语言程序）的程序

编译程序
一种翻译程序，实现将一种高级语言程序转换为另一种低级语言程序

编译程序分类
诊断编译程序(Diagnostic Compiler)：帮助程序员调试
优化编译程序(Optimizing Compiler)：专注目标代码的效率提升
交叉编译程序(Cross Compiler)：编译程序所在的宿主机和机器语言程序运行的目标机不同的Compiler
可变目标编译程序(Retargetable Compiler)：在不同目标机上运行时只需要重新编译与目标机相关代码的Compiler
解释程序
将源程序作为输入，边解释边执行源程序，在这个过程中并不会产生目标程序

编译VS解释
两者最大的区别在于是否产生了目标语言的程序

为什么要学编译原理

计算思维(Computational Thinking)

概念
利用计算机科学的基础概念去求解问题、设计系统和理解人类的行为
举例
编译理论与技术：理论与实践相结合的最好典范
抽象：图灵机是对计算的抽象，The Church-Turing thesis，描述高级语言词法规则的有限自动机，描述语言语法的形式文法
自动化：在计算机上实现抽象思维的结果，自动产生编译分析工具
分解(Decomposition)：将大规模的复杂问题分解为若干个较小规模的、更简单的问题加以解决。编译程序引入中间语言，高级语言->中间语言->目标语言；编译被分为多个阶段；一个分析阶段分为多遍扫描

递归(Recursion)：语法分析中递归下降分析，语义分析中基于树遍历的属性计算，语法制导翻译
权衡(Tradeoff)：用上下文无关文法来描述和处理高级语言程序，选择优化措施

学习意义

1. 学习编译程序构造原理和技术
2. 更好地理解高级语言
3. 运用编译原理和方法构造实用工具

编译原理和方法的应用

1. HTML/XML分析：浏览器利用词法、语法分析等方法将html文本转换表现形式
   
2. 语言处理工具：词法分析、语法分析
   字处理软件如word、wps
   
   

编译过程

概述

用人类自然语言翻译进行类比，把英文翻译为中文

词法分析

任务
接受源程序作为输入，对构成源程序的字符串进行扫描和分解，识别出单词符号
input为源程序字符串
output为识别出来的单词符号串，用单词属性二元组表示
原则
程序设计语言的词法规则
描述工具
使用有限自动机进行形式化描述
举个例子

语法分析

任务
根据语法规则将语法分析得到的单词符号串分解为各类语法单位
output用语法结构树表示
原则
语法单位构成的语法规则
描述工具
上下文无关文法
举个例子

中间代码生成

任务
对各类语法单位按语言的定义进行初步翻译，在这一阶段需要完成静态语义检查，中间代码生成，从翻译的角度阐明语法单位的意义
output为三元式、四元式或语义分析树
原则
语义规则
描述工具
属性文法
举个例子

优化

任务
加工变换前阶段产生的中间代码，帮助最后程序最后能产生一个更高效的目标代码（高效指时间、空间上有更高的效率）
原则
程序的等价变换规则
举个例子

优化前的中间代码：400次加法，200次乘法

优化后的中间代码：304次加法

目标代码产生

任务
生成目标语言程序代码
原则
目标平台的硬件系统结构和机器指令的含义
目标代码三种形式

1. 汇编指令代码：生成的是汇编程序，需要机器上的汇编程序进一步将其翻译为机器代码
2. 绝对指令代码：可以运行的目标语言代码
3. 可重定位指令代码：编译好的模块代码，需要装载、链接以执行的程序代码，基址+相对地址
   举个例子
   
   这里展示的是将汇编指令翻译为可重定位的指令代码
   16为指令，前4位为操作码，两位为寄存器操作数，两位为第二操作数类型，8为为变量地址或立即数的值，L为当前模块基址

编译程序的结构

编译程序总框

出错处理

出错处理程序
发现源程序中的错误并将有关错误信息报告给用户
分类
语法错误和语义错误
语法错误
不符合语法（或词法）规则的错误
eg: 非法字符、括号不匹配、缺少;等等
语义错误
不符合语义规则的错误
eg: 说明错误，作用域错误，类型不一致等等

遍(pass)

对源程序或源程序的中间表示从头到尾扫描一遍
阶段和遍
一遍可以由若干阶段组成，如语法制导翻译（将词法分析、语法分析和语义分析即中间代码生成用用一遍来完成，其中三个阶段对应三个子程序，并由语法分析子程序驱动整个过程进行。具体而言，语法分析调用词法分析得到token，从token序列中识别出语法结构，对识别出来的语法结构调用语义分析子程序生成对应的中间代码，即完成了翻译过程）
一个阶段可分若干遍完成，如代码优化阶段（第一遍识别中间代码总体结构，第二遍进行初步优化，第三遍进行循环优化…）

编译前端和后端

编译前端
编译过程中与源语言有关与目标机无关的的部分
词法分析、语法分析、语义分析和中间代码生成、与机器无关的优化
编译后端
编译过程中与源语言无关与目标机有关的的部分
与目标机有关的优化，目标代码的产生
前端后端划分好处

1. 使得编译程序逻辑结构清晰
2. 将优化阶段划分为与目标机无关的优化和与目标机有关的优化可使得代码优化更加充分
3. 有利于编译程序移植，在同一机器上编译不同源语言只需修改前端，在不同机器上编译相同源语言只需要修改后端
   体现了计算思维中的分解和权衡

编译程序的生成

使用机器语言和汇编语言

优点：针对具体机器充分发挥计算机的系统功能；生成程序执行效率高
缺点：程序难读、难写、易出错、难维护、生成效率低

使用高级语言

引入T型图描述编译关系

程序易读、易写、易维护、生成效率高

生成方法

思想：利用已有的某种语言的编译程序实现另一语言的编译程序

需要得到L2语言在A机器上的编译程序，先用L1语言书写，使用L1语言的编译程序进行编译，即可得到机器指令实现的L2语言的编译程序

移植方法

把A机器上的编译程序移植到B机器上

首先有了L语言编写的L语言到B代码的编译程序，现在只有能将L语言编译为A代码的编译程序，构造以下，现在有了能运行的将L语言编译为B代码的编译程序，再拿来编译一下，得到用B代码编写的L语言的编译程序√

自编译方法

先对$L_{sub}$编写编译程序，再利用$L_{sub}$编写L的编译程序，不断扩展

编译程序自动生成

LEX：词法分析程序产生器
YACC：语法分析程序产生器

参考资料

1. 国防科技大学编译原理课程视频