基于LLVM的编译原理简明教程 (1) - 写编译器越来越容易了

article/2025/10/1 18:39:42

基于LLVM的编译原理简明教程 (1) - 写编译器越来越容易了

进入21世纪，新的编程语言如雨后春笋一样不停地冒出来。需求当然是重要的驱动力量，但是在其中起了重要作用的就是工具链的改善。
2000年，UIUC的Chris Lattner主持开发了一套称为LLVM(Low Level Virtual Machine)的编译器工具库套件。后来，LLVM的scope越来越大，Low Level Virtual Machine已经不足以表示LLVM的全部，于是，LLVM就变成了正式的名字。LLVM可以用于常规编译器，JIT编译器，汇编器，调试器，静态分析工具等一系列跟编程语言相关的工作。
后来，Chris Lattner又主持开发了Clang，针对C/C++/Objective-C的前端。这个编译器直接挑战了GCC的统治地位。成为Apple系统的主要编译器，在Android中，指名使用Clang的模块也越来越多。
2012年，LLVM荣获美国计算机学会ACM的软件系统大奖，跟UNIX，WWW，TCP/IP，TeX，Java等经典系统作伴。
ACM系统奖完全名单

另外再八卦几句LLVM的主要作者和架构师Chris Lattner。这哥们生于1978年。
2005年，Chris Lattner加入Apple。因为Apple对于GCC支持Objective-C不力的不满，LLVM和Clang成为Apple替代GCC的杀手级武器。
2010年，Chris Lattner又开始主持开发Swift语言。

好了，言归正传。首先我们想说明的是，跟学院派的厚书给大家的印象不同，其实用LLVM写个简单的编译器是件容易的事情，因为大部分事情LLVM都替我们做了。

用LLVM做个简单的编译器很容易

我们先看一个使用LLVM工具之后，实现一门编程语言的简图：

编译器简图

完全需要我们手工，或者依靠其他工具如lex, yacc来做的事情，是从源代码到token的词法分析和从token到AST的语法分析。也就是前端的主要部分需要我们来实现，毕竟我们是这门语言的定义者。在介绍LLVM的书里，讲前端的部分都是只占很小的篇幅的，所以大家可以take it easy.
在LLVM的万花筒语言例子里，带有注释的词法分析和语法分析也不过400行。大家如果觉得还复杂，后面我会带大家做一些更简单的，先完成一小部分功能，然后迭代式开发。区区百余行代码，不需要学习编译原理。
比如Clang就是一个实现了C/C++/Objective-C的前端。
从AST转LLVM开始，LLVM就开始提供一系列的工具帮助我们快速开发。从IR(中间指令代码)到DAG(有向无环图)再到机器指令，针对常用的平台，LLVM有完善的后端。也就是说，我们只要完成了到IR这一步，后面的工作我们就享有和Clang一样的先进生产力了。
口说无凭，有例子为证，这是将二元表达式AST转成IR的函数：

Value *BinaryExprAST::codegen() {
...switch (Op) {case '+':return Builder.CreateFAdd(L, R, "addtmp");case '-':return Builder.CreateFSub(L, R, "subtmp");case '*':return Builder.CreateFMul(L, R, "multmp");case '<':L = Builder.CreateFCmpULT(L, R, "cmptmp");// Convert bool 0/1 to double 0.0 or 1.0return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");default:
...}
}

如何生成加减乘除的IR，在这个阶段完全不用关心，LLVM会帮我们生成相应的代码。
下面我们再看一个声明函数原型的：

Function *PrototypeAST::codegen() {// Make the function type:  double(double,double) etc.std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));FunctionType *FT =FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);Function *F =Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());// Set names for all arguments.unsigned Idx = 0;for (auto &Arg : F->args())Arg.setName(Args[Idx++]);return F;
}

词法分析

在正则表达式已经成为基本技能的今天，词法分析完全无门槛啊。正常情况下，我们只要写一组正则表达式，或者写个简单的状态机就可以了。

词法分析的输出是将源代码解析成一个个的token。这些token就是有类型和值的一些小单元，比如是关键字，还是数字，还是标识符等等。这个阶段不用管它们是如何组合的，都是干嘛的。
比如一个token类型是数值，值是3. 这个信息就已经足够了，至于这个3干嘛用，后面整理AST的时候再放到合适的位置上去。
至于什么时上下文无关语言，什么是确定有穷自动机，非确定有穷自动机等等这些，暂时都不需要了解。

语法分析

语法分析诚然是比词法分析要复杂一些。但是幸运的是，对于绝大多数语句和表达式来讲，并不需要高深的知识，“移进-归约”是个好方法，但是在我们学习的相当长的一段时期内都用不上。
语法分析的输出是抽象语法树AST，既然是棵树，自然构造时需要递归。所以在大部分的语句中，我们只按递归下降的方法就足够了。
对于表达式，递归下降还不够用，至少运算符还有优先级啊。所以针对表达式，我们还需要运算符优先分析法。SLR，LALR和LR暂时还用不上。

语法制导翻译和中间代码生成

从前面的简单例子中我们已经看到了，这部分大部分调用LLVM为我们提供的IR构造工具就可以了。入门阶段我们能想到的，如代码块，函数调用，控制结构等，LLVM都为我们准备好了。

优化

LLVM主我们提供了大量的优化Pass供我们选择和组合。在IR阶段和机器码阶段，我们都将花大量的篇幅来讨论优化。这可能也是我们真正感兴趣的部分。

词法分析很简单

我们看一个官方的例子，首先定义token的类型，有一种算一种吧。将来扩展都是体力活。

enum Token {tok_eof = -1,
...// primarytok_identifier = -4,tok_number = -5
};

然后就是解析正则表达式，一点技术含量也没有，哈哈~
我对官方的版本做了一点删节，看起来可以更清楚一些：

static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal;             // Filled in if tok_number/// gettok - Return the next token from standard input.
static int gettok() {static int LastChar = ' ';// Skip any whitespace.while (isspace(LastChar))LastChar = getchar();if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*IdentifierStr = LastChar;while (isalnum((LastChar = getchar())))IdentifierStr += LastChar;
...return tok_identifier;}if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+std::string NumStr;do {NumStr += LastChar;LastChar = getchar();} while (isdigit(LastChar) || LastChar == '.');NumVal = strtod(NumStr.c_str(), nullptr);return tok_number;}...// Check for end of file.  Don't eat the EOF.if (LastChar == EOF)return tok_eof;
...
}

如果不想手写的话，lex, flex之类的工具很多，就是根据正则表达式来决定token类型，根据类型存一下对应的值。
如果token的类型多，就是搭积木，写正则。都是体力活~

够用的语法分析其实也很简单

上面介绍了，我们自顶向下，构造抽象语法树。
先定义个根类型吧：

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:virtual ~ExprAST() {}virtual Value *codegen() = 0;
};

我们先来个简单的，就表示一个数字。这个好办，就一个节点，存个数值。

/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {double Val;public:NumberExprAST(double Val) : Val(Val) {}Value *codegen() override;
};

再来一个例子，变量，就是一个变量名么。赋值是下一步的事情了。

/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {std::string Name;public:VariableExprAST(const std::string &Name) : Name(Name) {}Value *codegen() override;
};

函数原型：

/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {std::string Name;std::vector<std::string> Args;public:PrototypeAST(const std::string &Name, std::vector<std::string> Args): Name(Name), Args(std::move(Args)) {}Function *codegen();const std::string &getName() const { return Name; }
};

然后我们再看看如何通过token去构造一个数值的AST:
词法分析时，已经把这个数值暂存了，我们把它拿来用就是了。

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {auto Result = llvm::make_unique<NumberExprAST>(NumVal);getNextToken(); // consume the numberreturn std::move(Result);
}

再看看函数声明的：

/// prototype
///   ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {if (CurTok != tok_identifier)return LogErrorP("Expected function name in prototype");std::string FnName = IdentifierStr;getNextToken();if (CurTok != '(')return LogErrorP("Expected '(' in prototype");std::vector<std::string> ArgNames;while (getNextToken() == tok_identifier)ArgNames.push_back(IdentifierStr);if (CurTok != ')')return LogErrorP("Expected ')' in prototype");// success.getNextToken(); // eat ')'.return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}

先读函数名，再找左括号，然后是参数列表，最后是处理右括号。什么嘛，一点技术含量也没有。。。

上面例子这些，都是没有嵌套的，也不需要递归下降和算符优先。这些是处理比如二元表达式的时候才会遇到的。我们可以先学习容易的，先能把这些容易的组件组成一门虽然语言功能不全，但是真正实现了从源码到机器指令的编译器。

上面的例子都来自官方的例子万花筒(Keleidoscope)语言的片段。官方教程当然写得已经足够好，但是还是稍嫌复杂了点，能生成一个可玩的编译器的速度还是有点慢。我打算把学习曲线再降低一下，通过不断地迭代，一点一点搭起可玩的编译器，然后慢慢扩充功能。

Hello,LLVM

LLVM的下载

  1. 先下载LLVM
svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
  1. 在LLVM的tools目录下，下载Clang(可选，但是建议):
cd llvm/tools
svn co http://llvm.org/svn/llvm-project/cfe/trunk clang
  1. 在LLVM的projects目录下，可选下载compiler-rt，Libomp，libcxx，libcxxabi。反正我都下载了
svn co http://llvm.org/svn/llvm-project/compiler-rt/trunk compiler-rt
svn co http://llvm.org/svn/llvm-project/openmp/trunk openmp
svn co http://llvm.org/svn/llvm-project/libcxx/trunk libcxx
svn co http://llvm.org/svn/llvm-project/libcxxabi/trunk libcxxabi

LLVM的编译

既然官方说大部分LLVM的开发者都使用Ninja，我们也就follow他们吧。
我在Mac下，所以使用Homebrew来安装CMake和Ninja。Linux与些类似，GCC版本太旧之类的请自助。Windows我还没试过，后面更新一下吧。

  1. 在LLVM目录下创建build目录
  2. cd build
  3. cmake -G Ninja
  4. Ninja

写个LLVM上的Hello,World程序吧

从AST转IR开始，我们都要用到LLVM的工具啦。先写个小程序学习一下LLVM的程序是如何编译的吧：

#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;
static std::map<std::string, llvm::Value *> NameValues;int main(){TheModule = llvm::make_unique<llvm::Module>("hello,llvm",TheContext);TheModule -> dump();return 0;
}

输出结果如下：

; ModuleID = 'hello,llvm'
source_filename = "hello,llvm"

如何链接LLVM的库

使用LLVM库的话，需要一大堆参数.
下面是在我的电脑上的参数：

-I/Users/ziyingliuziying/lusing/llvm/llvm/include -I/Users/ziyingliuziying/lusing/llvm/llvm/build/include  -fPIC -fvisibility-inlines-hidden -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wcovered-switch-default -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Werror=date-time -std=c++11 -fcolor-diagnostics   -fno-exceptions -fno-rtti -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS
-L/Users/ziyingliuziying/lusing/llvm/llvm/build/lib -Wl,-search_paths_first -Wl,-headerpad_max_install_names
-lLLVMCore -lLLVMSupport
-lcurses -lz -lm

每次都这么写吓死人了啊。于是LLVM为我们提供了llvm-config工具。刚才我那一大串，是用下面的命令行生成的：

llvm-config --cxxflags --ldflags --system-libs --libs core

完整的编译命令可以这么写：

clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy

http://chatgpt.dhexx.cn/article/gBvXQo40.shtml

相关文章

基于LLVM的编译原理简明教程: 写一个自己的编译器​

基于LLVM的编译原理简明教程: 写一个自己的编译器​

LLVM简介 进入21世纪&#xff0c;新的编程语言如雨后春笋一样不停地冒出来。需求当然是重要的驱动力量&#xff0c;但是在其中起了重要作用的就是工具链的改善。 2000年&#xff0c;UIUC的Chris Lattner主持开发了一套称为LLVM(Low Level Virtual Machine)的编译器工具库套件。…
阅读更多...
【极富参考价值！】第1章 ClickHouse 简介《ClickHouse 企业级大数据分析引擎实战》...

【极富参考价值！】第1章 ClickHouse 简介《ClickHouse 企业级大数据分析引擎实战》...

《ClickHouse 企业级大数据分析引擎实战》全书目录 目录 第1章 ClickHouse 简介 第2章 MergeTree 表存储引擎 第3章 ClickHouse SQL 执行原理 第4章 分布式的 ClickHouse：集群、分片、副本 第5章 项目实战：Spring Boot 集成 ClickHouse 第6章 ClickHouse 函数 第7章 集成外部…
阅读更多...
32.3-5带有通配符的匹配(自动机)

32.3-5带有通配符的匹配(自动机)

功能 这个程序可以判断一个带有通配符*的模式串是否在文本串中存在,没有记录位置信息,当然,想记录也是可以的 样例输入: abccbacbababc ab*bab*c 样例输出: 1 思路 对于样例输入,有限自动机如图所示: 我们把每个通配符隔开的字串看做独立的,在其上运行KMP算法的comput_s…
阅读更多...
自己动手写编译器:代码实现正则表达式到NFA状态机

自己动手写编译器:代码实现正则表达式到NFA状态机

在编译器开发中有两个非常重要的工具名为lex和yacc&#xff0c;他们是编译器的生成器。本质上我们不需要一行行去完成编译器的代码&#xff0c;只需要借助这两个工具&#xff0c;同时制定好词法解析和语法解析的规则后&#xff0c;这两个工具就会自动帮我们把代码生成&#xff…
阅读更多...
mac搭建网站服务器,Mac上搭建Web服务器--Apache

mac搭建网站服务器,Mac上搭建Web服务器--Apache

局域网搭建 Web 服务器测试环境,因为Mac OS X 自带了 Apache 和 PHP 环境，我们只需要简单的启动它就行了。 1.命令：sudo apachectl start Apache服务器默认的web根目录在：/Library/WebServer/Documents Apache的配置文件在：/etc/apache2 相关命令： 停止 Apache：sudo apac…
阅读更多...
aText for Mac(打字加速器)

aText for Mac(打字加速器)

aText作为一款文字效率的工具&#xff0c;对于文字工作者来说这款软件的目的是为了减少你在文字输入的过程当中的重复性&#xff0c;这款试用版本能够让你体验到一些较为基础的功能。 aText下载安装教程 镜像包下载完成后打开&#xff0c;双击.pkg按照安装引导器进行安装即可&a…
阅读更多...
共享文件夹无法打开——服务器存储空间不足，无法处理此命令

共享文件夹无法打开——服务器存储空间不足，无法处理此命令

原文地址为&#xff1a; 共享文件夹无法打开——服务器存储空间不足&#xff0c;无法处理此命令 共享某个文件夹后在网上邻居打开它&#xff0c;提示&#xff1a;“服务器存储空间不足&#xff0c;无法处理此命令”&#xff0c;如下图&#xff1a; 查看系统日志显示&#xff1…
阅读更多...
彻底解决win10 docker desktop镜像过大导致“C盘存储空间不足”的问题。

彻底解决win10 docker desktop镜像过大导致“C盘存储空间不足”的问题。

彻底解决win10 docker desktop镜像过大导致“C盘存储空间不足”的问题。 win10安装docker只需要双击安装包&#xff0c;真正实现了傻瓜式安装&#xff0c;这一点真的十分方便&#xff01;不过用了义端时间docker后&#xff0c;突然有一天我注意到C盘原本充裕的空间容量&#x…
阅读更多...
mysql数据库空间不足_mysql空间不足怎么解决？

mysql数据库空间不足_mysql空间不足怎么解决？

磁盘空间不足&#xff0c;使用du命令察看 du -h --max-depth1 当前目录下占空间比较大的是104个mysql-bin.00000X 和ibdata1。 mysql数据目录下有大量的mysql-bin.00000X文件&#xff0c;这些文件是做什么的呢&#xff1f; 这是数据库的操作日志&#xff0c;例如UPDATE一个表&a…
阅读更多...
ubuntu提示根目录存储空间不足的解决办法

ubuntu提示根目录存储空间不足的解决办法

因为每次使用系统都会产生大量的日志文件&#xff0c;如果没有设置自动清理日志文件或者分区较小&#xff0c;日志文件在一段时间的堆积后就会导致存储空间不足&#xff0c;所以需要清除日志文件。以下是清除步骤&#xff1a; 1、切换为超级用户 su2、查看日志文件大小 du &am…
阅读更多...
ES存储空间不足导致索引read-only解决

ES存储空间不足导致索引read-only解决

在es存储数据的时候报了这个错&#xff0c;然后网上都说是磁盘不够了&#xff0c;一看果然是磁盘剩余不足5个G了。。。 解决方案 1- 最简单的也就是清理下磁盘空间。 2- 更改elasticsearch.yml配置文件。在配置文件后加上&#xff1a; cluster.routing.allocation.disk.wate…
阅读更多...
如何解决IIS配置报错问题：存储空间不足？

如何解决IIS配置报错问题：存储空间不足？

如何解决IIS配置报错问题&#xff1a;存储空间不足 存储空间不足&#xff1b;并导致IIS安装失败 服务器说明&#xff1a; 当前服务器为阿里云服务器操作系统&#xff1a;windows services 2008 R2基本配置&#xff1a; 1G内存 20G40G存储盘服务器尚未安装配置IIS **“存储空间…
阅读更多...
解决群晖 “由于系统可用存储空间不足,您将无法登录“ 的问题

解决群晖 “由于系统可用存储空间不足,您将无法登录“ 的问题

最近打开群晖提醒 由于系统可用存储空间不足,您将无法登录。经过上网查询终于解决了问题&#xff0c;现记录如下&#xff1a; 问题总结 利用命令定位到哪个文件夹异常过大&#xff0c;删除之即可具体步骤 利用SSH进入群晖管理界面&#xff0c;利用sudo -i 拿到管理权限 利用…
阅读更多...
计算机管理 存储空间不足,Win7系统提示“存储空间不足，无法处理此命令”怎么办？...

计算机管理 存储空间不足,Win7系统提示“存储空间不足，无法处理此命令”怎么办？...

最近有Win7系统用户反映&#xff0c;打开某些程序的时候&#xff0c;出现提示“存储空间不足&#xff0c;无法处理此命令”&#xff0c;导致程序打开失败&#xff0c;这让用户非常苦恼。那么&#xff0c;Win7系统提示“存储空间不足&#xff0c;无法处理此命令”怎么办呢&#…
阅读更多...
32计算机内存不足,Win7 32位提示存储空间不足无法处理此命令

32计算机内存不足,Win7 32位提示存储空间不足无法处理此命令

近日&#xff0c;有不少用户反映说在win7 32位系统电脑上玩游戏或者打开程序的时候&#xff0c;遇到了无法运行的错误或者弹出错误信息“存储空间不足无法处理此命令”&#xff0c;导致无法运行游戏或者程序&#xff0c;为什么会出现这样的问题呢&#xff0c;下面就针对这个问题…
阅读更多...
远程桌面登录提示存储空间不足

远程桌面登录提示存储空间不足

远程桌面登录提示存储空间不足 云服务器windows2012远程桌面登录提示存储空间不足&#xff0c;无法完成此操作&#xff1b;点击确定按钮后回到登录界面&#xff1b; 使用控制台模式登录到服务器后端&#xff0c;查看RDP的登录权限&#xff0c;发现是本地系统账号&#xff1b;…
阅读更多...
打开共享文件提示服务器空间不足,访问网络共享报告“服务器存储空间不足，无法处理此命令”...

打开共享文件提示服务器空间不足,访问网络共享报告“服务器存储空间不足，无法处理此命令”...

访问网络共享报告“服务器存储空间不足，无法处理此命令” 万华数据 有些计算机在共享一个文件夹后，从网络上另一台计算机访问这个共享文件夹会出现“服务器存储空间不足，无法处理此命令”错误信息，更奇怪的是有时访问C盘的共享文件夹会出现这个问题，而访问其它盘的共享文件…
阅读更多...
局域网访问文件提示服务器内存不足,“服务器存储空间不足”的问题

局域网访问文件提示服务器内存不足,“服务器存储空间不足”的问题

局域网客户机通过网上邻居访问一台以windows 2003作为文件共享服务器的时候&#xff0c;出现“无法访问&#xff0c;您可能没有权限使用网络资源&#xff0c;请与管理员联系查明权限&#xff0c;服务器存储空间不足&#xff0c;无法处理此命令”的错误提示。 这个时候这台服务器…
阅读更多...
计算机管理 存储空间不足,win10系统提示“存储空间不足无法处理此命令”的处理技巧...

计算机管理 存储空间不足,win10系统提示“存储空间不足无法处理此命令”的处理技巧...

win10系统使用久了&#xff0c;好多网友反馈说win10系统提示“存储空间不足无法处理此命令”的问题&#xff0c;非常不方便。有什么办法可以永久解决win10系统提示“存储空间不足无法处理此命令”的问题&#xff0c;面对win10系统提示“存储空间不足无法处理此命令”的图文步骤…
阅读更多...
计算机提示存储空间不足怎么办,电脑提示存储空间不足,无法处理此命令是什么原因?怎么解决?...

计算机提示存储空间不足怎么办,电脑提示存储空间不足,无法处理此命令是什么原因?怎么解决?...

电脑“存储空间不足 无法处理此命令”怎么办&#xff1f;每次游戏玩着玩着就会弹出这样一个错误提示&#xff0c;那么造成这个情况的原因是什么&#xff1f;下面我们一起来看看。 “存储空间不足 无法处理此命令”原因&#xff1a; 第一是您的内存或虚拟内存空间不足&#xff0…
阅读更多...
推荐文章

Copyright @ 2022~2023