PKU 编译原理课程整理

注意

本文内容不完整，且原作者已停止更新。

一、前情提要

本教程采用纯C语言实现编译器，所有代码示例均使用标准C语言语法。对于需要面向对象特性的部分，我们使用函数指针和结构体来模拟。

1. 编译基本上是将高级语言（也称源程序）转化为可执行文件的过程。转化过程并非一步到位，需要一个中间表示。【这里的“编译”是泛指，包括了预处理等步骤，仅作理解意】

2. 这里使用的高级语言为 SysY，可以看作是精简版的 C

3. Koopa IR 是需要生成的中间表示。

4. libkoopa、koopac 分别负责生成 Koopa IR 和将 Koopa IR 转为 RISC‑V

5. sysy-runtime-lib 程序运行时提供支持的库函数（存放一些例如 printf 函数的机器实现）

6. “编译”的全过程

预处理 (Preprocessing)：处理源代码中以“#”开头的指令，例如将 #include 的头文件内容包含进来，展开宏定义 (#define) 等。

编译 (Compilation)：这是核心步骤，编译器将经过预处理的源代码翻译成汇编代码。汇编语言是一种低级的、更接近机器指令的语言。

汇编 (Assembly)：汇编器将汇编代码转换成机器可以执行的二进制指令，生成目标文件 (object file)。

链接 (Linking)：链接器 (linker) 将一个或多个目标文件以及程序所需的库文件（比如C语言的标准库函数）连接起来，最终生成一个单一的可执行文件。

二、需要做什么？

用C语言实现一个简易编译器（当然你也可以选择其它语言），仅实现“将源代码翻译为汇编代码”这一步骤。

也就是将输入的 SysY 源代码，编译到 RISC-V 汇编。在这种意义之下，编译器通常由以下几个部分组成：

• 前端：检查代码的拼写、语法和逻辑问题，然后将其转化成计算机容易理解的结构化大纲。

• 中端：提炼代码逻辑，对代码本身逻辑进行优化

• 后端：针对不同的硬件平台，如x86、arm进行优化

三、前端、中端、后端的处理流程？

【前端】

1. 词法分析

   • 词法分析器 lexer 将文件的内容拆分成一个个单词作为输出流，传递给语法分析器 parser。这个过程叫作 token 切分。 lexer 生成的 token 会包含一些信息，用来让 parser 区分每个 token 的种类，以及在必要时获取 token 的内容。

     int main() { int x; x = 3; return x; }

     int main ( ) { int x ; x = 3 ; return x ; }

2. 语法分析

   • 按照程序的语法规则， 将输入的 token 流变成程序的 AST（抽象语法树），即一张能够反映代码层次、逻辑的树状结构图，方便进行下一步处理。

3. 语义分析

如果你写的不是代码，而是英语作文，语法分析负责检查单词有没有拼错、句子结构（主谓宾）对不对。而语义分析，则是检查你的作文内容上有没有逻辑错误。

比如，你写了一句语法正确的话：

"The rock is pregnant."

这显然是不合逻辑的。如果以代码来表述，就像下面这段程序，在同一个函数内同时声明了两个相同的变量：语法上没有问题，但逻辑是冲突的。

int main() {
  int a = 1;
  int a = 2;
  return 0;
}

接下来展示如何实现逻辑检查

• 建立符号表 相当于为函数里的每个变量建立“户口本”。方便查找变量重定义错误和引用未定义变量等错误。
• 类型检查 检查是否有诸如“拿字符串乘以一个数字”的错误。当然还有类似于对一个类型进行不符合其类型的操作，譬如“int a =1; a[0] = 3;”就是对整型变量进行数组的取值操作。
• 【类型推断】 在某些编程语言中，如C++和Rust，即使你不明确说 a 是什么类型，编译器也能根据 a = "hello" 这样的代码，自己推断出 a 应该是字符串类型。这里不涉及。
• 提前计算必要的数据 比如代码里写了 const int ARRAY_SIZE = 10 + 20; 编译器在分析时就会直接算成 30。优化运行效率。

【中端】

AST 还是过于高级了，一步到位翻译成汇编仍然有些困难。比如 AST 中仍然存在一些 for 循环、条件判断等，很难直接翻译成汇编。需要继续生成一种中间表示，也就是开头提到的 Koopa IR，将 AST 中的这些复杂指令拆分。

为什么需要中间表示？

其实中间层的存在还是为了解决开发成本问题。世界上有很多编程语言（比如 C++, Rust, Swift），想让它们在 Intel x86, Apple ARM, RISC-V 等不同架构、不同指令集上运行。如果为每一种语言和每一种芯片的组合都开发一个专门转换工具，工作量就太大了。现在，这些不同编程语言生成相同规范的中间层，问题就少了很多。相当于原本需要开发 M * N 个转换工具，现在只需要 M + N 个。

还有个好处是前后端解耦，方便定位 bug。

以下是一个 Koopa IR 的示例

decl @getint(): i32       // 声明外部函数，这个函数不接收任何参数，返回32位整数

fun @main(): i32 {        // 定义一个返回 i32 类型的 main 函数
%entry:
  @x = call @getint()     // 调用 getint 函数，结果存到临时变量 @x
  %cond = lt @x, 10       // 比较 @x 是否小于 10，结果(true/false)存到 %cond
  br %cond, %then, %else  // 根据 %cond 的值，跳转到 %then 或 %else 代码块

%then:
  %0 = add %x, 1          // @x 加 1，结果存到临时变量 %0
  jump %end(%0)           // 跳转到 %end 代码块，并把 %0 作为结果

%else:
  %1 = mul %x, 4          // @x 乘 4，结果存到临时变量 %1
  jump %end(%1)           // 跳转到 %end 代码块，并把 %1 作为结果

%end(%result: i32):
  ret %result             // 返回从 %then 或 %else 传来的结果
}

【后端】

编译器进行的最后一步操作，就是将 IR 转换为目标代码，也就是目标指令系统的汇编代码。通常情况下，这一步通常要做以下几件事：

1. 指令选择 例如 IR 中有一条指令 lt，意思是“比较 A 是否小于 B”。 RISC-V 指令集内，有好几个工具都能完成这个比较任务。

   • slt ：专门用来比较两个寄存器里的值。
   • slti ：专门用来比较一个寄存器的值和一个立即数（固定的数字）。 所谓指令选择，就是根据不同的场景选择合适的工具
   • 如果 IR 是 lt @x, @y（比较两个变量），选择 slt 工具。
   • 如果 IR 是 lt @x, 10（比较一个变量和一个常数），选择 slti 工具。而不是将 10 存入寄存器，再调用 slt。

2. 寄存器分配 对于 IR 中需要经常使用的变量，存放在 CPU 寄存器中，这样读取速度会更快。 而对于不经常使用的变量，将其放入内存，因为 CPU 寄存器的大小有限。

3. 指令调度 在不改变程序逻辑的前提下通过重新排列指令的执行顺序，来更好地适应 CPU 的内部工作流水线，减少因数据依赖、内存访问等造成的停顿等待，从而提升性能。

提示

课程实践中实现的编译器并不会涉及这么多步骤，只需要重点关注第一部分。

四、前端实现初见

前情提要

EBNF（扩展巴科斯范式）是一种可以用来描述编程语言的语法。如果我们拥有某个 SysY 程序的扩展巴科斯范式，可以反推其源码实现。下面讲述推导过程：

int main() {
  // 这是一条注释
  return 0;
}

CompUnit  ::= FuncDef;

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

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

可以看出 EBNF 由若干条形如 A ::= B; 的形式构成。它的含义是：当遇到一个 A 时, 可以把 A 代换成 B。这种能被代换成其它符号的，称非终结符。

注意还有一条特殊的规则：IDENT 、INT_CONST 这种以全大写字母命名的，和用"" 括起来的，不能被代换。这种不能被代换成其它符号的，我们称终结符。

一通代换后，就可以变成这样：

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

是不是很接近上面提到的 token 切分了？

int main ( ) { return 0 ; }

IDENT 、INT_CONST 实际上表示 token 的属性。

IDENT 是 Identifier，即标识符的缩写，代表了所有由程序员命名的东西，比如变量名、函数名等。在 token 中的 main（函数名），它的属性就是标识符。

INT_CONST 是 Integer Constant，即整型常量的缩写。在 token 中的 0，它的属性就是标识符。

由此可以总结出，一个 token 不仅仅包括它的“值”本身，还包含了它的属性。词法分析的第一步是 token 切分。完成切分后，这些 token 还会转化成终结符的形式，作为最终的输出流，而不是以 main、0等字符形式。因为在下一步的语法检查中，分析器不需要在乎这些 token 的值，更需要关注它们的属性。

这正好对应第三节提到的：

lexer（词法分析器）生成的 token 会包含一些信息，用来让 parser（语法分析器）区分每个 token 的种类【属性】，以及在必要时获取 token 的内容【值】。

如何实现？

为了降低难度，可以直接配置现成的工具，直接生成个性化的 Lexer 和 Parser

提示

Flex 用于生成词法分析器 (Lexer)

它的功能是读取源代码文本，并将其分解成一个个有意义的最小单元，即终结符，也称为 Token。

需要在一个 .l 文件 (如 sysy.l) 中，使用正则表达式来定义各种 Token 的模式。例如，定义什么是标识符 ([a-zA-Z_][a-zA-Z0-9_]*)、什么是数字、什么是关键字 ("int") 等。Flex 会根据这些规则生成一个 C/C++ 函数（名为 yylex），这个函数能够识别并返回这些 Token。

提示

Bison 用于生成语法分析器 (Parser)

它的功能是接收由 Flex 生成的 Token 序列，并根据你定义的语法规则来判断这个序列的组合是否合法。如果合法，它就能构建出程序的语法结构，通常是一棵抽象语法树 (AST)。

需要在 .y 文件 (如 sysy.y) 中，使用类似 EBNF 的格式来描述语言的语法。例如，定义一个函数由“返回类型、函数名、括号和函数体”组成 (FuncDef ::= FuncType IDENT '(' ')' Block;)。Bison 会根据这些规则生成一个 C/C++ 函数（名为 yyparse），这个函数通过调用 yylex 来获取 Token，并进行语法匹配。

编写完成后执行 make 命令，CMake 会自动调用 Flex 和 Bison 将 .l 和 .y 文件转换成 .c 文件，然后通过编译链形成可执行文件，词法、语法分析器就完成了。

代码示例

以下是一个C语言版本的 lexer 配置（sysy.l）示例：

%option noyywrap
/* 设置选项。当Flex读取到文件末尾时，默认会调用一个 yywrap() 函数，询问是否还有其他文件要处理，此处禁用。*/

/* 性能优化。声明不会在代码中使用 unput() (将字符退回输入流) 和 input() (从输入流读取字符) 这两个函数，让Flex生成更小、更快的代码。*/
%option nounput
%option noinput

%{
#include <stdlib.h>
#include <string.h>
/* 标准库和字符串头文件，主要为了使用strtol【字符串转长整型数】和strdup【复制字符串】函数 */

#include "sysy.tab.h"
/* Flex必须包含的头文件，其中定义了所有Token的类型 */
%}

// 定义别名
WhiteSpace    [ \t\n\r]*              // 空白符
LineComment   "//".*                  // 行内注释
Identifier    [a-zA-Z_][a-zA-Z0-9_]*  // 标识符
Decimal       [1-9][0-9]*             // 十进制
Octal         0[0-7]*                 // 八进制
Hexadecimal   0[xX][0-9a-fA-F]+       // 十六进制

%%
/* 规则匹配和对应动作 */
{WhiteSpace}    {}  /* 执行空动作 */
{LineComment}   {}

"int"           { return INT; }  /* 返回token的类型为INT */
"return"        { return RETURN; }

{Identifier}    { yylval.str_val = strdup(yytext); return IDENT; }
/* yytext是Flex的一个全局char*变量，指向当前匹配到的字符串。
   在yylval的str_val字段中创建yytext的副本，返回IDENT这个token类型。 */

{Decimal}       { yylval.int_val = strtol(yytext, NULL, 0); return INT_CONST; }
{Octal}         { yylval.int_val = strtol(yytext, NULL, 0); return INT_CONST; }
{Hexadecimal}   { yylval.int_val = strtol(yytext, NULL, 0); return INT_CONST; }
/* 将当前匹配到的字符串转为长整型数，参数0表示自动检测进制。
   将转换后的整数值存入yylval的int_val字段，返回INT_CONST这个token类型。 */

.               { return yytext[0]; }
/* 匹配除换行符外的任意单个字符，直接返回该字符 */

之后, 我们可以在 sysy.y 中描述语法定义。

由于还没有学习如何设计和定义 AST，此处先使 parser 将接收到的信息流直接转为字符串输出作为 AST。

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 向前声明 */
int yylex(void);
void yyerror(char **ast, const char *s);
%}

/* 为生成的yyparse函数添加一个参数
   yyparse函数修改传入的char*指针， 返回生成的字符串（AST） */
%parse-param { char **ast }

/* 定义了一个名为 yylval 的联合体，用于在Flex和Bison之间传递Token的附加值。 */
%union {
  char *str_val; /* 当Token是一个标识符时，它的值（字符串）会存放在这个字段里。 */
  int int_val;   /* 当Token是一个整型常量时，它的值（整数）会存放在这个字段里。 */
}

/* 声明所有的终结符 */
%token INT RETURN
%token <str_val> IDENT  /* 说明其附加值对应%union的str_val字段 */
%token <int_val> INT_CONST

/* 声明所有的非终结符 */
%type <str_val> FuncDef FuncType Block Stmt Number  /* 这些非终结符的返回类型都为字符串 */

%%
/* 语法规则及动作
   $$ 代表当前规则左侧非终结符的返回值。
   $1, $2, ... 代表当前规则右侧第 N 个符号的值。 */

/* 定义一个编译单元的结构 */
CompUnit
  : FuncDef {
    *ast = $1; /* $1 是 FuncDef 返回的 char* */
  }
  ;

/* 定义一个函数的结构：一个函数类型，跟着一个标识符，最后是一个代码块 */
FuncDef
  : FuncType IDENT '(' ')' Block {
  
    /* 1. 计算字符串拼接后的总长度 (包括空格, "()", 和结尾的 '\0')
       $1=type, $2=ident, $5=block */
    size_t len = strlen($1) + 1 + strlen($2) + 2 + 1 + strlen($5) + 1;
  
    /* 2. 根据长度分配足够的内存 */
    char *result = (char *)malloc(len);
   
    /* 3. 将子规则返回的字符串拼接成一个新的字符串，存入 result */
    sprintf(result, "%s %s() %s", $1, $2, $5);
    
    /* 4. 将新生成的字符串作为返回值 */
    $$ = result;
   
    /* 5. 释放内存 */
    free($1);
    free($2);
    free($5);
  }
  ;

/* 定义函数类型
   FuncType ::= INT; */
FuncType
  : INT {
    $$ = strdup("int");
  }
  ;

/* 定义代码块：由大括号包围语句构成
   Block ::= '{' Stmt '}'; */
Block
  : '{' Stmt '}' {
    /* 类似 FuncDef 的处理 */
    size_t len = strlen($2) + 4 + 1; /* for "{ ", " }", and '\0' */
    char *result = (char *)malloc(len);
    sprintf(result, "{ %s }", $2);
    $$ = result;
    free($2);
  }
  ;

/* 定义语句：由RETURN关键字、一个数字和一个分号构成
   Stmt ::= RETURN Number ';'; */
Stmt
  : RETURN Number ';' {
   /* 逻辑同上，拼接成return...的形式 */
    size_t len = strlen("return ") + strlen($2) + 1 + 1; /* for ";" and '\0' */
    char *result = (char *)malloc(len);
    sprintf(result, "return %s;", $2);
    $$ = result;
    free($2);
  }
  ;

/* 定义数字为整形常量
   Number ::= INT_CONST; */
Number
  : INT_CONST {
    /* 需要将整数转换为字符串 */
    char buffer[50]; /* 足够存放一个整数的字符串形式 */
    sprintf(buffer, "%d", $1);
    $$ = strdup(buffer); /* 复制 buffer 中的内容到堆上 */
  }
  ;

%%

/* 定义错误处理函数
   使用 C 标准库的 stderr 输出错误信息 */
void yyerror(char **ast, const char *s) {
  fprintf(stderr, "error: %s\n", s);
}

配置好了 lexer 和 praser后，需要一个主函数来调用它们处理输入文本

下面提供一个C语言版本的主函数：

#include <assert.h>  /* 断言库，用于终止程序 */
#include <stdio.h>   /* 文件操作和输出 */
#include <stdlib.h>  /* 内存管理 */

extern FILE *yyin;   /* Flex生成的全局指针，用于指向输入文本 */
extern int yyparse(char **ast);  /* Bison生成的全局指针，用于指向解析结果 */

int main(int argc, const char *argv[]) {
/* ./compiler -koopa ../test/hello.c -o hello.koopa */
  assert(argc == 5);  /* 检查命令行参数必须为5 */
  const char *mode = argv[1];  /* 参数1: 模式参数 -koopa */
  const char *input = argv[2]; /* 参数2: 输入文件 */
  const char *output = argv[4];/* 输出文件 */
 
  yyin = fopen(input, "r");  /* 打开输入文件 */
  assert(yyin);  /* 断言用于检测打开有效性，失败则终止 */

  char *ast = NULL;
  int ret = yyparse(&ast);  /* yyparse解析成功返回0 */
  assert(!ret);

  printf("%s\n", ast);
  
  if (ast) {
    free(ast);
  }
  
  return 0;
}

五、AST 设计

在 Lv1.2 中，实现了一个能够调用 lexer 和 praser 的简单编译器，但其本质上只是一个“文本还原器”，无法将输入的 token 流变成程序的 AST（抽象语法树）。Lv1.3开始，将实现自主设计并生成 AST。

源文档中使用了一些 OOP 的思想来设计 AST。但由于本教程使用C语言开发，所以不得不使用结构体来模拟面向对象的继承关系。

为了在 C语言中实现类似面向对象的 AST 设计，我们需要设计多种节点，但每种节点的打印方式和销毁方式都不同，我们希望能用统一的方式处理它们。C语言本身不支持面向对象，所以我们用函数指针来模拟虚函数（类似Java中的抽象方法）。

/* 抽象AST基类 */
typedef struct BaseAST {
    void (*dump)(const struct BaseAST *self);    /* 打印AST */
    void (*destroy)(struct BaseAST *self);       /* 释放内存 */
} BaseAST;

/* 编译单元AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    BaseAST *func_def;      /* 包含的函数定义 */
} CompUnitAST;

/* 函数定义AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    BaseAST *func_type;     /* 函数类型 */
    char *ident;            /* 函数名 */
    BaseAST *block;         /* 函数体 */
} FuncDefAST;

/* 函数类型AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    int type;               /* 类型标识，如INT */
} FuncTypeAST;

/* 代码块AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    BaseAST *stmt;          /* 包含的语句 */
} BlockAST;

/* 语句AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    BaseAST *number;        /* 返回的数字 */
} StmtAST;

/* 数字AST */
typedef struct {
    BaseAST base;           /* 继承BaseAST */
    int value;              /* 数字值 */
} NumberAST;

/* AST构造和销毁函数示例 */

/* 创建CompUnit AST节点 */
CompUnitAST* create_comp_unit_ast(BaseAST *func_def) {
    CompUnitAST *ast = (CompUnitAST*)malloc(sizeof(CompUnitAST));
    ast->base.dump = comp_unit_dump;
    ast->base.destroy = comp_unit_destroy;
    ast->func_def = func_def;
    return ast;
}

/* CompUnit的dump函数实现 */
void comp_unit_dump(const BaseAST *self) {
    const CompUnitAST *comp_unit = (const CompUnitAST*)self;
    printf("CompUnitAST { ");
    comp_unit->func_def->dump(comp_unit->func_def);
    printf(" }");
}

/* CompUnit的destroy函数实现 */
void comp_unit_destroy(BaseAST *self) {
    CompUnitAST *comp_unit = (CompUnitAST*)self;
    if (comp_unit->func_def) {
        comp_unit->func_def->destroy(comp_unit->func_def);
    }
    free(comp_unit);
}

AST 设计完成后，根据文档内容继续设计中间表示。你可以先阅读 Lv0.2 中 Koopa IR 的语法规范。最后，遍历 AST 生成文本形式的 IR。注意：如果要通过 Lv1.5 的测试，需要添加对多行注释的支持。

生成文本形式的 IR 后，可以使用 libkoopa 的接口直接将文本形式 Koopa IR 转换为 raw program。这需要在代码中引用 libkoopa 的头文件：

#include "koopa.h"

注意

由于 koopa 库位于 docker 中，引用时出现报错是正常的。在容器内可以正常编译。或者尝试在容器内开发。

文档使用了内存流的方式完成解析流程：

AST → 内存字符串(Koopa IR文本) → libkoopa解析 → Raw Program

如果对内存流不熟悉，可以使用临时文件的方式解析：

AST → 临时文件(Koopa IR文本) → 读取文件到内存 → libkoopa解析 → Raw Program

解析完的 Raw Program 仍然是内存形式（C结构体）。libkoopa库帮我们自动完成了内存流的操作。

六、生成汇编

先前我们已经做到了将简易的C语言程序转换为内存形式的 IR，只差最后生成汇编了：遍历内存中的 Raw Program，根据函数列表输出对应的汇编代码文本。

以下是一个简单的RISC-V汇编生成示例：

void generate_assembly(const koopa_raw_program_t *program) {
    /* 输出汇编文件头 */
    printf("  .text\n");
    printf("  .globl main\n");
    
    /* 遍历所有函数 */
    for (size_t i = 0; i < program->funcs.len; ++i) {
        koopa_raw_function_t func = (koopa_raw_function_t)program->funcs.buffer[i];
        generate_function(func);
    }
}

/* 生成函数汇编 */
void generate_function(const koopa_raw_function_t func) {
    /* 输出函数标签 */
    printf("%s:\n", func->name + 1);  /* 去掉@前缀 */
    
    /* 遍历基本块 */
    for (size_t i = 0; i < func->bbs.len; ++i) {
        koopa_raw_basic_block_t bb = (koopa_raw_basic_block_t)func->bbs.buffer[i];
        generate_basic_block(bb);
    }
}

/* 生成基本块汇编 */
void generate_basic_block(const koopa_raw_basic_block_t bb) {
    /* 遍历指令 */
    for (size_t i = 0; i < bb->insts.len; ++i) {
        koopa_raw_value_t inst = (koopa_raw_value_t)bb->insts.buffer[i];
        generate_instruction(inst);
    }
}

/* 打印指令汇编 */
void generate_instruction(const koopa_raw_value_t inst) {
    switch (inst->kind.tag) {
        case KOOPA_RVT_RETURN: {
            koopa_raw_value_t ret_val = inst->kind.data.ret.value;
            if (ret_val->kind.tag == KOOPA_RVT_INTEGER) {
                /* 将返回值加载到a0寄存器 */
                printf("  li a0, %d\n", ret_val->kind.data.integer.value);
            }
            printf("  ret\n");
            break;
        }
        /* 其他指令类型的处理... */
        default:
            break;
    }
}

七、表达式处理

在前面的章节中，我们实现了一个只能处理简单常数返回的编译器。现在我们要让编译器支持表达式计算，这是编译器功能的一个重要扩展。本章将实现对各种表达式（一元、二元、括号表达式等）的支持。

语法规范扩展

相比之前只能处理 return 0; 这样的简单语句，现在我们的编译器需要处理更复杂的表达式：

int main() {
  return 1 + 2 * -3;
}

更新后的 EBNF（扩展巴科斯范式）语法规范如下：

CompUnit    ::= FuncDef;

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

Block       ::= "{" Stmt "}";
Stmt        ::= "return" Exp ";";

Exp         ::= LOrExp;
PrimaryExp  ::= "(" Exp ")" | 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;

这个语法规范体现了C语言中的运算符优先级和结合性

1. PrimaryExp：最高优先级，括号表达式和数字字面量
2. UnaryExp：一元运算符 `+`、`-`、`!`
3. MulExp：乘法、除法、取模 `*`、`/`、`%`
4. AddExp：加法、减法 `+`、`-`
5. RelExp：关系比较 `<`、`>`、`<=`、`>=`
6. EqExp：相等比较 `==`、`!=`
7. LAndExp：逻辑与 `&&`
8. LOrExp：逻辑或 `||`（最低优先级）

对应的语义规范也要实现

1. 数据类型：所有表达式的类型均为 `int` 型，计算结果为32位有符号整数
2. 逻辑运算：
   - 逻辑或 `||`：当左右操作数有任意一个非0时，结果为1，否则为0
   - 逻辑与 `&&`：当左右操作数有任意一个为0时，结果为0，否则为1
   - 逻辑非 `!`：操作数为0时结果为1，非0时结果为0
3. 算术运算：与C语言语义完全一致
4. 未定义行为：有符号整数溢出属于未定义行为（UB），编译器可以假定程序永远不会发生溢出

实现一元表达式

基于项目现有的AST结构，我们需要扩展表达式相关的AST节点：

/* 表达式节点类型枚举 */
typedef enum {
    AST_COMP_UNIT,  /* 编译单元 */
    AST_FUNC_DEF,   /* 函数定义 */
    AST_FUNC_TYPE,  /* 函数类型 */
    AST_BLOCK,      /* 代码块 */
    AST_STMT,       /* 语句 */
    AST_NUMBER,     /* 数字字面量 */
    AST_UNARY,      /* 一元表达式 */
    AST_BINARY      /* 二元表达式（为后续扩展预留）*/
} ASTNodeType;

/* 一元表达式AST节点 */
typedef struct {
    BaseAST base;
    char op;           /* 运算符：'+', '-', '!' */
    BaseAST *operand;  /* 操作数 */
} UnaryAST;

在Bison文件中，我们需要处理运算符优先级和|语法：

%type <ast_val> Exp PrimaryExp UnaryExp

%%

Stmt
  : RETURN Exp ';' {
    $$ = create_stmt_ast($2);
  }
  ;

Exp
  : UnaryExp { $$ = $1; }
  ;

PrimaryExp
  : '(' Exp ')' { 
    $$ = $2;  /* 括号表达式直接返回内部表达式 */
  }
  | Number { 
    $$ = $1; 
  }
  ;

UnaryExp
  : PrimaryExp { 
    $$ = $1;  /* 直接传递PrimaryExp */
  }
  | '+' UnaryExp { 
    $$ = $2;  /* 一元正号不产生新节点，直接返回操作数 */
  }
  | '-' UnaryExp { 
    $$ = create_unary_ast('-', $2);  /* 一元负号 */
  }
  | '!' UnaryExp { 
    $$ = create_unary_ast('!', $2);  /* 逻辑非 */
  }
  ;

接下来实现常量折叠优化。在编译时就能计算出结果的表达式，直接计算出值：

/**
 * 递归求值常量表达式
 * @param expr 表达式AST节点
 * @param out 输出计算结果
 * @return 1表示成功求值，0表示不是常量表达式
 */
int eval_const_expr(const BaseAST *expr, int *out) {
    if (!expr || !out) return 0;
    
    switch (expr->type) {
        case AST_NUMBER: {
            /* 数字字面量直接返回值 */
            const NumberAST *n = (const NumberAST *)expr;
            *out = n->value;
            return 1;
        }
        
        case AST_UNARY: {
            /* 一元表达式递归求值 */
            const UnaryAST *u = (const UnaryAST *)expr;
            int operand_val = 0;
            
            /* 先求操作数的值 */
            if (!eval_const_expr(u->operand, &operand_val)) {
                return 0;  /* 操作数不是常量 */
            }
            
            /* 根据运算符计算结果 */
            switch (u->op) {
                case '+': 
                    *out = +operand_val;  /* 一元正号 */
                    return 1;
                    
                case '-': 
                    *out = -operand_val;  /* 一元负号 */
                    return 1;
                    
                case '!': 
                    *out = (operand_val == 0) ? 1 : 0;  /* 逻辑非 */
                    return 1;
                    
                default: 
                    return 0;  /* 未知运算符 */
            }
        }
        
        default:
            return 0;
    }
}

Koopa IR生成

虽然我们可以在编译时计算常量表达式，但为了演示完整的编译过程，让我们看看如何将一元运算转换为Koopa IR。

提示

Koopa IR不直接支持一元运算，需要转换为二元运算：

• 一元负号 x → sub 0, x

• 逻辑非 !x → eq x, 0

• 一元正号 +x → 不生成IR，直接使用 x

/**
 * 生成一元表达式的Koopa IR
 * @param gen 代码生成器
 * @param expr 一元表达式AST
 * @return 生成的临时变量名
 */
char* codegen_unary_expr(CodeGenerator *gen, const UnaryAST *expr) {
    assert(gen && expr);
    
    /* 先生成操作数的IR */
    char *operand_var = codegen_expr(gen, expr->operand);
    
    switch (expr->op) {
        case '+': {
            /* 一元正号直接返回操作数 */
            return operand_var;
        }
        
        case '-': {
            /* 一元负号：0 - operand */
            char *result_var = gen_temp_var(gen);
            fprintf(gen->output, "  %s = sub 0, %s\n", 
                    result_var, operand_var);
            return result_var;
        }
        
        case '!': {
            /* 逻辑非：operand == 0 */
            char *result_var = gen_temp_var(gen);
            fprintf(gen->output, "  %s = eq %s, 0\n", 
                    result_var, operand_var);
            return result_var;
        }
        
        default:
            assert(0 && "Unknown unary operator");
            return NULL;
    }
}

实现二元表达式（算术表达式）

基于项目现有的AST结构，我们需要扩展表达式相关的AST节点：

/**
 * 二元表达式AST节点
 * MulExp ::= UnaryExp | MulExp ("*" | "/" | "%") UnaryExp;
 * AddExp ::= MulExp | AddExp ("+" | "-") MulExp;
 * 表示二元运算表达式，包含左右操作数和运算符
 */
typedef struct {
    BaseAST base;
    char op;           /* '*', '/', '%', '+', '-' */
    BaseAST *left;     /* 左操作数 */
    BaseAST *right;    /* 右操作数 */
} BinaryAST;

/**
 * 创建二元表达式AST节点
 * @param op 二元运算符：'*', '/', '%', '+', '-'
 * @param left 左操作数
 * @param right 右操作数
 * @return 新创建的BinaryAST节点
 */
BaseAST* create_binary_ast(char op, BaseAST *left, BaseAST *right);

同样地，在Bison文件中，我们需要正确处理运算符的优先级和左结合性：

/* 二元表达式语法规则 */

%type <ast_val> Exp AddExp MulExp PrimaryExp UnaryExp

%%

Exp
  : AddExp { $$ = $1; }
  ;

/* 乘法表达式：优先级高于加法 */
MulExp
  : UnaryExp { 
    $$ = $1; 
  }
  | MulExp '*' UnaryExp { 
    $$ = create_binary_ast('*', $1, $3); 
  }
  | MulExp '/' UnaryExp { 
    $$ = create_binary_ast('/', $1, $3); 
  }
  | MulExp '%' UnaryExp { 
    $$ = create_binary_ast('%', $1, $3); 
  }
  ;

/* 加法表达式：优先级低于乘法 */
AddExp
  : MulExp { 
    $$ = $1; 
  }
  | AddExp '+' MulExp { 
    $$ = create_binary_ast('+', $1, $3); 
  }
  | AddExp '-' MulExp { 
    $$ = create_binary_ast('-', $1, $3); 
  }
  ;

Koopa IR生成

/**
 * 生成二元表达式的Koopa IR
 * @param gen 代码生成器
 * @param expr 二元表达式AST节点
 * @return 生成的临时变量名
 */
char* codegen_binary_expr(CodeGenerator *gen, const BinaryAST *expr) {
    assert(gen && expr);
    
    /* 递归生成左右操作数的IR */
    char *left_var = codegen_expr(gen, expr->left);
    char *right_var = codegen_expr(gen, expr->right);
    
    /* 根据运算符选择Koopa IR指令 */
    const char *koopa_op = NULL;
    switch (expr->op) {
        case '+': koopa_op = "add"; break;
        case '-': koopa_op = "sub"; break;
        case '*': koopa_op = "mul"; break;
        case '/': koopa_op = "div"; break;
        case '%': koopa_op = "mod"; break;
        default: 
            assert(0 && "Unknown binary operator");
    }
    
    /* 生成临时变量和指令 */
    char *result_var = gen_temp_var(gen);
    fprintf(gen->output, "  %s = %s %s, %s\n", 
            result_var, koopa_op, left_var, right_var);
    
    /* 释放中间结果的内存 */
    free(left_var);
    free(right_var);
    
    return result_var;

常量折叠优化

/**
 * 扩展的常量表达式求值算法
 * 支持二元算术运算的常量折叠
 */
int eval_const_expr_extended(const BaseAST *expr, int *out) {
    if (!expr || !out) return 0;
    
    switch (expr->type) {
        case AST_NUMBER: {
            const NumberAST *n = (const NumberAST *)expr;
            *out = n->value;
            return 1;
        }
        
        case AST_UNARY: {
            const UnaryAST *u = (const UnaryAST *)expr;
            int operand_val = 0;
            if (!eval_const_expr_extended(u->operand, &operand_val)) {
                return 0;
            }
            
            switch (u->op) {
                case '+': *out = +operand_val; return 1;
                case '-': *out = -operand_val; return 1;
                case '!': *out = (operand_val == 0) ? 1 : 0; return 1;
                default: return 0;
            }
        }
        
        case AST_BINARY: {
            /* 二元表达式处理 */
            const BinaryAST *b = (const BinaryAST *)expr;
            int left_val = 0, right_val = 0;
            
            /* 递归求值左右操作数 */
            if (!eval_const_expr_extended(b->left, &left_val) ||
                !eval_const_expr_extended(b->right, &right_val)) {
                return 0;
            }
            
            /* 执行二元运算 */
            switch (b->op) {
                case '+': 
                    *out = left_val + right_val; 
                    return 1;
                case '-': 
                    *out = left_val - right_val; 
                    return 1;
                case '*': 
                    *out = left_val * right_val; 
                    return 1;
                case '/': 
                    if (right_val == 0) return 0;  /* 除零检查 */
                    *out = left_val / right_val; 
                    return 1;
                case '%': 
                    if (right_val == 0) return 0;
                    *out = left_val % right_val; 
                    return 1;
                default: 
                    return 0;
            }
        }
        
        default:
            return 0;
    }
}