2024/9/20

成绩组成：

教材：Modern Compiler Implementation in C（虎书）

第一部分是自己写一个编译器，第二部分是内存管理，面向对象语言设计，函数语言设计，后端优化介绍…

Compilers（编译器）

编译的核心就是把一个源程序（可以是各种语言：C/Java…）编译成目标程序（汇编[Assembly languages]/二进制[Binary languages]/高级语言…）。这个过程中可能编译不通过出现错误

  • 源语言（Sources languages）

    通常算是比较高级的语言，C语言其实可以内联汇编，是比较低级的程序。ML是这本书的作者偏爱的语言。这些语言是偏函数式的。Verilog(FPGA, 小板子编程，集成电路设计，舍友郭哥在学）。

  • 目标语言（Target languages）

    通常是机器的语言：汇编/二进制。目标语言也可以是高级语言，这就是source to source compiler。比如把其他语言翻译成js，来放到web里去跑；或者把web代码部署到安卓上去运行。编译器的种类是很多的，和源语言、目标语言的多样性有关。

    PS：objdump命令是Linux下的反汇编目标文件或者可执行文件的命令，它以一种可阅读的格式让你更多地了解二进制文件可能带有的附加信息。可以dump出汇编代码。

  • 不同的编译器结构（A variety of compiler structures）

    Single-pass 只经过每个编译单元的各个部分一次，立即将每个部分翻译成最终的机器码。

    multi-pass 多通道编译器将程序在源代码和机器码之间的步骤中转换为一个或多个中间表示，并且在每个顺序通道中重新处理整个编译单元。

    Load-and-go 像用IDE，点一下run就执行完成了。把程序直接映射到内存里运行。把编译和执行的边界就模糊掉了。对内存要求比较高，因为要把生成的多个文件直接放进内存里。

    Debugging：调试器也有编译的内容，比如单步执行可以模拟代码执行，这就需要知道代码在做什么

    Optimizaing：需要分析代码，知道语义，再去做针对性的优化。也会用到编译的结构。

    **Basic解释器:**它是一行行读入解析的。读一行模拟执行一行。这就不像gcc中生成可执行文件再去执行。（就是我们在SEP最后实现的大项目）

编译器内部世界

主要从一个例子的4个方面进行解释：

这里为了方便理解主要是采用了一个Lab，我们定义了一个简单的语言（直线式程序语言），没有分支，一行一行的执行，有赋值、输出、序列语句（用分号隔开的一行语句），有表达式(expression) 包含了：变量，数字，+，-，*，/。

Statement( 语句 ) 是没有返回值，Expression 是有返回值的。Expression sequence 要求最后一个指令一定是 expression。所以一个expression或者一个代码块可以作为一个返回值赋给别人。

  • 怎么定义源语言？

    主要说的是：站在编译器的视角，是如何来定义上面那个lab中的语言呢？回忆一下，在我们学习英语的时候，我们无非学的就是：单词（文法） + 正确的单词的组合方式（语法）；这里也一样：正则表达式（Regular expression）定义了文法，上下文无关语法（Context free grammar）定义了语法。之后会在2，3章着重介绍这两部分。

    • 文法定义

      上图中竖线表示或者的意思，*表示0/多个。就是大小写字母，阿拉伯数字排列组合成变量名字和数字

    • 语法定义

      十分简单，对照刚刚那个Example就能理解，其实和。

      简单给出Context-free Grammar的定义：

      Token（终结符，terminal symbol）： 不能再继续推导的内容，比如加减乘除、括号

      非终结符： 可以继续推导的符号，比如explist。

      我们的语法就是包含了推导规则，左边是非终结符，右边是终结符和非终结符。并且要求给定一个开始推导的符号。

  • 怎么内部表示一个程序？

    基本编译器结构：大致可以分成分析器（把源码编译成中间表达）和后端（合成目标语言）

    这是一个递归向下的树结构，可以参考之前写过的basic解释器理解这部分。我们用**C++**语言来看：

    image-20240923222314859

    Lab1

    TODO List：

    1. 写一个maxargs函数，告知给定语句中的任意子表达式内的print语句的参数个数。

      Ps：print语句中可能含有表达式，这些表达式可能还含有print

    2. 写一个interp函数，把程序通过解释的方法去执行一下。对不同的结构需要写不同的interp函数。

      Ps： 构造interpStm，interpExp

    分析：

    这个Lab整体来看比较简单，而且和后面的Tiger compiler没有联系，现在来简单分析一下。

    主要思想：递归，继承；把stm不断拆分成stm和exp，然后调用各自的函数即可

  • 怎么翻译源语言到compiler内部？

    刚才我们看到的树（AST），有了这个以后我们怎么做转化呢？涉及到scanner（词法分析）和parser（文法分析）

    Source传过来只是一个个字符，通过scanner就识别出了其中的token，给到parser就会根据我们定义的语法规则，生成中间表达，也就是我们的抽象语法树。

    为什么是preliminary，是比较原始的。如果a只有可能是0和1，并且后面有一句if (a > 2)，那么后端检测到以后就可以去掉，而在前端里面只是最简单的存储。

    比如a:=a-1，分解成a赋值再一个a-1，scanner可以得到a的类型。换句话说scanner的责任就是把字符映射到终结符(token)，做完词法分析以后，对语法分析来说没什么差别。因为格式被整理过了。

    很多c++的错误是语法分析的错误，还有一些是语义分析的错误（类型、强制转换）。语法分析器还会尝试做一些error correction，为的不是通过编译，而是为了找到后面的bug，尽可能一次性把所有的语法分析都报告出来。现在的parser是自动生成的。

  • 怎么把内部语言转化为目标？

    后端职责：拿到前端的中间表达转成机器码，需要给每个中间表达选择instruction。

    这里举一个有三部分的编译器的例子。我们把这个过程分成两个IR，把High-level的IR（比较接近source）转化为low-level的IR（接近target，里面有move，load之类的）。最终通过gode gen转化为机器码。实际的编译器可能更加复杂，有多层IR，每层需求也不一样。

    优化对每一部分都可以做，但是大部分优化在生成IR之后进行优化器（对固定IR循环分析，改进）

    这是课程的flow。。。。。。