v8的词法分析

本文将探讨v8是如何对utf8编码的js文件进行词法分析的!

简介

v8提供了一个Scanner类作为词法分析器,在该类中有这么一个指针:

1
Utf16CharacterStream* stream_;

这是个啥玩意?看一下源代码中对这个类的解释:

// Buffered stream of UTF-16 code units, using an internal UTF-16 buffer.

大概就是说,Utf16CharacterStream就是一个UTF-16代码单元的缓冲流。

啥是代码单元?v8的解释如下:

// 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.

这就涉及到了unicode规范,在unicode字符集中,每个unicode字符都有一个唯一的代码点

在utf8、utf16等编码形式中,代码点被映射到一个或者多个代码单元。

代码单元是各个编码形式中的最小单元,其大小:

  • UTF-8 中的代码单元由 8 位组成。
  • UTF-16 中的代码单元由 16 位组成。

每个代码点需要多少个代码单元呢?不同编码形式不一样:

  • UTF-8中,每个代码点被映射到一个、两个、三个或者四个代码单元。
  • UTF-16中,值小于等于U+FFFF的代码点被映射到单个代码单元中,对于值大于U+FFFF的代码点,每个代码点需要两个代码单元。在UTF-16 中,这些代码单元对有一个独特的术语:“Unicode 代理对”。

综上,我们可以知道Utf16CharacterStream中每一个UTF-16代码单元的含义:

UTF-16中,一个代码单元要么是一个16位的代码点,要么是“Unicode代理对”中的一半,其中“unicode代码对”是一个21位的代码点。

简而言之,Utf16CharacterStream中的每个代码单元,要么是一个独立的unicode字符,要么是一个unicode字符的一半(和下一个代码单元组合起来才能形成一个unicode字符)。

v8实际上就是基于utf16对输入字符序列进行词法分析的!这也是Ecmascript规范所要求的:

ECMAScript 源代码文本使用 Unicode 3.0 或更高版本的字符编码的字符序列来表示。
符合 ECMAScript 的实现不要求对文本执行正规化,也不要求将其表现为像执行了正规化一样。
本规范的目的是假定 ECMAScript 源代码文本都是由16位代码单元组成的序列。
像这样包含16位代码单元序列的源文本可能不是有效的 UTF-16 字符编码。
如果实际源代码文本没有用16位代码单元形式的编码,那就必须把它看作已经转换为 UTF-16 一样处理。

v8词法分析首先要做的是把输入字符序列转换成utf16 stream。

那如何把utf8编码的js文件转换成utf16 stream呢?

字节流

首先,我们需要先获得utf8字节流:

1
2
3
4
5
6
7
8
9
10
11
12
// 二进制方式打开
FILE* file = fopen(filename, "rb");
// 移到文件尾
fseek(file, 0, SEEK_END);
// 字节数
int file_size = ftell(file);
// 回到文件头
rewind(file);
// 字节数组
byte* chars = new byte[file_size]; // typedef unsigned char byte
fread(chars, 1, file_size, file);
chars[file_size] = 0

假设文件内容如下:

1
2
3
function 招聘() {
var 信息 = "复合搜索部前端工程师";
}

utf8字节流如下:

1
2
66 75 6E 63 74 69 6F 6E 20 E6 8B 9B E8 81 98 28 29 20 7B 0A 20 20 20 20 76 61 72 20 E4 BF A1 E6 81 AF 20 3D 20 22 E5 A4
8D E5 90 88 E6 90 9C E7 B4 A2 E9 83 A8 E5 89 8D E7 AB AF E5 B7 A5 E7 A8 8B E5 B8 88 22 3B 0A 7D 0A

转换

现在,我们需要把utf8的字节流转换成utf16字符流,前面我们说了,词法分析器扫描的是Utf16CharacterStream类,不过这个类是一个抽象类,不能直接使用,
v8用了一个BufferedUtf16CharacterStream类来提供具体的功能,它继承至Utf16CharacterStream

1.png

这个BufferedUtf16CharacterStream提供了一个缓冲区buffer_,我们转换的时候,就是要向这个缓冲区填充字符。

具体的转换功能由一个叫Utf8ToUtf16CharacterStream的类提供,它继承至BufferedUtf16CharacterStream

2.png

基本用法:

1
2
3
4
// utf8字节流数组头部指针,指向第一个字节
unsigned char* source_;
// 流指针
BufferedUtf16CharacterStream* stream_ = new Utf8ToUtf16CharacterStream(source_, length);

在生成一个BufferedUtf16CharacterStream实例之时,在其构造函数中,会进行第一次字符填充。

Utf8ToUtf16CharacterStream::FillBuffer方法中,有这么一段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (i < kBufferSize - 1) {
if (raw_data_pos_ == raw_data_length_) break;
// 取出当前字节
unibrow::uchar c = raw_data_[raw_data_pos_];
if (c <= unibrow::Utf8::kMaxOneByteChar) {
// 单字节字符
raw_data_pos_++;
} else {
// 多字节字符,向前继续读字节,计算出字符
c = unibrow::Utf8::CalculateValue(raw_data_ + raw_data_pos_,
raw_data_length_ - raw_data_pos_,
&raw_data_pos_);
}
if (c > kMaxUtf16Character) {
// 如果计算出来的字符超出U+FFFF,那就需要两个16位代码单元来表示,也就是我们前文所说的“Unicode代码对”
buffer_[i++] = unibrow::Utf16::LeadSurrogate(c);
buffer_[i++] = unibrow::Utf16::TrailSurrogate(c);
} else {
// 如果计算出来的字符小于U+FFFF,那就直接填入buffer_
buffer_[i++] = static_cast<uc16>(c);
}
}

最后的结果就是,BufferedUtf16CharacterStream::buffer_中的每一个元素都是一个16位代码单元,它要么是一个字符,要么是一个“Unicode代码对”的一半。

我们以上文得到的字节流为例,最后BufferedUtf16CharacterStream::buffer_中会类似这样:

3.png

得到所有字符之后,接下来的工作就是扫描每个字符,分析出Token

扫描

v8扫描BufferedUtf16CharacterStream::buffer_中的每个代码单元,然后按照Ecmascript的文法产生式分析出所有Token。

我们先来看看Scanner::Next这个方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 是否ASCII字符
if (static_cast<unsigned>(c0_) <= 0x7f) {
// 从`one_char_tokens`中取出该Token
Token::Value token = static_cast<Token::Value>(one_char_tokens[c0_]);
// 如果取出来的Token不是ILLEGAL的话,返回该Token
if (token != Token::ILLEGAL) {
int pos = source_pos();
next_.token = token;
next_.location.beg_pos = pos;
next_.location.end_pos = pos + 1;
Advance();
return current_.token;
}
}
// 否则继续扫描
Scan();
return current_.token;

我们注意到上面代码中的one_char_tokens,这货是啥?它其实就是个大小为128的数组,其中元素大部分是Token::ILLEGAL,只有几个有效的Token:

  • Token::LPAREN “(“
  • Token::RPAREN “)”
  • Token::COMMA “,”
  • Token::COLON “:”
  • Token::SEMICOLON “;”
  • Token::CONDITIONAL “?”
  • Token::LBRACK “[“
  • Token::RBRACK “]”
  • Token::LBRACE “{“
  • Token::RBRACE “}”
  • Token::BIT_NOT “~”

如果没匹配到one_char_tokens,则调用Scanner::Scan继续扫描:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
switch(c0_) {
// 匹配各种常见的字符...
case ' '
case '\t'
case '='
case '~'
...
default:
// 匹配identifier或者keyword等
if (unicode_cache_->IsIdentifierStart(c0_)) {
token = ScanIdentifierOrKeyword();
} else if (IsDecimalDigit(c0_)) {
token = ScanNumber(false);
} else if (SkipWhiteSpace()) {
token = Token::WHITESPACE;
} else if (c0_ < 0) {
token = Token::EOS;
} else {
token = Select(Token::ILLEGAL);
}
break;
}

注意到上面的ScanIdentifierOrKeyword方法,这个方法是Token分析的核心,顾名思义,它就是用来分析identifier或者keyword的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 字符链
// 比如`name`这样一个Token,有4个字符,这4个字符就连成了一个LiteralScope
// 当扫描完这4个字符后,会调用`LiteralScope::Complete`,这样就完成了一个Token的分析
LiteralScope literal(this);
// 扫描unicode转义字符
if (c0_ == '\\') {
uc32 c = ScanIdentifierUnicodeEscape();
// Only allow legal identifier start characters.
if (c < 0 ||
c == '\\' || // No recursive escapes.
!unicode_cache_->IsIdentifierStart(c)) {
return Token::ILLEGAL;
}
// \u0020
AddLiteralChar(c);
return ScanIdentifierSuffix(&literal);
}
uc32 first_char = c0_;
Advance();
AddLiteralChar(first_char);
// 向前扫描字符,直至遇到一个不是有效的identifier字符为止,比如空格、(、[等
while (unicode_cache_->IsIdentifierPart(c0_)) {
if (c0_ != '\\') {
uc32 next_char = c0_;
Advance();
AddLiteralChar(next_char);
continue;
}
// Fallthrough if no longer able to complete keyword.
return ScanIdentifierSuffix(&literal);
}
// 结束一个字符链,即已经扫描出了一个identifier或者keyword
literal.Complete();
if (next_.literal_chars->is_one_byte()) {
Vector<const uint8_t> chars = next_.literal_chars->one_byte_literal();
// 判断是标志符还是关键词
// v8内部定义了一系列关键词matcher,能match到的就是关键词,否则就是标志符
return KeywordOrIdentifierToken(chars.start(),
chars.length(),
harmony_scoping_,
harmony_modules_);
}
return Token::IDENTIFIER;

我们以前文的buffer_字符数组为例,经过Scanner扫描后,会产生类似这样的结果:

4.png

最后,对整个文件内容扫描完的结果大概就类似这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
No of tokens: 12
=> FUNCTION at (0, 8)
=> IDENTIFIER at (9, 11)
=> LPAREN at (11, 12)
=> RPAREN at (12, 13)
=> LBRACE at (14, 15)
=> VAR at (20, 23)
=> IDENTIFIER at (24, 26)
=> ASSIGN at (27, 28)
=> STRING at (29, 41)
=> SEMICOLON at (41, 42)
=> RBRACE at (43, 44)
=> EOS at (45, 45)

在utf8编码的情况下,v8整个词法分析过程,大概就是这样,当然实际过程中,还有很多细节问题需要处理,比如跳过js注释、html注释
、扫描十六进制字符、8进制字符、unicode转义字符等等

这就是本人粗略看了v8词法分析源码之后的一点理解,欢迎各路大神点评!