最近开始学习编译原理了，但是学的CS143的课一直在讲一些偏理论的东西，而且我对他上课讲的偏理论的东西的理解也很模糊。虽然有lab，但由于用到了flex和bison，极大程度简化了lexer和parser过程，我想尝试动手写这两部分。因此这个lab不适合目前的我，所以着手寻找手写编译器前端的教程。然后就找到了LLVM的教程。

此教程介绍了一个非常简单的语言 Kaleidoscope ，并实现它的前端部分。

编译器性质

此教程实现的编译器前端是一个 LL(1) 分析、手写lexer和parser实现、简单的语义分析阶段（在递归调用codegen发射到llvm ir过程中进行的：变量存在检查、表达式内自定义操作符检查、函数重定义等）、发射到llvm后端、支持用户定义表达式中的binary和unary操作符、支持jit运行、支持aot编译到object file的编译器。总的来说是一个比较好的实践编译器前端的学习项目。

但是本文章重点在于记录遇到的问题，等以后的文章再详细叙述这些东西吧。

编译器实现过程中出现的问题

Parser中一次完整的AST生成必须等待下一个TOKEN的输入

如果你在REPL内输入一串想要进行处理的合法表达式后，不输入多余的新的token，此编译器会等待下一个token的到来才能完整处理当前表达式。

效果比较像：在REPL内输入1+1并期望结果，此时不会有任何输出，因为在解析表达式时编译器被阻塞在了最后一步——执行gettok以获取新的token上了。它期望从标准输入中获得新的token，所以会等待用户输入新的字符。

而在编译器的具体实现上，由于语法的设计，我们完全可以区分各种表达式，等待下一个tok的到来的这一步明显没有必要，因此我想了一个“改进”：

• 将gettok从每个parse函数移到最前方，读取到当前的token后再进行处理，处理完毕直接输出结果。
• 不在初始化编译器时的主循环之前手动gettok并更新parser内部暂存的cur_tok

我认为这样就可以在解析表达式时，避免需要读取下一个token才能完成当前ast的生成这个问题。

但是为什么要这么设计？经过思考后，我唯一能想到的原因，大概是作者期望在REPL模式下，每个语句必须以;结尾。而;会在主循环中被忽略并等待读取下一个token。从而能够让REPL看起来是在处理一个包含了分号的完整的语句。实际上教程中几乎都是这么个写法。

所以经过分析得到了一个教程中理所当然的情况

从LLVM-9开始，即使是分隔模块也不支持重复符号

在实现第四章的代码中，官方文档提示了此问题，从而导致原文后文章节中“重定义同名函数”这一操作不能按照原有教程实现：原文的操作是直接将新的包含原来已存在函数名的模块添加进JIT，并更新函数表中的prototype。但是由于此feature的更新，不能简单实现类似脚本语言的“重定义同名函数”的操作。

经过搜索后，LLVM文档有提到添加进JIT的模块是可以被删除的，通过在添加模块时创建ResourceTracker一起传入JIT，在随后需要时可以通过此rt来删除已经添加进JIT的模块。

为此我们需要修改函数表，将函数表的定义修改为

std::map<string, std::pair<unique_ptr<prototype>, llvm::orc::ResourceTrackerSP>>
    function_meta;  

在map的value处通过使用pair，添加ResourceTrackerSP来把此函数的ResourceTracker。

另外需要注意的是，由于codegen函数签名不可轻易改变，又因为codegen函数内部会更新函数表，而在调用codegen的handle函数才能获取ResourceTracker，为了更好的解耦，不应把获取ResourceTracker放在codegen函数中，也就是说修改函数表时value的第二个参数需要延时赋值。所以经过修改后handle函数和codegen的行为如下

1. codegen 负责更新函数表，但是value的second成员填空指针。

   auto &p = *proto;
   function_meta[p.get_name()] = std::pair(std::move(proto), nullptr);

2. handle_def函数 调用codegen并在取得ResourceTracker并将module添加进JIT后修改函数表，为对应函数添加ResourceTracker

   auto rt = the_jit->getMainJITDylib().createResourceTracker();
   auto tsm = llvm::orc::ThreadSafeModule(std::move(the_module),
                                           std::move(the_context));
   EOE(the_jit->addModule(std::move(tsm), rt));
   function_meta[fn_ir->getName().str()].second = std::move(rt);

另外，由于kaleidoscope支持extern函数，此函数并不具体存在module内，而是通过运行时JIT使用dlsym函数动态查找执行，因此无需创建ResourceTracker。对extern进行parse的过程不会对JIT做出修改，它只修改了函数表。

所以对于重定义的函数，在函数的codegen过程，可以通过查表并判断其value的second成员是否存在来确定是否应该删除发送给JIT的module。

auto the_function = get_function(proto->get_name());
// release the module where function is in before re-defining
if (the_function) {
    auto rt = function_meta[proto->get_name()].second;
    if (rt) {
        log_err("Removing exists function");
        EOE(rt->remove());
    }
}

即使是从LLVM-9版本之后，用这样的方法也能实现重定义函数的功能。

无法加载编译器本身导出的函数

如果你跟着教程走，会发现在定义extern putchard(x)后仍然不能执行此函数，LLVM会报错无法找到此符号并退出。Stackoverflow中能找到此回答，需要给clang添加-Xlinker --export-dynamic参数解决。

原因

简单研究了一下，这条命令是给linker传递--export-dynamic参数，此参数强制指定连接器导出所有符号到动态符号表。对于是否将符号添加进符号表，ld的默认策略是

the dynamic symbol table will normally contain only those symbols which are referenced by some dynamic object mentioned in the link.

即会导出在链接过程中被其他动态库引用的符号。

例如有一个lib.c，定义extern int A();，编译为动态库后利用objdump -T查看动态符号表，发现A为UND。在main.c中编写A的实现，在main.c和lib.c编译链接的过程中ld会根据要链接的动态库文件对某个符号的依赖，来修改对应符号的符号属性，从而保证动态库也能查找到此符号。此时查看生成的ELF文件的动态符号表，可以发现A符号已经出现在动态符号表中了。

对于当前情况，自定义的功能函数在编译后没有添加到动态库中，导致JIT运行时无法通过dlsym查找到此函数，因此需要指定链接器导出所有符号到符号表中。

或许通过编写链接脚本，手动指定putchard这类工具库函数导出会是一个更好的方案？

总结

LLVM作为后端真的很大程度降低了一个编译器的实现难度，但是我仍然希望以后能手动搓一个编译器后端实现。