LLVM系列第十二章：写一个简单的词法分析器Lexer

系列文章目录

LLVM系列第一章：编译LLVM源码
LLVM系列第二章：模块Module
LLVM系列第三章：函数Function
LLVM系列第四章：逻辑代码块Block
LLVM系列第五章：全局变量Global Variable
LLVM系列第六章：函数返回值Return
LLVM系列第七章：函数参数Function Arguments
LLVM系列第八章：算术运算语句Arithmetic Statement
LLVM系列第九章：控制流语句if-else
LLVM系列第十章：控制流语句if-else-phi
LLVM系列第十一章：写一个Hello World
LLVM系列第十二章：写一个简单的词法分析器Lexer
LLVM系列第十三章：写一个简单的语法分析器Parser
LLVM系列第十四章：写一个简单的语义分析器Semantic Analyzer
LLVM系列第十五章：写一个简单的中间代码生成器IR Generator
LLVM系列第十六章：写一个简单的编译器
LLVM系列第十七章：for循环
LLVM系列第十八章：写一个简单的IR处理流程Pass
LLVM系列第十九章：写一个简单的Module Pass
LLVM系列第二十章：写一个简单的Function Pass
LLVM系列第二十一章：写一个简单的Loop Pass
LLVM系列第二十二章：写一个简单的编译时函数调用统计器(Pass)
LLVM系列第二十三章：写一个简单的运行时函数调用统计器(Pass)
LLVM系列第二十四章：用Xcode编译调试LLVM源码
LLVM系列第二十五章：简单统计一下LLVM源码行数

---

---

前言

在此记录下，基于LLVM写一个简单的词法分析器（Simple Lexer）的过程，以备查阅。

开发环境的配置请参考《LLVM系列第一章：编译LLVM源码》。

编译器是一个很大的话题，我们简单的介绍一下，以便切入本章重点。从编译器的设计角度来看，它通常分为前端和后端两部分。前端主要负责处理源代码，后端则负责生成机器码。

前端通常分为以下部分:

1. 词法分析器(Lexical analyzer，简称 Lexer)，读取源文件并生成令牌流(Tokens)。
2. 解析器(Parser)，从令牌流构建出一棵抽象语法树(AST)。
3. 语义分析器(Semantic Analyzer)，即对AST进行语义分析、添加语义信息等。
4. 代码生成器(Code Generator，简称 CodeGen)，从 AST 生成用中间表达语言(Intermediate Representation，简称IR)组成的程序代码。

而后端则把IR程序代码进行优化（及链接），并最终生成汇编程序代码或目标文件。

本章内容，仅仅与词法分析(Lexer)有关，是一个最简单的示例而已。

一、SimpleLang语言

为了方便起见，我们自己定义一种很简单的语言如下（示例）：

calc : ("with" ident ("," ident)* ":")? expr ;
expr: term(("+"|"-")term)* ;
term : factor (( "*" | "/") factor)* ;
factor : ident | number | "(" expr ")" ;
ident : ([a-zAZ])+ ;
number : ([0-9])+ ;

这是用扩展巴科斯范式写的语法规则，我们就暂时把这门语言命名为SimpleLang。其实，这并不是什么新的语言，这些规则源自于一门经典语言（名叫Modula-2）。

二、项目结构

我们把这个简单的项目命名为SimpleLexer。源码组织结构如下（示例）：

% tree -I "build|build-xcode"
.
├── CMakeLists.txt
├── src
│   ├── CMakeLists.txt
│   ├── Lexer.cpp
│   ├── Lexer.h
│   └── LexerPlayer.cpp

源文件Lexer.h和Lexer.cpp，包含了SimpleLang语言的词法分析器(Lexer)的定义及实现代码。main函数放在源文件LexerPlayer.cpp中，包含了Lexer的测试代码。

三、项目细节

1. 程序模块

这个简单的项目只包含了一个模块：

1. simplelexer，一个简单的可执行程序文件

以下是跟项目组织结构相关的部分CMake脚本。

(1) 项目根目录（示例）：

# CMakeLists.txt

...
project ("SimpleLexer")
...
add_subdirectory ("src")

这里创建了一个项目(project)，并把src目录下的子项目加入进来。

(2) src目录（示例）：

# src/CMakeLists.txt

...
add_executable(simplelexer ...)
...

这是src目录下的子项目，用来构建simplelexer程序。

2. 引入LLVM

我们需要做一些与LLVM相关的配置，才能顺利地使用LLVM（示例）：

# CMakeLists.txt

...
find_package(LLVM REQUIRED CONFIG)
message("Found LLVM ${LLVM_PACKAGE_VERSION}, build type ${LLVM_BUILD_TYPE}")
list(APPEND CMAKE_MODULE_PATH ${LLVM_DIR})
...
add_definitions(${LLVM_DEFINITIONS})
include_directories(SYSTEM ${LLVM_INCLUDE_DIRS})
llvm_map_components_to_libnames(llvm_libs Core)
...

# src/CMakeLists.txt

...
target_link_libraries(simplelexer PRIVATE ${llvm_libs})

3. Simple Lexer

我们的C++代码放在两个文件中：

1. src/LexerPlayer.cpp，包含了main函数
2. src/Lexer.h，src/Lexer.cpp，包含了Lexer和Token两个类

main函数（示例）：

#include "Lexer.h"
...

static llvm::cl::opt<std::string> input(llvm::cl::Positional, llvm::cl::desc("<input expression>"), llvm::cl::init(""));

int main(int argc, const char** argv)
{
    ...
    Lexer lex(input);

    Token token;
    lex.Next(token);
    while (token.GetKind() != Token::eoi)
    {
        llvm::outs() << "token type: " << token.GetKind() << ", token text: \"" << token.GetText() << "\"\n";

        lex.Next(token);
    }
   ...
}

我们看到以上代码调用了Lexer来做词法分析，并逐一打印出所有的Token。Lexer的定义如下（示例）：

class Lexer
{
public:

    Lexer(const llvm::StringRef& Buffer)
    {
        bufferStart = Buffer.begin();
        bufferPtr = bufferStart;
    }

    void Next(Token& token);
    ...
private:

    const char* bufferStart;
    const char* bufferPtr;
};

Lexer的实现如下（示例）：

void Lexer::GetNext(Token& token)
{
    while (*bufferPtr && std::isspace(*bufferPtr))
    {
        ++bufferPtr;
    }

    if (!*bufferPtr)
    {
        token.SetType(Token::kEOI);

        return;
    }

    if (std::isalpha(*bufferPtr))
    {
        const char* end = bufferPtr + 1;
        while (std::isalpha(*end))
        {
            ++end;
        }

        llvm::StringRef name(bufferPtr, end - bufferPtr);
        Token::TokenType type = (name == "with" ? Token::kKeywordWith : Token::kIdent);
        InitializeToken(token, end, type);

        return;
    }
    else if (std::isdigit(*bufferPtr))
    {
        const char* end = bufferPtr + 1;
        while (std::isdigit(*end))
        {
            ++end;
        }

        InitializeToken(token, end, Token::kNumber);

        return;
    }
    else
    {
        switch (*bufferPtr)
        {
        case '+':
            InitializeToken(token, bufferPtr + 1, Token::kPlus);
            break;

        case '-':
            InitializeToken(token, bufferPtr + 1, Token::kMinus);
            break;

        case '*':
            InitializeToken(token, bufferPtr + 1, Token::kStar);
            break;

        case '/':
            InitializeToken(token, bufferPtr + 1, Token::kSlash);
            break;

        case '(':
            InitializeToken(token, bufferPtr + 1, Token::kLeftParen);
            break;

        case ')':
            InitializeToken(token, bufferPtr + 1, Token::kRightParen);
            break;

        case ':':
            InitializeToken(token, bufferPtr + 1, Token::kColon);
            break;

        case ',':
            InitializeToken(token, bufferPtr + 1, Token::kComma);
            break;

        default:
            InitializeToken(token, bufferPtr + 1, Token::kUnknown);
        }

        return;
    }
}

void Lexer::InitializeToken(Token& token, const char* tokenEnd, Token::TokenType type)
{
    token.SetType(type);
    token.SetText(llvm::StringRef(bufferPtr, tokenEnd - bufferPtr));

    bufferPtr = tokenEnd;
}

注意到Lexer的实现，用了一个简单的状态机。在编译器的词法分析方面，这是常会提到的经典算法。

Lexer把SimpleLang程序的源代码当做一个简单的文本，把其中的字符逐一遍历、分析，试图把该文本切分成了以下几类词语：

1. 空格字符，如空格, \t, \n
2. 程序结束符，即EOI
3. 关键字，即with
4. 数字，如5, 234
5. 符号（数学运算符、分隔符），如+, -, *, /, (, ), :, ,

四、编译

1. 生成项目文件

用CMake生成项目文件（示例）：

mkdir build
cd build

cmake -G Ninja -DCMAKE_BUILD_TYPE=Debug ..

输出log如下（示例）：

-- The C compiler identification is AppleClang 13.0.0.13000029
-- The CXX compiler identification is AppleClang 13.0.0.13000029
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found ZLIB: /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.1.sdk/usr/lib/libz.tbd (found version "1.2.11") 
-- Found LibXml2: /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.1.sdk/usr/lib/libxml2.tbd (found version "2.9.4") 
Found LLVM 12.0.1, build type Release
-- Configuring done
-- Generating done
-- Build files have been written to: .../SimpleLexer/build

2. 编译

用ninja进行编译（示例）：

ninja

输出log如下（示例）：

[3/3] Linking CXX executable src/simplelexer

3. 运行

运行simplelexer（示例）：

src/simplelexer "with abc,xyz: (abc+xyz)*3 - 10/abc"

我们用于测试的SimpleLang程序代码，只有这么简单的一行而已with abc,xyz: (abc+xyz)*3 - 10/abc。输出结果如下（示例）：

Input: "with abc,xyz: (abc+xyz)*3 - 10/abc"
token type: 12, token text: "with"
token type: 2, token text: "abc"
token type: 4, token text: ","
token type: 2, token text: "xyz"
token type: 5, token text: ":"
token type: 10, token text: "("
token type: 2, token text: "abc"
token type: 6, token text: "+"
token type: 2, token text: "xyz"
token type: 11, token text: ")"
token type: 8, token text: "*"
token type: 3, token text: "3"
token type: 7, token text: "-"
token type: 3, token text: "10"
token type: 9, token text: "/"
token type: 2, token text: "abc"

可以看到，我们的simplelexer工具把SimpleLang程序代码切分成了一系列的Token。

五、总结

我们参考编译器设计的经典词法分析算法，基于LLVM提供的API，用C++写了一个很简单的词法分析器，并且编译运行成功。完整源码示例请参看：
https://github.com/wuzhanglin/llvm-simple-lexer