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}
$$

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial JetBrains License不要用破解版本的JetBrains软件OK?凭自己的能力获取他的License不行吗? 先来看看这个页面,这里介绍了开源项目的定义 满足开源定义。 正在积极开发中,即在过去 3...

版本

使用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,虚拟机是一个操作系统。