如何通过具体语法树（CST）生成抽象语法树（AST）？

核心概念前置区分 #

• 具体语法树（CST）：1:1 对齐源码所有内容，包含空白符、注释、语法分隔符（括号、逗号、分号等）、关键字等所有语法细节，每个节点都绑定对应源码的位置范围
• 抽象语法树（AST）：仅保留语义相关的结构信息，丢弃无语法语义价值的冗余元素，仅保留能表征代码逻辑的核心节点

完整实现流程 #

1. 定义语法规则 #

你提到的 Ungrammar 就是专门用于描述编程语言语法结构的DSL，相比传统EBNF更简洁，适合用来定义CST的节点类型和层级关系。你可以先基于目标语言的语法规范，用Ungrammar写出完整的语法规则，明确每个语法结构的组成部分。

2. 实现词法分析（分词） #

编写词法分析器将输入的源码文本拆分为Token流，需要注意：CST场景下的分词不能丢弃空白、注释、换行这类无直接语义的Token，需要全部保留供后续CST构建使用，每个Token需要绑定其在源码中的起止位置、文本内容、Token类型属性。

3. 构造CST #

根据你定义的语法规则实现解析器，将Token流转换为CST结构：

• 解析器可以选择手写递归下降，或者使用LR/LL等自动生成的解析器，CST解析器建议做好错误恢复逻辑，遇到语法错误时不要直接终止，尽可能生成完整的CST结构
• 每个CST节点需要记录自己覆盖的Token范围、子节点列表，所有语法层面的元素都要在CST中对应到具体的节点或者Token，比如if关键字、条件表达式外层的括号、语句末尾的分号都要存在于CST中。

4. CST转AST #

对生成的CST进行遍历，提取语义信息生成AST：

• 遍历过程中过滤掉无意义的语法分隔符、关键字等冗余元素，只保留核心语义结构，比如解析变量声明语句let a = 1;时，CST包含let关键字、标识符a、等号、字面量1、分号，转AST后仅保留变量声明节点，包含变量名、初始值两个核心属性
• 可以将CST节点的源码位置信息绑定到对应的AST节点上，方便后续报错、代码定位等场景使用
• 对于CST中存在的语法错误节点，可以在AST中生成对应的错误节点，保证后续流程可以正常处理不完整的代码

解析器构建注意事项 #

如果不想从零手写完整的CST解析器，不同语言生态都有对应的成熟工具链可以使用：比如Rust生态可以直接基于CST构建通用库，搭配Ungrammar的语法定义快速生成解析器框架，只需要补全语法匹配逻辑即可。手写递归下降的CST解析器调试成本更低，适合小语种或者定制化语法的场景。

内容的提问来源于stack exchange，提问作者Steven Barragán