kc‘s blog

抽象语法树相关

志宇 郑's photo
志宇 郑
·

5 min read

抽象语法树

大多数编译器分为三个主要阶段：解析，转换和代码生成

  1. 解析正在获取原始代码并将其转换为更抽象的代码 代码的表示形式。
  2. 转换采取这种抽象表示并操纵去做 编译器想要的任何东西。
  3. 代码生成采用代码的转换表示形式， 将其转换为新代码。

解析

解析通常分为两个阶段：词法分析和句法分析。

  1. 词法分析提取原始代码并将其拆分为标记器（或词法分析器）的事物称为标记。
  2. 标记器是由微小的小物体组成的数组，描述了一个孤立的片断的语法。它们可以是数字，标签，标点符号，运算符，任何。
  3. 句法分析提取标记器并将其重新格式化为描述语法的每个部分及其关系的表示形式彼此。这称为中间表示或抽象语法树。
  4. 抽象语法树，简称AST，是一个深层嵌套的对象，以易于使用的方式表示代码，并告诉我们很多信息。

对于以下代码：

(add 2 (subtract 4 2))=>...=>add(2, subtract(4, 2));

标记器像这样:

[
    { 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: ')'        },
]

抽象语法树像这样:

{    
   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',
     }]
   }]
  }]
}

转换

编译器的下一个阶段类型是转换。同样，这只是从最后一步获取AST并对其进行更改。它可以操纵 AST可以使用相同的语言，也可以将其翻译成全新的语言语言。

您可能会注意到，我们的AST中包含看起来非常相似的元素。 这些对象具有type属性。这些都被称为AST节点。 这些节点已在其上定义了描述以下内容的属性：树的孤立部分(isolated part of the tree)。

//NumberLiteral节点
{
    type: 'NumberLiteral',
    value: '2',
}
//CallExpression节点
{
    type: 'CallExpression',
    name: 'subtract',
    params: [...其他嵌套节点...],
}

转换AST时，我们可以通过添加/删除/替换属性， 我们可以添加新节点，删除节点或我们可以不使用现有的AST(如果我们的目标是新语言则可以把重点放在创建一种特定于目标语言的AST)， 而可以创建一个全新的基于AST的在上面。

遍历

为了浏览所有节点我们需要使用深度优先遍历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',
     }]
   }]
  }]
}

.png)

这样我们就可以对AST中的元素进行操作

访问者对象

创建一个访问者对象。 该对象具有接受不同节点类型的方法。

这样当我们进行遍历时需要输入匹配的节点和父节点

var visitor = {
    NumberLiteral(node, parent) {},
    CallExpression(node, parent) {},
};

但同时我们也需要一个用来退出的方法

-> Program (enter)
  -> CallExpression (enter)
    -> Number Literal (enter)
    <- Number Literal (exit)
    -> Call Expression (enter)
       -> Number Literal (enter)
       <- Number Literal (exit)
       -> Number Literal (enter)
       <- Number Literal (exit)
    <- CallExpression (exit)
  <- CallExpression (exit)
<- Program (exit)

var visitor = {
    NumberLiteral: {
        enter(node, parent) {},
        exit(node, parent) {},
    }
};

代码生成

编译器的最后阶段是代码生成。有时候编译器会做与转换重叠的东西，但大部分是代码生成只是意味着用我们的AST并字符串化代码。

我们的代码生成器将知道如何有效的打印所有不同的内容AST的节点类型，它将递归调用自身以打印嵌套节点，直到所有内容都打印成一长串代码。

一个小栗子

1.解析

将代码分成标记器数组

1.解析function tokenizer(input){//接收一个代码字符串
    let current = 0;//用一个光标变量跟踪我们在代码中的位置
    let tokens = [];//初始化标记器数组
     while(current<input.length){
        let char = input[current];//把当前字符储存在char中
        if(char === '('){//检查是否有左括号
            tokens.push({
                type: "paren",
                value: "(",
            })
            current++;
            continue;//继续遍历
        }
        if (char === ")") {//检查右括号
            tokens.push({
                type: "paren",
                value: ")",
            });
            current++;
            continue;
        }
        let WHITSPACE = /\s/;
        if(WHITSPACE.test(char)){
            current++;
            continue;//跳过空格的处理 
        }
        //数字类型
        let NUMBERS = /[0-9]/;
        if (NUMBERS.test(char)) {
            let value = "";
            while (NUMBERS.test(char)) {
                value += char;
                char = input[++current];
            }
            tokens.push({ type: "number", value });
            continue;//拿到连续的数字
        }
        //字符串类型
        if (char === '"') {
            let value = "";
            char = input[++current];
            while (char !== '"') {
                value += char;
                char = input[++current];
            }
            char = input[++current];
            tokens.push({ type: "string", value });
            continue;//跳过开头结尾的双引号提取字符串
        }
        //名称类型
        let LETTERS = /[a-z]/i;
        if (LETTERS.test(char)) {
            let value = "";
            while (LETTERS.test(char)) {
                value += char;
                char = input[++current];
            }
            tokens.push({ type: "name", value });
            continue;
        }
        throw new TypeError("I dont know what this character is: " + char);//错误字符处理
    }
    return tokens;//返回标记器数组
}

2. 转换

[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }

function parser(tokens){
    let current = 0;//光标
    //递归
    function walk(){
        let token = tokens[current];//拿到标记器
        //按类型分类
        if (token.type === "number") {
            current++;
            return {
                type: "NumberLiteral",
                value: token.value,
            };//返回一个AST节点
        }
        if (token.type === "string") {
            current++;
            return {
                type: "StringLiteral",
                value: token.value,
            };
        }
        if (token.type === "paren" && token.value === "(") {
            token = tokens[++current];//跳过括号
            let node = {
                type: "CallExpression",
                name: token.value,
                params: [],
            };//创建基本节点
            token = tokens[++current];//跳过名称
            while (
                token.type !== "paren" ||
                (token.type === "paren" && token.value !== ")")
            ) {
                node.params.push(walk());
                token = tokens[current];
            }
            current++;
            return node;
        }
        throw new TypeError(token.type);//错误处理
    }
    let ast = {
        type: "Program",
        body: [],
    };//创建AST根节点
    while (current < tokens.length) {
        ast.body.push(walk());
    }//遍历推入AST节点
    return ast;
}

2.1遍历器、访问者对象

function traverser(ast,visitor){
    //遍历数组，并调用traverseNode
    function traverseArray(array, parent) {
        array.forEach((child) => {
            traverseNode(child, parent);
        });
    }
    function traverseNode(node, parent) {
        let methods = visitor[node.type];
        if (methods && methods.enter) {
            methods.enter(node, parent);
        }//检测是否定义并进入
        switch (node.type) {
            case "Program":
                traverseArray(node.body, node);
                break;
            case "CallExpression":
                traverseArray(node.params, node);
                break;
            case "NumberLiteral":
            case "StringLiteral":
                break;
            default:
                throw new TypeError(node.type);//错误处理
        }
        if (methods && methods.exit) {
            methods.exit(node, parent);
        }
    }
    traverseNode(ast, null);//启动遍历器
}

2.2转化的AST

 * ----------------------------------------------------------------------------
 *   Original AST                     |   Transformed AST
 * ----------------------------------------------------------------------------
 *   {                                |   {
 *     type: 'Program',               |     type: 'Program',
 *     body: [{                       |     body: [{
 *       type: 'CallExpression',      |       type: 'ExpressionStatement',
 *       name: 'add',                 |       expression: {
 *       params: [{                   |         type: 'CallExpression',
 *         type: 'NumberLiteral',     |         callee: {
 *         value: '2'                 |           type: 'Identifier',
 *       }, {                         |           name: 'add'
 *         type: 'CallExpression',    |         },
 *         name: 'subtract',          |         arguments: [{
 *         params: [{                 |           type: 'NumberLiteral',
 *           type: 'NumberLiteral',   |           value: '2'
 *           value: '4'               |         }, {
 *         }, {                       |           type: 'CallExpression',
 *           type: 'NumberLiteral',   |           callee: {
 *           value: '2'               |             type: 'Identifier',
 *         }]                         |             name: 'subtract'
 *       }]                           |           },
 *     }]                             |           arguments: [{
 *   }                                |             type: 'NumberLiteral',
 *                                    |             value: '4'
 * ---------------------------------- |           }, {
 *                                    |             type: 'NumberLiteral',
 *                                    |             value: '2'
 *                                    |           }]
 *  (sorry the other one is longer.)  |         }
 *                                    |       }
 *                                    |     }]
 *                                    |   }
 * ----------------------------------------------------------------------------

function transformer(ast) {
    let newAst = {
        type: "Program",
        body: [],
    };
    ast._context = newAst.body;//创建一个引用
    traverser(ast, {
        NumberLiteral: {
            enter(node, parent) {
                parent._context.push({
                    type: "NumberLiteral",
                    value: node.value,
                });
            },
        },
        StringLiteral: {
            enter(node, parent) {
                parent._context.push({
                    type: "StringLiteral",
                    value: node.value,
                });
            },
        },
        CallExpression: {
            enter(node, parent) {
                let expression = {
                    type: "CallExpression",
                    callee: {
                        type: "Identifier",
                        name: node.name,
                    },
                    arguments: [],
                };
                node._context = expression.arguments;
                if (parent.type !== "CallExpression") {
                    expression = {
                        type: "ExpressionStatement",
                        expression: expression,
                    };
                }
                parent._context.push(expression);
            },
        },
    });//调用遍历器
    return newAst;
}

代码生成器

function codeGenerator(node) {
    switch (node.type) {
        case "Program":
            return node.body.map(codeGenerator).join("\n");//使用换行把他们串起来
        case "ExpressionStatement":
            return (
                codeGenerator(node.expression) + ";" // << (...because we like to code the *correct* way)
            );
        case "CallExpression":
            return (
                codeGenerator(node.callee) +
                "(" +
                node.arguments.map(codeGenerator).join(", ") +
                ")"
            );
        case "Identifier":
            return node.name;
        case "NumberLiteral":
            return node.value;
        case "StringLiteral":
            return '"' + node.value + '"';
        default:
            throw new TypeError(node.type);
    }
}

整合代码

function compiler(input) {
    let tokens = tokenizer(input);
    let ast = parser(tokens);
    let newAst = transformer(ast);
    let output = codeGenerator(newAst);
    return output;
}