前言

本篇博客主要记录我学习 complier 的过程.

主要参考书籍: 《编译器设计(第二版)》、《编译方法、技术与实践》

正文

9-10

Lv0. 环境配置

记录一下上一周完成的：根据北大编译实验在线文档完成了Lv0.环境配置配置了docker源，并且根据docker写了一个启动脚本，我选择了c/c++路线使用cmake进行编译。

脚本如下：

#!/bin/bash

docker run -it --rm -v $(pwd):/root/compiler maxxing/compiler-dev bash -c "
    cd compiler &&
    cmake -DCMAKE_BUILD_TYPE=Debug -B build &&
    cmake --build build &&
    cd build &&
    bash
"

其中第一行是根据 Maxxing 的 docker run 脚本改的启动脚本，使用了 $(pwd) 增加脚本的通用性.

后面的内容很容易理解.

Lv1. main函数

Lv1.1. 编译器的结构

编译器通常由以下几个部分组成:

前端: 通过词法分析和语法分析, 将源代码解析成抽象语法树 (abstract syntax tree, AST). 通过语义分析, 扫描抽象语法树, 检查其是否存在语义错误.
中端: 将抽象语法树转换为中间表示 (intermediate representation, IR), 并在此基础上完成一些机器无关优化.
后端: 将中间表示转换为目标平台的汇编代码, 并在此基础上完成一些机器相关优化.

一些英文用语

词法分析器 (lexer)
语法分析器 (parser)
字节流 (byte stream)
单词流 (token stream)
中间表示 (IR)
抽象语法树 (AST)

词法分析的作用, 是把字节流转换为单词流 (token stream). 语法分析的目的, 按照程序的语法规则, 将输入的 token 流变成程序的 AST. 在语法分析的基础上, 编译器会对 AST 做进一步分析, 以期 “理解” 输入程序的语义, 为之后的 IR 生成做准备. 编译器通常会将 AST 转换为另一种形式的数据结构, 我们把它称作 IR. IR 的抽象层次比 AST 更低, 但又不至于低到汇编代码的程度. 在此基础上, 无论是直接把 IR 进一步转换为汇编代码, 还是在 IR 之上做出一些优化, 都相对更容易.（比较出名的LLVM 里面就有很多IR）编译器进行的最后一步操作, 就是将 IR 转换为目标代码, 也就是目标指令系统的汇编代码.

Lv1.2. 语法/词法分析初见

由于生在一个好时代，我们想要实现一个效率蛮不错的词法/语法分析器，并不需要手写递归下降分析器。不过我先在这里放一个网址，可以以后留着来看 Kaleidoscopea↗. 现在的工具可以根据正则表达式和 EBNF 生成词法/语法分析器.

EBNF, 即 Extended Backus–Naur Form↗, 扩展巴科斯范式, 可以用来描述编程语言的语法.

9-11

示例：

int main() {
  // 忽略我的存在
  return 0;
}

的语法用EBNF表示为

CompUnit  ::= FuncDef;

FuncDef   ::= FuncType IDENT "(" ")" Block;
FuncType  ::= "int";

Block     ::= "{" Stmt "}";
Stmt      ::= "return" Number ";";
Number    ::= INT_CONST;

通过推导可以得到

"int" IDENT "(" ")" "{" "return" INT_CONST ";" "}"

由于活在一个好的时代，在C/C++中，我们可以使用 Flex 和 Bison 来分别生成词法分析器和语法分析器.

Flex 用来描述 EBNF 中的终结符部分, 也就是描述 token 的形式和种类. 你可以使用正则表达式来描述 token.
Bison 用来描述 EBNF 本身, 其依赖于 Flex 中的终结符描述. 它会生成一个 LALR parser.

关于 Flex 和 Bison 的学习，Maxxing 推荐参考 Calc++↗ 这里先行放置一下，等以后过来可以学习一下.

Flex 将会读取 *.l 文件中描述的词法规则，Bison 将会读取 *.y 文件中描述的语法规则.由于这两个文件是互相依赖的由于 Flex 和 Bison 生成的 lexer 和 parser 会互相调用, 所以这两个文件里的内容也相互依赖.

这两种后缀的文件的结构都是：

// 这里写一些选项, 可以控制 Flex/Bison 的某些行为

%{

// 这里写一些全局的代码
// 因为最后要生成 C/C++ 文件, 实现主要逻辑的部分都是用 C/C++ 写的
// 难免会用到头文件, 所以通常头文件和一些全局声明/定义写在这里

%}

// 这里写一些 Flex/Bison 相关的定义
// 对于 Flex, 这里可以定义某个符号对应的正则表达式
// 对于 Bison, 这里可以定义终结符/非终结符的类型

%%

// 这里写 Flex/Bison 的规则描述
// 对于 Flex, 这里写的是 lexer 扫描到某个 token 后做的操作
// 对于 Bison, 这里写的是 parser 遇到某种语法规则后做的操作

%%

// 这里写一些用户自定义的代码
// 比如你希望在生成的 C/C++ 文件里定义一个函数, 做一些辅助工作
// 你同时希望在之前的规则描述里调用你定义的函数
// 那么, 你可以把 C/C++ 的函数定义写在这里, 声明写在文件开头

实验中给出的实例代码可以在这里↗ 看一看.

在誊抄了lab中的代码后，我也是成功运行了这个简易 “编译器” 了.

当然，运行complier的时候记得参数中文件的地址，比如示例文件中 hello.c 在 ../ 中，别忘了修改参数，不然会报错

compiler: /root/compiler/src/main.cpp:27: int main(int, const char **): Assertion `yyin' failed.
Aborted (core dumped)

9-14

强烈推荐使用 VScode 中的 Yash 插件,可以高亮 Flex & Bison 的语法以及纠错.

在 parser 里可以使用 unique_ptr 智能指针来很好的减轻内存管理的压力.

基本特性:

自动管理内存（RAII）
独占所有权（不能复制，只能移动）
离开作用域时自动删除所指向的对象

示例:

#include <memory>
#include <string>

// 基本使用示例
void uniquePtrBasics() {
    // 创建 unique_ptr
    std::unique_ptr<std::string> ptr1 = std::make_unique<std::string>("Hello");
    
    // 或者使用 new（不推荐）
    std::unique_ptr<std::string> ptr2(new std::string("World"));
    
    // 访问内容
    std::cout << *ptr1 << std::endl;        // 解引用
    std::cout << ptr1->length() << std::endl; // 成员访问
    
    // 移动语义（转移所有权）
    std::unique_ptr<std::string> ptr3 = std::move(ptr1);
    // 现在 ptr1 为空，ptr3 拥有字符串
    
    // 离开作用域时自动删除内存
}

Union 联合体

基本特性:

所有成员共享同一块内存
大小等于最大成员的大小
同一时间只能使用其中一个成员

示例

// 基本 union 示例
union BasicUnion {
    int int_val;
    float float_val;
    char char_val;
};

int main() {
    BasicUnion u;
    
    // 只能同时使用一个成员
    u.int_val = 42;
    cout << "int: " << u.int_val << endl;  // 输出: 42
    
    u.float_val = 3.14f;
    cout << "float: " << u.float_val << endl;  // 输出: 3.14
    cout << "int: " << u.int_val << endl;      // 输出: 垃圾值，因为被覆盖了
    
    return 0;
}

Lv1.3. 解析main函数

本节的内容需要我处理以下EBNF:

CompUnit  ::= FuncDef;

FuncDef   ::= FuncType IDENT "(" ")" Block;
FuncType  ::= "int";

Block     ::= "{" Stmt "}";
Stmt      ::= "return" Number ";";
Number    ::= INT_CONST;

我使用了智能指针的方案,进一步理解了面向对象编程中多态这一个概念后,我开始照着Maxxing的示例进行编写. 我创建了 ast.h, ast.cpp, include.h , 分别用来保存ast中相关类的定义,ast中各个类中Dump()函数的编写.以及原来的一些头文件.

ast.h

#pragma once

#include "include.h"

class BaseAST {
public:
    virtual ~BaseAST() = default;
    virtual void Dump() const = 0;
};

class CompUnitAST : public BaseAST {
public:
    std::unique_ptr<BaseAST> fun_def;
    void Dump() const override;
};

class FunDefAST : public BaseAST {
public:
    std::unique_ptr<BaseAST> fun_type;
    std::string ident;
    std::unique_ptr<BaseAST> block;
    void Dump() const override;
};

class FunTypeAST : public BaseAST {
public:
    std::string tp;
    void Dump() const override;
};

class BlockAST : public BaseAST {
public:
    std::unique_ptr<BaseAST> stmt;
    void Dump() const override;
};

class StmtAST : public BaseAST {
public:
    std::string retrn = "return";
    std::unique_ptr<BaseAST> number;
    std::string fenhao = ";";
    void Dump() const override;
};

class NumberAST : public BaseAST {
public:
    int int_const;
    void Dump() const override;
};

ast.cpp


#include "include.h"
#include "ast.h"

void CompUnitAST :: Dump() const {
    std::cout << "CompUnitAST { ";
    fun_def -> Dump();
    std::cout << " } ";
}

void FunDefAST :: Dump() const{
    std::cout << "FuncDefAST { ";
    fun_type -> Dump();
    std::cout << ident << " ( ) ";
    block -> Dump();
    std::cout << " } " ;
}

void FunTypeAST :: Dump() const{
    std::cout << "FuncTypeAST { ";
    std::cout << tp ;
    std::cout << " } ";
}


void BlockAST :: Dump() const{
    std::cout << "BlockAST { ";
    stmt -> Dump() ;
    std::cout << " } ";    
}

void StmtAST :: Dump() const{
    std::cout << "StmtAST { ";
    std::cout << retrn;
    number -> Dump();
    std::cout << fenhao;
    std::cout << " } ";
}

void NumberAST :: Dump() const{
    std::cout << int_const;
}

了解了智能指针的用法后,这些还是比较容易写出来的,就是有点费时间.

然后在 sysy.y 照着示例将所有字符串更新成为 AST 类即可.

写完后我遇到了两个问题,第一是在 Stmt 返回的第二个参数返回的类型,和我设计的预期不符合

Stmt
  : RETURN Number ';' {
    auto numbr = new StmtAST();
    numbr -> number = unique_ptr<BaseAST>($2);
    $$ = numbr;
  }
  ;

这其实是照着教程给非终结符定义的时候将Number 定义成了 int_val 导致 ($2) 的返回值是一个int ,导致错误.

把Number 加入了 ast_val 后就成功解决了.

第二个问题是链接的时候出现问题, *.cpp 类型的文件都不能放在别的文件的 include path 当中,会重复定义.

删除了这些 ast.cpp 就ok了.

得到结果

9-15

Lv1.4. IR 生成

这一节,演示代码几乎消失不见了,只剩下我们需要实现的目标:

我们应该生成一个 Koopa IR 程序.
程序中有一个名字叫 main 的函数.
函数里有一个入口基本块.
基本块里有一条返回指令.
返回指令的返回值就是 SysY 里 return 语句后跟的值, 也就是一个整数常量.

并且最后生成一个这个程序:

fun @main(): i32 {  // main 函数的定义
%entry:             // 入口基本块
  ret 0             // return 0
}

打算用 vector<unique_ptr<xxx>> 之类的来存.今日进度不佳.

9-16

我定义好了 Ir.h 和 Ir.cpp 里的内容,定义好了如何 IR 里的内容.方法和 AST 类似,Dump()函数也类似.这回也是纯纯手写代码上了.

现在就是写 IRGenerator 的时间,我本来想使用函数式定义这个 GENERATOR 不过考虑到这个函数可能会过于庞大,还是用类来定义了.

这是我初版的 IRGenerator 的定义:

class IRGenerator {
private:
    std::unique_ptr<IRProgram> program;
    static int blockcount;
    
public:
    IRGenerator(){};
    void visitCompUnit(const CompUnitAST* ast);
    void visitFunDef(const FunDefAST* ast);
    void visitFunType(const FunTypeAST* ast);
    void visitBlock(const BlockAST* ast);
    void visitStmt(const StmtAST* ast);
    void visitNumber(const NumberAST* ast);
    std::unique_ptr<IRProgram> get_irprogram();
};

比较好理解,不过这里每一个 visit 函数的参数并没有使用 unique_ptr<BaseAST> 的类型,使用了各种 AST 分别的类的指针,会安全一些.

但是,我在之前生成 AST 的时候,基于多态性质,利用的所有指针都是 BaseAST 类型的,怎么才能优秀的传入 visit 函数的参数中呢?

if (ast && ast->fun_def) {
    if (auto func_def = dynamic_cast<FunDefAST*>(ast->fun_def.get())) {
        visitFuncDef(func_def);
    }
}

这个代码是 ai 生成的 ,我觉得很有意思,它做了这些事情:

void IRGenerator::visitCompUnit(const CompUnitAST* ast) {
    // 步骤1：检查 ast 指针是否有效
    if (!ast) {
        std::cout << "CompUnitAST is null!" << std::endl;
        return;
    }
    
    // 步骤2：检查 fun_def 成员是否存在
    if (!ast->fun_def) {
        std::cout << "fun_def is null!" << std::endl;
        return;
    }
    
    // 步骤3：检查 fun_def 的实际类型是否是 FunDefAST
    auto func_def = dynamic_cast<const FunDefAST*>(ast->fun_def.get());
    if (!func_def) {
        std::cout << "fun_def is not a FunDefAST!" << std::endl;
        return;
    }
    
    // 步骤4：安全地调用 visitFuncDef
    visitFuncDef(func_def);
}

dynamic_cast<目标类型>(源对象) 这个函数的作用是尝试将源对象转化成目标类型, 如果失败返回 nullptr,十分满足我的需求.不过,需要注意的是,该操作虽然安全,但是有性能开销,还有一种函数是 static_cast 这个会快速一些,但是会导致未定义行为,以后的实践可能会用到这个优化.

我觉得可以学习这种写法,优秀的解决了参数类型的问题,还带有检测ast以及ast -> fun_def是否为空的问题.

9-17

顺利的写出了IR的内容.

修改了 IRGenerator 里 visit 函数的定义 , 给visit Block等函数添加了 IRBasicBlock* 类的参数.

给参数是指针的函数传递参数的时候,要使用 std::move() 转移所有权,不然会出现问题;

Lv1.5. 测试

按照要求,我更新了我的 run.sh 的内容,添加了测试的功能.

#!/bin/bash

# 获取项目目录的绝对路径
PROJECT_DIR=$(pwd)

# 检查第一个参数
if [ "$1" = "test" ]; then
    # 测试模式：运行 autotest
    sudo docker run -it --rm -v $PROJECT_DIR:/root/compiler maxxing/compiler-dev \
        autotest -koopa -s "$2" /root/compiler
else
    # 默认模式：进入交互式 bash
    sudo docker run -it --rm -v $PROJECT_DIR:/root/compiler maxxing/compiler-dev bash -c "
        cd compiler &&
        cmake -DCMAKE_BUILD_TYPE=Debug -B build &&
        cmake --build build &&
        cd build &&
        bash
    "
fi

输入./run.sh test lv1就可以开始测试了.

这回没过第二个测试点,原来是遗留的作业没有做完,多行匹配.

CSDN 经过几年的运营 ,越来越差了, 基本都是垃圾, 不垃圾的需要冲会员.

在 .l 里写了多行匹配的正则表达式之后,就完成了测试.

Lv2. 初试目标代码生成

Lv2.1. 处理Koopa IR

由于我写出来的IRGenerator是存储在内存当中的,所以这一节跳过.

Lv2.2. 目标代码生成

我需要把

fun @main() : i32 {
%entry0 :
  ret 0 
}

变成

  .text
  .globl main
main:
  li a0, 0
  ret

这样的汇编代码,我准备在每个 Value 的类中添加转化成Risc-V的代码,应该不会很复杂.

9-19

我在所有的 value basicblock function program IR 类中添加了To_Riscv 函数，按照实例代码翻译即可，还是很容易的.

这里我给之前的代码做出一些修改，将return Number 这个操作合并到ReturnValue 这个类中，这样就不会出现生成koopa IR和生成RiscV汇编的时候出现ret 和number 顺序出错的问题了.

Lv2.3. 测试

我又更新了我的 run.sh 增加了一个参数，可以手动选择测试的时候要 -koopa 还是 -riscv .

这是更新后的代码

#!/bin/bash

# 获取项目目录的绝对路径
PROJECT_DIR=$(pwd)

# 检查第一个参数
if [ "$1" = "test" ]; then
    # 测试模式：运行 autotest
    sudo docker run -it --rm -v $PROJECT_DIR:/root/compiler maxxing/compiler-dev \
        autotest "$2" -s "$3" /root/compiler
else
    # 默认模式：进入交互式 bash
    sudo docker run -it --rm -v $PROJECT_DIR:/root/compiler maxxing/compiler-dev bash -c "
        cd compiler &&
        cmake -DCMAKE_BUILD_TYPE=Debug -B build &&
        cmake --build build &&
        cd build &&
        bash
    "
fi

可能是之前写AST和IR都选择了纯手写，保存IR到内存，所以第二章需要增添的内容挺少的，顺利通过了第二章。

Lv3. 表达式

Lv3.1. 一元表达式

本章我要完成这样一个EBNF

Stmt        ::= "return" Exp ";";

Exp         ::= UnaryExp;
PrimaryExp  ::= "(" Exp ")" | Number;
Number      ::= INT_CONST;
UnaryExp    ::= PrimaryExp | UnaryOp UnaryExp;
UnaryOp     ::= "+" | "-" | "!";

要将Stmt重写.

9-21

天下英雄如过江之鲫

我感觉要走的路还是太长了,走着走着就迷茫了.

我定义好了 AST 并且写出了对应的 Bison 内容,明天写 IR 的内容.

9-22

这是 maxxing 给出的实例代码

int main() {
  return +(- -!6);  // 看起来像个颜文字
}

我们只看

  +(- -!6)

根据 EBNF 规则，该语句可以这样被推导出来

Exp -> UnrayExp 
-> UnrayOp UnrayExp
-> "+" PrimaryExp
-> "+" "(" Exp ")" 
-> "+" "(" UnrayExp ")" 
-> "+" "(" UnrayOp UnrayExp ")" 
-> "+" "(" "-" UnrayOp UnrayExp ")" 
-> "+" "(" "-" "-" UnrayOp UnrayExp ")" 
-> "+" "(" "-" "-" "!" PrimaryExp ")" 
-> "+" "(" "-" "-" "!" Number ")" 
-> "+" "(" "-" "-" "!" INT_CONST ")"

我貌似发现了一些问题，我的 Bison 文件中，括号里的 Exp 好像并没有被优先处理。

得 ATFA 了.

实际上我可能对 parser 的工作原理还完全没有了解.

我只知道它在做上述推导规则的逆过程

Bison 使用了 LR 的推导规则, LR 是 Left-to-right, Rightmost derivation 的缩写. 这是一种自底向上的Parser规则.

还有一些其他的 Parser 规则,比如 LL 以及其他,这里用 ai 做了个表.

Parser 类型	优点	缺点	适用场景
递归下降	简单直观，容易调试	只支持 LL(k)，左递归需要改写	简单语言，原型开发
LR/LALR	强大，支持大多数实际文法	冲突难调试，表格较大	生产级编译器
GLR	支持有歧义文法	复杂，性能开销大	自然语言处理，复杂 DSL
Parser Combinator	模块化，类型安全	性能可能不如表驱动	函数式语言，小型 DSL
PEG	无歧义，支持任意前瞻	某些文法表达困难	现代编程语言

LR PARSER

关于 LR 的原理,我来简单说下我的理解.

我觉得要理解 LR Parser 的实现过程,理解 ACTION table 和 GOTO table 是怎么生成的会比较关键一些.

不过我们等会再说这两个 table 是怎么生成,我们先看看 LR Parser 会进行哪些操作.

LR Parser 会严格的按照两张 table (ACTION & GOTO) 对 两个栈 进行操作:

状态栈 : 保存解析过程中的状态序列
符号栈 : 保存已经识别出的文法符号 (终结符和非终结符)

而操作有四种:

Shift (移进) : 从输入流中读入一个符号,并推入符号栈,同时将新状态推入状态栈
Reduce (归约) : 从符号栈的栈顶 pop 出若干元素 ,从栈顶弹出若干符号（某条语法规则的右侧），压入一个新的非终结符（该规则的左侧），并根据 GOTO 表压入新状态
Accept (接受) : 解析成功完成
Error (错误) : 检测到语法错误

LR parser 绝大部分时候只会干两件事情 Shift 和 Reduce.

首先的问题是,什么是状态?

状态表示 当前解析进度的所有可能情况的集合

而这个情况我们可以用项目来描述,

项目大致长这样

Stmt -> RETURN • Exp ';'

和 EBNF 语句几乎完全一样,但是多了一个点.

这个点是解析进度标记,在这个点前面的语句代表已经识别的符号,点后面的代表还需要识别的符号.

那么上述的项目可以理解为 已经看到 RETURN，现在期望 Exp

既然我期望得到他,那我就把所有能得到他的项目创建成一个状态,比如说这样

核心: Stmt → RETURN • Exp ';'

CLOSURE(I1):
Stmt → RETURN • Exp ';'
Exp → • UnaryExp             [因为点后是 Exp]
UnaryExp → • PrimaryExp      [因为点后是 UnaryExp]
UnaryExp → • UnaryOp UnaryExp
PrimaryExp → • '(' Exp ')'   [因为点后是 PrimaryExp]
PrimaryExp → • Number
UnaryOp → • '+'              [因为点后是 UnaryOp]
UnaryOp → • '-'
UnaryOp → • '!'
Number → • INT_CONST         [因为点后是 Number]

这样我们就得到了一个状态即项目的集合.

我们已经解析完了 RETURN 这时候,如果我们读取到了一个新的 TOKEN ,比如说 “42” 这是一个 INT_CONST 我们就知道我们可以进入一个新的状态了.

这个时候我们可以得到一条 ACTION 表的语句当我们在状态 I1 , 然后读取到了 INT_CONST 的时候,我们把这个 INT_CONST 压入到符号栈栈顶同时把状态 I2 压入状态栈的栈顶

简写成

ACTION	INT_CONST
I1	s2

现在的符号栈栈顶是 I2

CLOSURE(I2)
Number → INT_CONST •         [归约项目]

这个项目的点已经走到了尽头,代表他可以归约.

这个时候我们压入 NUMBER , pop 了状态栈的顶部元素 I2 回到了 I1;

这个时候我们会进入这样一个状态空间

PrimaryExp → • Number

假设上面的这个状态是 I7 ,那么我们就得到一个 goto 表的项了

GOTO	NUMBER
I1	I7

显然, GOTO 表只处理非终结符

不过 Bison 会使用 GOTO 函数的方法去构造这个表,这里就不再赘述,不过核心思想就是我刚才演示的那两条.

我们来看个例子

注:下面的 GOTO 皆为 GOTO 函数的意思,并非 GOTO 表

GOTO 函数：在构造 LR 自动机时使用的状态转移函数

格式： GOTO (状态, 符号) = 新状态
可以处理任何文法符号（终结符和非终结符）
用于构造状态机和生成分析表

第一步：从语法生成项目集和状态

这是 maxxing 给的语法规则 (ENBF)

(0) S' → Stmt                    [增广文法]
(1) Stmt → RETURN Exp ';'
(2) Exp → UnaryExp  
(3) UnaryExp → PrimaryExp
(4) UnaryExp → UnaryOp UnaryExp
(5) PrimaryExp → '(' Exp ')'
(6) PrimaryExp → Number
(7) UnaryOp → '+'
(8) UnaryOp → '-'
(9) UnaryOp → '!'
(10) Number → INT_CONST

状态生成过程

状态 I0（初始状态）

核心项目: S' → • Stmt

CLOSURE(I0):
S' → • Stmt
Stmt → • RETURN Exp ';'    [因为点后是 Stmt]

GOTO(I0, RETURN) = I1

核心: Stmt → RETURN • Exp ';'

CLOSURE(I1):
Stmt → RETURN • Exp ';'
Exp → • UnaryExp             [因为点后是 Exp]
UnaryExp → • PrimaryExp      [因为点后是 UnaryExp]
UnaryExp → • UnaryOp UnaryExp
PrimaryExp → • '(' Exp ')'   [因为点后是 PrimaryExp]
PrimaryExp → • Number
UnaryOp → • '+'              [因为点后是 UnaryOp]
UnaryOp → • '-'
UnaryOp → • '!'
Number → • INT_CONST         [因为点后是 Number]

GOTO(I1, INT_CONST) = I2

Number → INT_CONST •         [归约项目]

GOTO(I1, ’+’) = I3

UnaryOp → '+' •              [归约项目]

GOTO(I1, ’-’) = I4

UnaryOp → '-' •              [归约项目]

GOTO(I1, ’!’) = I5

UnaryOp → '!' •              [归约项目]

GOTO(I1, ’(’) = I6

核心: PrimaryExp → '(' • Exp ')'

CLOSURE(I6):
PrimaryExp → '(' • Exp ')'
Exp → • UnaryExp
UnaryExp → • PrimaryExp
UnaryExp → • UnaryOp UnaryExp
PrimaryExp → • '(' Exp ')'
PrimaryExp → • Number
UnaryOp → • '+'
UnaryOp → • '-'
UnaryOp → • '!'
Number → • INT_CONST

这里还有很多状态,这里不多做解释.

GOTO(I1, Number) = I7

PrimaryExp → Number •        [归约项目]

GOTO(I1, PrimaryExp) = I8

UnaryExp → PrimaryExp •      [归约项目]

GOTO(I1, UnaryOp) = I9

核心: UnaryExp → UnaryOp • UnaryExp

CLOSURE(I9):
UnaryExp → UnaryOp • UnaryExp
UnaryExp → • PrimaryExp
UnaryExp → • UnaryOp UnaryExp
PrimaryExp → • '(' Exp ')'
PrimaryExp → • Number
UnaryOp → • '+'
UnaryOp → • '-'
UnaryOp → • '!'
Number → • INT_CONST

这里也还有很多状态,不过不再多做解释.

GOTO(I1, UnaryExp) = I10

Exp → UnaryExp •             [归约项目]

GOTO(I1, Exp) = I11

Stmt → RETURN Exp • ';'

GOTO(I11, ’;’) = I12

Stmt → RETURN Exp ';' •      [归约项目]

GOTO(I0, Stmt) = I13

S' → Stmt •                  [接受项目]

第二步：构造分析表

ACTION 表

状态	RETURN	INT_CONST	’+'	'-'	'!'	'('	')'	';‘	$
I0	s1
I1		s2	s3	s4	s5	s6
I2			r10	r10	r10		r10	r10	r10
I3			r7	r7	r7		r7	r7	r7
I4			r8	r8	r8		r8	r8	r8
I5			r9	r9	r9		r9	r9	r9
I6		s2	s3	s4	s5	s6
I7			r6	r6	r6		r6	r6	r6
I8							r3	r3	r3
I9		s2	s3	s4	s5	s6
I10							r2	r2	r2
I11								s12
I12									r1
I13									acc
…		…	…	…	…	…	…	…	…

GOTO 表

状态	Stmt	Exp	UnaryExp	PrimaryExp	UnaryOp	Number
I0	13
I1		11	10	8	9	7
I6		14	15	16	17	18
I9			19	8	9	7

s = shift（移入）
r = reduce（归约，数字表示产生式编号）
acc = accept（接受）

现在我们来看看一个具体的示例吧.

模拟解析 return +42;

输入 Token 序列

[RETURN, '+', INT_CONST(42), ';', $]

详细的 Shift/Reduce 过程

步骤	栈	状态栈	输入	查表	动作	说明
1	[]	[I0]	RETURN +42;$	ACTION[I0][RETURN] = s1	shift 1	移入 RETURN，转到状态 I1
2	[RETURN]	[I0,I1]	+42;$	ACTION[I1][+] = s3	shift 3	移入 +，转到状态 I3
3	[RETURN,+]	[I0,I1,I3]	42;$	ACTION[I3][INT_CONST] = r7	reduce 7	用规则 7：UnaryOp → ’+’ 归约

归约过程详解（步骤 3）：

1. 规则 7：UnaryOp → '+' 需要弹出 1 个符号
2. 弹出：栈变成 [RETURN]，状态栈变成 [I0,I1]
3. 压入 UnaryOp：栈变成 [RETURN, UnaryOp]
4. 查 GOTO[I1][UnaryOp] = 9：状态栈变成 [I0,I1,I9]

步骤	栈	状态栈	输入	查表	动作	说明
4	[RETURN,UnaryOp]	[I0,I1,I9]	42;$	ACTION[I9][INT_CONST] = s2	shift 2	移入 42，转到状态 I2
5	[RETURN,UnaryOp,42]	[I0,I1,I9,I2]	;$	ACTION[I2][;] = r10	reduce 10	用规则 10：Number → INT_CONST 归约

归约过程详解（步骤 5）：

1. 规则 10：Number → INT_CONST 需要弹出 1 个符号  
2. 弹出：栈变成 [RETURN,UnaryOp]，状态栈变成 [I0,I1,I9]
3. 压入 Number：栈变成 [RETURN,UnaryOp,Number]
4. 查 GOTO[I9][Number] = 7：状态栈变成 [I0,I1,I9,I7]

步骤	栈	状态栈	输入	查表	动作	说明
6	[RETURN,UnaryOp,Number]	[I0,I1,I9,I7]	;$	ACTION[I7][;] = r6	reduce 6	用规则 6：PrimaryExp → Number 归约
7	[RETURN,UnaryOp,PrimaryExp]	[I0,I1,I9,I8]	;$	ACTION[I8][;] = r3	reduce 3	用规则 3：UnaryExp → PrimaryExp 归约
8	[RETURN,UnaryOp,UnaryExp]	[I0,I1,I9,I19]	;$	ACTION[I19][;] = r4	reduce 4	用规则 4：UnaryExp → UnaryOp UnaryExp 归约

归约过程详解（步骤 8）：

1. 规则 4：UnaryExp → UnaryOp UnaryExp 需要弹出 2 个符号
2. 弹出：栈变成 [RETURN]，状态栈变成 [I0,I1]  
3. 压入 UnaryExp：栈变成 [RETURN,UnaryExp]
4. 查 GOTO[I1][UnaryExp] = 10：状态栈变成 [I0,I1,I10]

步骤	栈	状态栈	输入	查表	动作	说明
9	[RETURN,UnaryExp]	[I0,I1,I10]	;$	ACTION[I10][;] = r2	reduce 2	用规则 2：Exp → UnaryExp 归约
10	[RETURN,Exp]	[I0,I1,I11]	;$	ACTION[I11][;] = s12	shift 12	移入 ;，转到状态 I12
11	[RETURN,Exp,;]	[I0,I1,I11,I12]	$	ACTION[I12][$] = r1	reduce 1	用规则 1：Stmt → RETURN Exp ’;’ 归约

归约过程详解（步骤 11）：

1. 规则 1：Stmt → RETURN Exp ';' 需要弹出 3 个符号
2. 弹出：栈变成 []，状态栈变成 [I0]
3. 压入 Stmt：栈变成 [Stmt]  
4. 查 GOTO[I0][Stmt] = 13：状态栈变成 [I0,I13]

步骤	栈	状态栈	输入	查表	动作	说明
12	[Stmt]	[I0,I13]	$	ACTION[I13][$] = acc	accept	解析成功！

编译器,真神奇吧.

回到一元运算 IR 的生成. 由于我们只会在访问 Unaryexp 并且这是一个 UNARYEXP 类型 ,并且他的 unaryexp指针指向primaryexp 的时候才会生产一条指令 , 那么我得 visitUnaryExp形式会蛮复杂的.

我现在发现,我设计的这个IR ,可以非常方便的拓展到不同的 IR形式,不仅是Koopa IR , 只需要添加新的Dump函数就可以直接生产LLVM IR.

9-26

中间咕咕了一会,在昨天把3.1的生成koopa IR的部分通过了.

一些debug趣闻:

不要使用这种弱智写法

if(ast -> NUMBER){
    ...
}

NUMBER只是一个枚举的类型,不是成员.

不要忘记删掉断点…

To_RiscV() 的时候 Sub 操作的判断有些麻烦.

你要判断 left 和 right 的类型 ,并且如果是 Integer 形的话,还要判断其是否为 0.

大概的判断流程是这样.

SUB 操作的逻辑判断表

左操作数类型	左操作数值	右操作数类型	右操作数值	生成的 RISC-V 代码
立即数	0	立即数	0	`sub t?, x0, x0`
立即数	0	立即数	非0	`li t_temp, 右值; sub t?, x0, t_temp`
立即数	0	寄存器	-	`sub t?, x0, 右寄存器`
立即数	非0	立即数	0	`li t?, 左值; sub t?, t?, x0`
立即数	非0	立即数	非0	`li t?, 左值; li t_temp, 右值; sub t?, t?, t_temp`
立即数	非0	寄存器	-	`li t?, 左值; sub t?, t?, 右寄存器`
寄存器	-	立即数	0	`sub t?, 左寄存器, x0`
寄存器	-	立即数	非0	`li t_temp, 右值; sub t?, 左寄存器, t_temp`
寄存器	-	寄存器	-	`sub t?, 左寄存器, 右寄存器`

比 koopa IR 复杂多了.

然后就是关于 EQ 操作的一些问题.

如果 EQ 操作的 left 是一个寄存器的话,要使用 mv 指令而非 li 指令.

这样就顺利的通过了 3.1 的所有测试.

9-28

Lv3.2. 算术表达式

本节增加了这些 ENBF 规则

Exp         ::= AddExp;
PrimaryExp  ::= ...;
Number      ::= ...;
UnaryExp    ::= ...;
UnaryOp     ::= ...;
MulExp      ::= UnaryExp | MulExp ("*" | "/" | "%") UnaryExp;
AddExp      ::= MulExp | AddExp ("+" | "-") MulExp;

由于上一节写sub操作花了大量的时间,列出了所有情况,而 ADD MUL DIV MOD 的 To_RiscV() 和 SUB 操作几乎一模一样,所以直接复制粘贴即可 .

不过现在就会出现一个非常大的问题了

根据koopa IR

fun @main(): i32 {
%entry:
  %0 = mul 2, 3
  %1 = add 1, %0
  ret %1
}

对应的示例的RiscV是

  li  t0, 2
  li  t1, 3
  mul t1, t0, t1
  li  t2, 1
  add t2, t1, t2

不过我目前的寄存器结果返回的策略是,将 IR 中临时变量的第一位 result_name[1] 取出来当 reg_num ,这就导致一个问题, 如果我二元操作的 left 和 right 都是立即数,那么就会有问题,像这样:

  .text
  .global main
main:
  li t0, 2
  li t0, 3
  mul t0, t0, t0
  li t1, 1
  add t1, t1, t0
  mv a0, t1
  ret

和示例RiscV不一致,这就很麻烦了,最后返回的寄存器 reg_num 和 IR 的 num 不一样.

并且RiscV的临时寄存器只有7位.

我最后使用了一种ai给的比较蠢的方法,如果左右两边是两个立即数的话,使用一个固定寄存器去存这个数就好了

比如使用 t6 去存第二次 li 操作.

那么就得到这个结果:

  .text
  .global main
main:
  li t0, 2
  li t6, 3
  mul t0, t0, t6
  li t1, 1
  add t1, t1, t0
  mv a0, t1
  ret

这样就得到了一个目前我能接受的结果,通过了19个测试,不过后续还是需要重构的,因为我想了一下,如果有100条add指令,那么我这个To_RiscV()就玩完了.

看看 LV4 的时候 maxxing 怎么说吧.

Lv3.3. 比较和逻辑表达式

本节我要完成一下内容,

Exp         ::= LOrExp;
PrimaryExp  ::= ...;
Number      ::= ...;
UnaryExp    ::= ...;
UnaryOp     ::= ...;
MulExp      ::= ...;
AddExp      ::= ...;
RelExp      ::= AddExp | RelExp ("<" | ">" | "<=" | ">=") AddExp;
EqExp       ::= RelExp | EqExp ("==" | "!=") RelExp;
LAndExp     ::= EqExp | LAndExp "&&" EqExp;
LOrExp      ::= LAndExp | LOrExp "||" LAndExp;

和上一节基本没啥区别,就是多了一些要在 lexer 里的操作.

关于逻辑与和或操作 A && B or A || B 操作我构建的IR流程是直接生成 (A ne 0) | (B ne 0) or (A ne 0) & (B ne 0) 即可，不过并没有短路优化啥的.

10-9

咕咕了好久，这几天一直在忙 linux 宣讲会的事情，搞好了 Archinstall 双系统安装的网站，以及为我而博客网站添加了许多内容.

重构了 BinaryIRValue::To_RiscV() 现在有一个更通用的表示函数

void BinaryIRValue::To_RiscV() const {
    char reg_num = result_name[1];
    reg_num = char('0' + (((reg_num)-'0') % 6));
    auto left_int = dynamic_cast<IntegerIRValue*>(left.get());
    auto right_int = dynamic_cast<IntegerIRValue*>(right.get());
    
    // 根据操作类型选择指令名称
    std::string op_name;
    switch (operation) {
        case ADD: op_name = "add"; break;
        case SUB: op_name = "sub"; break;
        case MUL: op_name = "mul"; break;
        case DIV: op_name = "div"; break;
        case MOD: op_name = "rem"; break;
        case LT:  op_name = "slt"; break;
        case GT:  op_name = "sgt"; break;
        case AND: op_name = "and"; break;
        case OR:  op_name = "or";  break;
        
        // 比较操作需要特殊处理
        case EQ:
        case NE:
        case LE:
        case GE:
            emitComparisonOp(operation, reg_num, left_int, right_int);
            return;
            
        default:
            std::cout << "  # Unknown operation" << std::endl;
            return;
    }
    
    // 统一处理算术和逻辑运算
    emitBinaryOp(op_name, reg_num, left_int, right_int);
}

然后再根据立即数与寄存器的 4 种排列方式写 4 个 Dump 函数，还可以给一些特定运算进行优化。

testcase 27 会出现超过 6 条语句，那么我们 RiscV 的六个临时寄存器肯定是不够用的，将regnum的策略改成 mod 6 就可以临时解决了，不过等后面还是要写更现代的图着色寄存器分配的。

这样就把 LV3 的内容全部完成了。

Lv4. 常量与变量

Lv4.1. 常量

强度要上来了，本章要完成这些内容

CompUnit      ::= FuncDef;

Decl          ::= ConstDecl | VarDecl;
ConstDecl     ::= "const" BType ConstDef {"," ConstDef} ";";
BType         ::= "int";
ConstDef      ::= IDENT "=" ConstInitVal;
ConstInitVal  ::= ConstExp;
VarDecl       ::= BType VarDef {"," VarDef} ";";
VarDef        ::= IDENT | IDENT "=" InitVal;
InitVal       ::= Exp;

FuncDef       ::= FuncType IDENT "(" ")" Block;
FuncType      ::= "int";

Block         ::= "{" {BlockItem} "}";
BlockItem     ::= Decl | Stmt;
Stmt          ::= LVal "=" Exp ";"
                | "return" Exp ";";

Exp           ::= LOrExp;
LVal          ::= IDENT;
PrimaryExp    ::= "(" Exp ")" | LVal | Number;
Number        ::= INT_CONST;
UnaryExp      ::= PrimaryExp | UnaryOp UnaryExp;
UnaryOp       ::= "+" | "-" | "!";
MulExp        ::= UnaryExp | MulExp ("*" | "/" | "%") UnaryExp;
AddExp        ::= MulExp | AddExp ("+" | "-") MulExp;
RelExp        ::= AddExp | RelExp ("<" | ">" | "<=" | ">=") AddExp;
EqExp         ::= RelExp | EqExp ("==" | "!=") RelExp;
LAndExp       ::= EqExp | LAndExp "&&" EqExp;
LOrExp        ::= LAndExp | LOrExp "||" LAndExp;
ConstExp      ::= Exp;

新加了很多内容。

Thanks for reading!

编译学习笔记

周三 9月 10 2025

7959 字 · 41 分钟

tech 编译器 compliers 学习笔记

状态	RETURN	INT_CONST	’+'	'-'	'!'	'('	')'	';‘	$
I0	s1
I1		s2	s3	s4	s5	s6
I2			r10	r10	r10		r10	r10	r10
I3			r7	r7	r7		r7	r7	r7
I4			r8	r8	r8		r8	r8	r8
I5			r9	r9	r9		r9	r9	r9
I6		s2	s3	s4	s5	s6
I7			r6	r6	r6		r6	r6	r6
I8							r3	r3	r3
I9		s2	s3	s4	s5	s6
I10							r2	r2	r2
I11								s12
I12									r1
I13									acc
…		…	…	…	…	…	…	…	…

状态	RETURN	INT_CONST	’+'	'-'	'!'	'('	')'	';‘	$
I0	s1
I1		s2	s3	s4	s5	s6
I2			r10	r10	r10		r10	r10	r10
I3			r7	r7	r7		r7	r7	r7
I4			r8	r8	r8		r8	r8	r8
I5			r9	r9	r9		r9	r9	r9
I6		s2	s3	s4	s5	s6
I7			r6	r6	r6		r6	r6	r6
I8							r3	r3	r3
I9		s2	s3	s4	s5	s6
I10							r2	r2	r2
I11								s12
I12									r1
I13									acc
…		…	…	…	…	…	…	…	…

状态	RETURN	INT_CONST	’+'	'-'	'!'	'('	')'	';‘	$
I0	s1
I1		s2	s3	s4	s5	s6
I2			r10	r10	r10		r10	r10	r10
I3			r7	r7	r7		r7	r7	r7
I4			r8	r8	r8		r8	r8	r8
I5			r9	r9	r9		r9	r9	r9
I6		s2	s3	s4	s5	s6
I7			r6	r6	r6		r6	r6	r6
I8							r3	r3	r3
I9		s2	s3	s4	s5	s6
I10							r2	r2	r2
I11								s12
I12									r1
I13									acc
…		…	…	…	…	…	…	…	…