AST-抽象语法树

编译器的底层原理 AST

编译器介绍：它会将用某种编程语言写成的源代码，转换成另一种编程语言。编译器（compiler）是一种用于将源代码（通常是高级编程语言编写的代码）翻译成目标代码（如机器语言或中间代码）的软件工具。目标代码通常可以直接在计算机上执行，或者在特定的运行环境中执行。编译器的主要目的是使程序员编写的源代码能够在计算机硬件上运行。

编译器实现的思路

Parsing

这一部分主要实现的功能是将源码转换为抽象语法树

解析通常分为两个阶段：词法分析（Lexical Analysis）和语法分析（Syntactic Analysis）。

词法分析 将原始代码拆分成称为标记（tokens）的部分，这个过程由一个称为分词器（tokenizer）或词法分析器（lexer）的东西完成。

标记是描述语法中独立部分的小对象的数组。它们可以是数字、标签、标点符号、操作符等。
语法分析 将标记重新格式化为描述语法各部分及其相互关系的表示形式。这被称为中间表示或抽象语法树（AST）。

抽象语法树（AST）是一个深度嵌套的对象，它以一种易于处理并包含大量信息的方式表示代码。

对于以下语法：

(add 2 (subtract 4 2))

Tokens应该是这样的这样：

[
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'add'      },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'subtract' },
  { type: 'number', value: '4'        },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: ')'        },
  { type: 'paren',  value: ')'        },
]

而抽象语法树（AST）可能看起来像这样：

{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [{
      type: 'NumberLiteral',
      value: '2',
    }, {
      type: 'CallExpression',
      name: 'subtract',
      params: [{
        type: 'NumberLiteral',
        value: '4',
      }, {
        type: 'NumberLiteral',
        value: '2',
      }]
    }]
  }]
}

Transformation

这一部分主要实现的功能是对初始的抽象语法树进行操作使其变成我们所期望的抽象语法树。

同样，这个阶段只是接收上一步生成的AST并对其进行更改。它可以在相同的语言中操作AST，也可以将其转换为完全新的语言。

让我们看看如何转换一个AST。

你可能会注意到，我们的AST中有一些看起来非常相似的元素。这些对象都有一个type属性。每个这样的对象都被称为AST节点。这些节点上有定义的属性，用来描述树的一个独立部分。

我们可以有一个表示“NumberLiteral”（数字字面量）的节点：

{
  type: 'NumberLiteral',
  value: '2',
}

或者一个表示“CallExpression”（调用表达式）的节点：

{
  type: 'CallExpression',
  name: 'subtract',
  params: [...嵌套节点在这里...],
}

在转换AST时，我们可以通过添加/移除/替换属性来操作节点，我们可以添加新节点，移除节点，或者保留现有的AST不变，基于它创建一个全新的AST。

由于我们目标是一种新语言，因此我们将专注于创建一个特定于目标语言的全新AST。

Code Generation

将新的语法树转换成新的代码

Welcome to Yuyang's Blog