编译器文档：详细阶段设计与实现

总览
- 目标与概述
- 编译阶段的顺序
解析器（Parser）
- 功能与目标
- 输入输出
- 核心思路
- 实现细节
类型检查器（Typing）
- 功能与目标
- 输入输出
- 类型推导与验证
- 错误处理机制
K-正则形式（Knf）
- 功能与目标
- 输入输出
- 转换规则与示例
闭包转换（Closure）
- 功能与目标
- 输入输出
- 闭包表示的结构与生成
RISCV 汇编代码生成（RISCV）
- 功能与目标
- 输入输出
- 汇编指令生成与优化
JavaScript 代码生成（JS）
- 功能与目标
- 输入输出
- 核心思路
- 实现细节
阶段间交互
- 数据流与依赖关系
- 每阶段输入输出数据示例

1. 总览

编译器目标与概述

本编译器设计用于将源代码转化为多种目标格式（RISCV 汇编、JavaScript 等），经过以下阶段逐步完成：

Parser: 解析源码为抽象语法树（AST）。
Typing: 类型推导与验证，确保类型安全。
Knf: 转换为 K-正则形式，简化表达式。
Closure: 捕获自由变量并生成闭包表示。
RISCV: 转换为目标架构的汇编代码。
JS: 转换为 JavaScript 代码，支持浏览器或Node.js运行。

2. 解析器（Parser）

功能与目标

解析器（Parser）是 MiniMoonbit 编译器的一个关键组件，它负责将源代码转换为抽象语法树（AST）。解析器主要工作分为两个部分，第一部分词法分析器读取源代码并生成Token流；第二部分读取词法分析器生成的Token，并根据语法规则生成相应的语法树节点。

输入与输出

输入: 源代码（字符串形式）。
输出:
- 抽象语法树（@types.Syntax）。
- 含解析结果和语法节点。

核心思路

Parser由一组递归下降解析函数组成，每个函数负责解析特定的语法结构，与MiniMoonBit语法定义对应。参数为当前待解析的Token数组视图，返回相应的抽象语法树节点和剩余的Token数组视图。

实现细节

pub fn parse(source_code : String) -> @types.Syntax

参数
- source_code：类型为 String，表示要解析的源代码字符串。
返回值
- 返回值类型为 @types.Syntax，表示解析生成的抽象语法树（AST）。
功能描述
1. 使用源代码字符串初始化词法分析上下文 context，包括源代码字符串、偏移量和标记数组。
2. 调用 @lex.lex(context) 对源代码进行词法分析，将源代码转换为标记（Token）。
3. 调用 prog(context) 进入语法分析部分，生成抽象语法树（AST）。

pub fn prog(context : @lex.Context) -> @types.Syntax

参数
- context：类型为 @lex.Context，表示词法分析上下文，主要使用到其中的Token数组。
返回值
- 返回 @types.Syntax，表示解析生成的抽象语法树（AST）。
功能描述
1. 递归下降入口函数，调用 top_level(context.array[:]) 解析顶层声明
2. 检查是否以 EOF 结束
- 使用 checkToken(rest, @lex.EOF) 检查剩余的标记数组视图是否以 EOF 结束。
- 如果不是以 EOF 结束，抛出错误。

// 顶层声明
fn top_level(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn top_let_decl(rest : ArrayView[@lex.Token]) -> (((String, @types.Type), @types.Syntax), ArrayView[@lex.Token])
fn toplevel_fn_decl(rest : ArrayView[@lex.Token]) -> (@types.Fundef, ArrayView[@lex.Token])
fn main_fn_decl(rest : ArrayView[@lex.Token]) -> (@types.Fundef, ArrayView[@lex.Token])
fn top_fn_decl(rest : ArrayView[@lex.Token]) -> (@types.Fundef, ArrayView[@lex.Token])
// 函数体与参数解析
fn param_list(rest : ArrayView[@lex.Token]) -> (Array[(String, @types.Type)], ArrayView[@lex.Token])
fn param(rest : ArrayView[@lex.Token]) -> ((String, @types.Type), ArrayView[@lex.Token])
fn fn_body(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
// 非顶层函数解析
fn nontop_fn_decl(rest : ArrayView[@lex.Token]) -> (@types.Fundef, ArrayView[@lex.Token])
fn nontop_param_list(rest : ArrayView[@lex.Token]) -> (Array[(String, @types.Type)], ArrayView[@lex.Token]) 
fn nontop_param(rest : ArrayView[@lex.Token]) -> ((String, @types.Type), ArrayView[@lex.Token])

对于顶层函数，需要对参数和返回值给出明确的类型描述，非顶层函数可以不需要给出类型描述
参数
- rest：待解析的Token数组
返回值
- let_decl 返回(Identifier_name, Identifier_type), expr 和剩余Token数组
- fn_decl 返回Fundef 和剩余Token数组
功能描述
1. top_level 实际上由若干个Let((String, Type), Syntax, Syntax) 和LetRec(Fundef, Syntax) 语法节点组成，构成整个程序的框架。连续解析至EOF节点即完成对整个程序的解析
2. param 解析出具体参数，组成param_list ，返回给fn_decl 完成函数声明

// Statements
fn stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn let_tuple_stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn let_stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn fn_decl_stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn assign_stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn get_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn expr_stmt(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])

参数
- rest：待解析的Token数组
返回语法树节点类型
- let_tuple_stmt : LetTuple(Array[(String, Type)], Syntax, Syntax)
- let_stmt: Let((String, Type), Syntax, Syntax)
- fn_decl_stmt: LetRec(Fundef, Syntax)
- assign_stmt : Put(Syntax, Syntax, Syntax)
- expr_stmt : expr

// expression
fn expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn add_sub_level_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn mul_div_level_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn if_level_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn if_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn get_or_apply_level_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])

参数
- rest：待解析的Token数组
返回语法树节点类型
- add_sub_level_expr: Prim(left_syntax, expr, Add, kind=None) | Prim(left_syntax, expr, Sub, kind=None)
- mul_div_level_expr: Prim(left_syntax, expr, Mul, kind=None) | Prim(left_syntax, expr, Div, kind=None)
- if_level_expr : if_expr
- if_expr : If(Syntax, Syntax, Syntax)
- get_or_apply_level_expr: App(Syntax, Array[Syntax]) | Get(Syntax, Syntax)

// Value expression
fn value_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn unit_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn tuple_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn block_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn bool_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn neg_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn floating_point_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn int_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn not_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn array_make_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])
fn identifier_expr(rest : ArrayView[@lex.Token]) -> (@types.Syntax, ArrayView[@lex.Token])

参数
- rest：待解析的Token数组
返回语法树节点类型
- unit_expr: Unit
- tuple_expr : Tuple(Array[Syntax])
- block_expr : '{' stmt '}'
- neg_expr : Neg(Syntax, mut ~kind : Kind?)
- floating_point_expr : Double(Double)
- int_expr: Int(Int)
- not_expr: Not(Syntax)
- array_make_expr : Array(Syntax, Syntax)
- identifier_expr : Var(String)

fn skip(rest : ArrayView[@lex.Token], tk : @lex.Token) -> ArrayView[@lex.Token]
fn type_annotation(rest : ArrayView[@lex.Token]) -> (@types.Type, ArrayView[@lex.Token])

参数
- rest：类型为 ArrayView[@lex.Token]，表示剩余的Token数组视图
- tk：类型为 @lex.Token，表示要跳过的Token
返回值
- 返回值类型为 ArrayView[@lex.Token]，表示跳过指定标记后的剩余Token数组视图
功能描述
1. 跳过指定标记：检查 rest 中的第一个标记是否与 tk 匹配
  - 如果匹配，跳过该标记并返回剩余的Token数组视图
  - 如果不匹配，抛出错误

fn checkToken(rest : ArrayView[@lex.Token], tk : @lex.Token) -> Bool

参数
- rest：类型为 ArrayView[@lex.Token]，表示剩余的Token数组视图
- tk：类型为 @lex.Token，表示要检查的Token
返回值
- 返回值类型为 Bool，表示当前第一个Token是否匹配
功能描述
1. 检查标记是否匹配，比较 rest 中的第一个Token与 tk 是否相同
  - 如果相同，返回 true
  - 如果不同，返回 false

3. 类型检查器（Typing）

功能与目标

推导类型：根据给定的表达式推导出其类型，并处理其中可能的类型变量。
统一类型：通过 unify 函数将不同类型进行统一，确保表达式中的类型一致性。
递归处理：支持递归表达式（如 LetRec）的类型推导，能够正确推导出递归函数的类型。
类型清理：通过类型清理（deref_type）过程，将类型中的所有变量类型解引用为具体的类型，避免类型的不一致。
类型检查与错误报告：捕获并报告类型错误（如类型不匹配），为程序提供清晰的错误信息。

输入与输出

输入:
- 抽象语法树（@types.Syntax）。
输出:
- 类型化语法树（typechecked）。

实现细节

以下是该类型检查器实现的详细补充说明。

1. 类型推导上下文 (extenv)

extenv 是一个全局的类型环境，用于存储标准库函数的类型。每个标准库函数都有一个对应的类型，描述它们的输入输出。

pub let extenv : Map[String, @types.Type] = {
  "read_int": Fun([], Int),
  "print_int": Fun([Int], Unit),
  "read_char": Fun([], Int),
  "print_char": Fun([Int], Unit),
  "print_newline": Fun([], Unit),
  "int_of_float": Fun([Double], Int),
  "float_of_int": Fun([Int], Double),
  "truncate": Fun([Double], Int),
  "floor": Fun([Double], Double),
  "abs_float": Fun([Double], Double),
  "sqrt": Fun([Double], Double),
  "sin": Fun([Double], Double),
  "cos": Fun([Double], Double),
  "atan": Fun([Double], Double),
}

2. 类型检查器 (infer 和 unify)

infer 函数负责根据表达式推导类型，处理不同类型的表达式，包括基本类型和复杂表达式。

从抽象语法树（AST）开始，递归推导每个子表达式的类型。
对于每个基本类型（如 Int、Bool、Double），直接返回其类型。
对于 LetRec 和 App 等复杂表达式，递归推导其子表达式的类型，并统一函数参数和返回值类型。

unify 函数用于检查两个类型是否一致，并执行必要的类型合并。

它首先检查两个类型是否匹配。如果匹配，则继续；如果不匹配，则抛出类型错误。
处理多种类型：基本类型、变量类型、函数类型、元组类型和数组类型。

fn unify(t1 : @types.Type, t2 : @types.Type) -> Unit!TyErr {
  let t1 = repr(t1)
  let t2 = repr(t2)
  match (t1, t2) {
    // 基本类型匹配
    (Int, Int) | (Bool, Bool) | (Double, Double) | (Unit, Unit) => ()
    
    // 变量类型和其他类型匹配
    (Var(t) as tvar, ty) | (ty, Var(t) as tvar) => {
      check_occur!(tvar, ty)
      t.val = Some(ty)
    }

    // 函数类型匹配
    (Fun(params1, ret1), Fun(params2, ret2)) => {
      if params1.length() != params2.length() {
        raise TyErr::Mismatch(t1, t2, "Function parameter count mismatch")
      }
      for index = 0; index < params1.length(); index = index + 1 {
        let p1 = params1[index]
        let p2 = params2[index]
        unify!(p1, p2)
      }
      unify!(ret1, ret2)
    }

    // 元组类型匹配
    (Tuple(types1), Tuple(types2)) => {
      if types1.length() != types2.length() {
        raise TyErr::Mismatch(t1, t2, "Tuple element count mismatch")
      }
      for index = 0; index < types1.length(); index = index + 1 {
        let t1_elem = types1[index]
        let t2_elem = types2[index]
        unify!(t1_elem, t2_elem)
      }
    }

    // 数组类型匹配
    (Array(elem_type1), Array(elem_type2)) => unify!(elem_type1, elem_type2)
    
    // 其他类型不匹配
    _ => raise TyErr::Mismatch(t1, t2, "Type mismatch")
  }
}

3. 类型推导示例 (infer)

在推导类型时，代码会根据表达式的具体形式（如 Int、Let、App）进行相应的推导。以下是一些推导类型的示例：

`LetRec` 递归

在递归定义函数时，首先推导参数类型，然后递归推导函数体类型，最后统一函数类型。

函数调用 (`App`)

对于函数调用，首先推导函数本身和参数的类型，然后统一它们与期望的类型。

一元负号 (`Neg`)

对于负号表达式，会根据操作数的类型推导出返回类型。如果操作数的类型是 Int 或 Double，则统一为相应的类型。

数组 (`Array`)

对于数组类型，会先推导数组的元素类型，然后确保索引是 Int 类型。

fn infer(ctx : LocalCtx, e : @types.Syntax) -> @types.Type!TyErr {
  match e {
    // 基本类型
    Unit => Unit
    Int(_) => Int
    Bool(_) => Bool
    Double(_) => Double

    // 变量类型
    Var(x) =>
      match ctx._[x] {
        Some(t) => t
        None => {
          let t = new_tvar()
          extenv[x] = t
          t
        }
      }

    // 递归函数类型推导
    LetRec({ name: (f, t), args, body }, rest) => {
      let env_with_f = ctx._.add(f, t)
      let params_ty = args.map(fn { (_, t) => t })
      let mut env_with_params = env_with_f
      for p in args {
        env_with_params = env_with_params.add(p.0, p.1)
      }
      let body_ty = infer!(env_with_params, body)
      unify!(t, Fun(params_ty, body_ty))
      infer!(env_with_f, rest)
    }

    // 函数调用
    App(f, args) => {
      let ret_ty = new_tvar()
      let f_ty = infer!(ctx, f)
      let args_ty = []
      for a in args {
        args_ty.push(infer!(ctx, a))
      }
      unify!(f_ty, Fun(args_ty, ret_ty))
      ret_ty
    }

    // 其他表达式类型的推导...
  }
}

4. 类型清理与标准化 (deref_type)

deref_type 负责解引用类型中的所有变量类型，直到找到具体的类型。这在处理类型变量（Var 类型）时非常重要，可以保证类型的一致性。

fn deref_type(t : @types.Type) -> @types.Type {
  match t {
    // 递归解引用函数类型
    Fun(params, result) =>
      Fun(params.map(fn { t => deref_type(t) }), deref_type(result))
    
    // 解引用元组类型
    Tuple(types) => Tuple(types.map(fn { t => deref_type(t) }))
    
    // 解引用数组类型
    Array(t) => Array(deref_type(t))
    
    // 解引用变量类型
    Var(inner_t) =>
      match inner_t.val {
        Some(ty) => {
          let ty = deref_type(ty)
          inner_t.val = Some(ty)
          ty
        }
        None => {
          inner_t.val = Some(Unit)
          Unit
        }
      }

    // 返回其他类型
    t => t
  }
}

5. 主函数 (typing)

typing 函数是类型检查器的主入口，它将整个类型检查过程串联起来，从类型推导到类型清理，并返回类型化后的抽象语法树。

pub fn typing(e : @types.Syntax) -> @types.Syntax!TyErr {
  let mut ctx = @immut/hashmap.T::new()
  
  // 初始化上下文，将外部环境添加到上下文中
  for item in extenv {
    ctx = ctx.add(item.0, item.1)
  }

  // 推导表达式的类型并统一为 `Unit`
  unify!(Unit, infer!(ctx, e))

  // 对外部函数进行类型标准化
  for ext_f, ext_t in extenv {
    extenv[ext_f] = deref_type(ext_t)
  }

  // 解引用表达式并返回
  deref_term(e)
}

4. K-正则形式（Knf）

功能与目标

输入与输出

输入:
- 类型化语法树（typechecked）。
输出:
- K-正则形式代码（knf）。

实现细节

1. 概述

KNF（合取范式，Klausel Normal Form）是一种逻辑表达式的标准化形式，通常在编译器、逻辑推理或约束求解等领域中使用。本代码的核心是通过一个环境结构 (KnfEnv) 来管理逻辑表达式中的变量和函数的定义，并提供工具方法来支持 KNF 转换过程。

2. 核心数据结构

`KnfEnv` 结构

该结构用于存储和管理 KNF 转换过程中的各种上下文信息，包括变量、函数和类型的映射表：

counter: 一个计数器，用于生成新的唯一标识符。
externals: 不可变的外部变量映射。
signTable: 用于存储变量名称到类型和标识符的映射。
funcTable: 用于存储函数名称到类型和标识符的映射。
name_and_type: 名称和类型的映射，用于快速检索特定名称的类型。

KnfEnv 示例代码

struct KnfEnv {
  mut counter : Int,
  externals : @immut/hashmap.T[String, Type],
  signTable : @hashmap.T[String, (Name, Type)],
  funcTable : @hashmap.T[String, (Name, Type)],
  func_name_and_type : @hashmap.T[Name, Type],
  name_and_type : @hashmap.T[Name, Type],
}

3. 核心功能

3.1. 环境变量管理

添加变量到环境 函数 addVarToEnv 将一个变量添加到 signTable 和 name_and_type，同时根据需求更新已有条目。

pub fn addVarToEnv(env : KnfEnv, s : String, n : Name, t : Type) -> Bool {
  if env.signTable[s] != None && env.signTable[s].unwrap().1 == Type::Unit {
    ignore(env.signTable.remove(s))
    env.signTable[s] = (n, t)
    env.name_and_type[n] = t
    return true
  }
  env.signTable[s] = (n, t)
  env.name_and_type[n] = t
  true
}

检索变量信息 函数 getVarFromEnv 检索变量的标识符和类型。如果变量不存在，返回默认值。

pub fn getVarFromEnv(env : KnfEnv, s : String) -> (Name, Type) {
  if env.signTable[s] != None {
    return env.signTable[s].unwrap()
  }
  return (Name::slot_only(0), Type::Unit)
}

3.2. 函数管理

添加函数 addFuncToEnv 将函数及其对应的标识符和类型添加到 funcTable。

pub fn addFuncToEnv(env : KnfEnv, s : String, n : Name, t : Type) -> Bool {
  env.funcTable[s] = (n, t)
  env.func_name_and_type[n] = t
  true
}

检索函数信息 getFuncFromEnv 提供函数名称到类型和标识符的映射查找。

pub fn getFuncFromEnv(env : KnfEnv, s : String) -> (Name, Type) {
  if env.funcTable[s] != None {
    return env.funcTable[s].unwrap()
  }
  return (Name::slot_only(0), Type::Unit)
}

3.3. 临时变量生成

new_temp: 生成一个临时标识符，使用 counter 确保唯一性。

fn KnfEnv::new_temp(self : KnfEnv) -> Name {
  let temp = Name::slot_only(self.counter)
  self.counter += 1
  temp
}

new_named_temp: 为一个已有变量生成一个带计数的临时变量。

fn KnfEnv::new_named_temp(self : KnfEnv, name : Name) -> Name {
  let counter = self.counter
  self.counter += 1
  { ..name, slot: counter }
}

3.4. KNF 转换支持

插入 let 表达式 函数 insert_let 实现了一个重要的 KNF 逻辑处理步骤：将任意表达式绑定到一个变量，并继续处理后续逻辑。

fn insert_let(self : KnfEnv, e : Knf, t : Type, k : (Name) -> Knf) -> Knf {
  match e {
    Var(x) => k(x), // 如果是变量，直接调用继续函数 k
    _ => {
      let x = new_temp(self) // 生成一个临时标识符
      let e1 = k(x)
      ...
    }
  }
}

4. KNF 的实现逻辑

创建和初始化一个环境对象 (KnfEnv)。
通过 insert_let 等函数，将表达式逐步分解为变量绑定（合取形式）。
使用临时变量 (new_temp) 和类型映射管理 (name_and_type) 确保逻辑表达式的一致性。
提供对变量、函数和类型的查询、添加和更新操作。

5.`to_knf` 函数说明

函数签名：

def to_knf(node: AstNode) -> KNF:

参数：

node (AstNode): 输入的抽象语法树（AST）节点，表示一个表达式或语句。该节点可以是不同类型的表达式，可能包括布尔值、整数、浮动数字、逻辑运算符等。

返回值：

返回一个 KNF 类型的中间表示，表示通过逻辑转换后的标准化范式（可能是某种形式的可满足范式或其他标准化形式）。

函数功能：

该函数接受一个 AST 节点作为输入，并将其转换为中间表示形式 KNF。转换过程根据 AST 节点的类型进行递归处理。不同类型的节点会经过相应的处理逻辑以生成符合 KNF 的结构。

主要步骤：

基础类型处理：当遇到常量类型节点（如布尔值、整数、浮动数字等）时，直接将其转换为对应的 KNF 形式。
逻辑操作符：对于涉及逻辑操作（如 Not 或 Neg 等）的节点，函数会递归地处理操作数，并根据操作符的类型调整逻辑结构。例如：
- Not 运算符会递归处理其操作数，并根据其值生成相应的中间表示。
- 对于其他逻辑运算符，可能会插入中间变量以简化表达式，使用 insert_let 来确保表达式的一致性。
递归处理：函数通过递归调用 to_knf 来处理复杂的表达式树，并逐步将各个子树转换为 KNF。每次递归都会逐渐细化并标准化节点，直到整个 AST 被转换为 KNF 格式。
插入中间变量：在某些情况下，当处理复杂的逻辑表达式时，函数会使用 insert_let 来插入中间变量，这有助于避免重复计算或优化表达式的结构。

适用场景：

该函数适用于处理涉及逻辑运算的抽象语法树，尤其是在涉及布尔运算符、条件表达式、逻辑公式等场景下。
适用于将逻辑表达式转化为规范形式（如可满足范式，KNF），以便于后续的求解或简化。

5. 闭包转换（Closure）

功能与目标

功能：将 K-正则形式的代码转换为闭包表示，适应后续的闭包调用和优化。此过程通过将函数封装为闭包，提取出自由变量，并转换为低级表示形式。
目标：生成能够处理自由变量的闭包表示，使得函数调用可以以闭包的形式执行，从而支持递归和高阶函数的调用。

输入与输出

输入:
- K-正则形式代码（knf）：程序的 K-正则形式表示，其中包含了表达式、函数定义等信息。
输出:
- 闭包表示（closure_ir）：转换后的程序表示，包含闭包的创建、自由变量的处理、以及相应的函数调用。

实现细节

自由变量提取（fv 函数）： fv 函数用于提取表达式中的自由变量。这些自由变量是未被绑定的变量，对于闭包转换至关重要。fv 通过递归处理不同的表达式类型，收集所有自由变量。
辅助函数：
- add_to_array: 将新元素添加到数组中，避免重复。
- union: 将两个数组中的元素合并，去重。
- remove: 从数组中删除指定元素。
闭包转换（knf_program_to_closure 函数）：
- 对于每个 K-正则形式的表达式，knf_program_to_closure 函数将递归地将其转换为闭包表示。
- 如果遇到 LetRec（递归定义），函数会处理递归函数的自由变量，并生成相应的闭包定义。
- 对于函数调用（Apply）和其他表达式类型，转换成闭包调用或闭包操作。
- 对于 LetRec，递归地处理函数体，并生成闭包及相应的函数定义。
低级类型转换（type_to_lowtype）：
- 将高级类型（如 Type::Fun、Type::Array）转换为低级类型（如 LowType::ClosureFn、LowType::Array），以适应闭包表示。
递归函数处理：
- 对于递归函数，提取出所有自由变量，生成闭包，并将函数定义添加到最终的闭包表示中。
闭包表示的返回：
- 最终返回一个包含闭包和相应函数定义的程序表示（Program）。此程序表示可以直接用于后续的执行或优化阶段。

6. RISCV 汇编代码生成（RISCV）

功能与目标

该模块的主要功能是将闭包表示（closure_ir）转换为对应的RISCV汇编代码。通过对函数调用、变量赋值、闭包捕获等操作的处理，生成可执行的RISCV指令。

输入与输出

输入:
- 闭包表示（closure_ir）：包括表达式、函数定义、变量等信息的结构化表示。
输出:
- RISCV 汇编代码（asm）：生成的RISCV汇编代码，用于后续的编译和执行。

实现细节

寄存器分配器 (RegAllocator)
寄存器分配器管理着可用的通用寄存器（available_regs）、浮点寄存器（available_fregs）以及已经分配的寄存器（used_regs、used_fregs）和栈（stack）。它还维护了栈偏移量（stack_offset）和临时寄存器索引（temp_index 和 temp_findex）用于生成汇编代码。
外部环境 (extenv)
extenv 存储了外部函数的类型映射。例如，minimbt_read_int 映射到 Int 类型，minimbt_print_int 映射到 Unit 类型等。
寄存器分配与存储
通过一系列的辅助函数，如 prepareOperand、prepareFOperand、prepareArgs 等，管理寄存器的分配和加载。这些函数根据表达式的类型（整数、浮点数等）选择合适的寄存器进行存储。
临时寄存器的管理
prepareTempReg 和 prepareTempFReg 用于分配和管理临时寄存器，保证每次生成的代码使用的是有效的寄存器。
闭包与栈管理
对于闭包表达式（如 MakeClosure），会生成一个新的栈帧来存储捕获的自由变量。通过 createClosure 函数，动态分配内存，并将闭包的代码和自由变量存储在栈上。
代码生成
- 在处理 Let 表达式时，通过递归的方式生成对每个变量的栈分配和寄存器加载。
- 对于 MakeTuple 等复合类型，使用动态分配内存的方法，并将元素存储到生成的数组中。
- 支持基本的控制流结构，如条件语句 IfLe 和 IfEq，通过标签跳转来生成对应的汇编代码。
内存分配与函数调用
使用 callMalloc 和 callCreatePtrArray 等函数来为闭包和数组等动态数据结构分配内存，并生成相应的汇编代码。
外部函数调用
外部函数（如 minimbt_malloc、minimbt_create_ptr_array）的调用通过 Call 指令进行，其中传递的参数被映射到寄存器中。

7. JavaScript 代码生成（JS）

功能与目标

代码生成器（Js/transformer）负责将抽象语法树（AST）转换为目标语言代码。在这个实现中，目标语言是 JavaScript。代码生成器读取解析器生成的 AST，并生成相应的 JavaScript 代码

输入与输出

输入:
- 抽象语法树（@types.Syntax）。
输出:
- JavaScript 源代码（String）。

核心思路

通过递归遍历 AST 的各个节点，根据节点类型生成相应的 JavaScript 代码

实现细节

1. 全局变量

struct tmpvar {
  mut count: Int
} derive(Show)

let t: tmpvar = tmpvar::{
  count: 0
}

初始化计数器：
- 结构体实例 t 的 count 字段初始化为 0，用于记录生成的临时变量的数量
生成临时变量名：
- 在需要生成临时变量名时，通过增加 count 字段的值来生成唯一的变量名
- 例如，当变量名为 _ 时，生成的临时变量名为 tempvar1、tempvar2 等
```
fn genVarName(name: String) -> String {
  if name == "_" {
    t.count = t.count + 1
    "tempvar" + t.count.to_string()
  }
  else {
    name
  }
}
```

2. Js代码生成部分

pub fn generator(ast: @types.Syntax) -> String {
  jscodegen(ast) + "\n" + "export default main;"
}
fn jscodegen(ast: @types.Syntax) -> String {
  match ast {
    @types.Syntax::Unit => ""
    @types.Syntax::Bool(value) => if value { "true" } else { "false" }
    ······
 	}
}

每个节点类型对应一个生成函数，这些函数通过模式匹配处理不同类型的语法节点。

处理不同类型的语法节点：
- 对于基本类型（如 Unit、Bool、Int、Double），直接生成相应的 JavaScript 字面量。
- 对于变量（Var），根据变量名生成相应的 JavaScript 变量名，并处理特殊函数名的映射。
- 对于复合类型（如 Tuple、Array），递归生成其子节点的 JavaScript 代码，并组合成相应的 JavaScript 表达式。
- 对于运算符（Prim），根据操作符类型生成相应的 JavaScript 运算符，并递归生成操作数的 JavaScript 代码。
生成函数定义和调用：
- 对于函数定义（LetRec），生成相应的 JavaScript 函数定义代码，包括函数名、参数列表和函数体。
- 对于函数调用（App），生成相应的 JavaScript 函数调用代码，包括函数名和参数列表。

处理变量和类型转换：

通过 genVarName 函数生成变量名，处理临时变量的命名。

通过 calcuPrim 函数处理基本运算，生成相应的 JavaScript 运算表达式。

fn calcuPrim(ast: @types.Syntax) -> String {
  match ast {
    @types.Syntax::If(cond, then_branch, else_branch) => "(" + jscodegen(cond) + " ? " + jscodegen(then_branch) + " : " + jscodegen(else_branch) + ")"
    @types.Syntax::Prim(lhs, rhs, op, ..) => {
      let mut op = op.to_string()
      match op {
        "Add" => op = "+"
        "Sub" => op = "-"
        "Mul" => op = "*"
        "Div" => op = "/"
        _ => @util.die("wrong op")
      }
      "(" + calcuPrim(lhs) + " " + op + " " + calcuPrim(rhs) + ")"
    }
    _ => jscodegen(ast)
  }
}

生成带有返回值的代码：

由于MiniMoonBit表达式中不包含return语句，需要在生成JavaScript代码时特别处理，在函数体中递归进入到最后一条语句时加上return语句
通过 jscodegen_with_return 函数生成带有返回值的 JavaScript 代码，处理 Let、LetRec、LetTuple 和 Put 语法节点，并在适当的位置添加 return 语句

fn jscodegen_with_return(ast: @types.Syntax) -> String {
  match ast {
    @types.Syntax::Let((name, _), value, rest) => "let " + genVarName(name) + " = " + jscodegen(value) + "\n" + jscodegen_with_return(rest)
    @types.Syntax::LetRec(fundef, rest) => {
      jscodegen_fundef(fundef) + "\n" + jscodegen_with_return(rest)
    }
    @types.Syntax::LetTuple(arr, value, rest) => {
      let mut result = genVarName(arr[0].0)
      for arg in arr[1:] {
        result = result + ", " + genVarName(arg.0)
      }
      "let [" + result + "] = " + jscodegen(value) + "\n" + jscodegen_with_return(rest)
    }
    @types.Syntax::Put(array, value, rest) => ...
    @types.Syntax::If(cond, then_branch, else_branch) => 	...
    _ => "return " + jscodegen(ast) 
  }
}

判断进入最后一条语句的方法：return语句不会是 Let、LetRec、LetTuple 、 Put 和 If ，当在函数体中递归进入到非以上5类语句，认为到达了return语句

8. 阶段间交互

数据流

阶段	输入数据	输出数据
Parser	源代码（字符串）	抽象语法树（AST）
Typing	抽象语法树	类型化语法树
Knf	类型化语法树	K-正则形式代码
Closure	优化后的K-正则形式	闭包中间表示
RISCV	闭包中间表示	RISCV 汇编代码
JS	抽象语法树	JavaScript 源代码

Name		Name	Last commit message	Last commit date
Latest commit History 159 Commits
.idea		.idea
course		course
js_rt		js_rt
licenses		licenses
riscv_rt		riscv_rt
src		src
test		test
.gitignore		.gitignore
.gitmodules		.gitmodules
.moonbit-lsp.json		.moonbit-lsp.json
2		2
MiniMoonBit.g4		MiniMoonBit.g4
adder.out		adder.out
build_riscvrt.sh		build_riscvrt.sh
build_rvlinux.sh		build_rvlinux.sh
cls-bug.out		cls-bug.out
cls-bug2.out		cls-bug2.out
cls-reg-bug.out		cls-reg-bug.out
even-odd.out		even-odd.out
fib.out		fib.out
float.out		float.out
funcomp.out		funcomp.out
inprod-loop.out		inprod-loop.out
inprod-rec.out		inprod-rec.out
inprod.out		inprod.out
license		license
matmul-flat.out		matmul-flat.out
matmul.out		matmul.out
moon.mod.json		moon.mod.json
non-tail-if.out		non-tail-if.out
print.out		print.out
readme.md		readme.md
rvelf		rvelf
rvlinux		rvlinux
spill.out		spill.out
temp.txt		temp.txt
test.sh		test.sh

License

YYYYimo/MiniMoonbit-Compiler

Folders and files

Latest commit

History

Repository files navigation

编译器文档：详细阶段设计与实现

目录

1. 总览

编译器目标与概述

2. 解析器（Parser）

功能与目标

输入与输出

核心思路

实现细节

参数

返回值

功能描述

返回值

功能描述

参数

返回语法树节点类型

参数

返回语法树节点类型

参数

参数

返回值

功能描述

参数

返回值

功能描述

3. 类型检查器（Typing）

功能与目标

输入与输出

实现细节

LetRec 递归

函数调用 (App)

一元负号 (Neg)

数组 (Array)

4. K-正则形式（Knf）

功能与目标

输入与输出

实现细节

1. 概述

2. 核心数据结构

KnfEnv 结构

KnfEnv 示例代码

3. 核心功能

3.1. 环境变量管理

3.2. 函数管理

3.3. 临时变量生成

3.4. KNF 转换支持

4. KNF 的实现逻辑

5.to_knf 函数说明

5. 闭包转换（Closure）

功能与目标

输入与输出

实现细节

6. RISCV 汇编代码生成（RISCV）

功能与目标

输入与输出

实现细节

7. JavaScript 代码生成（JS）

功能与目标

输入与输出

核心思路

实现细节

1. 全局变量

2. Js代码生成部分

8. 阶段间交互

数据流

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

`LetRec` 递归

函数调用 (`App`)

一元负号 (`Neg`)

数组 (`Array`)

`KnfEnv` 结构

5.`to_knf` 函数说明

Packages