编译原理：抽象语法树，AST

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

编译原理系列

全文基于Abstract syntax tree

概念

抽象语法树（Abstract Syntax Tree，AST），或简称语法树，用树来表示由某特定语言写出的文本的抽象语法结构。

…, a tree representation of the abstract syntactic structure of text (often source code) written in a formal language.

首先，它是一个树形结构；它的每个节点表示文本中的一种构造方法，比如“while”、“return”。

abstract 是指该树仅体现结构等重要信息，并不展现文本语法的所有细节。相对应的，分析树（parse tree，concrete syntax tree）生成 AST。

示例

Euclidean algorithm，用来求两个正整数最大公约数的算法

while b ≠ 0:
    if a > b:
        a := a - b
    else:
        b := b - a
return a

上述代码可以用 AST 表示为，

有了源码，为啥还要搞个 AST

AST 通常是编译器语法分析的结果，被用来表示代码结构。作为 IR（intermediate representation），AST 存在于编译器的多个工作阶段，对最终结果有很大的影响：

• AST 可以被编辑、添加元素相关的信息。而这在源码无法隐式地完成。
• AST 相较于源码丢掉了无关紧要的符号（大括号、分号等）
• AST 通常包含一些有用的额外信息。因为经历编译器的多个分析阶段，比如每个元素的位置可以被保存，这可以用来打印错误信息
• 实现上下文无关。编程语言通常是上下文无关（Context-Free Grammar）的， AST 可以通过上下文来分析、实现其目标行为。比如以下几种情况：
  • 消除语法歧义
  • 鸭子类型（duck typing）
  • 重载运算符

对 AST 的要求

AST 的设计与编译器的设计紧密关联，因此有以下几项核心要求：

• 变量类型以及其声明在源码中的位置需要被保留
• 可执行语句的顺序需要被显式表达
• 二元运算的左右分量需要被保存以及正确识别（推广，也要能灵活处理包含更多子元素的操作）
• 赋值语句的标识符和所赋的值需要被保存

此外，为了验证编译器，AST 需要可以被反向解析为源代码，且和源代码的内容和运行足够相似。

应用

• 语义分析。AST 被用来检查程序元素或者编程语言是否被正确使用；也能通过 AST 生成符号表。
• 生成 IR。通过 AST 生成 IR，进一步作为最终机器码生成的基础。

都看到这儿了，不如关注每日推送的“科文路”、互动起来~