• 手动写编译器实现加减乘除运算

    众所周知啊（或许并不hh），写一个编译器需要词法、语法和代码生成这些部分。
    本迷你编译器目的是接收一个算术表达式，生成汇编代码，并在linux上运行，从而生成结果。
    如果没有Linux系统，可以把driver.c注释掉，在main里直接复制汇编代码文本，在虚拟机上跑。
    为什么不写一个能在Windows上能直接跑出来的呢？因为我不会。。（众所周知啊，Linux和Windows所能接收的汇编语言是不一样的）

    那么，什么是编译器？

    C语言代码由固定的词汇按照固定的格式组织起来，简单直观，程序员容易识别和理解，但是对于CPU，C语言代码就是天书，根本不认识，CPU只认识几百个二进制形式的指令。这就需要一个工具，将C语言代码转换成CPU能够识别的二进制指令，也就是将代码加工成 .exe 程序；这个工具是一个特殊的软件，叫做编译器（Compiler）。

    编译器能够识别代码中的词汇、句子以及各种特定的格式，并将他们转换成计算机能够识别的二进制形式，这个过程称为编译（Compile）。

    编译也可以理解为“翻译”，类似于将中文翻译成英文、将英文翻译成象形文字，它是一个复杂的过程，大致包括词法分析、语法分析、语义分析、性能优化、生成可执行文件五个步骤，期间涉及到复杂的算法和硬件架构。对于学计算机或者软件的大学生，“编译原理”是一门专业课程，有兴趣的读者请自行阅读《编译原理》一书，这里我们不再展开讲解。

    C语言的编译器有很多种，不同的平台下有不同的编译器，例如：

    Windows 下常用的是微软开发的 cl.exe，它被集成在 Visual Studio 或 Visual C++ 中，一般不单独使用；

    Linux 下常用的是 GUN 组织开发的 GCC，很多 Linux 发行版都自带 GCC；

    Mac 下常用的是 LLVM/Clang，它被集成在 Xcode 中（Xcode 以前集成的是 GCC，后来由于 GCC 的不配合才改为 LLVM/Clang，LLVM/Clang 的性能比 GCC 更加强大）。

    你的代码语法正确与否，编译器说了才算，我们学习C语言，从某种意义上说就是学习如何使用编译器，让编译器生成可执行程序（例如 Windows 下的 .exe 程序）。

    编译器可以 100% 保证你的代码从语法上讲是正确的，因为哪怕有一点小小的错误，编译也不能通过，编译器会告诉你哪里错了，便于你的更改。

    类的描述：Lexer提供词法，Parser提供语法，AstNode定义语法树为Parser服务，Print用来打印，CodeGen生成汇编代码，driver接收代码，main用来测试。
    具体代码如下：
    Lexer.h:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#ifndef COMPILER_LEXER_H
#define COMPILER_LEXER_H
#include 
#include 

namespace compiler {

    enum class TokenKind{
        Add,
        Sub,
        Mul,
        Div,
        Num,
        Eof,
        Null
    };

    class Token{
    public:
        TokenKind kind;
        int value;
        std::string_view content;
    };

    class Lexer {
    private:
        std::string_view sourceCode;
        std::shared_ptr<Token> currentToken;
        char currentChar{' '};
        int cursor{0};
    public:
        Lexer(const char *code){
            sourceCode = code;
        }
        void GetNextToken();
        void GetNextChar();
        std::shared_ptr<Token> GetCurrentToken();
    };
}


#endif //COMPILER_LEXER_H


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    Lexer.cpp:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#include "Lexer.h"

void compiler::Lexer::GetNextToken() {
    while (isspace(currentChar)){
        GetNextChar();
    }
    TokenKind kind = TokenKind::Null;
    int value = 0;
    int startPos = cursor -1;
    if (currentChar == '\0'){
        kind = TokenKind::Eof;
    }
    else if (currentChar == '+'){
        kind = TokenKind::Add;
        GetNextChar();
    }
    else if (currentChar == '-'){
        kind = TokenKind::Sub;
        GetNextChar();
    }
    else if (currentChar == '*'){
        kind = TokenKind::Mul;
        GetNextChar();
    }
    else if (currentChar == '/'){
        kind = TokenKind::Div;
        GetNextChar();
    }
    else if (std::isdigit(currentChar)){
        value = 0;
        kind = TokenKind::Num;
        do{
            value = value * 10 + currentChar - '0';
            GetNextChar();
        } while (isdigit(currentChar));
    } else {
        printf("error:invalid type\n");
    }
    currentToken = std::make_shared<Token>();
    currentToken->kind = kind;
    currentToken->value = value;
    currentToken->content = sourceCode.substr(startPos, cursor - startPos - 1);
}

void compiler::Lexer::GetNextChar() {
    if (cursor >= sourceCode.size()){
        currentChar = '\0';
        cursor++;
    } else {
        currentChar = sourceCode[cursor++];
    }
}

std::shared_ptr<compiler::Token> compiler::Lexer::GetCurrentToken() {
    return currentToken;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    Parser.h:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#ifndef COMPILER_PARSER_H
#define COMPILER_PARSER_H
#include "Lexer.h"
#include "AstNode.h"

namespace compiler {
    class Parser {
    private:
        Lexer &lexer;
        std::shared_ptr<AstNode> ParseExpr();
        std::shared_ptr<AstNode> ParseAddExpr();
        std::shared_ptr<AstNode> ParseMulExpr();
        std::shared_ptr<AstNode> ParsePrimaryExpr();
    public:
        Parser(Lexer &lexer):lexer(lexer){}
        std::shared_ptr<ProgramNode> Parse();
    };
}


#endif //COMPILER_PARSER_H


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    Parser.cpp

    //
// Created by xiaoyu ren on 2022/11/21.
//

#include "Parser.h"

std::shared_ptr<compiler::ProgramNode> compiler::Parser::Parse() {
    auto node = std::make_shared<ProgramNode>();
    node->Lhs = ParseExpr();
    return node;
}

std::shared_ptr<compiler::AstNode> compiler::Parser::ParseExpr() {
    return ParseAddExpr();
}

std::shared_ptr<compiler::AstNode> compiler::Parser::ParseAddExpr() {
    std::shared_ptr<AstNode> left = ParseMulExpr();
    while (lexer.GetCurrentToken()->kind == TokenKind::Add || lexer.GetCurrentToken()->kind == TokenKind::Sub) {
        BinaryOperator binaryOperator = BinaryOperator::Add;
        if (lexer.GetCurrentToken()->kind == TokenKind::Sub){
            binaryOperator = BinaryOperator::Sub;
        }
        lexer.GetNextToken();
        auto node = std::make_shared<BinaryNode>();
        node->binaryOperator = binaryOperator;
        node->Lhs = left;
        node->Rhs = ParseMulExpr();
        left = node;
    }
    return left;
}

std::shared_ptr<compiler::AstNode> compiler::Parser::ParseMulExpr() {
    std::shared_ptr<AstNode> left = ParsePrimaryExpr();
    while (lexer.GetCurrentToken()->kind == TokenKind::Mul || lexer.GetCurrentToken()->kind == TokenKind::Div) {
        BinaryOperator binaryOperator = BinaryOperator::Mul;
        if (lexer.GetCurrentToken()->kind == TokenKind::Div){
            binaryOperator = BinaryOperator::Div;
        }
        lexer.GetNextToken();
        auto node = std::make_shared<BinaryNode>();
        node->binaryOperator = binaryOperator;
        node->Lhs = left;
        node->Rhs = ParsePrimaryExpr();
        left = node;
    }
    return left;
}

std::shared_ptr<compiler::AstNode> compiler::Parser::ParsePrimaryExpr() {
    auto node = std::make_shared<ConstantNode>();
    node->value = lexer.GetCurrentToken()->value;
    lexer.GetNextToken();
    return node;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    AstNode.h:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#ifndef COMPILER_ASTNODE_H
#define COMPILER_ASTNODE_H
#include 

namespace compiler {
    class AstVisitor;

    class AstNode {
    public:
        virtual ~AstNode(){};
        virtual void Accept(AstVisitor *visitor) {};
    };

    class ProgramNode : public AstNode{
    public:
        std::shared_ptr<AstNode> Lhs;
        void Accept(AstVisitor *visitor) override;
    };

    enum class BinaryOperator{
        Add,
        Sub,
        Mul,
        Div
    };

    class BinaryNode : public AstNode{
    public:
        BinaryOperator binaryOperator;
        std::shared_ptr<AstNode> Lhs;
        std::shared_ptr<AstNode> Rhs;
        void Accept(AstVisitor *visitor) override;
    };

    class ConstantNode : public AstNode{
    public:
        int value;
        void Accept(AstVisitor *visitor) override;
    };

    class AstVisitor{
    public:
        virtual void VisitorProgramNode(ProgramNode *node) {};
        virtual void VisitorBinaryNode(BinaryNode *node) {};
        virtual void VisitorConstantNode(ConstantNode *node) {};
    };
}


#endif //COMPILER_ASTNODE_H


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    AstNode.cpp:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#include "AstNode.h"

void compiler::BinaryNode::Accept(compiler::AstVisitor *visitor) {
    visitor->VisitorBinaryNode(this);
}

void compiler::ConstantNode::Accept(compiler::AstVisitor *visitor) {
    visitor->VisitorConstantNode(this);
}

void compiler::ProgramNode::Accept(compiler::AstVisitor *visitor) {
    visitor->VisitorProgramNode(this);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    Print.h:

    //
// Created by xiaoyu ren on 2022/11/22.
//

#ifndef COMPILER_PRINT_H
#define COMPILER_PRINT_H
#include "AstNode.h"

namespace compiler {
    class Print : public AstVisitor {
    private:
        void VisitorBinaryNode(BinaryNode *node) override;
        void VisitorConstantNode(ConstantNode *node) override;
    public:
        void VisitorProgramNode(ProgramNode *node) override;
    };
}


#endif //COMPILER_PRINT_H


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    Print.cpp:

    //
// Created by xiaoyu ren on 2022/11/22.
//

#include 
#include "Print.h"

void compiler::Print::VisitorProgramNode(compiler::ProgramNode *node) {
    node->Lhs->Accept(this);
    printf("\n");
}

void compiler::Print::VisitorBinaryNode(compiler::BinaryNode *node) {
    node->Rhs->Accept(this);
    node->Lhs->Accept(this);
    switch (node->binaryOperator) {
        case BinaryOperator::Add:
            printf("+ ");
            break;
        case BinaryOperator::Sub:
            printf("- ");
            break;
        case BinaryOperator::Mul:
            printf("* ");
            break;
        case BinaryOperator::Div:
            printf("/ ");
            break;
        default:
            assert(0);
    }
}

void compiler::Print::VisitorConstantNode(compiler::ConstantNode *node) {
    printf("%d ", node->value);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    CodeGen.h:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#ifndef COMPILER_CODEGEN_H
#define COMPILER_CODEGEN_H
#include "AstNode.h"

namespace compiler {
    class CodeGen : public AstVisitor {
    private:
        int top{0};
        void VisitorBinaryNode(BinaryNode *node) override;
        void VisitorConstantNode(ConstantNode *node) override;
        void Push();
        void Pop(const char *reg);
    public:
        CodeGen(){}
        void VisitorProgramNode(ProgramNode *node) override;
    };
}


#endif //COMPILER_CODEGEN_H


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    CodeGen.cpp:

    //
// Created by xiaoyu ren on 2022/11/21.
//

#include "CodeGen.h"
#include 

void compiler::CodeGen::VisitorProgramNode(compiler::ProgramNode *node) {
    printf("\t.text\n");
#ifdef __linux__
    printf("\t.global prog\n");
    printf("_prog\n");
#endif
    printf("\tpush %%rbp\n");
    printf("\tmove %%rsp, %%rbp\n");
    printf("\tsub $32, %%rsp\n");

    node->Lhs->Accept(this);
    assert(top == 0);

    printf("\tmove %%rbp, %%rsp\n");
    printf("\tpop %%rbp\n");
    printf("\tret\n");
}

void compiler::CodeGen::VisitorBinaryNode(compiler::BinaryNode *node) {
    node->Rhs->Accept(this);
    Push();
    node->Lhs->Accept(this);
    Pop("%rdi");
    switch (node->binaryOperator) {
        case BinaryOperator::Add:
            printf("\tadd %%rdi, %%rax\n");
            break;
        case BinaryOperator::Sub:
            printf("\tsub %%rdi, %%rax\n");
            break;
        case BinaryOperator::Mul:
            printf("\timul %%rdi, %%rax\n");
            break;
        case BinaryOperator::Div:
            printf("\tcqo\n");
            printf("\tdiv %%rdi\n");
            break;
        default:
            assert(0);
    }
}

void compiler::CodeGen::VisitorConstantNode(compiler::ConstantNode *node) {
    printf("\tmove $%d, %%rax\n", node->value);
}

void compiler::CodeGen::Push() {
    printf("\tpush %%rax\n");
    top++;
}

void compiler::CodeGen::Pop(const char *reg) {
    printf("\tpop %s\n", reg);
    top--;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    driver.c:

    //
// Created by xiaoyu ren on 2022/11/23.
//
#include 

int prog();

int main() {
    printf("%d\n", prog());
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    main.cpp:

    #include 
#include "Lexer.h"
#include "Parser.h"
#include "Print.h"
#include "CodeGen.h"

int main() {
    const char *code = " 5 + 1 - 3 * 4 / 2";
    compiler::Lexer lexer(code);
    //test lexer
//    do{
//        lexer.GetNextToken();
//        std::cout << lexer.GetCurrentToken()->content << std::endl;
//    } while (lexer.GetCurrentToken()->kind != compiler::TokenKind::Eof);
    //test parser，后序遍历
    lexer.GetNextToken();
    compiler::Parser parser(lexer);
//    compiler::Print visitor;
//    auto root = parser.Parse();
//    root->Accept(&visitor);
    //test codeGen
    compiler::CodeGen codeGen;
    auto root = parser.Parse();
    root->Accept(&codeGen);
    //execute
//    make
//    ./compiler "5+1-3*4/2" > tmp.s
//    clang tmp.s ../driver.c -o tmp.out
//    ./tmp.out
//    0
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    下载链接：https://github.com/643064456/manual-complier

  • 相关阅读:
    element-ui《input》输入框效验
    粗糙集知识约简的python代码
    科技云报道：不卷自研大模型，金山办公如何创新生成式AI？
    【网络】想学TCP，这一篇就够了 —— TCP理论知识详解（基于前面手搓TCP服务端博客的补充）
    js 数组去重
    Linux_oops缺页异常后输出的宕机日志解读
    图的bfs遍历
    JavaScript设计模式（三） 迭代器模式 发布-订阅模式
    python中的code object
    【Golang】Gin处理GET、POST请求
  • 原文地址：https://blog.csdn.net/r643064456/article/details/128039947