这几个月我用golang写了个后端基于llvm的模仿golang的带有一系列较高级特性的编程语言，在limfx上记录一下
Chronostasys/calc: A golang-like toy language|一个模仿golang的玩具语言 (github.com)
寒假对编译原理很感兴趣，因此准备自学一下编译器的相关知识，理解一下基础的编译原理。
其实在大二还是大三的时候，我已经学习过编译原理的课程，但是那个时候我主要死记概念，而且在做实验的时候大量参考了别人的代码（实验是自己完成一个c--编译器）。因此虽然能通过考核但是我并不觉得我真的学会了。
于是，我重新借了舍友的编译原理教科书，重新看了一些基本的理论。只能说书上理论真的多，而且我最后发现其实很多没什么用。。。
编译器前端最困难的部分之一就是语法分析，这部分书上使用大篇幅介绍的是自下向上分析法。自下向上分析法是一种使用归约进行分析的方法，它基于自动状态机理论，具体的实现说起来会比较复杂，但是整个过程可以高度自动化。因此自下而上的分析法往往被用于各种自动生成语法分析器的工具中，比如bison。
一开始，我预计我实现编译器是需要使用这些自动化工具的（我准备用的是lex和bison），作为尝试我先用它实现了一个小的算式计算器。然而在实现之后我发现它存在两个主要的问题：
太简单了，lexer和parser都完全可以自动生成，甚至二义性都可以帮你找出来，没啥成就感
更重要的，使用lex和bison意味着要使用c或cpp来开发编译器，我的c和cpp水平都不咋地
因此，我就想：有没有一种可能，我是说可能，编译器前端用递归下降法手写也不是很复杂。但是书上对此方面的信息并不是很多，因此我google了一下，找到了一个很好的系列博文。
这个博客是做lisp的解释器，其实解释器基本上就是个编译器前端。里边对文法设计和实现有很详细的设计和实现。推荐想入门编译器的朋友都可以看一下这个。
然后我大概看了五六篇吧，大概就把它这个思想搞明白了。这个时候我就发现编译器前端实际上很简单了。我们把一个编译器前端拆开，可以看作三个部分：
lexer 词法分析器
parser语法分析器（生成ast）
从ast生成中间代码
lexer这东西太简单了，说白了就是一个把输入的源代码程序拆分成一个一个基础单词的工作，这事情任何一个入门的程序员都应该能手写。我觉得用相比使用lex从正则表达式自动生成lexer，学习正则的时间都够够你手撸一个。
parser手写相对来讲会比较的困难，手写就基本不考虑自下向上分析了，因为那个手写太复杂了，打草稿可能要好几张A4纸都写不下的那种。因此我采用递归下降分析法。递归下降分析法的原理非常简单：就是靠猜。
一个递归下降分析器的工作步骤如下：
使用lexer读入一个单词
寻找所有能用这个单词开头的文法，选中其中第一个
使用lexer读入下一个单词
检查是否符合当前文法中对下一个单词的约束
如果符合，则继续转到3
如果不符合，选中第2步中找出的第二个文法，转到3
任何时候如果某文法完全分析完了（文法不需要读下一个单词了）则转到1
如果lexer单词读完了，且文法正好也分析完了，分析成功
别的情况分析失败
这部分主要依赖parser生成的ast，我们在这一步中需要对ast进行遍历，生成中间代码。注意一些特殊的语法可能需要对ast进行多次遍历才能正确生成中间代码（例如for、if），而设计得当的语法和ast也有方法规避多次遍历。规避多次遍历是加速前端编译的最主要因素之一。
我不是很擅长整理文字资料，我代码总是写的比文字多，平时也不是很喜欢写注释和文档。但是这个系列我有空应该会继续更，因为有些东西如果不写下来以后自己也会遗忘。路走的太快会摔倒，要走稳才行。
Calc语言从开始写至今已经拥有了相当多的现代语言特性，比如
ducktype interface
泛型
模块化
async/await io模型和协程
generator（生成器
闭包
gc，栈逃逸分析
其中很多部分的实现方法都是很值得记录的。虽然我估计不会有多少人看，但是如果有读者对哪部分特别感兴趣，可以留言告诉我，我可能就会先写那一部分。
题外话：bgm名称：月光 鬼束千寻yyds！