模拟实现

2023年06月11日

柏拉文

越努力，越幸运

一、实现

---

1.1 /src/tokenizer.ts

import { isWhiteSpace, isAlpha, isDigit, isUnderline } from "./utils";

export enum TokenType {
  Let = "Let",
  Const = "Const",
  Var = "Var",
  Assign = "Assign",
  Function = "Function",
  Number = "Number",
  Operator = "Operator",
  Identifier = "Identifier",
  LeftParen = "LeftParen",
  RightParen = "RightParen",
  LeftCurly = "LeftCurly",
  RightCurly = "RightCurly",
  Comma = "Comma",
  Dot = "Dot",
  Semicolon = "Semicolon",
  StringLiteral = "StringLiteral",
  Return = "Return",
  Import = "Import",
  Export = "Export",
  Default = "Default",
  From = "From",
  As = "As",
  Asterisk = "Asterisk",
}

export enum ScanMode {
  Normal,
  Identifier,
  StringLiteral,
  Number,
}

export type Token = {
  type: TokenType;
  value?: string;
  start: number;
  end: number;
  raw?: string;
};

// 策略模式
const TOKENS_GENERATOR: Record<string, (...args: any[]) => Token> = {
  let(start: number) {
    return { type: TokenType.Let, value: "let", start, end: start + 3 };
  },
  const(start: number) {
    return { type: TokenType.Const, value: "const", start, end: start + 5 };
  },
  var(start: number) {
    return { type: TokenType.Var, value: "var", start, end: start + 3 };
  },
  assign(start: number) {
    return { type: TokenType.Assign, value: "=", start, end: start + 1 };
  },
  import(start: number) {
    return {
      type: TokenType.Import,
      value: "import",
      start,
      end: start + 6,
    };
  },
  export(start: number) {
    return {
      type: TokenType.Export,
      value: "export",
      start,
      end: start + 6,
    };
  },
  from(start: number) {
    return {
      type: TokenType.From,
      value: "from",
      start,
      end: start + 4,
    };
  },
  as(start: number) {
    return {
      type: TokenType.As,
      value: "as",
      start,
      end: start + 2,
    };
  },
  asterisk(start: number) {
    return {
      type: TokenType.Asterisk,
      value: "*",
      start,
      end: start + 1,
    };
  },
  default(start: number) {
    return {
      type: TokenType.Default,
      value: "default",
      start,
      end: start + 7,
    };
  },
  number(start: number, value: string) {
    return {
      type: TokenType.Number,
      value,
      start,
      end: start + value.length,
      raw: value,
    };
  },
  function(start: number) {
    return {
      type: TokenType.Function,
      value: "function",
      start,
      end: start + 8,
    };
  },
  return(start: number) {
    return {
      type: TokenType.Return,
      value: "return",
      start,
      end: start + 6,
    };
  },
  operator(start: number, value: string) {
    return {
      type: TokenType.Operator,
      value,
      start,
      end: start + value.length,
    };
  },
  comma(start: number) {
    return {
      type: TokenType.Comma,
      value: ",",
      start,
      end: start + 1,
    };
  },
  leftParen(start: number) {
    return { type: TokenType.LeftParen, value: "(", start, end: start + 1 };
  },
  rightParen(start: number) {
    return { type: TokenType.RightParen, value: ")", start, end: start + 1 };
  },
  leftCurly(start: number) {
    return { type: TokenType.LeftCurly, value: "{", start, end: start + 1 };
  },
  rightCurly(start: number) {
    return { type: TokenType.RightCurly, value: "}", start, end: start + 1 };
  },
  dot(start: number) {
    return { type: TokenType.Dot, value: ".", start, end: start + 1 };
  },
  semicolon(start: number) {
    return { type: TokenType.Semicolon, value: ";", start, end: start + 1 };
  },
  stringLiteral(start: number, value: string, raw: string) {
    return {
      type: TokenType.StringLiteral,
      value,
      start,
      end: start + value.length + 2,
      raw,
    };
  },
  identifier(start: number, value: string) {
    return {
      type: TokenType.Identifier,
      value,
      start,
      end: start + value.length,
    };
  },
};

type SingleCharTokens = "(" | ")" | "{" | "}" | "." | ";" | "," | "*" | "=";

const KNOWN_SINGLE_CHAR_TOKENS = new Map<
  SingleCharTokens,
  typeof TOKENS_GENERATOR[keyof typeof TOKENS_GENERATOR]
>([
  ["(", TOKENS_GENERATOR.leftParen],
  [")", TOKENS_GENERATOR.rightParen],
  ["{", TOKENS_GENERATOR.leftCurly],
  ["}", TOKENS_GENERATOR.rightCurly],
  [".", TOKENS_GENERATOR.dot],
  [";", TOKENS_GENERATOR.semicolon],
  [",", TOKENS_GENERATOR.comma],
  ["*", TOKENS_GENERATOR.asterisk],
  ["=", TOKENS_GENERATOR.assign],
]);

const QUOTATION_TOKENS = ["'", '"', "`"];

const OPERATOR_TOKENS = [
  "+",
  "-",
  "*",
  "/",
  "%",
  "^",
  "&",
  "|",
  "~",
  "<<",
  ">>",
];

export class Tokenizer {
  private _tokens: Token[] = [];
  private _currentIndex: number = 0;
  private _source: string;
  private _scanMode = ScanMode.Normal;
  constructor(input: string) {
    this._source = input;
  }

  scanIndentifier(): void {
    this._setScanMode(ScanMode.Identifier);
    // 继续扫描，直到收集完整的单词
    let identifier = "";
    let currentChar = this._getCurrentChar();
    const startIndex = this._currentIndex;
    while (
      isAlpha(currentChar) ||
      isDigit(currentChar) ||
      isUnderline(currentChar)
    ) {
      identifier += currentChar;
      this._currentIndex++;
      currentChar = this._getCurrentChar();
    }
    let token;
    // 1. 结果为关键字
    if (identifier in TOKENS_GENERATOR) {
      token =
        TOKENS_GENERATOR[identifier as keyof typeof TOKENS_GENERATOR](
          startIndex
        );
    }
    // 2. 结果为标识符
    else {
      token = TOKENS_GENERATOR["identifier"](startIndex, identifier);
    }
    this._tokens.push(token);
    this._resetScanMode();
  }

  scanStringLiteral(): void {
    this._setScanMode(ScanMode.StringLiteral);
    const startIndex = this._currentIndex;
    let currentChar = this._getCurrentChar();
    // 记录引号
    const startQuotation = currentChar;
    // 继续找字符串
    this._currentIndex++;
    let str = "";
    currentChar = this._getCurrentChar();
    while (currentChar && currentChar !== startQuotation) {
      str += currentChar;
      this._currentIndex++;
      currentChar = this._getCurrentChar();
    }
    const token = TOKENS_GENERATOR.stringLiteral(
      startIndex,
      str,
      `${startQuotation}${str}${startQuotation}`
    );
    this._tokens.push(token);
    this._resetScanMode();
  }

  _scanNumber(): void {
    this._setScanMode(ScanMode.Number);
    const startIndex = this._currentIndex;
    let number = "";
    let currentChar = this._getCurrentChar();
    let isFloat = false;
    // 如果是数字，则继续扫描
    // 需要考虑到小数点
    while (isDigit(currentChar) || (currentChar === "." && !isFloat)) {
      if (currentChar === ".") {
        isFloat = true;
      }
      number += currentChar;
      this._currentIndex++;
      currentChar = this._getCurrentChar();
    }
    if (isFloat && currentChar === ".") {
      throw new Error('Unexpected character "."');
    }
    const token = TOKENS_GENERATOR.number(startIndex, number);
    this._tokens.push(token);
    this._resetScanMode();
  }

  tokenize(): Token[] {
    // 扫描
    while (this._currentIndex < this._source.length) {
      let currentChar = this._source[this._currentIndex];
      const startIndex = this._currentIndex;
      // 1. 判断是否是分隔符
      if (isWhiteSpace(currentChar)) {
        this._currentIndex++;
        continue;
      }
      // 2. 判断是否是字母
      else if (isAlpha(currentChar)) {
        this.scanIndentifier();
        continue;
      }
      // 3. 判断是否是单字符 () {} . ; *
      else if (KNOWN_SINGLE_CHAR_TOKENS.has(currentChar as SingleCharTokens)) {
        // * 字符特殊处理
        if (currentChar === "*") {
          // 前瞻，如果是非 import/export，则认为是二元运算符，避免误判
          const previousToken = this._getPreviousToken();
          if (
            previousToken.type !== TokenType.Import &&
            previousToken.type !== TokenType.Export
          ) {
            this._tokens.push(
              TOKENS_GENERATOR.operator(startIndex, currentChar)
            );
            this._currentIndex++;
            continue;
          }
          // 否则按照 import/export 中的 * 处理
        }
        const token = KNOWN_SINGLE_CHAR_TOKENS.get(
          currentChar as SingleCharTokens
        )!(startIndex);
        this._tokens.push(token);
        this._currentIndex++;
      }
      // 4. 判断是否为引号
      else if (QUOTATION_TOKENS.includes(currentChar)) {
        this.scanStringLiteral();
        // 跳过结尾的引号
        this._currentIndex++;
        continue;
      }
      // 5. 判断二元计算符
      else if (
        OPERATOR_TOKENS.includes(currentChar) &&
        this._scanMode === ScanMode.Normal
      ) {
        this._tokens.push(TOKENS_GENERATOR.operator(startIndex, currentChar));
        this._currentIndex++;
        continue;
      } else if (
        OPERATOR_TOKENS.includes(currentChar + this._getNextChar()) &&
        this._scanMode === ScanMode.Normal
      ) {
        this._tokens.push(
          TOKENS_GENERATOR.operator(
            startIndex,
            currentChar + this._getNextChar()
          )
        );
        this._currentIndex += 2;
        continue;
      }
      // 6. 判断数字
      else if (isDigit(currentChar)) {
        this._scanNumber();
        continue;
      }
    }
    this._resetCurrentIndex();
    return this._getTokens();
  }

  private _getCurrentChar() {
    return this._source[this._currentIndex];
  }

  private _getNextChar() {
    if (this._currentIndex + 1 < this._source.length) {
      return this._source[this._currentIndex + 1];
    }
    return "";
  }

  private _resetCurrentIndex() {
    this._currentIndex = 0;
  }

  private _getTokens() {
    return this._tokens;
  }

  private _getPreviousToken() {
    // 前瞻 Token
    if (this._tokens.length > 0) {
      return this._tokens[this._tokens.length - 1];
    }
    throw new Error("Previous token not found");
  }

  private _setScanMode(mode: ScanMode) {
    this._scanMode = mode;
  }

  private _resetScanMode() {
    this._scanMode = ScanMode.Normal;
  }
}

1.2 /src/parser.ts

import { Token, TokenType } from "./tokenizer";
import {
  BlockStatement,
  CallExpression,
  Expression,
  ExpressionStatement,
  FunctionDeclaration,
  FunctionType,
  Identifier,
  ImportDeclaration,
  ImportSpecifiers,
  Literal,
  MemberExpression,
  NodeType,
  Program,
  Statement,
  VariableDeclaration,
  VariableDeclarator,
  VariableKind,
  ReturnStatement,
  ExportSpecifier,
  ExportDeclaration,
  FunctionExpression,
  BinaryExpression,
} from "./node-types";

export class Parser {
  private _tokens: Token[] = [];
  private _currentIndex = 0;
  constructor(token: Token[]) {
    this._tokens = [...token];
  }

  parse(): Program {
    const program = this._parseProgram();
    return program;
  }

  private _parseProgram(): Program {
    const program: Program = {
      type: NodeType.Program,
      body: [],
      start: 0,
      end: Infinity,
    };
    while (!this._isEnd()) {
      const node = this._parseStatement();
      program.body.push(node);
      if (this._isEnd()) {
        program.end = node.end;
      }
    }
    return program;
  }

  private _parseStatement(): Statement {
    if (this._checkCurrentTokenType(TokenType.Function)) {
      return this._parseFunctionDeclaration() as FunctionDeclaration;
    } else if (this._checkCurrentTokenType(TokenType.Identifier)) {
      return this._parseExpressionStatement();
    } else if (this._checkCurrentTokenType(TokenType.LeftCurly)) {
      return this._parseBlockStatement();
    } else if (this._checkCurrentTokenType(TokenType.Return)) {
      return this._parseReturnStatement();
    } else if (this._checkCurrentTokenType(TokenType.Import)) {
      return this._parseImportStatement();
    } else if (this._checkCurrentTokenType(TokenType.Export)) {
      return this._parseExportStatement();
    } else if (
      this._checkCurrentTokenType([
        TokenType.Let,
        TokenType.Var,
        TokenType.Const,
      ])
    ) {
      return this._parseVariableDeclaration();
    }
    console.log(this._getCurrentToken());
    throw new Error("Unexpected token");
  }

  private _parseImportStatement(): ImportDeclaration {
    const { start } = this._getCurrentToken();
    const specifiers = [];
    this._goNext(TokenType.Import);
    // import a
    if (this._checkCurrentTokenType(TokenType.Identifier)) {
      const local = this._parseIdentifier();
      const defaultSpecifier = {
        type: NodeType.ImportDefaultSpecifier,
        local,
        start: local.start,
        end: local.end,
      };
      specifiers.push(defaultSpecifier);
      if (this._checkCurrentTokenType(TokenType.Comma)) {
        this._goNext(TokenType.Comma);
      }
    }
    // import { name1 }
    if (this._checkCurrentTokenType(TokenType.LeftCurly)) {
      this._goNext(TokenType.LeftCurly);
      while (!this._checkCurrentTokenType(TokenType.RightCurly)) {
        const specifier = this._parseIdentifier();
        let local = null;
        if (this._checkCurrentTokenType(TokenType.As)) {
          this._goNext(TokenType.As);
          local = this._parseIdentifier();
        }
        const importSpecifier = {
          type: NodeType.ImportSpecifier,
          imported: specifier,
          local: local ? local : specifier,
          start: specifier.start,
          end: local ? local.end : specifier.end,
        };
        specifiers.push(importSpecifier);
        if (this._checkCurrentTokenType(TokenType.Comma)) {
          this._goNext(TokenType.Comma);
        }
      }
      this._goNext(TokenType.RightCurly);
    }
    // import * as a
    else if (this._checkCurrentTokenType(TokenType.Asterisk)) {
      const { start } = this._getCurrentToken();
      this._goNext(TokenType.Asterisk);
      this._goNext(TokenType.As);
      const local = this._parseIdentifier();
      const importNamespaceSpecifier = {
        type: NodeType.ImportNamespaceSpecifier,
        local,
        start,
        end: local.end,
      };
      specifiers.push(importNamespaceSpecifier);
    }

    // from 'a'
    if (this._checkCurrentTokenType(TokenType.From)) {
      this._goNext(TokenType.From);
    }
    const source = this._parseLiteral();
    const node: ImportDeclaration = {
      type: NodeType.ImportDeclaration,
      specifiers: specifiers as ImportSpecifiers,
      start,
      end: source.end,
      source,
    };
    this._skipSemicolon();
    return node;
  }

  private _parseExportStatement(): ExportDeclaration {
    const { start } = this._getCurrentToken();
    let exportDeclaration: ExportDeclaration | null = null;
    const specifiers: ExportSpecifier[] = [];
    this._goNext(TokenType.Export);
    // export default
    if (this._checkCurrentTokenType(TokenType.Default)) {
      this._goNext(TokenType.Default);
      // export default a
      // export default obj.a
      if (this._checkCurrentTokenType(TokenType.Identifier)) {
        const local = this._parseExpression();
        exportDeclaration = {
          type: NodeType.ExportDefaultDeclaration,
          declaration: local,
          start: local.start,
          end: local.end,
        };
      }
      // export default function() {}
      else if (this._checkCurrentTokenType(TokenType.Function)) {
        const declaration = this._parseFunctionDeclaration();
        exportDeclaration = {
          type: NodeType.ExportDefaultDeclaration,
          declaration,
          start,
          end: declaration.end,
        };
      }
      // TODO: export default class {}
      // TODO: export default { a: 1 };
    }
    // export {
    else if (this._checkCurrentTokenType(TokenType.LeftCurly)) {
      this._goNext(TokenType.LeftCurly);
      while (!this._checkCurrentTokenType(TokenType.RightCurly)) {
        const local = this._parseIdentifier();
        let exported = local;
        if (this._checkCurrentTokenType(TokenType.As)) {
          this._goNext(TokenType.As);
          exported = this._parseIdentifier();
        }
        const exportSpecifier: ExportSpecifier = {
          type: NodeType.ExportSpecifier,
          local,
          exported,
          start: local.start,
          end: exported.end,
        };
        specifiers.push(exportSpecifier);
        if (this._checkCurrentTokenType(TokenType.Comma)) {
          this._goNext(TokenType.Comma);
        }
      }
      this._goNext(TokenType.RightCurly);
      if (this._checkCurrentTokenType(TokenType.From)) {
        this._goNext(TokenType.From);
      }
      const source = this._parseLiteral();
      exportDeclaration = {
        type: NodeType.ExportNamedDeclaration,
        specifiers,
        start,
        declaration: null,
        end: source.end,
        source,
      };
    }
    // export const/let/var
    else if (
      this._checkCurrentTokenType([
        TokenType.Const,
        TokenType.Let,
        TokenType.Var,
      ])
    ) {
      const declaration = this._parseVariableDeclaration();
      exportDeclaration = {
        type: NodeType.ExportNamedDeclaration,
        declaration,
        start,
        end: declaration.end,
        specifiers: specifiers as ExportSpecifier[],
        source: null,
      };
      return exportDeclaration;
    }
    // export function
    else if (this._checkCurrentTokenType(TokenType.Function)) {
      const declaration =
        this._parseFunctionDeclaration() as FunctionDeclaration;
      exportDeclaration = {
        type: NodeType.ExportNamedDeclaration,
        declaration,
        start,
        end: declaration.end,
        specifiers: specifiers as ExportSpecifier[],
        source: null,
      };
    }
    // export * from 'mod'
    else {
      this._goNext(TokenType.Asterisk);
      let exported: Identifier | null = null;
      if (this._checkCurrentTokenType(TokenType.As)) {
        this._goNext(TokenType.As);
        exported = this._parseIdentifier();
      }
      this._goNext(TokenType.From);
      const source = this._parseLiteral();
      exportDeclaration = {
        type: NodeType.ExportAllDeclaration,
        start,
        end: source.end,
        source,
        exported,
      };
    }
    if (!exportDeclaration) {
      throw new Error("Export declaration cannot be parsed");
    }
    this._skipSemicolon();
    return exportDeclaration!;
  }

  private _parseVariableDeclaration(): VariableDeclaration {
    const { start } = this._getCurrentToken();
    const kind = this._getCurrentToken().value;
    this._goNext([TokenType.Let, TokenType.Var, TokenType.Const]);
    const declarations = [];
    const isVariableDeclarationEnded = (): boolean => {
      if (this._checkCurrentTokenType(TokenType.Semicolon)) {
        return true;
      }
      const nextToken = this._getNextToken();
      // 往后看一个 token，如果是 =，则表示没有结束
      if (nextToken && nextToken.type === TokenType.Assign) {
        return false;
      }
      return true;
    };
    while (!isVariableDeclarationEnded()) {
      const id = this._parseIdentifier();
      let init = null;
      if (this._checkCurrentTokenType(TokenType.Assign)) {
        this._goNext(TokenType.Assign);
        if (
          this._checkCurrentTokenType([
            TokenType.Number,
            TokenType.StringLiteral,
          ])
        ) {
          init = this._parseLiteral();
        } else {
          init = this._parseExpression();
        }
      }
      const declarator: VariableDeclarator = {
        type: NodeType.VariableDeclarator,
        id,
        init,
        start: id.start,
        end: init ? init.end : id.end,
      };
      declarations.push(declarator);
      if (this._checkCurrentTokenType(TokenType.Comma)) {
        this._goNext(TokenType.Comma);
      }
    }
    const node: VariableDeclaration = {
      type: NodeType.VariableDeclaration,
      kind: kind as VariableKind,
      declarations,
      start,
      end: this._getPreviousToken().end,
    };
    this._skipSemicolon();
    return node;
  }

  private _parseReturnStatement(): ReturnStatement {
    const { start } = this._getCurrentToken();
    this._goNext(TokenType.Return);
    const argument = this._parseExpression();
    const node: ReturnStatement = {
      type: NodeType.ReturnStatement,
      argument,
      start,
      end: argument.end,
    };
    this._skipSemicolon();
    return node;
  }

  private _parseExpressionStatement(): ExpressionStatement {
    const expression = this._parseExpression();
    const expressionStatement: ExpressionStatement = {
      type: NodeType.ExpressionStatement,
      expression,
      start: expression.start,
      end: expression.end,
    };
    return expressionStatement;
  }

  // 需要考虑 a.b.c 嵌套结构
  private _parseExpression(): Expression {
    // 先检查是否是一个函数表达式
    if (this._checkCurrentTokenType(TokenType.Function)) {
      return this._parseFunctionExpression();
    }
    if (
      this._checkCurrentTokenType([TokenType.Number, TokenType.StringLiteral])
    ) {
      return this._parseLiteral();
    }
    // 拿到标识符，如 a
    let expresion: Expression = this._parseIdentifier();
    while (!this._isEnd()) {
      if (this._checkCurrentTokenType(TokenType.LeftParen)) {
        expresion = this._parseCallExpression(expresion);
      } else if (this._checkCurrentTokenType(TokenType.Dot)) {
        // 继续解析，a.b
        expresion = this._parseMemberExpression(expresion as MemberExpression);
      } else if (this._checkCurrentTokenType(TokenType.Operator)) {
        // 解析 a + b
        expresion = this.__parseBinaryOperatorExpression(expresion);
      } else {
        break;
      }
    }
    return expresion;
  }

  private __parseBinaryOperatorExpression(
    expression: Expression
  ): BinaryExpression {
    const { start } = this._getCurrentToken();
    const operator = this._getCurrentToken().value!;
    this._goNext(TokenType.Operator);
    const right = this._parseExpression();
    const node: BinaryExpression = {
      type: NodeType.BinaryExpression,
      operator,
      left: expression,
      right,
      start,
      end: right.end,
    };
    return node;
  }

  private _parseMemberExpression(
    object: Identifier | MemberExpression
  ): MemberExpression {
    this._goNext(TokenType.Dot);
    const property = this._parseIdentifier();
    const node: MemberExpression = {
      type: NodeType.MemberExpression,
      object,
      property,
      start: object.start,
      end: property.end,
      computed: false,
    };
    return node;
  }

  private _parseCallExpression(callee: Expression) {
    const args = this._parseParams(FunctionType.CallExpression) as Expression[];
    // 获取最后一个字符的结束位置
    const { end } = this._getPreviousToken();
    const node: CallExpression = {
      type: NodeType.CallExpression,
      callee,
      arguments: args,
      start: callee.start,
      end,
    };
    this._skipSemicolon();
    return node;
  }

  private _parseFunctionDeclaration(): FunctionDeclaration {
    const { start } = this._getCurrentToken();
    this._goNext(TokenType.Function);
    let id = null;
    if (this._checkCurrentTokenType(TokenType.Identifier)) {
      id = this._parseIdentifier();
    }
    const params = this._parseParams();
    const body = this._parseBlockStatement();
    const node: FunctionDeclaration = {
      type: NodeType.FunctionDeclaration,
      id,
      params,
      body,
      start,
      end: body.end,
    };
    return node;
  }

  private _parseFunctionExpression(): FunctionExpression {
    const { start } = this._getCurrentToken();
    this._goNext(TokenType.Function);
    let id = null;
    if (this._checkCurrentTokenType(TokenType.Identifier)) {
      id = this._parseIdentifier();
    }
    const params = this._parseParams();
    const body = this._parseBlockStatement();
    const node: FunctionExpression = {
      type: NodeType.FunctionExpression,
      id,
      params,
      body,
      start,
      end: body.end,
    };
    return node;
  }

  private _parseParams(
    mode: FunctionType = FunctionType.FunctionDeclaration
  ): Identifier[] | Expression[] {
    this._goNext(TokenType.LeftParen);
    const params = [];
    while (!this._checkCurrentTokenType(TokenType.RightParen)) {
      let param =
        mode === FunctionType.FunctionDeclaration
          ? // 函数声明
            this._parseIdentifier()
          : // 函数调用
            this._parseExpression();
      params.push(param);
      if (!this._checkCurrentTokenType(TokenType.RightParen)) {
        this._goNext(TokenType.Comma);
      }
    }
    this._goNext(TokenType.RightParen);
    return params;
  }

  private _parseLiteral(): Literal {
    const token = this._getCurrentToken();
    let value: string | number | boolean = token.value!;
    if (token.type === TokenType.Number) {
      value = Number(value);
    }
    const literal: Literal = {
      type: NodeType.Literal,
      value: token.value!,
      start: token.start,
      end: token.end,
      raw: token.raw!,
    };
    this._goNext(token.type);
    return literal;
  }

  private _parseIdentifier(): Identifier {
    const token = this._getCurrentToken();
    const identifier: Identifier = {
      type: NodeType.Identifier,
      name: token.value!,
      start: token.start,
      end: token.end,
    };
    this._goNext(TokenType.Identifier);
    return identifier;
  }

  private _parseBlockStatement(): BlockStatement {
    const { start } = this._getCurrentToken();
    const blockStatement: BlockStatement = {
      type: NodeType.BlockStatement,
      body: [],
      start,
      end: Infinity,
    };
    this._goNext(TokenType.LeftCurly);
    while (!this._checkCurrentTokenType(TokenType.RightCurly)) {
      const node = this._parseStatement();
      blockStatement.body.push(node);
    }
    blockStatement.end = this._getCurrentToken().end;
    this._goNext(TokenType.RightCurly);
    return blockStatement;
  }

  private _checkCurrentTokenType(type: TokenType | TokenType[]): boolean {
    if (this._isEnd()) {
      return false;
    }
    const currentToken = this._tokens[this._currentIndex];
    if (Array.isArray(type)) {
      return type.includes(currentToken.type);
    } else {
      return currentToken.type === type;
    }
  }

  private _skipSemicolon(): void {
    if (this._checkCurrentTokenType(TokenType.Semicolon)) {
      this._goNext(TokenType.Semicolon);
    }
  }

  private _goNext(type: TokenType | TokenType[]): Token {
    const currentToken = this._tokens[this._currentIndex];
    // 断言当前 Token 的类型，如果不能匹配，则抛出错误
    if (Array.isArray(type)) {
      if (!type.includes(currentToken.type)) {
        throw new Error(
          `Expect ${type.join(",")}, but got ${currentToken.type}`
        );
      }
    } else {
      if (currentToken.type !== type) {
        throw new Error(`Expect ${type}, but got ${currentToken.type}`);
      }
    }
    this._currentIndex++;
    return currentToken;
  }

  private _isEnd(): boolean {
    return this._currentIndex >= this._tokens.length;
  }

  private _getCurrentToken(): Token {
    return this._tokens[this._currentIndex];
  }

  private _getPreviousToken(): Token {
    return this._tokens[this._currentIndex - 1];
  }

  private _getNextToken(): Token | false {
    if (this._currentIndex + 1 < this._tokens.length) {
      return this._tokens[this._currentIndex + 1];
    } else {
      return false;
    }
  }
}

1.3 /src/node-types.ts

export enum NodeType {
  Program = "Program",
  VariableDeclaration = "VariableDeclaration",
  FunctionDeclaration = "FunctionDeclaration",
  Identifier = "Identifier",
  BlockStatement = "BlockStatement",
  ExpressionStatement = "ExpressionStatement",
  ReturnStatement = "ReturnStatement",
  CallExpression = "CallExpression",
  BinaryExpression = "BinaryExpression",
  MemberExpression = "MemberExpression",
  FunctionExpression = "FunctionExpression",
  Literal = "Literal",
  ImportDeclaration = "ImportDeclaration",
  ImportSpecifier = "ImportSpecifier",
  ImportDefaultSpecifier = "ImportDefaultSpecifier",
  ImportNamespaceSpecifier = "ImportNamespaceSpecifier",
  ExportDeclaration = "ExportDeclaration",
  ExportSpecifier = "ExportSpecifier",
  ExportDefaultDeclaration = "ExportDefaultDeclaration",
  ExportNamedDeclaration = "ExportNamedDeclaration",
  ExportAllDeclaration = "ExportAllDeclaration",
  VariableDeclarator = "VariableDeclarator",
}

export enum FunctionType {
  FunctionDeclaration,
  CallExpression,
}

export interface Node {
  type: string;
  start: number;
  end: number;
}

export interface Program extends Node {
  type: NodeType.Program;
  body: Statement[];
}

export interface Literal extends Node {
  type: NodeType.Literal;
  value: string;
  raw: string;
}

export interface Identifier extends Node {
  type: NodeType.Identifier;
  name: string;
}

export interface CallExpression extends Node {
  type: NodeType.CallExpression;
  callee: Expression;
  arguments: Expression[];
}

export interface MemberExpression extends Node {
  type: NodeType.MemberExpression;
  object: Identifier | MemberExpression;
  property: Identifier;
  computed: boolean;
}

export interface BlockStatement extends Node {
  type: NodeType.BlockStatement;
  body: Statement[];
}

export interface ExpressionStatement extends Node {
  type: NodeType.ExpressionStatement;
  expression: Expression;
}

export interface FunctionExpression extends FunctionNode {
  type: NodeType.FunctionExpression;
}

export interface FunctionDeclaration extends FunctionNode {
  type: NodeType.FunctionDeclaration;
  id: Identifier | null;
}

export type VariableKind = "var" | "let" | "const";

export interface VariableDeclarator extends Node {
  type: NodeType.VariableDeclarator;
  id: Identifier;
  init: Expression | Literal | null;
}

export interface VariableDeclaration extends Node {
  type: NodeType.VariableDeclaration;
  kind: "var" | "let" | "const";
  declarations: VariableDeclarator[];
}

export interface ImportSpecifier extends Node {
  type: NodeType.ImportSpecifier;
  imported: Identifier;
  local: Identifier;
}

export interface ImportDefaultSpecifier extends Node {
  type: NodeType.ImportDefaultSpecifier;
  local: Identifier;
}

export interface ImportNamespaceSpecifier extends Node {
  type: NodeType.ImportNamespaceSpecifier;
  local: Identifier;
}

export type ImportSpecifiers =
  | (ImportSpecifier | ImportDefaultSpecifier)[]
  | ImportNamespaceSpecifier[];

export interface ImportDeclaration extends Node {
  type: NodeType.ImportDeclaration;
  specifiers: ImportSpecifiers;
  source: Literal;
}

export type Declaration =
  | FunctionDeclaration
  | VariableDeclaration
  | ImportDeclaration
  | ExportDeclaration
  | VariableDeclarator;

export interface ExportSpecifier extends Node {
  type: NodeType.ExportSpecifier;
  exported: Identifier;
  local: Identifier;
}

export interface ExportNamedDeclaration extends Node {
  type: NodeType.ExportNamedDeclaration;
  declaration: Declaration | null;
  specifiers: ExportSpecifier[];
  source: Literal | null;
}

export interface ExportDefaultDeclaration extends Node {
  type: NodeType.ExportDefaultDeclaration;
  declaration: Declaration | Expression;
}

export interface ExportAllDeclaration extends Node {
  type: NodeType.ExportAllDeclaration;
  source: Literal;
  exported: Identifier | null;
}

export type ExportDeclaration =
  | ExportNamedDeclaration
  | ExportDefaultDeclaration
  | ExportAllDeclaration;

export interface BinaryExpression extends Node {
  type: NodeType.BinaryExpression;
  left: Expression;
  right: Expression;
  operator: string;
}
export interface FunctionNode extends Node {
  id: Identifier | null;
  params: Expression[] | Identifier[];
  body: BlockStatement;
}

export interface ReturnStatement extends Node {
  type: NodeType.ReturnStatement;
  argument: Expression;
}

export type Statement =
  | ImportDeclaration
  | ExportDeclaration
  | VariableDeclaration
  | FunctionDeclaration
  | ExpressionStatement
  | BlockStatement
  | ReturnStatement;

export type Expression =
  | CallExpression
  | MemberExpression
  | Identifier
  | Literal
  | BinaryExpression
  | FunctionExpression;

1.4 /src/utils.ts

// 分隔符
export function isWhiteSpace(char: string): boolean {
  return char === " " || char === "\t" || char === "\n" || char === "\r";
}

// 字母
export function isAlpha(char: string): boolean {
  return (char >= "a" && char <= "z") || (char >= "A" && char <= "Z");
}

// 数字
export function isDigit(char: string): boolean {
  return char >= "0" && char <= "9";
}

// 下划线
export function isUnderline(char: string): boolean {
  return char === "_";
}

1.5 /src/index.ts

import { Parser } from "./parser";
import { Tokenizer } from "./tokenizer";

export function parse(code: string) {
  const tokenizer = new Tokenizer(code);
  const tokens = tokenizer.tokenize();
  const parser = new Parser(tokens);
  return parser.parse();
}

export * from "./tokenizer";
export * from "./node-types";

二、测试

---

2.1 tokenizer

import { Tokenizer } from '../dist/tokenizer.js';

const tokenizer = new Tokenizer('let a = function() {}');
const tokens = tokenizer.tokenize();
console.log("tokens",tokens);

2.2 parser

import { Parser } from '../dist/parser.js';
import { Tokenizer } from '../dist/tokenizer.js';

const code = `let a = function() {};`;
const tokenizer = new Tokenizer(code);
const parser = new Parser(tokenizer.tokenize());
const program = parser.parse();
console.log('program', program);

2.3 parse

import { parse } from "../dist/index.js"

const code = "let a = function() {};"
const program = parse(code);
console.log('program', program);