Compiler01 Introduction
2020-12-26 23:42:00 # Compiler

看的是英文版的龙书,各种翻译看看就好...

大概前半段是课本，后半段是网课的笔记。因为课程好像都不讲Chap. 2，所以下一节的笔记大概就没有课堂内容了

1.1 Language Processors

词汇:

intermediate 中间的

compile 编译

interpret 解释

assemble 汇编

relocatable 可重定位的

编译器指的是将源代码翻译成等价的另一种语言的程序的程序(饶舌)

编译器的一项重要职责是检测error

编译语言的编译和执行是分开的:

  1. 源代码->[编译]->程序

  2. 输入->[执行程序]->输出

解释器是另一种语言处理器,解释语言没有编译过程:

  1. 源代码+输入->[解释]->输出

通常来讲编译器要比解释器快得多(显然)

而解释器通常能更好的检测error(解释器一步步执行)

Java语言结合了翻译(Translate)和解释(Interpret):

  1. 源代码->[翻译]->字节码(bytecode)

  2. 字节码+输入->[虚拟机]->输出 这里的字节码是一种中间程序(intermediate program),其好处在于可以在编译后跨平台解释 有些java编译器直接把字节码翻译成机器语言来加速

从源代码到可执行文件之间不止需要编译器一个程序(过程)

源代码(source code)->[预处理器(preprocessor)]->修改过的源代码(modified sourcecode)->[编译器(compiler)]->汇编语言(assembly program)->[汇编(assembler)]->可重定位机器码(relocatable machine code)->[链接(Linker/Loader)]->目标机器码(target machine code)

通常情况下源代码有多个,它们先被预处理器处理(宏展开 代码替换等)得到修改过的源代码

修改过的源代码然后被给了编译器,编译后得到汇编程序(较抽象 方便调试)

汇编程序传给汇编器后得到relocatable machine code.编译过程中可能会有多个源代码,这时候就要把它们(还有一些需要的部分)链接起来,最后才得到可执行的程序(executable program)

Exercise for 1.1

  1. 编译器和解释器的区别？ 笔记里有
  2. 编译器和解释器的优劣？ 笔记里有
  3. 编译器为什么产生汇编程序而不直接得到机器语言？
  4. Assembly language is easier to produce as output
  5. It is easier to debug (there may be more than one source codes)
  6. 把一种高级语言翻译成另一种高级语言的的编译器叫做“source-to-source translator”.那么用C作为目标语言的编译器有什么好处？ C语言比较通用、易于阅读(compared to other intermediate languages)...C语言的优势都算
  7. 描述一下assembler的任务 笔记里有

1.2 The Structure of a Compiler

词汇:

grammar 语法

lexical 词法的

syntax syntactical 句法 句法的

semantic 语义的

synthesis 合成

constituent 组成的

impose 施加

sound 合理的

coercions 强制类型转换

judicious 明智的

phase 阶段

pass 通路

syntax-directed translation

前面讲了整个编译的过程,后面主要讲Compiler这一部分

编译可以分成两个部分:分析(Analysis)和合成(Synthesis)

Analysis:

compiler的前端(front end)

把源代码分解成若干小部分,再用这些部分构建语法结构,并利用语法结构来建立一种中间表达(Intermediate Representation = IR)

如果Analysis过程中检测到了error(语法错误、语义错误)compiler能够及时报错

同时Analysis过程中compiler会收集一些信息储存在symbol table(一种数据结构)中,并连同IR一起传递给Synthesis过程

##　Synthesis:

compiler的后端(back end)

接收IR和symbol table,并据此产生目标程序

compiler的流程一套下来大概是这样的:

characters->lexical analysis->tokens->syntax analysis->syntax tree(语法树)->semantic analysis->decorated syntax tree->Intermediate code generator->IR->optimizer1->IR->code generator->machine code->optimizer2->machine code

其中symbol table全程在线,随时可用

流程里的optimizer不一定都有,不一定没有,都属于可选项

Lexical Analysis

这是compiler的第一部分,这个部分compiler会读取字符流中的字符,然后得到若干词语(lexeme)组成的序列

每个lexeme都可以表示为形式如下的token:

<token-name, value>

书中举了这样一个例子:


position = initial + rate * 60;

就会被翻译成类似


<id, 1> <=> <id, 2> <+> <id, 3> <*> <num, 60>

这样的语句.此时symbol table就会变成这个样子


1 position 20

2 initial 12

3 rate 0.25

我们看到的


<id, x>

就可以理解成从symbol table中的第x个元素,其余的类似(如果学过汇编可能会理解得好一点)

如果出现了无法识别的字符/词语,那么编译器就会报错

否则Lexical Analysis就会把若干这样的tokens传递给下一个环节

Syntax Analysis/Parsing

在这一环节parser会利用前面的tokens建立一个树形结构来表示语法结构

一个例子是语法树(syntax tree).语法树的每一个节点都代表一个操作(operator),节点的儿子是操作的对象.

语法树的结构有利于维持传统运算的优先级顺序,也就是说它直观上是很好理解的

Semantic Analysis

这一环节semantic analyzer会根据语言的规范，利用语法树和symbol table中的信息来检查源代码的语义.一个具体的检查例子就是typecheck

有的时候语言还有隐式的类型转换，这种时候compiler就需要判断出转换的类型，一个简单的例子是(int x = 60.0 * 2;)

同时，这一阶段还会收集变量的类型等各种信息用于后续过程

IR Generation

在编译过程中可能出现不止一种、不止一次IR，语法树只是其中常用的一种

在词法分析、语法分析、语义分析后，compiler通常会产生一种特殊的IR

它较低级(low-level)，靠近机器语言(machine-like)，所以

  1. 容易生成

  2. 容易翻译成目标机器语言

3AC

3AC(3-adress code)是IR一个例子 (这个东西的形式很像寄存器的各种操作，通常有各种中间变量)

一条常见的3AC指令形如: A = B opt C

  1. 至多一个操作符(可以没有:赋值操作)，至多两个操作变量

  2. 所有操作按固定顺序执行

Opimization

喜闻乐见的优化环节

优化分两种，机器无关(machine dependent)/机器相关(machine independent)，通常指的是运行速度优化

优化还可能包括(更少的能耗/更小的程序)

对IR的优化属于机器无关的优化(为什么?)，其意图在于减少语句的同时保证所有的语句仍然符合IR规范

现代编译器的区别主要在于optimization环节，致力于optimization的compiler被称为"optimizing compilers"

Code Generation

这个环节compiler将IR转变为机器代码(直接操作寄存器、内存)的序列

这一步的重点在于明智地分配寄存器和高效代码的生成

本书到目前为止忽略了identifier(变量)的储存分配，现在只需要知道这在生成IR的环节或这一环节完成就行

Symbol Table Management

这个数据结构记录了变量、变量类型、使用位置、函数等等信息，并且应该支持快速的查找和修改各种信息

(怎么看怎么像BST囧,哪来的table)

Grouping Phases into Passes

一个流程的各逻辑阶段叫做Phases。在实际操作中可能会把多个Phases同时实现(例如同时实现词法和语法分析)

一个读入一段文件并输出一段文件的流程叫做Pass，是流程的实际阶段分割

这一段讲的是compiler的组织结构和模块化

在上面把compiler分为front end和back end的好处在于

  1. 可以用一个语言的前端配上不同机器的后端

  2. 可以用不同语言的前端配上特定机器的后端

语言发展史

机器语言->汇编->Fortran、Cobol、Lisp、C、C++->NOMAD、SQL、Postscript->Prolog、OPS5

一些概念(哪哪都是这几位)

命令式语言(Imperative)

描述操作过程的语言

声明式语言(Declarative)

描述操作目的的语言

冯诺依曼语言

所有以冯诺依曼体系结构为基础的语言都是。基于lambda验算的语言则不是

脚本语言

逐行执行，无需全文编译即可运行的语言

Name&Variable&Identifier

Identifier是一段字符，用来表示某个实体(entity)

Name指的是代码中的某个静态实体，可以是函数/变量/其它。所有的Id都是Name，但Name不都是Id(例如Id.Id也可以表示一个Name)

Variable用来指代运行时Name的动态含义(某个Name究竟指内存中的哪段数据)。

静态/动态

如果一个问题需要运行程序才能得到答案，那么这个问题就是"动态的"，否则是"静态的"

一个经典的问题就是静态/动态的作用域。作用域设计的问题是：在某处提及的Name x究竟是在何处被声明的 x？

静态的作用域很好理解；动态作用域的一个例子出现在OOP中。例如对于父类和子类都实现了的方法method()，x.method();究竟dispatch到哪一个，就依赖于x动态指向的对象。

Environment&State

环境：从Name到储存位置的映射(左值)

状态：从储存位置到值的映射(右值)

那么上面说到的"OOP中函数的作用域由环境决定"的说法就可以理解了，即类中函数的作用域由receiver object在储存中的位置决定。

从这个角度看，Allocation Site Abstraction就是在用Name对Variable建模

上一页
2020-12-26 23:42:00 # Compiler
下一页