《编译原理》课堂笔记(1)

有关信息

编译程序是计算机系统的核心支撑软件
贯穿程序语言、运行时系统、体系结构
大量专业工作与编译技术相关

教学目的要求

  • 掌握编译程序/系统设计的基本原理
  • 掌握“常见”语言机制的实现技术
  • 经历开发一个小型编译程序的主要阶段
  • 自学并使用自动构造工具
  • 加深对计算机系统的理解
  • 会将所学知识灵活应用

实验项目

实现一个小型面向对象语言(给定架构下扩展或改造)

编译程序(系统)概述

什么是编译程序

从基本功能来看,编译程序(Compiler)是一种翻译程序(Translator)

  • 将语言A的程序翻译为语言B的程序
  • 称语言A为源语言(Source Language)
  • 称语言B为目标语言(Target Language)

编译程序是较为复杂的翻译程序

  • 需要对源程序进行分析(Analysis):识别源程序的语法结构信息,理解源程序的语义信息,反馈相应的出错信息
  • 根据分析结果及目标信息进行综合(Synthesis):生成语义上等价于源程序的目标程序

较为简单的翻译程序包括预处理程序(Preprocessor)和汇编程序(Assembler)
编译程序通常是从较高级语言的程序翻译至较低级语言的程序。

传统的编译程序

  • 源语言通常为高级语言
  • 目标语言通常为机器级语言或较低级的虚拟机语言

编程语言的主要范型(Paradigms)包括:

  • 命令式语言(Imperative Languages):Fortran、Algol、Cobol、C、C++、Pascal、Basic、Java、C#……
  • 面向对象语言(Object-Oriented Languages):Smalltalk、Simula67、Java、C++、C#……
  • 陈述式语言(Declarative Languages):函数式(Functional):Lisp、Scheme、Haskell、ML、Caml……;函数型(Logic):Prolog……
  • 并发语言(Concurrent Languages):并发Pascal、Ada、Java、Linda、HPF、OpenMP
  • 其他:同步语言(Synchronous Languages):Signal、Lustre……;脚本语言(Scripting Languages):Perl、PHP……

编译基础设施(Compiler Infrastructure):

  • 共享的编译程序研究/开发平台
  • 多源语言多目标机体系结构
  • 多级中间表示

编译程序的逻辑结构

编译程序在逻辑结构上至少包含两大阶段:

  • 分析(Analysis)阶段:理解源程序,挖掘源程序的语义
  • 综合(Synthesis)阶段:生成与源程序语义上等价的目标程序

编译程序的前端、中端和后端

  • 前端(Front End):实现主要的分析任务,通常以第一次生成中间代码为标志
  • 后端(Back End):实现主要的综合任务(目标代码生成和优化),通常以从最后一级中间代码生成目标代码为标志
  • 中端(Middle End):实现各级中间代码上的操作(中间代码生成与优化)

典型编译程序的逻辑过程

comp1-1.png
前端:没有本质过程
中端:开始本质优化
后端:生成目标代码
1. 词法分析
扫描源程序字符流识别出有词法意义的单词,返回单词的类别和单词的值,或词法错误信息
例:保留字、标识符、分隔符、字符串常量……
2. 语法分析
(如果程序正确)以单词作为终结符,进行语法分析(需要一个上下文无关文法),生成语法分析树(叶子是单词)
3. 语义分析
对语法分析后的程序进行语义分析,不符合语义规则时给出语义错误信息
语法分析只能计算出与上下文无关文法有关的部分
4. 符号表
收集每个名字的各种属性用于语义分析及后续各阶段
5. 出错处理
检查错误:报告出错信息(error reporting)
排错:恢复编译工作(error recovery)
6. 中间代码生成
刚才生成的是具体语法树,对后续分析作用不大
抽象语法树AST
从抽象语法树生成三地址码TAC
7. 目标代码生成
生成目标机代码(MIPS汇编码之类的……)

小结

典型编译程序的主要逻辑模块:词法分析模块、语法分析模块、语义分析模块、中间代码生成模块
中间代码优化模块、目标代码生成模块、目标代码优化模块、符号表管理模块、错误处理模块

编译程序的组织

编译程序的遍(Passes/Phases)

  • 对一种代码形式从头到尾扫描一遍
  • 将一个代码空间变换到另一个代码空间
  • 代码空间=代码+符号表+其他有用信息

编译程序的组织取决于各遍的组织

  • 单遍编译程序,多遍编译程序
  • 多个遍之间有逻辑上的先后关系
  • 多个遍的实现可采用顺序结构或并发结构(不常用)

例:一个以语法、语义分析程序为中心的单遍编译程序组织

编译程序的伙伴程序

解释程序(Interpreter)

  • 不产生目标程序文件
  • 不区别翻译阶段和执行阶段
  • 翻译源程序的每条语句后直接执行
  • 程序执行期间一直有解释程序守候
  • 常用语实现虚拟机

预处理程序(Preprocessor)

  • 支持宏定义(Macro Definition)
  • 支持文件包含(File inclusion)
  • 支持其他更复杂的源程序扩展信息

汇编程序(Assembler)

  • 翻译汇编语言程序至可重定位(Relocatable)的机器语言程序

装入和链接程序(Loader and Link-editor)

  • 装入程序对可重定位机器语言程序进行修改,将相对地址变换为机器绝对地址
  • 链接程序合并多个可重定位机器语言程序文件到同一个程序
  • 装入和链接程序产生最终可执行的机器语言程序

调试程序(Debugger)

  • 反馈目标程序运行时信息
  • 将目标程序运行时信息与源程序关联
  • 断点管理、单步跟踪、读写目标机状态等功能
编译程序与T型图
S:源语言
T:目标语言
I:编译程序的实现语言
comp1-2.png
T型图是可以叠加的。
本地编译器和交叉编译器

用已有的语言L1实现新的语言L2

comp1-3.png
步骤:
(1)用L1语言编写L2语言到M机器语言的编译程序
(2)将该L2语言编译程序用L1语言编译程序进行编译

编译程序的移植

comp1-4.png
将机器A上的语言L移植到机器B,步骤:
(1)用L语言编写L语言到B机器语言的编译程序X
(2)用L编译程序对X进行编译,产生一个能在机器A上运行的产生B机器代码的编译程序Y(交叉编译程序)
(3)再用Y对X进行编译,得到可以在机器B上运行的L语言编译程序

教学内容预览

课堂教学内容及课时计划

  • 编译程序/系统概述 2学时
  • 实验项目简介 3学时(穿插介绍)
  • 词法分析 1学时
  • 语法分析 自顶向下(3学时) 自底向上(5学时)
  • 语法制导的语义计算基础 3学时
  • 符号表组织 1学时
  • 语义分析 1学时
  • 中间代码生成 3学时
  • 运行时存储组织 2学时
  • 目标代码生成 2学时
  • 代码优化 3学时

实践部分

Decaf/Mind项目

  • PA1 词法和语法分析
  • PA2 静态语义分析
  • PA3 中间代码生成
  • PA4 简单数据流分析或简单优化(选做)


新增一则回应

除非特别注明,本页内容采用以下授权方式: Creative Commons Attribution-ShareAlike 3.0 License