解析构建AST时如何按概念顺序存储类型定义与宏展开内容？

我正在开发一门编程语言，当前核心工作是处理类型定义的顺序化逻辑：类型定义必须按特定的概念顺序排列，同时存在延迟求值的MACRO，会在INSERT指令所在位置注入对应代码。需要明确的是，必须放弃「先预解析所有宏再处理主内容」的思路，严格按照宏出现的顺序处理。

示例代码 #

INSERT z
type a
type b
INSERT x
type c
type d
INSERT y

MACRO y {
  type p
  type q
  INSERT w
}

MACRO z {
  type t
  type v
}

MACRO x {
  type h
  type i
}

MACRO w {
  type l
  type m
  type n
}

期望的AST顺序 #

期望生成的AST节点顺序如下：

[{ type: 't' },{ type: 'v' },{ type: 'a' },{ type: 'b' },{ type: 'h' },{ type: 'i' },{ type: 'c' },{ type: 'd' },{ type: 'p' },{ type: 'q' },{ type: 'l' },{ type: 'm' },{ type: 'n' }]

当前问题与已有思路 #

朴素的按代码发现顺序处理的算法会生成错误的排序结果。目前已有两种可行思路：

• 使用SortedSet，以节点的概念顺序索引为键，实现有序存储
• 通过WAIT对象指针动态插入数组，但该方案效率较低

现寻求更优的实现方案，能够高效维护按概念顺序存储的有序列表或哈希表。

内容的提问来源于stack exchange，提问作者Lance Pollard