前言

本篇博客主要记录我学习 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;

新加了很多内容。

10-23

我又回来做编译了，刚打完 ASC 校赛

其中很有意思的是关于带有大括号的语法，比如

Block ::= '{' {BlockItem} '}'

这种 ENBF 的语法分析该如何实现呢？

在 LR PARSER 中可以使用递归的 bison 规则，比如这样

%ast_val Block BlockItems BlockItem

Block
  : BlockItems{
    ...
  }

BlockItems
  : BlockItem {
    ...
  }
  | BlockItems BlockItem{
    ...
  }
  ;

当在符号栈中第一次匹配到 BlockItem 时，通过查表 reduce 出一个 BlockItems，此时再 shift 进一个 BlockItem 时，符号栈中有 BlockItems 和 BlockItem ，通过查表 reduce 出一个新的 BlockItems 列表，以此类推。

感觉这种方式在 LR PARSER 里比较容易实现，在 LL PARSER 里可能需要一些额外的操作.

10-24

把 AST 定义与 parser 规则定义好了。

由于现在语法规则越来越复杂，现在需要添加一个词法分析的阶段，即要添加一个符号表.

但是完全不知道符号表怎么写呢.

10-27

现在需要完成一个符号表，我已经把初步的 symbol 定义写好了，对于每一个 symbol ，他是一个 name , type , datatype , scope_level ,以及其本身 value 的类，其中 type 用来区分其是常量，变量，还是函数 , scope_level 用来表示生命周期（为后文做铺垫） .

另外，重构了 IRGenerator 中的 current_block 访问形式，之前是以函数的参数传递形式访问的，但是这样非常的重复冗余，所以现在设计一个上下文相关的类

struct GenContext
{
    IRBasicBlock* current_block;
    SymbolTable* symbol_table;
    IRProgram* program;
};

用来提供 block table 和 program 统一的访问接口,这样就不用在函数参数里加一堆 IRBasicblock* current_block 以及符号表了，好看多了。

发现现在的 Generator 机制并没有完成对多个 block 的处理。这个以后要处理一下。

10-28

要备赛 ASC26 了，编译进度放缓。

11-10

又写了一会编译器，最近的代码时间实在是太少了，从下周开始要多写一些代码了。

符号表借鉴 ai 的写法增添了很多 rubustness 。现在可以很方便的用 enterScope() 进入新作用域 exitScope() 退出作用域。

用 declare() 去声明一个符号，用 lookup() 去查询一个符号。

目前相当于第四章和第五章一块写了，因为这个作用域我觉得要先写了。现在大概可以明晰符号表的工作周期了

在生成 program 的时候创建了符号表，当进入 / 离开 block 的时候，进行作用域的管理。

符号表是一个 map 的 vector ，每一张 map 代表一个作用域，这样就可以方便的管理同一个作用域下的 symbol 了。

其实我想了一下，一张 map 也可以管理多个作用域下的 symbol ，就是在 symbol 的属性里加入 scope 这一属性就行，但是问题就是，这样代码复杂性会高很多，并且如果要 exitScope() 的话需要遍历所有的 symbol ，这样时间复杂度会高很多，不过他的内存消耗会少很多。

问了 AI ，GCC 和 LLVM 都是使用的第一种方案，即使用多个 vector<map> 来存符号表。

现在符号表搞好了，还需要干一些事情，就是在 visitConstDef() 的时候，要把常量折叠了。再存进符号表里面，等后面用到 LVal 的时候再把这个加入到 IR 中 block 的 value 列表里面。

其实半个小时就能干很多事情了。

最近有些急躁了，没干啥正事，需要矫正一下了。

今天还是 11 月 10 日

现在把 4.1 写完了， koopa IR 和 RiscV 都过了。

我把常量折叠搞完了。这样的话关于可能新增的 IRvalue 也就只有 LVAl 相关的东西了，然后会被替换成立即数，所以说 KoopaIR 和 RiscV 并没有需要新增的东西。

然后就是一些 bug 和坑。

可以在 Flex & Bison 中开启调试模式来增加额外的信息。

遇到 Bison 的 syntax error 需要系统地调试。

🔍 关于调试

方法 1：启用 Bison 调试模式

修改你的 sysy.y 文件：

%{
#include <iostream>
#include <memory>
#include <string>
#include "include/ast.h"

int yylex();
void yyerror(std::unique_ptr<BaseAST> &ast, const char *s);

using namespace std;
%}

// ✅ 添加这行：启用详细错误信息
%define parse.error verbose

// ✅ 添加这行：启用调试追踪
%define parse.trace

%parse-param { std::unique_ptr<BaseAST> &ast }

方法 2：在 main.cpp 中启用调试

#include <iostream>
#include <memory>
#include "include/ast.h"
#include "include/Ir_generator.h"

using namespace std;

// ✅ 声明外部调试变量
extern int yydebug;
extern FILE* yyin;
extern int yyparse(unique_ptr<BaseAST> &ast);

int main() {
    // ✅ 启用 Bison 调试输出
    yydebug = 1;
    
    auto ast = unique_ptr<BaseAST>(nullptr);
    
    int ret = yyparse(ast);
    
    if (ret != 0) {
        cerr << "Parse failed!" << endl;
        return 1;
    }
    
    // ... 其余代码
}

方法 3：添加详细的错误处理

在 sysy.y 中修改 yyerror 函数：

%{
// ... 头文件 ...

// ✅ 声明外部变量
extern int yylineno;
extern char* yytext;
extern FILE* yyin;

void yyerror(std::unique_ptr<BaseAST> &ast, const char *s) {
    // ✅ 输出详细错误信息
    std::cerr << "Error at line " << yylineno << ": " << s << std::endl;
    std::cerr << "Near token: '" << yytext << "'" << std::endl;
}
%}

方法 4：在 Flex 中启用行号追踪

修改你的 sysy.l 文件：

/* filepath: /home/yoo/Documents/Compliers/LEARNING_Compilers/src/front/sysy.l */

%{
#include <cstdlib>
#include <string>
#include "include/ast.h"
#include "sysy.tab.hpp"

using namespace std;
%}

/* ✅ 启用行号追踪 */
%option yylineno

/* ✅ 启用调试 */
%option debug

%%

/* ... 词法规则 ... */

开启 debug 选项后，得到的信息就多了，我出现的问题原来是这个

Error at line 2: syntax error, unexpected $undefined, expecting EQ
Near token: '='

这样我就懂了。

我们期望得到一个赋值符号 = 不过我在语法规则里设置的是 EQ 也就是 == 那么就会有问题了。

总之，我最后在 main 函数里面写了一个 -debug 的选项，用来开始 flex 和 bison 的调试模式。

然后就是关于 Bison 的一些小知识，重新学习了一下，以下内容可以定义 token 的优先级，越往下优先级越高。

%left '='
%left LOR
%left LAND
%left EQ NE
%left LT LE GT GE
%left '+' '-' 
%left '*' '/' '%'

汇总一下这一节做完的事情：

添加了常量相关的 AST 以及 lexer, parser 规则。
添加了常量折叠函数。
添加了符号表
- 并且有作用域管理

Lv4.2. 变量

我让 gemini 写了一篇关于介绍 AI 编译器的文章，之前一直不太了解 AI 编译器，现在对这个有一些了解了，link↗

11.25

在变量这一小节，我们需要实现以下 EBNF

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

...

Block         ::= ...;
BlockItem     ::= ...;
Stmt          ::= LVal "=" Exp ";"
                | "return" Exp ";";

总的来说，要完成变量相关的三种新 IR (alloc store load) 的编写，以及相关联的符号表内容。

照着常量的定义写完了新的 AST 定义以及 parser 规则的编写

一个我常出现的bug

/usr/bin/ld: CMakeFiles/compiler.dir/src/backend/Ir_generator.cpp.o: in function `IRGenerator::visitDecl(DeclAST const*)':
/root/compiler/src/backend/Ir_generator.cpp:118: undefined reference to `typeinfo for VarDeclAST'
/usr/bin/ld: CMakeFiles/compiler.dir/src/backend/Ir_generator.cpp.o: in function `IRGenerator::visitVarDecl(VarDeclAST const*)':
/root/compiler/src/backend/Ir_generator.cpp:258: undefined reference to `typeinfo for VarDefsAST'

链接出现问题，这是在头文件中申明了函数但是最后没有在 .cpp 文件定义的问题。补上声明就行。

我在中途犯了一个愚蠢的问题，我试图将变量的 InitVal 进行常量折叠，忘记了有的变量在程序运行时候才会被赋值，不过类似

int x = 10;

这样的变量申明，后续有优化，名字叫 常量传播

还没写 IR 和 RiscV 的 Dump 函数，不过已经能额外多过一个测试点了.

给买了哈基米1年的号，用了用那个动态视图模式，这个确实初看上去非常惊艳，但是用了一会发现了问题，前端不够精细，会有不美观的地方，一次性生成的内容量较少。

再者就是使用 nano banana pro 的体验，非常良好，我让他生成了一副魂魄妖梦的连环画，我给他的 prompt 是

然后他输出了一些关于生图的 tag,我转手再问了他一次。他给出的连环画是这样的

我只能说，给 🍌 👴 👻 了.

今天先到此为止吧.

11-26

搞完了 IR 的 Dump()

把之前的有些内容忘记了，以为我自己写错了 IRGenerator 里的 VisitVarDef store 相关的内容

if(auto initval = dynamic_cast<InitValAST*>(ast->initval.get())){
    if(auto exp = dynamic_cast<ExpAST*>(initval ->exp.get())){
        auto var_value = visitExp(exp);
        auto store = std::make_unique<StoreIRValue>(std::move(var_value),var_name);

        ctx.current_block->ADD_Value(std::move(store));
    }
}

关于 StoreIRValue 的第一个参数，现在是一个 TemporaryIRValue ，我忘记 visitEXP() 的时候就会把赋值内容里的 Value 添加到 Block 里了。

实际上这段代码没问题 ()

然后就是 To_RiscV() 的内容了

这部分比较复杂，涉及到了函数，变量的栈帧，我需要设计一个 StackFrameManager 类，来管理栈帧，为了知道每一条和内存相关的 IRValue 所产生的 offset 我们需要遍历一个 Functino 两次，第一次计算 offset 第二次再正常的 To_RiscV .

在这个 StackFrameManager 里面，得有一张 map 来映射每个变量和其 offset 这样在第二次 Dump() 的时候，编译器才知道要移动几位.

然后我打算将这个 stack 添加到之前的 GenContext 里面，然后再添加一个全局的访问点，也就是类的静态成员，这样就可以全局访问一个 stack 了.

然后我们在这个栈上计算 offset 存在表里，当我们下一次访问到一个 TemporaryIRValue 类型的变量时，直接查表，然后使用 lw 指令就能把栈上的那一块对应区域加载到寄存器里了。

lw 寄存器1, 偏移量(寄存器2) 的含义是将寄存器2 的值和偏移量相加作为内存地址, 然后从内存中读取一个 32 位的数据放到寄存器1 中.

sw 寄存器1, 偏移量(寄存器2) 的含义是将寄存器2 的值和偏移量相加作为内存地址, 将寄存器1 中的值存入到内存地址对应的 32 位内存空间中.

lw/sw 中偏移量的范围和 addi 一致.

AI 帮我把之前的寄存器分配的屎山删除了，以前在进行愚蠢的 IR 符号到临时寄存器的映射非常的好笑，现在的寄存器分配策略正如文档中说的，不分配寄存器，全部存在栈上面。

现在的 BinaryIRValue 变的清爽很多了。直接判断左右 value 的类型，然后加载到t0 t1 寄存器，最后把结果存在 t0 就行了，所以全程只用两个寄存器。

也是通过了 To_RiscV()

Lv5. 语句块和作用域

因为之前写了符号表的 enter_scope() 和 exit_scope() 所以说语义分析部分不需要重新写了。

仅需要在语法分析添加新的 stmt 的 ebnf 语句即可。然后IR 的话都是之前的，比较方便。

这样可以通过 3 个测试点。

EBNF 里没有讲 { } 这样也是一个 block ，将其添加到语法规则后过了 5 个测试点。

然后就是不同作用域的同名变量的问题了。这在语法中是允许的，但是当生成IR 的时候，IR 的 NAME 不能有重复的名称。比如

int main(){
  int a;
  {
    int a;
    {
      int a;
    }
  }
}

这样的，按之前的逻辑生成的IR 就会出现问题。

解决方案是在符号表里添加一个新的 ir_name 选项即可，再利用一个 map 去计数，给 ir_name 添加数字，比如上面的 ir_name 分别是 @a, @a_1, @a_2 .

这样就没啥问题了，进入下一章

Lv6. if 语句

alt text

Thanks for reading!

编译学习笔记

周三 9月 10 2025 Pin

11248 字 · 56 分钟

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
…		…	…	…	…	…	…	…	…