[Node] 淡如止水 TypeScript （四）：语法分析

作者: 何幻 | 来源:发表于2020-01-01 12:02 被阅读0次

0. 回顾

上一篇中，我们粗略的跟了一下 TypeScript 词法分析器的扫描过程，
调用 nextToken() 之后，词法分析器做了很多事情，
但给人的感觉是井然有序的，每种情况都硬编码，然后覆盖全面。

本文，我们开始研究语法分析相关的代码，
TypeScript 语法分析是一个递归下降的处理过程，由非常多的 parseXXX 函数的互相调用完成，
每一个 parseXXX 处理 AST 的一个子树，最后拼成一棵完整的 AST。

1. 最顶层的 parseList

上一篇，我们执行过了 nextToken()，
位于 parseSourceFileWorker，src/compiler/parser.ts#L843 中，

function parseSourceFileWorker(fileName: string, languageVersion: ScriptTarget, setParentNodes: boolean, scriptKind: ScriptKind): SourceFile {
  ...
  sourceFile = createSourceFile(fileName, languageVersion, scriptKind, isDeclarationFile);
  
  ...
  nextToken();
  
  ...
  sourceFile.statements = parseList(ParsingContext.SourceElements, parseStatement);

  ...
  return sourceFile;

  ...
}

我们来看随后 parseList 的执行过程。

parseList，src/compiler/parser.ts#L1756，
这里得记住，传入的第二个参数是 parseStatement，它会层层传递，最后以回调方式调用，

function parseList<T extends Node>(kind: ParsingContext, parseElement: () => T): NodeArray<T> {
  ...
  while (!isListTerminator(kind)) {
    if (isListElement(kind, /*inErrorRecovery*/ false)) {
      const element = parseListElement(kind, parseElement);
      list.push(element);

      continue;
    }

    ...
  }

  ...
  return createNodeArray(list, listPos);
}

parseList 调用了 parseListElement，src/compiler/parser.ts#L1779，
第二个参数 parseElement 透传，值为 parseStatement。

然后 parseListElement 调用了参数 parseElement，它的值就是 parseStatement。

function parseListElement<T extends Node>(parsingContext: ParsingContext, parseElement: () => T): T {
  ...
  return parseElement();
}

parseStatement，src/compiler/parser.ts#L5512，是一个有非常多个 case 构成的函数。

function parseStatement(): Statement {
  switch (token()) {
    ...
    case SyntaxKind.ConstKeyword:
      if (isStartOfDeclaration()) {
        return parseDeclaration();
      }
      break;
  }
  ...
}

它先调用 token()，src/compiler/parser.ts#L1910，获取当前 token 的种类，
注意是 token 的种类，而不是当前 token 的值。

function token(): SyntaxKind {
  return currentToken;
}

然后，通过对 token 种类 SyntaxKind 进行 switch，分情况处理。
示例中，我们的 token 是 const，种类为 SyntaxKind.ConstKeyword。

TypeScript 会判断当前源码位置，是否一个变量声明，
如果是的话，就当做变量声明来解析。

if (isStartOfDeclaration()) {
  return parseDeclaration();
}
break;

2. 关键的 parseStatement

2.1 前瞻判断 isStartOfDeclaration

我们先来看 isStartOfDeclaration，src/compiler/parser.ts#L5437，

function isStartOfDeclaration(): boolean {
  return lookAhead(isDeclaration);
}

其中，isDeclaration，src/compiler/parser.ts#L5359 是一个函数，
这里是当做回调来传入的，虽然尚未执行，但我们知道它会返回 true，

function isDeclaration(): boolean {
  while (true) {
    switch (token()) {
      ...
      case SyntaxKind.ConstKeyword:
        return true;
      ...
    }
  }
}

下面我们来看 lookAhead，src/compiler/parser.ts#L1176，

function lookAhead<T>(callback: () => T): T {
  return speculationHelper(callback, /*isLookAhead*/ true);
}

然后，speculationHelper，src/compiler/parser.ts#L1139，
其中 isLookAhead 为 true，

function speculationHelper<T>(callback: () => T, isLookAhead: boolean): T {
  ...
  const result = isLookAhead
    ? scanner.lookAhead(callback)
    : ...;
  
  ...
  return result;
}

scanner.lookAhead，src/compiler/scanner.ts#L2262，
注意到这里的 lookAhead 跟上面那个是不同的，位于 scanner.ts 中。

function lookAhead<T>(callback: () => T): T {
  return speculationHelper(callback, /*isLookahead*/ true);
}

speculationHelper，src/compiler/scanner.ts#L2217，
这个 speculationHelper 跟上文的也不同，也位于 scanner.ts 中。

其中，isLookahead 为 true。

function speculationHelper<T>(callback: () => T, isLookahead: boolean): T {
  const savePos = pos;
  const saveStartPos = startPos;
  const saveTokenPos = tokenPos;
  const saveToken = token;
  const saveTokenValue = tokenValue;
  const saveTokenFlags = tokenFlags;
  const result = callback();

  // If our callback returned something 'falsy' or we're just looking ahead,
  // then unconditionally restore us to where we were.
  if (!result || isLookahead) {
    pos = savePos;
    startPos = saveStartPos;
    tokenPos = saveTokenPos;
    token = saveToken;
    tokenValue = saveTokenValue;
    tokenFlags = saveTokenFlags;
  }
  return result;
}

该函数会先将当前 token 信息保存起来，防止 callback 中对当前 token 误操作，
这里 callback 的值是上层透传过来的，实际上正是 isDeclaration，src/compiler/parser.ts#L5359，
我们之前已经分析过了，它会返回 true。

因此，speculationHelper 会返回 true。

这就回到了最上层，isStartOfDeclaration，src/compiler/parser.ts#L5437，会返回 true，

function isStartOfDeclaration(): boolean {
  return lookAhead(isDeclaration);
}

2.2 子树的解析

parseStatement，src/compiler/parser.ts#L5512，中判断了 isStartOfDeclaration 之后，
就要开始解析变量声明了，parseDeclaration，

function parseStatement(): Statement {
  switch (token()) {
    ...
    case SyntaxKind.ConstKeyword:
      if (isStartOfDeclaration()) {
        return parseDeclaration();
      }
      break;
  }
  ...
}

parseDeclaration，src/compiler/parser.ts#L5588，

function parseDeclaration(): Statement {
  ...

  const node = <Statement>createNodeWithJSDoc(SyntaxKind.Unknown);
  node.decorators = parseDecorators();
  node.modifiers = parseModifiers();
  if (isAmbient) {
    ...
  }
  else {
    return parseDeclarationWorker(node);
  }
}

它会先创建一个包含 js-doc 的 node，然后解析可能出现的各个部分，比如装饰器，
最后，调用 parseDeclarationWorker 解析变量声明的主体。

parseDeclarationWorker，src/compiler/parser.ts#L5624，

function parseDeclarationWorker(node: Statement): Statement {
  switch (token()) {
    ...
    case SyntaxKind.ConstKeyword:
      return parseVariableStatement(<VariableStatement>node);
    ...
  }
}

parseVariableStatement，src/compiler/parser.ts#L5810，

function parseVariableStatement(node: VariableStatement): VariableStatement {
  node.kind = SyntaxKind.VariableStatement;
  node.declarationList = parseVariableDeclarationList(/*inForStatementInitializer*/ false);
  parseSemicolon();
  return finishNode(node);
}

设置 node 的种类为变量表达式 SyntaxKind.VariableStatement，
然后，解析出变量声明列表，declarationList，
最后解析分号 parseSemicolon。

我们来看 parseVariableDeclarationList，src/compiler/parser.ts#L5763，

function parseVariableDeclarationList(inForStatementInitializer: boolean): VariableDeclarationList {
  const node = <VariableDeclarationList>createNode(SyntaxKind.VariableDeclarationList);

  switch (token()) {
    ...
    case SyntaxKind.ConstKeyword:
      node.flags |= NodeFlags.Const;
      break;
    ...
  }

  nextToken();

  ...
  if (token() === SyntaxKind.OfKeyword && lookAhead(canFollowContextualOfKeyword)) {
    ...
  }
  else {
    ...

    node.declarations = parseDelimitedList(ParsingContext.VariableDeclarations,
      inForStatementInitializer ? parseVariableDeclaration : parseVariableDeclarationAllowExclamation);

    ...
  }

  return finishNode(node);
}

先根据当前 token 的种类，设置 node.flags，
然后调用 nextToken() 处理下一个 token。

2.3 处理过程中的 nextToken()

之前我们分析过的 nextToken 的执行过程，
它会调用 scanner.scan src/compiler/scanner.ts#L1490 返回下一个 token 的种类。

我们看 debug/index.ts，const 后的下一个 token 应该为变量 i，

const i: number = 1;

跟到 scanner.scan src/compiler/scanner.ts#L1912 中，我们看到 tokenValue 的值确实为 i，

回到 parseVariableDeclarationList，src/compiler/parser.ts#L5763 中来，

function parseVariableDeclarationList(inForStatementInitializer: boolean): VariableDeclarationList {
  ...
  nextToken();

  ...
  if (token() === SyntaxKind.OfKeyword && lookAhead(canFollowContextualOfKeyword)) {
    ...
  }
  else {
    ...

    node.declarations = parseDelimitedList(ParsingContext.VariableDeclarations,
      inForStatementInitializer ? parseVariableDeclaration : parseVariableDeclarationAllowExclamation);

    ...
  }

  return finishNode(node);
}

执行完 nextToken() 之后，就开始解析 const 后面的内容了。
我们能看到这是一个递归下降的解析过程，每个产生式会对应一个 parseXXX。

3. 完整的调用链路

parseDelimitedList src/compiler/parser.ts#L2115 之后的处理过程，大同小异且非常的繁琐，
这里就不再逐个函数进行介绍了，按调用的层次结构列举如下，

parseList
  parseListElement
    parseElement                  // 值为 parseStatement
      parseDeclaration
        parseDecorators
        parseModifiers
        (parseDeclarationWorker)  // 辅助函数
          parseVariableStatement
            parseVariableDeclarationList
              parseDelimitedList  // <- 当前位置
                parseListElement
                  parseElement    // 值为 parseVariableDeclarationAllowExclamation
                    parseVariableDeclarationAllowExclamation
                      parseVariableDeclaration
                        parseIdentifierOrPattern
                          parseIdentifier
                        parseTypeAnnotation
                          parseType
                            parseTypeWorker
                              parseUnionTypeOrHigher
                                parseUnionOrIntersectionType
                                  parseConstituentType      // 值为 parseIntersectionTypeOrHigher
                                    parseUnionOrIntersectionType
                                      parseConstituentType  // 值为 parseTypeOperatorOrHigher
                                        parsePostfixTypeOrHigher
                                          parseNonArrayType
                                            parsePostfixTypeOrHigher 
                        parseInitializer
                          parseAssignmentExpressionOrHigher
                            parseBinaryExpressionOrHigher
                              parseUnaryExpressionOrHigher
                                parseUpdateExpression
                                  parseLeftHandSideExpressionOrHigher
                              parseBinaryExpressionRest
                            parseConditionalExpressionRest
                              parseOptionalToken
            parseSemicolon

我们看到上文分析的 parseDelimitedList 之后，还发生了很多事情。
同一个缩进层次，表示先后发生的两件事，
更深的缩进层次，表示调用另一个 parseXXX 来完成的。

整个 parseList 处理完后会得到一个类似的 AST，

{
  sourceFile: {

    // parseList
    statements: [

      // parseDeclaration
      {

        // parseDecorators
        decorators,

        // parseModifiers
        modifiers,

        // parseVariableDeclarationList
        declarationList: {

          // parseDelimitedList
          declarations: [

            // parseVariableDeclaration
            {
              // parseIdentifierOrPattern
              name,

              // parseTypeAnnotation
              type,

              // parseInitializer
              initializer,
            }
          ],
        },

        // parseSemicolon
      }
    ]
  }
}

4. 解析完毕

解析完毕后，流程就回到了篇首，
parseSourceFileWorker，src/compiler/parser.ts#L843

function parseSourceFileWorker(fileName: string, languageVersion: ScriptTarget, setParentNodes: boolean, scriptKind: ScriptKind): SourceFile {
  ...
  sourceFile.statements = parseList(ParsingContext.SourceElements, parseStatement);

  ...
  return sourceFile;

  ...
}

总结

在读 TypeScript 源码之前，也了解过递归下降解析器的编写方法，
也仅限于了解 LL(k) 解析器生成器的工作原理。

实际看了 TypeScript 的解析过程之后，发现 Compiler 前端并不是特别的艰深，
写出一个足够通用的解析器生成器才是困难的，甚至需要对文法做一些处理（清理 / 左递归消除），
或者引入一些数据结构（LR 状态机）。

因为可以调试，TypeScript 源码读起来，也会容易一些，
语法解析过程无非是用硬编码的方式，生成一棵 AST。
至于每个子节点是怎么处理的，要对 TypeScript 语法结构非常熟悉才行。

要照顾到所有可能的情况，这个确实是一个比较复杂的工程。

参考

TypeScript v3.7.3

[Node] 淡如止水 TypeScript （四）：语法分析

0. 回顾

1. 最顶层的 parseList

2. 关键的 parseStatement

2.1 前瞻判断 isStartOfDeclaration

2.2 子树的解析

2.3 处理过程中的 nextToken()

3. 完整的调用链路

4. 解析完毕

总结

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Node.js