nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
1. 引言想做编译器很久了，大学期间留下了不少遗憾，没有实现自己的编译器，没有实现自己的JVM，没有实现自己的数据库，当然这其中有很多原因，比如学院的要求太松，比如自己也不够主动，经过两个多月的学习，笔者的Pava1.0以及Pava编译器已经发布，这篇Blog主要介绍理论，将引导读者一步一步构建一个自己的编译器。
2. 学习重点开发编译器我能学到什么？编译器本身吗？其实不对，我们设计编译器的时候，会遇到很多问题，解决这些问题的方法才是最终重要的东西。
3. 编译器的流程从头开发一个编译器是非常困难的，这涉及到很多知识点，这一部分主要介绍现代编译器的架构。
龙书上把编译器分为前端和后端两个部分，源代码首先经过前端转化为中间代码，中间代码经过后端转化为汇编文件。此后的工作就不是编译器的管理范围了，接下来由汇编器和链接器将汇编文件转化为可执行文件。
12graph LR 源代码 --编译器前端--> 中间代码 --编译器后端--> 汇编文件 --汇编器和链接器--> 可执行文件
为什么编译器要分为两个部分？为什么要分出前端和后端？实际上这样的架构做好以后，只要我们为$m$种源代码编写一个前端，为$n$种架构的机器编写后端，则我们可以组成$n*m$种编译器。当一个新类型的源代码或者新架构的机器出现时，我们可以以更快的速度对编译器进行更新，从而支持这些源代码或机器。另一方面，如果想要对源程序进行优化，编译器前端负责优化吗？还是编译器后端负责优化？这其实是优化器的工作，优化器的输入是中间代码，输出也是中间代码。
阅读全文
fightinggg
6月 24, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接https://codeforces.com/contest/1555
1. A. PizzaForces1.1. 题意6元15个物品，8元20个物品，10元25个物品
现在需要买至少n个物品，问需要多少钱
1.2. 做法首先看单价，发现他们都相同，然后就是尽量不要多买了。
如果n比15,20,25的最小公倍数的两倍还要大，则多出的这一部分，可以考虑直接购买6元的，剩下的小范围dp即可
核心思想： 大范围贪心，小范围dp
notes: 注意一定是至少两倍以上才能贪心
阅读全文
fightinggg
8月 01, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接https://codeforces.com/contest/1551
1. A. Polycarp and Coins1.1. 题意给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差
1.2. 做法对模3的余数进行分类讨论
1.3. 代码123456789101112131415161718192021222324#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; } }}
阅读全文
fightinggg
7月 24, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
UML
统一建模语言（英语：Unified Modeling Language，缩写 UML）是非专利的第三代建模和规约语言。UML是一种开放的方法，用于说明、可视化、构建和编写一个正在开发的、面向对象的、软件密集系统的制品的开放方法。UML展现了一系列最佳工程实践，这些最佳实践在对大规模，复杂系统进行建模方面，特别是在软件架构层次已经被验证有效。
摘自： 维基百科，自由的百科全书
类图类图主要描述的是类与类之间的关系，这些关系分为泛化关系(generalization)、实现关系(realize)、聚合关系(aggregation)、组合关系(composition)、关联关系(association)、依赖关系(dependency)
泛化关系泛化即类的继承，自行车继承车，猫继承动物，
所以自行车是车的泛化，猫是动物的泛化，男人是人的泛化 (箭头应该是空心)
1234classDiagram 车 <|-- 自行车 动物 <|-- 猫 人 <|-- 男人
1234classDiagram 车 <|-- 自行车 动物 <|-- 猫 人 <|-- 男人
阅读全文
fightinggg
7月 21, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接VK Cup 2021 - Elimination (Engine)
1. A. Binary Decimal1.1. 题意给你一个十进制数，你要把它拆成多个只由0和1组成的十进制数之和，问最少拆几个。
1.2. 做法答案就是十进制数每个位上的数中的最大值
1.3. 代码1234567891011121314151617181920#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; }}
阅读全文
fightinggg
7月 18, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
题目大意：你需要计算有多少对满足长度为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}$$
阅读全文
fightinggg
7月 16, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
版本使用6.2.4
sds.h sds.c内存对齐__attribute__((__packed__))可以让编译器对结构体不进行内存对齐，详细参考
1234567891011121314151617181920212223242526#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 && ./apacked: 17nopacked: 24*/
宏####后标识的字符串会被替换，然后其左右的内容加上自己会被合并到一起，编译器将其视为标识符进行解析，详细参考
阅读全文
fightinggg
6月 26, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
运行源码我们将运行1.13.0版本的Flink，其scala环境为2.12
Step1. 获取学习项目1git clone https://github.com/fightinggg/flink-src-study.git --recursive
在这个项目中，笔者把flink源码作为了一个git submodule放置于文件夹flink中，用来临时查看，当然我个人不建议看这些代码，因为这个文件夹太大了，IDE都不能很好的处理他。
然后就可以直接运行了
阅读全文
fightinggg
6月 08, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
容器与开发语言容器随着云计算领域的兴起，容器这个词出现了，但是什么是容器？
容器英文名Container，是基于Linux Namespace以及Cgroups技术实现的具备隔离特性的一组进程。
OK，他是一组具备隔离特性的进程。
虚拟机虚拟机是使用Hypervisor技术提供的虚拟化硬件的操作系统。
OK，虚拟机是一个操作系统。
阅读全文
fightinggg
4月 16, 2021