1. 引言

想做编译器很久了，大学期间留下了不少遗憾，没有实现自己的编译器，没有实现自己的JVM，没有实现自己的数据库，当然这其中有很多原因，比如学院的要求太松，比如自己也不够主动，经过两个多月的学习，笔者的Pava1.0以及Pava编译器已经发布，这篇Blog主要介绍理论，将引导读者一步一步构建一个自己的编译器。

2. 学习重点

开发编译器我能学到什么？编译器本身吗？其实不对，我们设计编译器的时候，会遇到很多问题，解决这些问题的方法才是最终重要的东西。

3. 编译器的流程

从头开发一个编译器是非常困难的，这涉及到很多知识点，这一部分主要介绍现代编译器的架构。

龙书上把编译器分为前端和后端两个部分，源代码首先经过前端转化为中间代码，中间代码经过后端转化为汇编文件。此后的工作就不是编译器的管理范围了，接下来由汇编器和链接器将汇编文件转化为可执行文件。

1
2

graph LR
  源代码 --编译器前端--> 中间代码 --编译器后端--> 汇编文件 --汇编器和链接器--> 可执行文件

为什么编译器要分为两个部分？为什么要分出前端和后端？实际上这样的架构做好以后，只要我们为$m$种源代码编写一个前端，为$n$种架构的机器编写后端，则我们可以组成$n*m$种编译器。当一个新类型的源代码或者新架构的机器出现时，我们可以以更快的速度对编译器进行更新，从而支持这些源代码或机器。另一方面，如果想要对源程序进行优化，编译器前端负责优化吗？还是编译器后端负责优化？这其实是优化器的工作，优化器的输入是中间代码，输出也是中间代码。

比赛链接

https://codeforces.com/contest/1555

1. A. PizzaForces

1.1. 题意

6元15个物品，8元20个物品，10元25个物品

现在需要买至少n个物品，问需要多少钱

1.2. 做法

首先看单价，发现他们都相同，然后就是尽量不要多买了。

如果n比15,20,25的最小公倍数的两倍还要大，则多出的这一部分，可以考虑直接购买6元的，剩下的小范围dp即可

核心思想： 大范围贪心，小范围dp

notes: 注意一定是至少两倍以上才能贪心

比赛链接

https://codeforces.com/contest/1551

1. A. Polycarp and Coins

1.1. 题意

给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差

1.2. 做法

对模3的余数进行分类讨论

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int step;
    cin >> step;
    while (step--) {
        int n;
        cin >> n;
        if (n % 3 == 0) {
            cout << n / 3 << " " << n / 3 << endl;
        } else if (n % 3 == 1) {
            cout << n / 3 + 1 << " " << n / 3 << endl;
        } else {
            cout << n / 3 << " " << n / 3 + 1 << endl;
        }
    }
}
 

UML

统一建模语言（英语：Unified Modeling Language，缩写 UML）是非专利的第三代建模和规约语言。UML是一种开放的方法，用于说明、可视化、构建和编写一个正在开发的、面向对象的、软件密集系统的制品的开放方法。UML展现了一系列最佳工程实践，这些最佳实践在对大规模，复杂系统进行建模方面，特别是在软件架构层次已经被验证有效。

摘自： 维基百科，自由的百科全书

类图

类图主要描述的是类与类之间的关系，这些关系分为泛化关系(generalization)、实现关系(realize)、聚合关系(aggregation)、组合关系(composition)、关联关系(association)、依赖关系(dependency)

泛化关系

泛化即类的继承，自行车继承车，猫继承动物，

所以自行车是车的泛化，猫是动物的泛化，男人是人的泛化 (箭头应该是空心)

1
2
3
4

classDiagram
  车 <|-- 自行车
  动物 <|-- 猫
  人 <|-- 男人

1
2
3
4

classDiagram
  车 <|-- 自行车
  动物 <|-- 猫
  人 <|-- 男人

比赛链接

VK Cup 2021 - Elimination (Engine)

1. A. Binary Decimal

1.1. 题意

给你一个十进制数，你要把它拆成多个只由0和1组成的十进制数之和，问最少拆几个。

1.2. 做法

答案就是十进制数每个位上的数中的最大值

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int mx = 0;
        while (x) {
            mx = max(mx, x % 10);
            x /= 10;
        }
        cout << mx << endl;
    }
}

题目大意：

你需要计算有多少对满足长度为n的排列$p$和$q$，满足$p$字典序>$q$ 且 $inv(p)<inv(q)$，答案取模

$inv$ 为逆序对个数

做法：

设$f(i,j)$为长度为$i$、逆序对个数为$j$的排列的个数 , 考虑第一个数字为$t$

$f(i,j) = \sum_{t \in [1,i]} f(i-1,j-t+1)$

一个填$u$，另一个填$v$ $u<v$

$$
\begin{aligned}
ans[i] \&= i * ans[i-1] + \sum_{1<=u<v<=i, x+u>y+v} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>v-u, 1<=u<v<=i} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>d, 1<=d<i} (i-d)*f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x,y} f(i-1,x)\cdot f(i-1,y) \cdot \sum_{x-y>d, 1<=d<i} (i-d)
\end{aligned}
$$

版本

使用6.2.4

sds.h sds.c

内存对齐

__attribute__((__packed__))可以让编译器对结构体不进行内存对齐，详细参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <stdint.h>
#include <stdio.h>

struct __attribute__((__packed__)) sdshdr64 {
    uint64_t len;        /* used */
    uint64_t alloc;      /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct _sdshdr64 {
    uint64_t len;        /* used */
    uint64_t alloc;      /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

int main() {
    printf("packed: %d\n", sizeof(struct sdshdr64));
    printf("nopacked: %d\n", sizeof(struct _sdshdr64));
}
/*
gcc a.c -o a && ./a
packed: 17
nopacked: 24
*/

宏##

##后标识的字符串会被替换，然后其左右的内容加上自己会被合并到一起，编译器将其视为标识符进行解析，详细参考

运行源码

我们将运行1.13.0版本的Flink，其scala环境为2.12

Step1. 获取学习项目

1

git clone https://github.com/fightinggg/flink-src-study.git --recursive

在这个项目中，笔者把flink源码作为了一个git submodule放置于文件夹flink中，用来临时查看，当然我个人不建议看这些代码，因为这个文件夹太大了，IDE都不能很好的处理他。

然后就可以直接运行了

容器与开发语言

容器

随着云计算领域的兴起，容器这个词出现了，但是什么是容器？

容器英文名Container，是基于Linux Namespace以及Cgroups技术实现的具备隔离特性的一组进程。

OK，他是一组具备隔离特性的进程。

虚拟机

虚拟机是使用Hypervisor技术提供的虚拟化硬件的操作系统。

OK，虚拟机是一个操作系统。