【Compilation Principle】 Introduction

发表于 | 分类于 ， | | 阅读次数:

Compilers: computer languages

Translate one language to another
Source language(input) to target language (output)
Source language : high-level language c or c++
Target language : object code, machine code (machine instruction)
一般是从高级语言 -> 低级语言，但是不一定


A Brief History of Compiler

  • Machine language: programs were written in machine language in late 1940s (c706 0000 0002)

  • Assembly language

    Assembler

    Defects: difficult to read/understand, depend on the particular machine

  • FORTRAN: Between 1954 and 1957, by IBM, John Backus

    完全静态的语言（运行前内存分配就已固定，没有指针 -> 指针式动态内存分配的工具）

    多用于工业控制

    对语言进行层次划分，将语法分为type0, type1, type2, type3，四个层次从0-3互为包含关系（从0-3可以看成是从大到小的同心圆）

  • Parsing problem: 1960s and 1970s

  • Optimization techniques: improve compiler efficiency (时间效率、空间效率)
  • Compiler-compilers (parser generator, 语法分析器)
  • YACC (yet another compiler-compiler, 语法分析器): 1975, by Steve Johnson for UNIX.
  • Lex (词法分析器): 1975 by Mike Lest


  • Interpreters

    解释器，与编译器功能相同

  • Assemblers

    汇编器，与编译器配合使用

    source code —>（编译器）—> assembly code —>（汇编器）—> object code

  • Linkers

    连接器（拼接成可执行文件）

  • Loaders

    重定位（相对地址）

  • Preprocessors

    预处理，删除注释、做include和宏定义

  • Editors

    编译器，生成标准文件

  • Debuggers

    调试器

  • Profilers

    手机程序运行中的相关信息，为程序改进提供信息

  • Project managers

    多文件操作（project），引入控制、多人协作


The Translation Process

image-20200307101832977

Scanner：词法分析（lexical analysis）

Token：单词、令环（不可分割的最小单位）

Parser：语法分析（syntax analysis）

Syntax tree：语法树

Semantic Analyzer：语义分析器（Semantic analysis）

Annotated tree：带注释的树（标注语义信息）

Source code optimizer：优化器（源程序代码级优化，依赖源代码特性），从而提高效率

Intermediate code：中间代码（m种源代码 -> n种目标代码，有m*n种映射；如果有中间代码，减少至m+n种）

Code generator：代码生成器

Target code：目标码

Target code optimizer：目标码优化，依赖目标码特性

Literal table：常量表

Symbol table：符号表（重要），用于提升性能

Error handler：用于错误处理和错误恢复（容错性）

Scanner

词法分析（lexical analysis）

输入符号流，输出token（不管值）

同时将标识符放入symbol table，将常量放入literal table

image-20200307124000496

Parser

语法分析（syntax analysis）

输入符号（token），输出语法树（syntax tree）或解析树（parse tree）

在语法树中，叶子对应终结符，非叶节点对应非终结符

Parse Tree：（具体）

image-20200307124410124

Syntax Tree：（抽象，parse tree的压缩）

image-20200307124856028

Semantic analyzer

语义分析器

  • 静态语义（static semantics）：包括声明和类型检查（编译时可以确定）
  • 动态语义（dynamic semantics）

根据语义信息得到属性（attribute） –> 语义信息语法化

例如加入“类型”这一语义属性（作用：保证程序安全）

Annotated Tree：

image-20200307145447835

Source code optimizer

源代码级优化

生成中间代码（intermediate code or IR） –> 表示形态主要有三地址码（three-address code）、P-code两种

  • 三地址码：比较接近高级语言
  • P-code：pascal语言的中间代码（接近机器语言）

会进行例如常量叠加等操作（不同的编译器执行的优化种类和优化阶段位置都会有差异）

image-20200307151136599

image-20200307150619488

Code generator

输入中间代码，输出机器码（目标机器用的代码）

image-20200307165109546

Target code optimizer

目标代码级优化

  • 选择寻址模式，提高性能
  • 用更快的指令代替慢的（如，用左移代替*2 –> 速度：左移 > 加法 > 乘法）
  • 去除多余的和不必要的操作

image-20200307165319770


Major Data Structures In A Compiler

  • Tokens
    可数，可通过定义枚举变量表示

  • Syntax Tree

    每个节点都是一条记录，递归表示parser和semantic analyzer收集到的信息

  • Symbol Table

    符号表。存储标识符信息（函数、变量、常量、数据类型等）

  • Literal Table

    常量表，存储常数、字符串等

  • Intermediate Code

    中间代码

  • Temporary Files

    用临时文件保存中间步骤


Other Issues

  • Analysis：lexical analysis（词法分析）、syntax analysis（语法分析）、semantic analysis(optimization)（语义分析）

  • Synthesis：code generation(optimization)（代码生成）

根据源代码和目标代码来划分前端后端：

  • Front end：scanner, parser, senabtic analyzer, intermediate code synthesis
  • Back end：code generator, optimization

  • （可能有middle end，gcc4.0根据中间代码进行优化）

  • Passes：Passes是相对于其余编译序列化的一个阶段或一组阶段，它在前一阶段完成之前不会启动，并且在任何后续阶段开始之前完成。对于一个程序要分为几个pass来多次处理，每个pass包含若干个阶段，商业级的编译器的pass数一般在30-40以上

  • Language definition
  • Compiler options and interfaces
  • Error handling: static error, execution error