手搓编译器，99%的人对我的内容不会感兴趣

25-10-30

目前进度：设计出编译器模块

设计目标

语法正确性保障：设计并实现解析器，能够对源代码进行词法和语法分析，捕获错误。
语义一致性验证：实现语义分析器，进行类型检查，作用域解析和命令约束验证，确保程序的逻辑正确性。
命令映射：将高层次抽象概念映射到卫星系统底层具体命令。
代码生成：生成一种结构化的、可供命令规划器使用的数据格式，该格式清晰地描述了任务、卫星分配、执行条件和命令序列。

编译器总体架构

词法分析：将源代码分解成Token。
语法分析：根据EBNF语法规则，将词法单元流构建成抽象语法树AST。
语义分析：遍历AST，进行类型检查、符号解析和高级语义规则验证，并对AST进行注解。
中间代码生成：将经过语义分析的 AST 转换为一种更适合优化的IR。
代码生成：将优化后的中间表示转换为最终的目标格式，供下游的命令规划器与执行器使用。

词法分析器

目标：词法分析器负责将源代码字符串转换为Token流。

输入：源代码文件。
输出：Token序列。实现：
根据行为语言设计中“词法规则”进行设计。
识别并区分标识符 (Identifier)、关键字 (Keyword)、字面量 (Literal)、运算符 (Operator) 和分隔符 (Separator)。
自动忽略空白符 (Whitespace)和注释 (Comment)。
每个Token包含类型、值和其在源代码中的位置行号和列号。 Token 示例

源代码	Token 类型	Token 值
`mission`	`KEYWORD`	`mission`
`Search`	`IDENTIFIER`	`Search`
`{`	`SEPARATOR`	`{`
`12.5`	`FLOAT_LITERAL`	`12.5`
`==`	`OPERATOR`	`==`

语法分析器

目标：接收词法分析器生成的 Token 流，并根据语言的语法规则构建 AST。

输入：Token序列。
输出：抽象语法树(AST) 。实现：
(根据行为语言设计中)“语法规则”的EBNF定义。
采用递归下降 (Recursive Descent)的解析策略，为每个非终结符构建一个解析函数。
AST的每个节点代表源代码中的一个语法结构，如MissionDefNode、TaskDefNode等。
若解析过程中发现不符合语法规则的Token，将报告语法错误，并指明错误位置。

AST 节点部分示例：

- ProgramNode
  - children: [
    - ApiDefNode (name: "Send", ...),
    - MissionDefNode (name: "Search")
      - body: BlockNode
        - children: [
          - VarDeclNode (name: "x", type: "float"),
          - OrientationStmtNode
            - condition: BinaryOpNode (op: "==", left: "rec_type", right: "target")
            - body: DecisionStmtNode (...)
        ]
    - GroupDefNode (name: "Tasks")
      - ...
  ]

语义分析器

目标：负责检查程序的静态语义，确保逻辑上是有效和一致的。

输入：AST。
输出：经过注解和验证的AST。
核心功能：
1. 符号表管理 (Symbol Table)：
  - 构建分层级的符号表，用于管理变量、任务、API 等标识符的作用域（如全局作用域、Mission 作用域、块作用域）。
  - 检查标识符的声明和使用情况，捕获“未声明的变量”或“重复定义”等错误。
2. 类型检查 (Type Checking)：
  - 依据《语言设计.md》第 4 节“类型系统”的规则。
  - 遍历表达式树，推导并验证每个子表达式的类型。
  - 检查赋值语句、函数调用、运算符操作数的类型兼容性。例如，Orientation 的条件表达式必须为 bool 类型。
3. 控制流与约束验证：
  - 验证 Orientation 和 Decision 结构的正确性。例如，确保 Orientation 链最终由一个 Decision 结尾。
  - 分析 Orientation 的条件数量与 Decision 块的数量是否匹配，以正确解析 if-elseif-else 逻辑。
4. 任务与群组结构分析：
  - 解析 Group 和 Task 定义，构建任务的层级关系和卫星分配表。
  - 验证分配给任务的卫星名称是否合法。
  - 检查任务的实现（= MissionName 或 = NULL）是否有效。

6. 中间代码 (IR) 生成

为了解耦前端（分析）和后端（生成），并为未来的优化做准备，编译器将 AST 转换为两种中间表示。

输入：语义分析后的 AST。
输出：控制流图 (CFG) 和任务依赖图 (TDG)。

6.1. 控制流图 (Control Flow Graph, CFG)

描述：将每个 mission 转换为一个 CFG，其中节点是 基本块 (Basic Block)，边代表控制流。
结构：
- 基本块：包含一系列顺序执行的指令（如变量声明、赋值、API 调用）。
- 条件分支：Orientation 语句被转换成分支节点，根据条件表达式的结果跳转到不同的后续基本块。
- 循环与 OODA 模型：整个 mission 的执行可以看作一个大的循环（OODA 循环），CFG 的结构将体现这一点，从 Observation 开始，经过 Orientation 和 Decision，最后到 Action，然后循环。

6.2. 任务依赖图 (Task Dependency Graph, TDG)

描述：用于表示 Group 中定义的任务结构和卫星分配。
结构：
- 节点：代表一个 Task。
- 边：表示任务的嵌套关系（父子任务）。
- 属性：每个节点包含任务名称、分配的卫星列表、以及该任务绑定的 mission（即 CFG）。

7. 优化器 (Optimizer)

优化器阶段在中间代码生成之后、最终代码生成之前。它接收 CFG 和 TDG 作为输入，通过一系列变换算法，在不改变程序语义的前提下，生成执行效率更高、资源占用更少的优化版 IR。

输入：控制流图 (CFG) 和任务依赖图 (TDG)。
输出：优化后的 CFG 和 TDG。
核心优化技术：
1. 常量折叠与传播 (Constant Folding and Propagation)：在编译期预先计算常量表达式的值，并将其传播到使用该常量的地方。例如，float a = 10.0 * 2.0; 会被直接优化为 float a = 20.0;。
2. 死代码消除 (Dead Code Elimination)：移除程序中永远不会被执行到的代码，如永不为真的条件分支或从未被调用的任务。
3. 公共子表达式消除 (Common Subexpression Elimination)：识别并消除重复计算的相同表达式，将计算结果存储在临时变量中重复使用。
4. 任务融合 (Task Fusion)：在满足约束的前提下，将多个小任务或指令序列合并为一个更大的任务，以减少任务切换和调度的开销。

8. 代码生成 (Code Generator)

代码生成器是编译器的最后一个阶段，其核心目标是为下游的命令规划器和执行器生成一个统一的、结构化的数据包。此数据包以 JSON 格式提供，包含两部分核心内容：

规划器输入 (planner_input)：根据 TPL 程序中的 Group、Task 声明以及外部配置文件（如卫星轨道参数、目标物理信息等），生成完全符合《规划器设计.md》中定义的输入数据。这部分数据用于宏观的任务规划与调度。
行为定义 (behavior_definitions)：将 TPL 程序中每个 mission 的具体逻辑（OODA 循环）编译成底层的行为树 (Behavior Tree)。规划器完成调度后，执行器将根据规划结果调用相应的行为树来执行具体任务。

输入：优化后的 CFG 和 TDG，以及外部世界模型数据（如可见时间窗、任务收益等）。
输出：一个包含 planner_input 和 behavior_definitions 的 JSON 对象。

8.1. 生成规划器输入 (Planner Input)

编译器的此部分功能负责聚合所有宏观规划所需的信息：

卫星集合 (Satellites)：从 TPL 的 Group 定义中提取所有参与任务的卫星 ID。
待观测任务集合 (Tasks)：
- 从 Task 定义中提取任务名称，并将其与外部数据（如收益 P_i、时长 d_i、期限 o_i）关联，形成任务三元组。
- TPL 中的 Task ... = MissionName 语句，将一个规划层面的抽象任务（如 GoToAndSearch）与一个行为层面的具体实现（GoToStation mission）绑定起来。
可见时间窗 (Windows)：通过外部轨道计算模块，根据任务的目标位置和卫星轨道，生成每个任务在每颗卫星上的可见时间窗集合 W_ij。
姿态调整时间 (Maneuver Time)：作为一个全局配置参数 z 载入。

8.2. 生成行为定义 (Behavior Definitions)

编译器的此部分功能负责将 TPL mission 的过程式、事件驱动逻辑转换为声明式、层级化的行为树。

Sequence (顺序节点)：用于执行一系列必须按顺序完成的子任务。TPL 中一个 Decision 块内的连续语句可被映射为一个 Sequence 节点。
Selector (选择节点)：用于实现决策逻辑（if-elseif-else）。TPL 中的 Orientation { (cond1) (cond2) } Decision { {block1} {block2} } 结构被映射为一个 Selector。
Condition (条件节点)：TPL Orientation 语句中的条件表达式（如 dist < min_dist）被映射为 Condition 节点。
Action (行动节点)：TPL 中的 api 调用（如 MoveTo, Send）和 Action 块中的硬件操作被映射为 Action 节点。

8.3. 目标统一 JSON 格式示例

最终生成的 JSON 文件将规划输入和行为定义整合在一起，形成一个自包含的任务描述包。

{
  "project_name": "alpha_search",

  "planner_input": {
    "satellites": ["s1", "s2", "s3", "s4", "s5"],
    "tasks": [
      { "id": "T1", "name": "GoToStation", "profit": 8, "duration": 40, "deadline": "15:10:00" },
      { "id": "T2", "name": "Search", "profit": 9, "duration": 35, "deadline": "12:30:00" }
    ],
    "windows": {
      "T1": {
        "s1": [ { "start": "08:00:00", "end": "08:15:00" } ],
        "s2": [ { "start": "08:32:00", "end": "08:47:00" } ]
      }
    },
    "maneuver_time": 120
  },

  "behavior_definitions": {
    "GoToStation": {
      "type": "Sequence",
      "name": "GoToStation_Mission",
      "children": [
        { "type": "Action", "name": "MoveTo", "params": [0.0, 0.0, 0.0] },
        {
          "type": "Selector",
          "name": "Check_Arrival",
          "children": [
            {
              "type": "Sequence",
              "children": [
                { "type": "Condition", "expression": "sx == tx && sy == ty && sz == tz" },
                { "type": "Action", "name": "exit" }
              ]
            },
            { "type": "Action", "name": "wait" }
          ]
        }
      ]
    },
    "Search": {
      "type": "Sequence",
      "name": "Search_Mission",
      "children": [
        // ... Search 任务对应的复杂行为树结构 ...
      ]
    }
  }
}

230

230手搓编译器之路