连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析

chrome v8连载，3~4天一篇，持续更新中...

原创出处：

连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析www.anquanke.com/post/id/253422

本次是第三篇，讲解V8中词法分析（scanner）的实现，这中间涉及到几个重要的数据结构和一些相关的编译知识，本文也尽量全面讲解相关的编译知识，争取让读者有一个全面的认识。注：本文不涉及V8的优化编译

1.V8编译流程

总体来说，V8的编译过程是同步实现的，主体流程是扫描在初始化时先生成一个token字，并放入缓存（cache），然后开始分析（parser），从缓存中取一个token做分析，然后生成抽象语法树的一个节点，再取下一个token进行分析，如此循环。如果缓存未命中(cache miss),便启动扫描去生成token，如图1所示。

下面看一下V8中的代码实现，Parser::ParseProgram方法，是图1中扫描器(scanner)的入口点。在这段代码中可以看到scanner_.Initialize()和FunctionLiteral* result = DoParseProgram(isolate, info),这两个方法的作用是：

1.初始化扫描器(scanner) 生成第一个token字，scanner.c0_指向第一个开始的字符，也就是要扫描的第一个字符。

2.DoParseProgram(isolate, info)： 读取token字，生成AST的body，最终所有body汇聚成AST语法树。

void Parser::ParseProgram(Isolate* isolate, Handle<Script> script,
                          ParseInfo* info,
                          MaybeHandle<ScopeInfo> maybe_outer_scope_info) {
  DCHECK_EQ(script->id(), flags().script_id());

  // It's OK to use the Isolate & counters here, since this function is only
  // called in the main thread.
  DCHECK(parsing_on_main_thread_);
  RCS_SCOPE(runtime_call_stats_, flags().is_eval()
                                     ? RuntimeCallCounterId::kParseEval
                                     : RuntimeCallCounterId::kParseProgram);
  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"), "V8.ParseProgram");
  base::ElapsedTimer timer;
  if (V8_UNLIKELY(FLAG_log_function_events)) timer.Start();

  // Initialize parser state.
  DeserializeScopeChain(isolate, info, maybe_outer_scope_info,
                        Scope::DeserializationMode::kIncludingVariables);

  DCHECK_EQ(script->is_wrapped(), info->is_wrapped_as_function());
  if (script->is_wrapped()) {
    maybe_wrapped_arguments_ = handle(script->wrapped_arguments(), isolate);
  }

  scanner_.Initialize();
  FunctionLiteral* result = DoParseProgram(isolate, info);
  MaybeResetCharacterStream(info, result);
  MaybeProcessSourceRanges(info, result, stack_limit_);
  PostProcessParseResult(isolate, info, result);

  HandleSourceURLComments(isolate, script);

  if (V8_UNLIKELY(FLAG_log_function_events) && result != nullptr) {
    double ms = timer.Elapsed().InMillisecondsF();
    const char* event_name = "parse-eval";
    int start = -1;
    int end = -1;
    if (!flags().is_eval()) {
      event_name = "parse-script";
      start = 0;
      end = String::cast(script->source()).length();
    }
    LOG(isolate,
        FunctionEvent(event_name, flags().script_id(), ms, start, end, "", 0));
  }
}

上述这段代码（Parser::ParseProgram）是分析V8中编译代码的最近入口点，从此处进入跟踪，可以看到编译的全流程。这个方法的外层也有很多调用者（caller）,但这些调用者的任务仅仅是做准备工作，这个方法开始进入了真正的编译，尤其要注意，在scanner的初始化阶段（scanner_.Initialize）就已经开始做了第一次扫描。

2.V8词法分析(scanner)工作流程

编译器的第一个步骤称为词法分析（lexical analysis）或扫描（scanning），在编译原理这门课程中，我的老师用“词法分析”这个名词，当我看编译器源码，面对工程实现时，看到是“扫描”这个名词，这两种叫法一个是注重原理，另一个是注重实现。词法分析器读入源程序的字符流，并且将他们组织成为有意义的词素（lexeme）的序列，再生成相应的词法单元(token)。
在V8中，源程序的字符流是UTF-16编码，存储字符流的数据结构如下：

// ---------------------------------------------------------------------
// Buffered stream of UTF-16 code units, using an internal UTF-16 buffer.
// A code unit is a 16 bit value representing either a 16 bit code point
// or one part of a surrogate pair that make a single 21 bit code point.
class Utf16CharacterStream {
 public:
  static constexpr base::uc32 kEndOfInput = static_cast<base::uc32>(-1);

  virtual ~Utf16CharacterStream() = default;

  V8_INLINE void set_parser_error() {
    buffer_cursor_ = buffer_end_;
    has_parser_error_ = true;
  }
  V8_INLINE void reset_parser_error_flag() { has_parser_error_ = false; }
  V8_INLINE bool has_parser_error() const { return has_parser_error_; }

  inline base::uc32 Peek() {
    if (V8_LIKELY(buffer_cursor_ < buffer_end_)) {
      return static_cast<base::uc32>(*buffer_cursor_);
    } else if (ReadBlockChecked()) {
      return static_cast<base::uc32>(*buffer_cursor_);
    } else {
      return kEndOfInput;
    }
  }

  // Returns and advances past the next UTF-16 code unit in the input
  // stream. If there are no more code units it returns kEndOfInput.
  inline base::uc32 Advance() {
    base::uc32 result = Peek();
    buffer_cursor_++;
    return result;
  }

//...............
//中间省略很多代码.....
//..............



  // Read more data, and update buffer_*_ to point to it.
  // Returns true if more data was available.
  //
  // ReadBlock() may modify any of the buffer_*_ members, but must sure that
  // the result of pos() remains unaffected.
  //
  // Examples:
  // - a stream could either fill a separate buffer. Then buffer_start_ and
  //   buffer_cursor_ would point to the beginning of the buffer, and
  //   buffer_pos would be the old pos().
  // - a stream with existing buffer chunks would set buffer_start_ and
  //   buffer_end_ to cover the full chunk, and then buffer_cursor_ would
  //   point into the middle of the buffer, while buffer_pos_ would describe
  //   the start of the buffer.
  virtual bool ReadBlock() = 0;

  const uint16_t* buffer_start_;
  const uint16_t* buffer_cursor_;
  const uint16_t* buffer_end_;
  size_t buffer_pos_;
  RuntimeCallStats* runtime_call_stats_;
  bool has_parser_error_ = false;
};

上述代码中，省略了很多中间代码，我保留最开始的英文注释和最后几个重要成员的英文注释，这几个重要的成员分别是bufferstart，buffercursor，bufferend，它们的作用是用来记录源码流，详细见代码中的注释。下面通过一个示例来看下class Utf16CharacterStream的应用场景。

图2中左侧是js源代码，右侧是源码被读进内存，准备编译，通过下面的代码移交给bufferstart进行管理。

bool ReadBlock() final {
    size_t position = pos();
    buffer_pos_ = position;
    buffer_start_ = &buffer_[0];
    buffer_cursor_ = buffer_start_;

    DisallowGarbageCollection no_gc;
    Range<uint8_t> range =
        byte_stream_.GetDataAt(position, runtime_call_stats(), &no_gc);
    if (range.length() == 0) {
      buffer_end_ = buffer_start_;
      return false;
    }

    size_t length = std::min({kBufferSize, range.length()});
    i::CopyChars(buffer_, range.start, length);
    buffer_end_ = &buffer_[length];
    return true;
  }

代码的bufferstart = &buffer[0]，这一句是用buffer_start指向待编译源码的第一个字符。图3给出的是Utf16CharacterStream类中重要的函数。这个函数是读取一个块代码(code unit)，是后续生成token时的输入字符串。

前面提到的scanner.c0这个成员，始终是指向即将开始token生成的字符串，下面的代码也说明了c0的作用。

void Advance() {
    if (capture_raw) {
      AddRawLiteralChar(c0_);
    }
    c0_ = source_->Advance();//看这里
  }

在scanner初始化的最后一步调用了下面这个方法，生成一个token。

void Scanner::Scan(TokenDesc* next_desc) {
  DCHECK_EQ(next_desc, &next());

  next_desc->token = ScanSingleToken();
  DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
  next_desc->location.end_pos = source_pos();

#ifdef DEBUG
  SanityCheckTokenDesc(current());
  SanityCheckTokenDesc(next());
  SanityCheckTokenDesc(next_next());
#endif
}

我们可以看到next_desc->token = ScanSingleToken()这句代码就是在生成一个token，可以看到next_desc是描述token字的关键结构，他是在Scanner中定义的一个结构体，代码如下：

struct TokenDesc {
    Location location = {0, 0};
    LiteralBuffer literal_chars;
    LiteralBuffer raw_literal_chars;
    Token::Value token = Token::UNINITIALIZED;
    MessageTemplate invalid_template_escape_message = MessageTemplate::kNone;
    Location invalid_template_escape_location;
    uint32_t smi_value_ = 0;
    bool after_line_terminator = false;

#ifdef DEBUG
    bool CanAccessLiteral() const {
      return token == Token::PRIVATE_NAME || token == Token::ILLEGAL ||
             token == Token::ESCAPED_KEYWORD || token == Token::UNINITIALIZED ||
             token == Token::REGEXP_LITERAL ||
             base::IsInRange(token, Token::NUMBER, Token::STRING) ||
             Token::IsAnyIdentifier(token) || Token::IsKeyword(token) ||
             base::IsInRange(token, Token::TEMPLATE_SPAN, Token::TEMPLATE_TAIL);
    }
    bool CanAccessRawLiteral() const {
      return token == Token::ILLEGAL || token == Token::UNINITIALIZED ||
             base::IsInRange(token, Token::TEMPLATE_SPAN, Token::TEMPLATE_TAIL);
    }
#endif  // DEBUG
  };

到此，词法分析的初始化完了，后面由Parse驱动它进行工作，词法分析工作的入口点如下。

void Scanner::Scan(TokenDesc* next_desc) {
  DCHECK_EQ(next_desc, &next());

  next_desc->token = ScanSingleToken();
  DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
  next_desc->location.end_pos = source_pos();

#ifdef DEBUG
  SanityCheckTokenDesc(current());
  SanityCheckTokenDesc(next());
  SanityCheckTokenDesc(next_next());
#endif
}

3.V8词法分析的知识点

编译技术是一个庞大的知识领域，涉及很多方面的理论知识，一个编译器的具体实现主要包括：词法分析、语义分析、中间代码、机器无关代码，机器码等多个阶段，此外，还有各种优化技术，例如：控制流优化、数据流优化、寄存器优化等等，这些优化技术与这些阶段交错执行，最终生成目标程序。从编译技术的角度看，V8的编译的每段代码都有相对应的理论支撑，看懂了这些理论，再来看V8编译源码，会很容易的。我们来看一下V8词法分析的知识点。
词法分析是编译的第一个阶段。词法分析器的主要任务是读入源程序的输入字符、将它他们组成词素（lexeme），生成并输出一个词法单元（token），每个词法单元对应一个词素，这个词法单元被输出到语法分析器进行语法分析。当词法分析器发现一个标识符时，还会利用符号表进行保存。词法分析的工作流程、与符号表的交互过程都是由语法分析器驱动，如图4。

图4中，getNextToken是驱动词法分析器工作,向其索取token的命令,直到它识别出下一个词素为止，然后将生成的token返回给语法分析器。看一下V8的这个过程的实现方法。

void ParserBase<Impl>::ParseStatementList(StatementListT* body,
                                          Token::Value end_token) {
  // StatementList ::
  //   (StatementListItem)* <end_token>
  DCHECK_NOT_NULL(body);

  while (peek() == Token::STRING) {
    bool use_strict = false;
#if V8_ENABLE_WEBASSEMBLY
    bool use_asm = false;
#endif  // V8_ENABLE_WEBASSEMBLY

    Scanner::Location token_loc = scanner()->peek_location();

    if (scanner()->NextLiteralExactlyEquals("use strict")) {
      use_strict = true;
#if V8_ENABLE_WEBASSEMBLY
    } else if (scanner()->NextLiteralExactlyEquals("use asm")) {
      use_asm = true;
#endif  // V8_ENABLE_WEBASSEMBLY
    }

    StatementT stat = ParseStatementListItem();
//.......................
//省略很多....
//.......................
  }

  while (peek() != end_token) {
    StatementT stat = ParseStatementListItem();
    if (impl()->IsNull(stat)) return;
    if (stat->IsEmptyStatement()) continue;
    body->Add(stat);
  }
}

这段代码很长，而且我们在调式过程中，由于选取的调试用例不同，不一定能覆盖到每一条语句。我们只看最后的一部分,我的调试代码触发了最后这个while()的执行，其中最重要是 ParseStatementListItem()，图5给出了Parse驱动SCanner的调用堆栈，堆栈中的函数调用流程，也就是图4中的getNextToken的具体实现。

在图5中还能看到前面(图1)提到的缓存(cache)，它在v8中的实现是Consum方法。下面给出V8中Token生成的详细实现。

V8_INLINE Token::Value Scanner::ScanSingleToken() {
  Token::Value token;
  do {
    next().location.beg_pos = source_pos();

    if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
      token = one_char_tokens[c0_];

      switch (token) {
//..............
//代码太长，省略很多
//..............

        case Token::CONDITIONAL:
          // ? ?. ?? ??=
          Advance();
          if (c0_ == '.') {
            Advance();
            if (!IsDecimalDigit(c0_)) return Token::QUESTION_PERIOD;
            PushBack('.');
          } else if (c0_ == '?') {
            return Select('=', Token::ASSIGN_NULLISH, Token::NULLISH);
          }
          return Token::CONDITIONAL;

        case Token::STRING:
          return ScanString();

        case Token::LT:
          // < <= << <<= <!--
          Advance();
          if (c0_ == '=') return Select(Token::LTE);
          if (c0_ == '<') return Select('=', Token::ASSIGN_SHL, Token::SHL);
          if (c0_ == '!') {
            token = ScanHtmlComment();
            continue;
          }
          return Token::LT;
        case Token::ASSIGN:
          // = == === =>
          Advance();
          if (c0_ == '=') return Select('=', Token::EQ_STRICT, Token::EQ);
          if (c0_ == '>') return Select(Token::ARROW);
          return Token::ASSIGN;

        case Token::NOT:
          // ! != !==
          Advance();
          if (c0_ == '=') return Select('=', Token::NE_STRICT, Token::NE);
          return Token::NOT;

        case Token::ADD:
          // + ++ +=
          Advance();
          if (c0_ == '+') return Select(Token::INC);
          if (c0_ == '=') return Select(Token::ASSIGN_ADD);
          return Token::ADD;
//..............
//代码太长，省略很多
//..............

        default:
          UNREACHABLE();
      }
    }

    if (IsIdentifierStart(c0_) ||
        (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
      return ScanIdentifierOrKeyword();
    }
    if (c0_ == kEndOfInput) {
      return source_->has_parser_error() ? Token::ILLEGAL : Token::EOS;
    }
    token = SkipWhiteSpace();

    // Continue scanning for tokens as long as we're just skipping whitespace.
  } while (token == Token::WHITESPACE);

  return token;
}

从代码中可以看出，生成token的过程就是这个switch case，它是一个自动机，token生成的过程也大量用到了正则表达。总结一句：token的生成过程就是字符匹配的过程，在V8中预先定义了token模板（TOKEN_LIST），再利用switch case完成字符匹配，生成token。
好了，今天到这里，下次见。
微信：qq9123013 备注：v8交流学习邮箱：[email protected]

连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析

连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析

原创出处：

1.V8编译流程

2.V8词法分析(scanner)工作流程

3.V8词法分析的知识点

Recommend

连载《Chrome V8 原理讲解》第六篇 bytecode字节码生成

What Do You Think?

Resources to practice web development

How to Exclude Pages from WordPress Search Results

GraphQL Mesh SDK with Next.js

Generating CSS spacing utils with SASS .

A look at the die of the 8086 processor

5 Security Vulnerabilities to Fix Without any Programming Skill

Start your programming journey: Coding bootcamps vs. Self-learning

Holy S**T, I love BlitzJS

About Joyk

连载《Chrome V8 原理讲解》第三篇 看V8编译流程，学习词法分析

连载《Chrome V8 原理讲解》第三篇 看V8编译流程，学习词法分析

原创出处：

1.V8编译流程

2.V8词法分析(scanner)工作流程

3.V8词法分析的知识点

Recommend

About Joyk

连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析

连载《Chrome V8 原理讲解》第三篇看V8编译流程，学习词法分析