2021-10-01发表2022-12-20更新记事 / 教程27 分钟读完 (大约4047个字)0次访问

从零开始的编译器生涯

近日一屑高二学生无聊动手写起了编译器….这是他的珍贵作战记录

0x01 理论基础

我摊牌，我没有看任何编译原理相关的书籍，因此这篇文章并不能作为严格的参考资料，甚至很多地方可能是错误的。

编译器，编译器，就是把高级语言的代码编译成另一种形式（class，asm，二进制，IR），而他在编译成另一种形式之前大概需要过这么个流程:

Lex -> Parse -> Compile

接下来逐步讲解这个过程。

Lexer

就是分词器，输入用户提供的代码接着把他分成 tokens，也就是 tokenstream。
你肯定看不懂上面那句话的意思，让我们来点实例：

a.value 里的那个 ArrayList 就是一个 token stream，str 是被解析的代码。不难发现，语句被 Lexer 按顺序进行了分类以及数据的分割，如 a 被识别为了一个 Identify (标记)。

因此也可以归纳出来 Token 大致的代码长啥样：

@AllArgsConstructor
@Getter
public class Token {
    private int line;
    private Type type;
    private String content;
}

Parser

Lexer 从源码中提取出 token stream 后将会交给 Parser 处理，它负责对 token stream 进行解析，生成一个 AST (Abstract Syntax Tree)，也就是 抽象语法树。

这张图直观的描述了这一过程，你可以看到它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。

接着，AST 将会丢给代码生成器用于生成代码，但是一般会先对 AST 进行优化，例如 常量折叠

Static Analyzing

但在这之前，我们还有一些问题要解决。
~~其实这玩意我是和 Parser 写一块的~~
试想一下，如果有这样一行代码：

1	var i = love + cats

代码生成器如何知道 love 和 cats 是什么？在 Parser 的眼里，他们只是 Identifier，然而它们之间不能相加减。

在这种时候，Parser 需要预先建立一个符号表，这样他才能找出 love 和 cats 究竟是什么以及是否能够编译。

同理，下面的代码也一样需要这一过程：

import java.util.List

void main(List<String> args){ // 此处 Parser 将会分析出 java.lang.String 和 java.util.List
  NullCat nc = new SBNC(); // 按照 Java 的逻辑，此处没有导入（或同包）于是会产生错误，因为Parser找不到 SBNC / NullCat

}

Code Generation

接着是生成代码！
一般编译器都会输出一种 IR (Intermediate Representation) 码，而他的作用则是一种中间表示。
例如，如果你输出 LLVM 的 IR 码，那么接下来你的编译工作（win,x64,linux,…jvm）就可以交给 LLVM 来完成，而像 LLVM 这样负责最后这一步骤的我们称之为 编译器的后端

使用这一种方法有几个好处：

它可以使得开发者更专注于 语言设计 而不用过多的考虑 优化，因为大多数编译器后端会帮你完成这件事情 ~~，除非你直接输出汇编那就得你自己负责优化了~~。
IR 是中间表示，它可以按照相同的语义编译出不同平台，不同架构的代码，大大节省了开发者时间
…

处于个人习惯，我选择了 Java 的字节码作为 “IR”，他将会被 JVM 加载并在运行过程中收集数据被更好的优化以及可以享受和 Java 互操作，跨平台的优势。

0x02 实践

知道了这些理论，我们立即可以开始编写我们的第一个 Lexer 了。

这是我们这一大章节的目标代码：

using java.util.List

fn main(args: List<String>){
  println "hello world!"
}

那么，让我们开始吧！
下文将会有大量代码，为了可读性，我会删掉一些无关紧要的部分。

Lexer

我的 Lexer 分为两步：fuzzyTokenize 和 tokenize。
实际上这是取决于做法的，有正则转 DFA（状态机）的，也有直接 charStream 的。

我选择了第二种，因为我认为使用正则的代码可读性比较糟糕，不易于维护。那么，让我们开始做一些准备工作…

public class Lexer {
    private final String fileName;
    private final String rawContent;

    public Lexer(String content,String fileName) {
        rawContent = content.replaceAll("//.*|(\"(?:\\\\[^\"]|\\\\\"|.)*?\")|(?s)/\\*.*?\\*/", "$1 "); // remove comments.
        this.fileName=fileName;
    }
}

从构造方法接受源代码和文件名并且删除注释。你可能会问文件名用来干啥，那当然是用来报错的～
接着，还有一个 LexedNode 用来表示 fuzzyTokenize 后的产物。

public class LexedNode {
    private NodeType type;
    private String content;
    
    // 初始化和getter...


    public enum NodeType {
        IDENTIFIER,SYMBOL,KEYWORD,OPERATOR,
        LINE_SEPERATOR,
        LITERAL_STRING,LITERAL_NUMBER
    }
}

这就是一个最基本的 token! 在后文，我们将会进行第二次 tokenize 使它变得更详细。

准备好了，开始写吧！首先是一个状态机：

public List<LexedNode> fuzzyTokenize() {
    char[] charStream = rawContent.toCharArray();
    List<LexedNode> nodes = new ArrayList<>();
    int line = 1;
    for (int i = 0; i < charStream.length; i++) { // 使用 fori 是为了循环时移动指针
        char now = charStream[i];
        switch (now) {
            case '\n':
              nodes.add(new LexedNode(NodeType.LINE_SEPERATOR,"\n"))
              continue; // 此处使用 continue 立即跳到下一次循环
        }
    }
    return nodes;
}

这就是你的第一个 Lexer，可以先输出一下看看结果：

LINE_SEPERATOR

LINE_SEPERATOR

LINE_SEPERATOR

LINE_SEPERATOR

LINE_SEPERATOR

因为代码有五行，因此是五个 LINE_SEPERATOR。
只有换行符可不够，我们还要识别 KEYWORD ，也就是关键词。
然而关键词使用空格分割，因此我们可以这样做：

switch(...){
    //...
    case ' ':                
        inIdOrLiteral = !inIdOrLiteral;
        if (inIdOrLiteral) { // start collecting
            continue;
        }
        // end!
        String str = buffer.toString();
        identifierParse(str, nodes);
        buffer = new StringBuilder(); // compose
         continue;
    // 此处换行同理
}
//...

/* Collect String or Identifier */
    if (inIdOrLiteral) {
        buffer.append(now);
        continue;
    }

你可以看到，我们引入了两个新的变量和一个方法，它们分别是 inIdOrLiteral 和 buffer 以及 identifierParse。

inIdOrLiteral 表示当前是否正在遍历一个 Identifier 或者一个字面量
buffer 用于收集这个字面量，当然你也可以使用 substring 和 charAt 的方法
identifierParse 是一个方法，他用于分类 Identifier。对于 11，他会分类成一个 LITERAL_NUMBER，对于 not_a_keyword，他会分类成一个 identifier，对于 fn，他会分类成一个 Keyword。

还没完，天资聪颖的你肯定已经注意到了这里少了一样东西——我要怎么匹配最开头的一个 using ？ using 的前头可没有一个空格。
这时你可以回忆一下，在各种编程语言中作为 Identifier 的符号应该符合什么规则….是的，他们通常不会以运算符作为开头，以及他们不是一个关键字，因此我们还可以利用这个特性写出这样的代码:

         /* Other Symbols */
         if (SYMBOL_OR_OPERATORS.contains(now）) {
             if (inIdOrLiteral) { // keyword
                 // now == a symbol,we should end this.
                 identifierParse(buffer.toString(), nodes);
                 buffer = new StringBuilder();
                 inIdOrLiteral = false;
             }
             if (SYMBOLS.contains(now)) {
                 nodes.add(new LexedNode(now, LexedNode.NodeType.SYMBOL));
                 continue;
             } else if (OPERATORS.contains(now)) {
                 nodes.add(new LexedNode(now, LexedNode.NodeType.OPERATOR));
                 continue;
             } else {
                 throw new LexerException(fileName+": Unknown char: " + now+" line: "+line);
             }
         } else {
             inIdOrLiteral = true; // not symbol & not identifier
         }

/* Collect String or Identifier */
 if (inIdOrLiteral) {
     buffer.append(now);
     continue;
 }

这一段代码将会在匹配第一个字符没有遇到语言规定的操作符或者特殊符号的时候把 inIdOrLiteral 设置为 true。配合上面的代码，在遇到一个空格的时候他会结束收集并且尝试判断是什么。

实际上应该是 switch 的任务但是写成 if 更加直观一些。

那么到现在，我们可以开始尝试代码了！这是 Lexer 的输出：

KEYWORD using
IDENTIFIER java
OPERATOR .
IDENTIFIER util
OPERATOR .
IDENTIFIER List
LINE_SEPERATOR 

LINE_SEPERATOR 

KEYWORD fn
IDENTIFIER main
SYMBOL (
IDENTIFIER args
OPERATOR :
IDENTIFIER List<String>
SYMBOL )
SYMBOL {
LINE_SEPERATOR 

KEYWORD println
- LITERAL_STRING hello world!
+ IDENTIFIER "hello
+ IDENTIFIER world!"
LINE_SEPERATOR 

SYMBOL }
5: RIGHT_BRACKET }

相比你已经注意到了，理应出现的 LITERAL_STRING 被两个 IDENTIFIER 代替了，这显然不是我们想要的结果。因此，我们要给 String 加入特殊支持

switch(now){
    case '"':
                    if (i != 0 && charStream[i - 1] != '\\') {
                        // string starts or end
                        inIdOrLiteral = !inIdOrLiteral;
                        stringMode = true;
                        if (!inIdOrLiteral) {
                            stringMode = false;
                            // a new string!
                            nodes.add(new LexedNode(buffer.toString(), LexedNode.NodeType.LITERAL_STRING));
                            buffer = new StringBuilder();
                            continue;
                        }
                    }
                    continue;
                    //...
}

以及

    case ' ':
+        if (stringMode) {
+            break;
+        }

1 2	- if (SYMBOL_OR_OPERATORS.contains(now)) { + if (SYMBOL_OR_OPERATORS.contains(now) && !stringMode) {

这样我们就躲开了这个陷阱，完成了对于 String 的支持后，我们的 fuzzyTokenize 就做好了！

关于 OPERATORS 和 SYMBOLS
一门语言里的符号很多，你绝对不会想把他们一个个 add 到 list 里面的，但你可以写一个 loader 来解决这个问题

然后，是 tokenizer。fuzzyTokenize 输出的结果显然不足以交给 Parser 做解析，我们需要使i结果更加详细。

好在经过 fuzzyTokenize 后代码已经被格式化成了比较模糊的 Token Stream，这一点使我们写第二次 tokenize 的时候会轻松很多，因为你不会再见到 inIdOrLiteral 和 stringMode 这种让人抓狂的东西了。

首先，让我们从一个新的 Token 开始（你不会想和 LexedNode 混一块的）:

@AllArgsConstructor
@Getter
public class Token {
    private int line;
    private Type type;
    private String content;

    public enum Type{
        IDENTIFIER(""),

        CLASS("class"),FUNCTION("fn"),ANNOTATION("annotation"),FOR("for"),WHILE("while"),IF("if"),USING("using")
        ,THIS("this"),TRUE("true"),FALSE("false"),ELSE("else"),VAR("var"),NULL("null"),PRINTLN("println"), // KEYWORDS
        VAL("val"),

        LEFT_BRACE("("),RIGHT_BRACE(")"),
        LEFT_BRACKET("{"),RIGHT_BRACKET("}"),
        LEFT_MID_BRACE("["),RIGHT_MID_BRACE("]"),

        COMMA(","),DOT("."),MINUS("-"),PLUS("+"),STAR("*"),SLASH("/"), // operators
        BREAK_LINE("\n"),ASSIGNMENT("="),EQUALS("=="),SEMICOLON(";"),AT("@"),COLON(":"),

        LITERAL_STRING(""),LITERAL_NUMBER(""); // literals
        @Getter
        private String def;
        Type(String def){
            this.def=def;
        }
    }
}

比上文的 LexedNode 详细了很多——比如他主动去分类 keyword 了。
接着是一个 fori ：

public Pair<String,List<Token>> tokenize() {
    var lexedNodes = fuzzyTokenize();
    var tokens = new ArrayList<Token>();
    var line = 1;
    for (int i = 0; i < lexedNodes.size(); i++) {
        LexedNode lexedNode = lexedNodes.get(i);
        switch (lexedNode.getType()) {
            case LINE_SEPERATOR:
                tokens.add(new Token(line, Token.Type.BREAK_LINE,""));
                line++;
                break;
            case SYMBOL:
            case KEYWORD:
                var type = Arrays.stream(Token.Type.values()).filter(e -> e.getDef().equals(lexedNode.getContent())).findFirst().orElseThrow(()->{
                   return new NullPointerException(lexedNode.toString());
                });
                tokens.add(new Token(line, type, type.getDef()));
                break;
            case LITERAL_STRING:
                tokens.add(new Token(line, Token.Type.LITERAL_STRING, lexedNode.getContent()));
                break;
            case LITERAL_NUMBER:
                tokens.add(new Token(line, Token.Type.LITERAL_NUMBER, lexedNode.getContent()));
                break;
            case OPERATOR:
                // =
                boolean isEnd = (i == lexedNodes.size() - 1);
                switch (lexedNode.getContent()) {
                    case "=":
                        if (isEnd) {
                            throw new LexerException(fileName+": Invalid syntax line "+line);
                        }
                        if (lexedNodes.get(i + 1).getType() == LexedNode.NodeType.OPERATOR && lexedNodes.get(i + 1).getContent().equals("=")) { // ==
                            tokens.add(new Token(line, Token.Type.EQUALS, "=="));
                            i = i + 1; // skip next
                            break;
                        } else {
                            tokens.add(new Token(line, Token.Type.ASSIGNMENT, "="));
                        }
                        break;
                    case ".":
                        tokens.add(new Token(line, Token.Type.DOT, "."));
                        break;
                    case ",":
                        tokens.add(new Token(line, Token.Type.COMMA, ","));
                        break;
                    case "-":
                        tokens.add(new Token(line, Token.Type.MINUS, "-"));
                        break;
                    case "+":
                        tokens.add(new Token(line, Token.Type.PLUS, "+"));
                        break;
                    case "*":
                        tokens.add(new Token(line, Token.Type.STAR,"*"));
                        break;
                    case "/":
                        tokens.add(new Token(line, Token.Type.SLASH,"/"));
                        break;
                    case ";":
                        tokens.add(new Token(line, Token.Type.SEMICOLON,";"));
                        break;
                    case ":":
                        tokens.add(new Token(line,Token.Type.COLON,":"));
                        break;
                }
                break;
            case IDENTIFIER:
                tokens.add(new Token(line, Token.Type.IDENTIFIER, lexedNode.getContent()));
                break;

        }
    }
    return Pair.of(fileName,tokens);
}

这段代码并不难懂。在这个例子中，我们遍历来自 fuzzyTokenizer 的数据并且通过 switch 分类枚举来处理把他们转化成 Token 来表达并且存储到 tokens。对于 symbol 和 keyword，我们通过直接搜索 enum 内值的方法避免写出了像 case OPERATOR 里更糟糕的代码。

case OPERATOR 里写成这样是为了双符号操作的支持，例如 ==

回到原题，这次我们可以通过 tokenize 解析出这样的结果：

1: USING using
1: IDENTIFIER java
1: DOT .
1: IDENTIFIER util
1: DOT .
1: IDENTIFIER List
1: BREAK_LINE 
2: BREAK_LINE 
3: FUNCTION fn
3: IDENTIFIER main
3: LEFT_BRACE (
3: IDENTIFIER args
3: COLON :
3: IDENTIFIER List<String>
3: RIGHT_BRACE )
3: LEFT_BRACKET {
3: BREAK_LINE 
4: PRINTLN println
4: LITERAL_STRING hello world!
4: BREAK_LINE 
5: RIGHT_BRACKET }
5: RIGHT_BRACKET }

是不是详细了很多？接着我们就可以靠着这个写一个 Parser了

在 Parse 之前

在 Parse 之前，我们需要先做一次 Static Analyzing。在这个阶段，Parser 会对文件里的类型和导入表作出关联，同时也是多文件编译的基础。

Metadata

你不可能靠着所有人的源码来建立索引，而且源码中的无用信息太多了。
实际上，确定符号链接只需要这些信息：

@Data
public class CatMetadata {
    private ClassDef classDefinition = new ClassDef();
    private Map<String,CatMetadata> cachedUsings = new HashMap<>(); // 这是对于被解析对象才有的
    private List< MethodSign> methods = new ArrayList<>();
    private Map<String, VariableDef> fields = new HashMap<>();
}

关于 ClassDef, MethodSign, VariableDef 等信息本文不贴出，因为并不会影响观看体验。
如果有兴趣，可以在这里找到他们相对应的具体代码

以及一个编译器全局索引，用 FQDN 确定唯一性的 Map:

public static class Global {
     private static final Map<String,CatMetadata> GLOBAL_METADATAS = new HashMap<>();
     public static final CatMetadata forClass(String str){
         /*
          * Scan compiler classPaths
          */
         var meta = NullCatCompiler.solveMeta(str);
         if(meta!=null) {
             GLOBAL_METADATAS.put(str, meta);
         }else{
             meta = NullCatCompiler.solveMeta("java.lang." + str);
         }
         return meta;
     }
 }

准备就绪，我们来单独拿出一个类作为 MetadataGenerator 状态机

@RequiredArgsConstructor
public class MetadataGenerator {
    private final String fileName;
    private final List<Token> tokens;
    private CatMetadata cm = new CatMetadata();
    private int i=0;
}

接着，是提取数据的部分:

public CatMetadata gen(){
    for (i = 0; i < tokens.size(); i++) {
        Token now = tokens.get(i);
        boolean end = (i==tokens.size()-1);
        Token next = end?null:tokens.get(i+1);
        switch(now.getType()){
            case USING:
                if(!end){
                    i=i+1;
                    var clazz = readAsStringUntilLB();
                    cm.getCachedUsings().put(clazz, Optional.ofNullable(CatMetadata.Global.forClass(clazz)).orElseThrow(()->new ParseException("Can't find clazz "+clazz)));
                }else{
                    throwEOF();
                }
                continue;
            case FUNCTION:
                if (end) {
                    throwEOF();
                }
                // fn main(){}
                if(next.getType() != Token.Type.IDENTIFIER){
                    throw new ParseException(fileName+": Unexcepted "+next.getType()+" at line "+now.getLine());
                }
                String methodName = next.getContent();
                i=i+1; // Move Pointer to (
                MethodSign sign = readMethodSign(methodName);
                if(cm.getMethods().stream().anyMatch(e->e.hashCode()==sign.hashCode())){
                    throw new ParseException(fileName+": Duplicated method: "+sign+" at line "+now.getLine());
                }
                cm.getMethods().add(sign);
                skipCodeBlocks();
                continue;
            // ...
        }
    }
    return cm;
}

在这个循环当中，我们通过获取到 Token 的类型来判定需要做的操作，这是基于语言设计定义来做的—— 例如 fn 的后面必然是一个方法签名，而不可以是别的。最终 MetadataGenerator 将会返回一个 CatMetadata 以供后续操作。

因此，这一阶段我们也可以发掘出类型错误和大的语法错误。

与 Java 的世界

我们需要和 Java 交互，因此我们需要给 Class 建立 CatMetadata 。好在这很简单，因为 CatMetadata 需要的所有数据都可以通过反射获取，这里提供一段参考代码：

@AllArgsConstructor
public class ClassMetaPathImpl implements MetaPath{
    private ClassLoader classLoader;
    @Override
    public CatMetadata findClass(String clazz) {
        CatMetadata cm = new CatMetadata();
        Class<?> claz = Util.runCatching(()->{
            return Class.forName(clazz,false,classLoader);
        }).getResult();
        if(claz==null){
            return null;
        }
        for (Field declaredField : claz.getDeclaredFields()) {
            if(!Modifier.isPublic(declaredField.getModifiers())) continue;
            VariableDef def = new VariableDef(declaredField.getType().getCanonicalName(),declaredField.getName());
            cm.getFields().put(declaredField.getName(),def);
        }
        for(Method declaredMethod: claz.getDeclaredMethods()){
            if(!Modifier.isPublic(declaredMethod.getModifiers()))continue;
            MethodSign sign = new MethodSign(declaredMethod.getName(), (ArrayList<String>) Arrays.stream(declaredMethod.getParameterTypes()).map(e->e.getCanonicalName()).collect(Collectors.toList()));
            cm.getMethods().add(sign);
        }
        ClassDef cdf = new ClassDef();
        cdf.setClassName(clazz);
        cdf.setSuperclass(claz.getSuperclass()==null?null:claz.getSuperclass().getCanonicalName());
        cdf.setInterfaces(Arrays.stream(claz.getInterfaces()).map(e->e.getCanonicalName()).collect(Collectors.toList()));
        cm.setClassDefinition(cdf);
        return cm;
    }
}

静态分析结束后，我们就要准备开始生成 AST 了。

附
我们从 token 流中获取数据，并且根据类型进行匹配——但我们其实没有用到状态
仔细看，你会发现这个东西：

        i=i+1; // Move Pointer to (
+        MethodSign sign = readMethodSign(methodName);
        if(cm.getMethods().stream().anyMatch(e->e.hashCode()==sign.hashCode())){
            throw new ParseException(fileName+": Duplicated method: "+sign+" at line "+now.getLine());
        }
        cm.getMethods().add(sign);
+        skipCodeBlocks();
        continue;

是不是有些象是 DSL？
这其实归咎于类字段中那个不起眼的 int i = 0，它使得 for 循环的指针可以被整个类里的方法所共享。

private final String readAsStringUntilLB(){ // 一只读，读到一个换行为止并且收集成字符串
    StringBuilder sb = new StringBuilder();
    int b=0;
    for(int a = i; tokens.get(a).getType()!= Token.Type.BREAK_LINE;a++){
        sb.append(tokens.get(a).getContent());
        b=a;
    }
    i = b;
    return sb.toString();
}

在经过更加详细的 tokenize 之后，代码实际上变得更加可观了，

Parser

先占个坑位～

从零开始的编译器生涯

https://ib67.io/2021/10/01/Writting-A-Compiler-1/

作者

iceBear67

发布于

2021-10-01

更新于

2022-12-20

许可协议

#compiler tech

从零开始的编译器生涯

0x01 理论基础

Lexer

Parser

Static Analyzing

Code Generation

0x02 实践

Lexer

在 Parse 之前

Metadata

与 Java 的世界

Parser

作者

发布于

更新于

许可协议

评论

归档

分类

标签

目录

follow.it