写文章
  1. 码农之家首页
  2. 前端教程

学习the-super-tiny-compiler

我心飞翔 • • 前端教程 • 阅读 4

学习链接：github.com/jamiebuilds…

词法分析——tokenizer

主要任务：从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元（token）形式

根据仓库代码的测试用例分析词法分析的作用

test("tokenizer", () => {
  const code = `(add 2 (subtract 4 2))`;
  const tokens = [
    { type:TokenTypes.Paren, value: "(" },
    { type:TokenTypes.Name, value: "add" },
    { type:TokenTypes.Number, value: "2" },
    { type:TokenTypes.Paren, value: "(" },
    { type:TokenTypes.Name, value: "subtract" },
    { type:TokenTypes.Number, value: "4" },
    { type:TokenTypes.Number, value: "2" },
    { type:TokenTypes.Paren, value: ")" },
    { type:TokenTypes.Paren, value: ")" },
  ];

  expect(tokenizer(code)).toEqual(tokens);
});
  1. 将代码字符串转换成语法单元(token)
  2. 提取代码中的基础语法组成部分
  3. 消除无意义字符,保留有意义语法单元
  4. 为语法分析提供输入
  5. 标识代码中的语法结构

词法分析实现

(add 2 (subtract 4 2))

主要处理内容：字母，数字，空格，括号

处理方式：

  1. 使用正则表达式识别语法单元:空格、字母、数字和括号
  2. 遍历代码字符串,匹配语法单元
  • 括号：type: Paren, value: 括号字符串
  • 字母： 正则匹配：/[a-z]/i ，type: Name, value: 字母
  • 数字： 正则匹配：/[0-9]/ ，type: Nmuber, value: 数字
  • 空格：正则匹配：/\s/，跳过
  1. 正则匹配成功后将生成的token放入tokens数组

语法分析——parse

语法解析的作用是生成AST来表示代码的语法结构,它位于编译过程的语法分析阶段,属于编译中间步骤的核心过程

主要任务： 从令牌（tokens）中创建出抽象语法树（AST）

根据仓库代码的测试用例分析parse的作用

test("parse", () =>{
    const tokens = [
        { type: TokenTypes.Paren, value: "(" },
        { type: TokenTypes.Name, value: "add" },
        { type: TokenTypes.Number, value: "2" },
        { type: TokenTypes.Paren, value: "(" },
        { type: TokenTypes.Name, value: "subtract" },
        { type: TokenTypes.Number, value: "4" },
        { type: TokenTypes.Number, value: "2" },
        { type: TokenTypes.Paren, value: ")" },
        { type: TokenTypes.Paren, value: ")" },
      ];
      const ast = {
        type: NodeTypes.Program,
        body: [
          {
            type: NodeTypes.CallExpression,
            name: "add",
            params: [
              {
                type: NodeTypes.NumberLiteral,
                value: "2",
              },
              {
                type: NodeTypes.CallExpression,
                name: "subtract",
                params: [
                  {
                    type: NodeTypes.NumberLiteral,
                    value: "4",
                  },
                  {
                    type: NodeTypes.NumberLiteral,
                    value: "2",
                  },
                ],
              },
            ],
          },
        ],
      };
      expect(parser(tokens)).toEqual(ast);
});
  1. 输入是令牌(tokens)数组,输出是抽象语法树(AST)。
  2. AST以嵌套的对象结构表示代码的语法结构
  3. 语法解析后的AST可用于代码生成、解释执行等后续处理。
  4. 用于后续代码生成、解释执行

parse实现

export function parser(tokens: Token[]) {
    let current = 0;
    const rootNode = createRootNode()

    function walk() {
        let token = tokens[current]
        if(token.type === TokenTypes.Number){
            current ++
            return createNumberNode(token.value)
        }

        if(token.type === TokenTypes.Paren && token.value === "("){
            token = tokens[++current]
            let node = createCallExpressionNode(token.value)

            token = tokens[++ current];
            while(!(token.type === TokenTypes.Paren && token.value === ")")){
                node.params.push(walk())
                token = tokens[current]
            }

            current ++
            return node
        }

        throw new Error(`不认识的token: ${token}`)
    }

    while (current < tokens.length){
        rootNode.body.push(walk())
    }
    return rootNode
};
  1. 判断token的类型并创建相应的节点：
  • 当token是数字类型时，创建数字的节点
  • 当token是字符串类型时，创建字符串的节点
  • 当token是左括号时，一般接下来就是要 解析到一个函数调用的语法结构：
  调用createCallExpressionNode来创建一个对应这个函数调用的AST节点
  循环调用函数判断创建节点，直到token是右括号
  如果token解析不了的话则抛出错误：throw new Error(`不认识的token: ${token}`)
  1. 判断tokens是否遍历完毕，没有则需要往下继续遍历

traverser 遍历 AST

主要任务：traverser 实现一个简单的AST遍历器，【判断一个节点是哪里的enter或者exit，并标识当前节点的类型和父节点的类型】

test("traverser", () => {
  const ast: RootNode = {
    type: NodeTypes.Program,
    body: [
      {
        type: NodeTypes.CallExpression,
        name: "add",
        params: [
          {
            type: NodeTypes.NumberLiteral,
            value: "2",
          },
          {
            type: NodeTypes.CallExpression,
            name: "subtract",
            params: [
              {
                type: NodeTypes.NumberLiteral,
                value: "4",
              },
              {
                type: NodeTypes.NumberLiteral,
                value: "2",
              },
            ],
          },
        ],
      },
    ],
  };

  const callCounts: Array<string | NodeTypes >[] = [];
  const visitor: Visitor = {
    Program: {
      enter(node, parent) {
        callCounts.push(["program-enter", node.type, ""]);
      },
      exit(node, parent) {
        callCounts.push(["program-exit", node.type, ""]);
      },
    },

    CallExpression: {
      enter(node, parent) {
        callCounts.push(["callExpression-enter", node.type, parent!.type]);
      },
      exit(node, parent) {
        callCounts.push(["callExpression-exit", node.type, parent!.type]);
      },
    },

    NumberLiteral: {
      enter(node, parent) {
        callCounts.push(["numberLiteral-enter", node.type, parent!.type]);
      },
      exit(node, parent) {
        callCounts.push(["numberLiteral-exit", node.type, parent!.type]);
      },
    },
  };

  traverser(ast, visitor);

   expect(callCounts).toEqual([    ["program-enter", NodeTypes.Program, ""],
    ["callExpression-enter", NodeTypes.CallExpression, NodeTypes.Program],
    ["numberLiteral-enter", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    ["numberLiteral-exit", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    [      "callExpression-enter",      NodeTypes.CallExpression,      NodeTypes.CallExpression,    ],
    ["numberLiteral-enter", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    ["numberLiteral-exit", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    ["numberLiteral-enter", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    ["numberLiteral-exit", NodeTypes.NumberLiteral, NodeTypes.CallExpression],
    ["callExpression-exit", NodeTypes.CallExpression, NodeTypes.CallExpression],
    ["callExpression-exit", NodeTypes.CallExpression, NodeTypes.Program],
    ["program-exit", NodeTypes.Program, ""],
  ]);
});

分析测试代码：

  1. 定义一个AST对象：包含一个 Program 节点和一些 CallExpression、NumberLiteral 子节点。
  2. 定义一个 callCounts 数组： 用于记录遍历过程中每个节点的进入和退出的调用。
  3. 定义一个 visitor 对象：包含了对每个节点类型的进入和退出时需要执行的回调函数。
  4. 最后调用 traverser 函数,传入 AST 对象和 visitor进行遍历。
    1. 在遍历过程中,会根据节点类型调用相应的 visitor.Program、visitor.CallExpression 等回调函数。这些回调函数会将当前访问的节点信息以及父节点信息记录到 callCounts 数组中。
  1. 这样就可以通过 callCounts 数组看到整个遍历过程中每个节点的进入和退出的顺序。

tarverser的实现

export function traverser(rootNode: RootNode, visitor: Visitor){
    // 1. 深度优先搜索
    // 2. visitor
    function traverseArray(array: ChildNode[],parent?:ParentNode) {
        array.forEach((node) => {
            traverseNode(node,parent)
        })
    }

    function traverseNode(node: ChildNode | RootNode, parent?:ParentNode) {
        const visitorObj = visitor[node.type]
        if(visitorObj){
            visitorObj.enter(node,parent);
        }
        switch (node.type) {
            case NodeTypes.NumberLiteral:
                break;
            case NodeTypes.CallExpression:
                traverseArray(node.params,node);
                break;
            case NodeTypes.Program:
                traverseArray(node.body,node);
                break;
        }
        if(visitorObj?.exit && visitorObj){
            visitorObj.exit(node,parent);
        }
    }

    traverseNode(rootNode)
}
  1. traverser函数就是一个遍历器，它接受两个参数：rootNode[ AST的根节点 ] 和visitor[ 一个对象，包含了访问AST节点时所要执行的操作 ] 。基于深度优先搜索算法，对AST进行遍历。
  2. traverseArray: 用于遍历一个节点的子节点数组，它接受一个数组和一个可选的父节点参数。该函数内部使用forEach方法遍历数组中的每个节点，并调用traverseNode函数对其进行遍历
  3. traverseNode： 用于遍历一个节点，并根据节点类型执行相应的操作。

在函数内部，首先从visitor对象中获取当前节点类型对应的操作，如果存在则执行其enter方法。

然后根据节点类型进行不同的处理，

  • 对于CallExpression类型的节点，会递归遍历其参数数组；
  • 对于Program类型的节点，会递归遍历其主体数组。
  • 在遍历完子节点后，如果当前节点类型对应的操作存在exit方法，则执行其exit方法。

transformer 转换 AST

主要任务：将一个AST转换为另一种形式的AST[新的 AST 可以更好地表示代码的结构和语义，便于进行代码重构、优化、分析、生成等操作]

首先定义了一个原始的AST，然后定义了一个期望的转换后的AST。接下来调用transformer函数对原始AST进行转换，并将转换后的AST与期望的AST进行比较，判断转换结果是否符合预期。

test("transformer", () => {
  const originalAST: RootNode = {
    type: NodeTypes.Program,
    body: [
      {
        type: NodeTypes.CallExpression,
        name: "add",
        params: [
          {
            type: NodeTypes.NumberLiteral,
            value: "2",
          },
          {
            type: NodeTypes.CallExpression,
            name: "subtract",
            params: [
              {
                type: NodeTypes.NumberLiteral,
                value: "4",
              },
              {
                type: NodeTypes.NumberLiteral,
                value: "2",
              },
            ],
          },
        ],
      },
    ],
  };

  const transformedAST = {
    type: NodeTypes.Program,
    body: [
      {
        type: "ExpressionStatement",
        expression: {
          type: "CallExpression",
          callee: {
            type: "Identifier",
            name: "add",
          },
          arguments: [
            {
              type: "NumberLiteral",
              value: "2",
            },
            {
              type: "CallExpression",
              callee: {
                type: "Identifier",
                name: "subtract",
              },
              arguments: [
                {
                  type: "NumberLiteral",
                  value: "4",
                },
                {
                  type: "NumberLiteral",
                  value: "2",
                },
              ],
            },
          ],
        },
      },
    ],
  };

  expect(transformer(originalAST)).toEqual(transformedAST);
});

对于originalAST：

  1. type： 表示该 AST 节点的类型 [不同的节点类型有不同的属性和语义，用于表示不同的语法结构和语义]
  2. name: 表示函数的名称
  3. params: 通常用于表示函数的参数列表
  4. value: 表示 AST 中的字面量节点的值 [只有特定的节点类型才具有 value 属性]

对于transformedAST：

  1. ExpressionStatement: 用于表示该对象是一个表达式语句
  2. callee 属性是一个对象，它表示被调用的函数。[包含一个 type 属性和一个 name 属性]
  • type 属性的值是字符串 “Identifier” ，用于表示该对象是一个标识符
  • name 属性的值是字符串 “add” ，用于表示被调用的函数的名称
  1. arguments 属性是一个数组，它表示函数调用时传递的参数列表。[包含两个对象，分别表示传递的两个参数]

这两个对象中都包含一个 type 属性和一个 value 属性

  • type 属性的值是字符串 “NumberLiteral” ，用于表示该对象是一个数字字面量
  • value 属性的值是字符串 “2” 和 “4” ，分别表示传递的两个参数的值

transformer的实现

export function transformer (ast: RootNode){
    const newAst = {
        type: NodeTypes.Program,
        body: []
    };

    ast.context = newAst.body

    traverser(ast,{
        CallExpression: {
            enter(node,parent) {
                // 如果节点类型是CallExpression,即函数调用表达式
                if(node.type === NodeTypes.CallExpression) {
                    // 构造一个新的CallExpression节点
                    let expression: any = {
                        type: "CallExpression",
                        callee: {  // callee是调用的函数标识符
                            type: "Identifier",
                            name: node.name
                        },
                        arguments: [],   // arguments为参数占位
                    };
                    
                    node.context = expression.arguments;

                    // 如果父节点不是CallExpression,则再包一层ExpressionStatement
                    if(parent?.type !== NodeTypes.CallExpression){
                        expression = {
                            type: "ExpressionStatement",
                            expression,
                        }
                    }

                    // 将ExpressionStatement推入父节点context中
                    parent?.context?.push(expression)
                }
            }
        },

        NumberLiteral: {
            enter(node, parent) {
                if(node.type === NodeTypes.NumberLiteral) {
                    const numberNode: any = {
                        type: "NumberLiteral",
                        value: node.value
                    };

                    parent?.context?.push(numberNode)
                }
            }
        }
    })

    return newAst
}
  1. ast.context = newAst.body [将原始 AST 的 context 属性指向新的 AST 的 body 属性，这样在遍历原始 AST 的过程中，可以方便地将新的节点添加到新的 AST 中]

对于 CallExpression,递归求值 callee 和 arguments,然后执行调用

对于 NumberLiteral 直接返回 value 值

codegen

主要任务：将 AST 转换成 JavaScript 代码

test("codegen", () => {
  const ast = {
    type: NodeTypes.Program,
    body: [
      {
        type: "ExpressionStatement",
        expression: {
          type: "CallExpression",
          callee: {
            type: "Identifier",
            name: "add",
          },
          arguments: [
            {
              type: "NumberLiteral",
              value: "2",
            },
            {
              type: "CallExpression",
              callee: {
                type: "Identifier",
                name: "subtract",
              },
              arguments: [
                {
                  type: "NumberLiteral",
                  value: "4",
                },
                {
                  type: "NumberLiteral",
                  value: "2",
                },
              ],
            },
          ],
        },
      },
    ],
  };

  expect(codegen(ast)).toMatchInlineSnapshot('"add(2, subtract(4, 2));"');
});

codegen实现

export function codegen (node) {
    switch (node.type) {
        case "Program":
            return node.body.map(codegen).join("");
        case "ExpressionStatement":
            return codegen(node.expression) + ";"
        case "NumberLiteral":
            return node.value;
        case "CallExpression":
            return (
                node.callee.name + "(" + node.arguments.map(codegen).join(", ") + ")"
            );
    }
}

接受一个 AST 对象作为参数，将其转换为 JavaScript 代码字符串并返回。

根据节点类型进行不同的处理：

  1. 对于 Program 节点，它将遍历 AST 的 body 属性，并对每个子节点递归调用 codegen 函数，最后将它们连接成一个字符串
  2. 对于 ExpressionStatement 节点，它将递归调用 codegen 函数处理 expression 属性，并在最后添加一个分号。
  3. 对于 NumberLiteral 节点，它将返回节点的 value 属性。
  4. 对于 CallExpression 节点，它将使用节点的 callee 属性的 name 属性作为函数名，并将 arguments 属性中的每个子节点递归调用 codegen 函数处理，最后将它们连接成一个字符串，用括号包裹。

整合实现——compiler

最终任务： 将 Lisp 代码编译成 JavaScript 代码

Lisp 是一种基于列表处理的编程语言，它的语法非常简单，只有两种数据类型：原子和列表。

Lisp 代码由原子和列表组成，原子可以是数字、字符串或符号，而列表则是用括号括起来的一组原子或列表。

test("compiler", () => {
  const code = `(add 2 (subtract 4 2))`;

  expect(compiler(code)).toBe("add(2, subtract(4, 2));");
});

整合

学习the-super-tiny-compiler

export function compiler(code: string){
    const tokens = tokenizer(code)
    const ast = parser(tokens)
    const transformedAST = transformer(ast)
    return codegen(transformedAST) 
}

原文链接：https://juejin.cn/post/7321271017430564916 作者：阿皮想当小怪兽

赞 (0)
我心飞翔我心飞翔
0 0
上一篇 2024年1月8日 下午4:42
下一篇 2024年1月8日 下午4:53

相关推荐

发表回复

登录后才能评论