AST (Abstract Syntax Tree)

title	Content
AST	AST Definition , Usage mode , principle
AST	AST Example
AST	AST application

---

AST Definition

• AST(Abstract Syntax Tree) Abstract syntax tree , abbreviation AST, It is source code ( That is to say, it is not only applied to JavaScript, It also applies to other languages , for example : Python,Rust etc. ) An abstract representation of a grammatical structure .
• It represents the syntax structure of programming language in the form of tree , Each node on the tree represents a structure in the source code .
• grammar 【 abstract 】: It means that the grammar here does not express every detail that appears in the real grammar .

---

AST Usage mode

• Our common lexical parser and parser ( It can be JavaScript Convert the source code into AST), For example, in the following example esprima, Of course, there are other , for example : acorn、shift、traceur etc.

purpose

• AST Abstract syntax trees are widely used , such as :

• vscode、atom、sublime Medium Code highlighting 、 Code formatting 、 Error message 、 Code auto completion ;

• eslint、prettier Check for code errors or styles ;

• babel translation ES6 To ES5
  …

• So if you want to optimize JavaScript Compilation and running speed ,AST It is essential to understand .

---

AST principle

Compilation process

• JavaScript The process of execution starts with reading JavaScript In the document Character stream , Secondly through Lexical analyzer generates token, After that parsers (Parser) Generate AST Trees , And then finally convert to Machine code perform .

var name = "jackdan";

• The first step is to read the above character stream 'var name = "jackdan"';
• Step 2 word segmentation : take 'var name = "jackdan"' The whole code string is divided into the smallest array of syntax units ; as follows :

[
  {
     type: 'Keyword', value: 'var' },
  {
     type: 'Identifier', value: 'name' },
  {
     type: 'Punctuator', value: '=' },
  {
     type: 'String', value: '"jackdan"' }
]

• The third step is grammatical analysis : On the basis of word segmentation, establish and analyze the relationship between grammatical units ; as follows :

- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
    
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
    
          type: "VariableDeclarator"
          - id: Identifier {
    
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
    
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

• Let's focus on combing the principles Lexical analysis and Syntax analysis , Those who have been exposed to these two should not be too strange .

Lexical analysis

• Lexical analysis ： Also known as scanning (scanner), Simply call
  next() Method , Read characters one letter at a time , And then with the defined JavaScript Key characters compare , Generate corresponding Token.Token It's a The smallest indivisible unit . for example :

var name = "jackdan";
//  Read first v, Then continue to read a, Last read r Form a var
// var These three characters are recognized as JavaScript Keywords in , As a whole , Semantically, it can no longer be decomposed , Therefore, we also regard it as a Token

• From the above code example, it is not difficult to get , Lexical analyzer , Every The keyword is a Token, Every The identifier is a Token, Every The operator is a Token, Every Punctuation is also a Token. besides , Will Filter out comments and white space characters in the program （ A newline 、 Space 、 Box drawings, etc ）.
• Final , We see that the whole code is divided into one tokens list （ Or a one-dimensional array ）.

[
  {
     type: 'Keyword', value: 'var' },
  {
     type: 'Identifier', value: 'name' },
  {
     type: 'Punctuator', value: '=' },
  {
     type: 'String', value: '"jackdan"' }
]

Syntax analysis

• Grammatical analysis is to put Lexical analysis tokns The list is transformed into an abstract syntax tree structure with grammatical meaning . Go at the same time Validation Syntax ( The highlighted 、 Automatic completion, etc ), If there is a mistake in grammar , Throw a syntax error .

- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
    
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
    
          type: "VariableDeclarator"
          - id: Identifier {
    
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
    
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

---

AST example

//  Source code 
var name = "jackdan";

// AST  Abstract syntax tree 
/** * * +-----------+ * | assign(=) | * +-----------+ * / \ * / \ * +----+ +---------+ * |name| |"jackdan"| * +----+ +---------+ * */

//  Run the output structure code 
- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
          type: "VariableDeclarator"
          - id: Identifier {
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

> var esprima = require('esprima');
> var program = 'var name = "jackdan"';

> esprima.tokenize(program);
[
  {
     type: 'Keyword', value: 'var' },
  {
     type: 'Identifier', value: 'name' },
  {
     type: 'Punctuator', value: '=' },
  {
     type: 'String', value: '"jackdan"' }
]

> esprima.parse(program);
Script {
    
  type: 'Program',
  body: [
    VariableDeclaration {
    
      type: 'VariableDeclaration',
      declarations: [Array],
      kind: 'var'
    }
  ],
  sourceType: 'script'
}

Thinking in JackDan