JavaScriptCore Deep Dive 3 - Lexical Analysis

Preface

Lexical analysis is the first task a compiler performs. After preprocessing source code, such as removing comments, unnecessary line breaks, and locating included files, lexical analysis decomposes the whole source program into words. These words fall into five categories: identifiers, keywords, constants, operators, and delimiters. This prepares the input for syntax analysis and semantic analysis.

Lexical analysis works on individual characters. Its purpose is to combine those characters into valid words, or strings. The main task of this stage is therefore to build a lexer. There are two common approaches:

  • Write it manually. For a specific language such as JavaScript, we write code by hand and simulate the conversion process according to the language rules. This is complex and error-prone, but it gives precise control over every part of lexical analysis and can be efficient.
  • Generate a lexer automatically. The process is: declarative specification -> automatic generation -> lexer. The generator accepts declarative rules as input and outputs a lexer. A declarative specification means that we only describe the rules for recognizing character streams, not how to recognize them. The rules are regular expressions. Keywords, identifiers, and integers in C can all be described by regular expressions. These regular expressions are fed into the generator, which produces a lexer, usually a DFA, or deterministic finite automaton. The overall process is: regular expression -> NFA -> DFA -> minimized DFA. If the input code is accepted by the finite automaton, it enters the syntax-analysis stage.

The most famous tools for lexical and syntax analysis are lex/yacc, along with their successors flex/bison. They provide language and text parsing capabilities for many pieces of software. They are powerful and interesting.

Although JavaScriptCore does not use them and instead implements its own lexer, the basic ideas are similar.

Data Types

As usual, let’s start with several basic data types used here.

CharacterType

JavaScript has the following character types, classified character by character:

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
// JavaScriptCore/parser/Lexer.cpp
enum CharacterType {
CharacterIdentifierStart,
CharacterZero,
CharacterNumber,

CharacterInvalid,
CharacterLineTerminator,
CharacterExclamationMark,
CharacterOpenParen,
CharacterCloseParen,
CharacterOpenBracket,
CharacterCloseBracket,
CharacterComma,
CharacterColon,
CharacterQuestion,
CharacterTilde,
CharacterQuote,
CharacterBackQuote,
CharacterDot,
CharacterSlash,
CharacterBackSlash,
CharacterSemicolon,
CharacterOpenBrace,
CharacterCloseBrace,

CharacterAdd,
CharacterSub,
CharacterMultiply,
CharacterModulo,
CharacterAnd,
CharacterXor,
CharacterOr,
CharacterLess,
CharacterGreater,
CharacterEqual,

CharacterWhiteSpace,
CharacterPrivateIdentifierStart
};

JSTokenType

JSTokenType in JavaScript is shown below. Every JavaScript keyword, arithmetic operator, and logical operator is listed as a token type. Since there are many token types, only part of them is shown here.

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
// JavaScriptCore/parser/ParseTokens.h
enum JSTokenType {
NULLTOKEN = KeywordTokenFlag,
TRUETOKEN,
FALSETOKEN,
BREAK,
CASE,
DEFAULT,
FOR,
NEW,
VAR,
LET,
CONSTTOKEN,
CONTINUE,
FUNCTION,
RETURN,
IF,
THISTOKEN,
DO,
WHILE,
SWITCH,
WITH,
RESERVED,
RESERVED_IF_STRICT,
THROW,
TRY,
CATCH,
FINALLY,
DEBUGGER,
ELSE,
IMPORT,
EXPORT,
YIELD,
CLASSTOKEN,
EXTENDS,
SUPER,
OPENBRACE = 0,
CLOSEBRACE,
OPENPAREN,
CLOSEPAREN,
OPENBRACKET,
CLOSEBRACKET,
COMMA,
QUESTION,
...

The mapping between the enum and keywords can be found in:

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
// JavaScriptCore/parser/Keywords.table
# Types.
null NULLTOKEN
true TRUETOKEN
false FALSETOKEN

# Keywords.
break BREAK
case CASE
catch CATCH
class CLASSTOKEN
const CONSTTOKEN
default DEFAULT
extends EXTENDS
finally FINALLY
for FOR
instanceof INSTANCEOF
new NEW
var VAR
let LET
continue CONTINUE
function FUNCTION
return RETURN
void VOIDTOKEN
delete DELETETOKEN
if IF
this THISTOKEN
do DO
while WHILE
else ELSE
in INTOKEN
super SUPER
switch SWITCH
throw THROW
try TRY
typeof TYPEOF
with WITH
debugger DEBUGGER
yield YIELD

...

Token

There is also a TokenType enum in the source code. This type is defined specifically for JSON parsing. Do not confuse it with the previous JSTokenType. It is not really part of the main topic, but it is worth mentioning to avoid confusion while reading the source code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// JavaScriptCore/runtime/LiteralParser.h
enum TokenType {
TokLBracket, // [
TokRBracket, // ]
TokLBrace, // {
TokRBrace, // }
TokString, // string
TokIdentifier, // identifier
TokNumber, // number
TokColon, // :
TokLParen, // (
TokRParen, // )
TokComma, // ,
TokTrue, // true
TokFalse, // false
TokNull, // null
TokEnd, // end
TokDot, // .
TokAssign, // =
TokSemi, // ;
TokError // error
};

JSToken

This type is more important. After JavaScript source code goes through lexical analysis, what we get is a sequence of JSToken values. It is a compound type:

JavaScriptCore Deep Dive 3 - Lexical Analysis: JSToken (figure 1)
1
2
3
4
5
6
7
struct JSToken {
JSTokenType m_type; // JSToken type.
JSTokenData m_data; // JSToken data.
JSTokenLocation m_location; // Location.
JSTextPosition m_startPosition; // Start position.
JSTextPosition m_endPosition; // End position.
};

JSTokenData is a union and can store four kinds of members. Different tokens represent their data differently. For example:

  • A parsed numeric literal can be represented by doubleValue.
  • A string may need the first structure.
  • A method name or variable name needs Identifier.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
union JSTokenData {
struct {
uint32_t line;
uint32_t offset;
uint32_t lineStartOffset;
};
double doubleValue;
const Identifier* ident;
struct {
const Identifier* cooked;
const Identifier* raw;
bool isTail;
};
};

JSTokenLocation contains the line number, line-start offset, source-file start offset, and source-file end offset:

1
2
3
4
5
6
struct JSTokenLocation {
int line;
unsigned lineStartOffset;
unsigned startOffset;
unsigned endOffset;
};

JSTextPosition represents a position. It contains the line number, source-file offset, and line offset:

1
2
3
4
5
struct JSTextPosition {
int line;
int offset;
int lineStartOffset;
};

Lexical Analysis Process

Lexer Initialization

In the project, the lexical-analysis class Lexer assists the Parser. The Parser class has a member variable named m_lexer, and it is initialized in the constructor:

1
2
3
4
5
6
7
8
9
10
// Definition.
std::unique_ptr<LexerType> m_lexer;

// Initialization in the constructor.
m_lexer = std::make_unique<LexerType>(vm, builtinMode);
m_lexer->setCode(source, &m_parserArena);
m_token.m_location.line = source.firstLine();
m_token.m_location.startOffset = source.startOffset();
m_token.m_location.endOffset = source.startOffset();
m_token.m_location.lineStartOffset = source.startOffset();

Identifier Parsing

It is then called in the Parser method nextExpectIdentifier. As the name suggests, it returns the next expected identifier.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ALWAYS_INLINE void nextExpectIdentifier(unsigned lexerFlags = 0)
{
// Save the end position of the previous token.
int lastLine = m_token.m_location.line;
int lastTokenEnd = m_token.m_location.endOffset;
int lastTokenLineStart = m_token.m_location.lineStartOffset;
m_lastTokenEndPosition = JSTextPosition(lastLine, lastTokenEnd, lastTokenLineStart);

// Set the line number.
m_lexer->setLastLineNumber(lastLine);

// Analyze the JSToken type.
m_token.m_type = m_lexer->lexExpectIdentifier(&m_token, lexerFlags, strictMode());
}

The logic lives in lexExpectIdentifier. Some alert-related code is removed here to keep the flow clear:

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
49
50
51
52
53
54
55
template <typename T>
ALWAYS_INLINE JSTokenType Lexer<T>::lexExpectIdentifier(JSToken* tokenRecord, unsigned lexerFlags, bool strictMode)
{
JSTokenData* tokenData = &tokenRecord->m_data;
JSTokenLocation* tokenLocation = &tokenRecord->m_location;

const T* start = m_code;
const T* ptr = start;
const T* end = m_codeEnd;
JSTextPosition startPosition = currentPosition();
if (ptr >= end) {
goto slowCase;
}

// It must be an ASCII character.
if (!WTF::isASCIIAlpha(*ptr))
goto slowCase;

// Walk forward until the next character is not a letter or digit.
++ptr;
while (ptr < end) {
if (!WTF::isASCIIAlphanumeric(*ptr))
break;
++ptr;
}

// Here's the shift
if (ptr < end) {
if ((!WTF::isASCII(*ptr)) || (*ptr == '\\') || (*ptr == '_') || (*ptr == '$'))
goto slowCase;
m_current = *ptr;
} else
m_current = 0;

m_code = ptr;

// Create an identifier. JSTokenType = IDENT.
if (lexerFlags & LexexFlagsDontBuildKeywords)
tokenData->ident = 0;
else
tokenData->ident = makeLCharIdentifier(start, ptr - start);

tokenLocation->line = m_lineNumber;
tokenLocation->lineStartOffset = currentLineStartOffset();
tokenLocation->startOffset = offsetFromSourcePtr(start);
tokenLocation->endOffset = currentOffset();
tokenRecord->m_startPosition = startPosition;
tokenRecord->m_endPosition = currentPosition();
m_lastToken = IDENT;
return IDENT;

slowCase:
// Core logic.
return lex(tokenRecord, lexerFlags, strictMode);
}

The point of this method is to open a fast path for identifiers. Source code contains a large number of identifiers. Compared with identifiers, keywords, constants, operators, and delimiters are less frequent. From a probability perspective, when parsing each JSToken, the result is very likely to be an identifier. This fast path saves time, which is exactly what the method name says: the next token is expected to be an identifier.

Core Logic

Apart from identifier parsing, the rest of the core lexical-analysis logic is in the lex method. The function is long, but the code and comments show the flow clearly:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
template <typename T>
JSTokenType Lexer<T>::lex(JSToken* tokenRecord, unsigned lexerFlags, bool strictMode)
{
JSTokenData* tokenData = &tokenRecord->m_data;
JSTokenLocation* tokenLocation = &tokenRecord->m_location;
m_lastTokenLocation = JSTokenLocation(tokenRecord->m_location);

JSTokenType token = ERRORTOK;
m_terminator = false;

start:
// Skip whitespace.
skipWhitespace();

// If we have reached the end, return EOFTOK.
if (atEnd()) return EOFTOK;

tokenLocation->startOffset = currentOffset();
ASSERT(currentOffset() >= currentLineStartOffset());
tokenRecord->m_startPosition = currentPosition();

// Determine the character type of the first character in the JSToken.
CharacterType type;
if (LIKELY(isLatin1(m_current)))
// typesOfLatin1Characters maps ASCII characters to CharacterType.
type = static_cast<CharacterType>(typesOfLatin1Characters[m_current]);
else if (isNonLatin1IdentStart(m_current))
type = CharacterIdentifierStart;
else if (isLineTerminator(m_current))
type = CharacterLineTerminator;
else
type = CharacterInvalid;

switch (type) {
case CharacterGreater:
shift();
if (m_current == '>')
{
shift();
if (m_current == '>') {
shift();
if (m_current == '=') {
shift();
// >>>= operator.
token = URSHIFTEQUAL;
break;
}

// >>> unsigned logical right shift.
token = URSHIFT;
break;
}
if (m_current == '=') {
shift();
// >>= operator.
token = RSHIFTEQUAL;
break;
}

// >> logical right shift.
token = RSHIFT;
break;
}

// >= greater-than-or-equal operator.
if (m_current == '=') {
shift();
token = GE;
break;
}

// > greater-than operator.
token = GT;
break;


case CharacterEqual:
{
if (peek(1) == '>') {
// Arrow function: x => x * x.
token = ARROWFUNCTION;
tokenData->line = lineNumber();
tokenData->offset = currentOffset();
tokenData->lineStartOffset = currentLineStartOffset();
ASSERT(tokenData->offset >= tokenData->lineStartOffset);
shift();
shift();
break;
}

shift();
if (m_current == '=') {
shift();
if (m_current == '=') {
shift();
// ===, strict equality: value and type.
token = STREQ;
break;
}

// ==, equality.
token = EQEQ;
break;
}

// =, assignment.
token = EQUAL;
break;
}

case CharacterLess:
shift();
if (m_current == '!' && peek(1) == '-' && peek(2) == '-') {
// <!-- single-line comment.
goto inSingleLineComment;
}
if (m_current == '<') {
shift();
if (m_current == '=') {
shift();
// <<= operator.
token = LSHIFTEQUAL;
break;
}
// << left shift.
token = LSHIFT;
break;
}
if (m_current == '=') {
shift();
// <= less-than-or-equal.
token = LE;
break;
}

// < less-than.
token = LT;
break;
case CharacterExclamationMark:
shift();
if (m_current == '=') {
shift();
if (m_current == '=') {
shift();
// !== strict inequality.
token = STRNEQ;
break;
}
// != inequality.
token = NE;
break;
}
// ! logical not.
token = EXCLAMATION;
break;
case CharacterAdd:
shift();
if (m_current == '+') {
shift();
token = (!m_terminator) ? PLUSPLUS : AUTOPLUSPLUS;
break;
}
if (m_current == '=') {
shift();
// += operator.
token = PLUSEQUAL;
break;
}
// + operator.
token = PLUS;
break;

case CharacterSub:
shift();
if (m_current == '-') {
shift();
if (m_atLineStart && m_current == '>') {
shift();
// Single-line comment.
goto inSingleLineComment;
}
token = (!m_terminator) ? MINUSMINUS : AUTOMINUSMINUS;
break;
}
if (m_current == '=') {
shift();
// -= operator.
token = MINUSEQUAL;
break;
}
token = MINUS;
break;
case CharacterMultiply:
shift();
if (m_current == '=') {
shift();
// *= operator.
token = MULTEQUAL;
break;
}
// * operator.
token = TIMES;
break;
case CharacterSlash:
shift();
if (m_current == '/') {
shift();
// Single-line comment.
goto inSingleLineCommentCheckForDirectives;
}
if (m_current == '*') {
// Multi-line comment.
shift();
if (parseMultilineComment())
goto start;
m_lexErrorMessage = ASCIILiteral("Multiline comment was not closed properly");
token = UNTERMINATED_MULTILINE_COMMENT_ERRORTOK;
goto returnError;
}
if (m_current == '=') {
shift();
// /= operator.
token = DIVEQUAL;
break;
}
// / division.
token = DIVIDE;
break;
case CharacterAnd:
shift();
if (m_current == '&') {
shift();
// && logical and.
token = AND;
break;
}
if (m_current == '=') {
shift();
// &= operator.
token = ANDEQUAL;
break;
}
// Bitwise and.
token = BITAND;
break;
case CharacterXor:
shift();
if (m_current == '=') {
shift();
token = XOREQUAL;
break;
}
token = BITXOR;
break;
case CharacterModulo:
shift();
if (m_current == '=') {
shift();
token = MODEQUAL;
break;
}
token = MOD;
break;
case CharacterOr:
shift();
if (m_current == '=') {
shift();
// |= operator.
token = OREQUAL;
break;
}
if (m_current == '|') {
shift();
// || logical or.
token = OR;
break;
}
// Bitwise or.
token = BITOR;
break;

case CharacterOpenParen:
// Left parenthesis: (
token = OPENPAREN;
tokenData->line = lineNumber();
tokenData->offset = currentOffset();
tokenData->lineStartOffset = currentLineStartOffset();
shift();
break;
case CharacterCloseParen:
// Right parenthesis: )
token = CLOSEPAREN;
shift();
break;
case CharacterOpenBracket:
// Left bracket: [
token = OPENBRACKET;
shift();
break;
case CharacterCloseBracket:
// Right bracket: ]
token = CLOSEBRACKET;
shift();
break;
case CharacterComma:
// Comma: ,
token = COMMA;
shift();
break;
case CharacterColon:
// Colon: :
token = COLON;
shift();
break;
case CharacterQuestion:
// Question mark: ?
token = QUESTION;
shift();
break;
case CharacterTilde:
// Tilde: ~
token = TILDE;
shift();
break;
case CharacterSemicolon:
// Semicolon: ;
shift();
token = SEMICOLON;
break;
case CharacterOpenBrace:
tokenData->line = lineNumber();
tokenData->offset = currentOffset();
tokenData->lineStartOffset = currentLineStartOffset();
shift();
// Left brace: {
token = OPENBRACE;
break;
case CharacterCloseBrace:
tokenData->line = lineNumber();
tokenData->offset = currentOffset();
tokenData->lineStartOffset = currentLineStartOffset();
shift();
// Right brace: }
token = CLOSEBRACE;
break;
case CharacterDot:
shift();
if (!isASCIIDigit(m_current)) {
if (UNLIKELY((m_current == '.') && (peek(1) == '.'))) {
shift();
shift();
// ... operator.
token = DOTDOTDOT;
break;
}
// . operator.
token = DOT;
break;
}
goto inNumberAfterDecimalPoint;
case CharacterZero:
shift();
// Hexadecimal number.
if ((m_current | 0x20) == 'x') {
if (!isASCIIHexDigit(peek(1))) {
m_lexErrorMessage = ASCIILiteral("No hexadecimal digits after '0x'");
token = UNTERMINATED_HEX_NUMBER_ERRORTOK;
goto returnError;
}

// Shift out the 'x' prefix.
shift();

parseHex(tokenData->doubleValue);
if (isIdentStart(m_current)) {
m_lexErrorMessage = ASCIILiteral("No space between hexadecimal literal and identifier");
token = UNTERMINATED_HEX_NUMBER_ERRORTOK;
goto returnError;
}
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
m_buffer8.shrink(0);
break;
}
// Binary number.
if ((m_current | 0x20) == 'b') {
if (!isASCIIBinaryDigit(peek(1))) {
m_lexErrorMessage = ASCIILiteral("No binary digits after '0b'");
token = UNTERMINATED_BINARY_NUMBER_ERRORTOK;
goto returnError;
}

// Shift out the 'b' prefix.
shift();

parseBinary(tokenData->doubleValue);
if (isIdentStart(m_current)) {
m_lexErrorMessage = ASCIILiteral("No space between binary literal and identifier");
token = UNTERMINATED_BINARY_NUMBER_ERRORTOK;
goto returnError;
}
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
m_buffer8.shrink(0);
break;
}
// Octal number.
if ((m_current | 0x20) == 'o') {
if (!isASCIIOctalDigit(peek(1))) {
m_lexErrorMessage = ASCIILiteral("No octal digits after '0o'");
token = UNTERMINATED_OCTAL_NUMBER_ERRORTOK;
goto returnError;
}

// Shift out the 'o' prefix.
shift();

parseOctal(tokenData->doubleValue);
if (isIdentStart(m_current)) {
m_lexErrorMessage = ASCIILiteral("No space between octal literal and identifier");
token = UNTERMINATED_OCTAL_NUMBER_ERRORTOK;
goto returnError;
}
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
m_buffer8.shrink(0);
break;
}

record8('0');
if (strictMode && isASCIIDigit(m_current)) {
m_lexErrorMessage = ASCIILiteral("Decimal integer literals with a leading zero are forbidden in strict mode");
token = UNTERMINATED_OCTAL_NUMBER_ERRORTOK;
goto returnError;
}
if (isASCIIOctalDigit(m_current)) {
if (parseOctal(tokenData->doubleValue)) {
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
}
}
FALLTHROUGH;
case CharacterNumber:
if (LIKELY(token != INTEGER && token != DOUBLE))
{
if (!parseDecimal(tokenData->doubleValue)) {
token = INTEGER;

// Parse the decimal part.
if (m_current == '.') {
shift();
inNumberAfterDecimalPoint:
parseNumberAfterDecimalPoint();
// We can now be sure this is a decimal number, so the type is DOUBLE.
token = DOUBLE;
}

// Parse the exponent part.
if ((m_current | 0x20) == 'e') {
if (!parseNumberAfterExponentIndicator()) {
m_lexErrorMessage = ASCIILiteral("Non-number found after exponent indicator");
token = atEnd() ? UNTERMINATED_NUMERIC_LITERAL_ERRORTOK : INVALID_NUMERIC_LITERAL_ERRORTOK;
goto returnError;
}
}
size_t parsedLength;
tokenData->doubleValue = parseDouble(m_buffer8.data(), m_buffer8.size(), parsedLength);
if (token == INTEGER)
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
} else
token = tokenTypeForIntegerLikeToken(tokenData->doubleValue);
}

if (UNLIKELY(isIdentStart(m_current))) {
m_lexErrorMessage = ASCIILiteral("No identifiers allowed directly after numeric literal");
token = atEnd() ? UNTERMINATED_NUMERIC_LITERAL_ERRORTOK : INVALID_NUMERIC_LITERAL_ERRORTOK;
goto returnError;
}
m_buffer8.shrink(0);
break;

case CharacterQuote: {
// Quote character. Parse a string.
StringParseResult result = StringCannotBeParsed;
if (lexerFlags & LexerFlagsDontBuildStrings)
result = parseString<false>(tokenData, strictMode);
else
result = parseString<true>(tokenData, strictMode);

if (UNLIKELY(result != StringParsedSuccessfully)) {
token = result == StringUnterminated ? UNTERMINATED_STRING_LITERAL_ERRORTOK : INVALID_STRING_LITERAL_ERRORTOK;
goto returnError;
}
shift();
token = STRING;
break;
}
case CharacterBackQuote: {
// Skip backquote.
shift();

// Parse a template literal.
StringParseResult result = StringCannotBeParsed;
if (lexerFlags & LexerFlagsDontBuildStrings)
result = parseTemplateLiteral<false>(tokenData, RawStringsBuildMode::BuildRawStrings);
else
result = parseTemplateLiteral<true>(tokenData, RawStringsBuildMode::BuildRawStrings);

if (UNLIKELY(result != StringParsedSuccessfully)) {
token = result == StringUnterminated ? UNTERMINATED_TEMPLATE_LITERAL_ERRORTOK : INVALID_TEMPLATE_LITERAL_ERRORTOK;
goto returnError;
}
token = TEMPLATE;
break;
}
case CharacterIdentifierStart:
ASSERT(isIdentStart(m_current));
FALLTHROUGH;
case CharacterBackSlash:
// Backslash: \.

parseIdent:
if (lexerFlags & LexexFlagsDontBuildKeywords)
token = parseIdentifier<false>(tokenData, lexerFlags, strictMode);
else
token = parseIdentifier<true>(tokenData, lexerFlags, strictMode);
break;
case CharacterLineTerminator:
// ASCII 10 and 13.
ASSERT(isLineTerminator(m_current));
shiftLineTerminator();
m_atLineStart = true;
m_terminator = true;
m_lineStart = m_code;
goto start;
case CharacterPrivateIdentifierStart:
if (m_parsingBuiltinFunction)
goto parseIdent;
FALLTHROUGH;
case CharacterInvalid:
m_lexErrorMessage = invalidCharacterMessage();
token = ERRORTOK;
goto returnError;
default:
RELEASE_ASSERT_NOT_REACHED();
m_lexErrorMessage = ASCIILiteral("Internal Error");
token = ERRORTOK;
goto returnError;
}

m_atLineStart = false;
goto returnToken;

inSingleLineCommentCheckForDirectives:
// Script comment directives like "//# sourceURL=test.js".
if (UNLIKELY((m_current == '#' || m_current == '@') && isWhiteSpace(peek(1)))) {
shift();
shift();
parseCommentDirective();
}
// Fall through to complete single line comment parsing.

inSingleLineComment:
while (!isLineTerminator(m_current)) {
if (atEnd())
return EOFTOK;
shift();
}
shiftLineTerminator();
m_atLineStart = true;
m_terminator = true;
m_lineStart = m_code;
if (!lastTokenWasRestrKeyword())
goto start;

token = SEMICOLON;
// Fall through into returnToken.

returnToken:
// Return the normal parse result.
tokenLocation->line = m_lineNumber;
tokenLocation->endOffset = currentOffset();
tokenLocation->lineStartOffset = currentLineStartOffset();
ASSERT(tokenLocation->endOffset >= tokenLocation->lineStartOffset);
tokenRecord->m_endPosition = currentPosition();
m_lastToken = token;
return token;

returnError:
// Return the error result.
m_error = true;
tokenLocation->line = m_lineNumber;
tokenLocation->endOffset = currentOffset();
tokenLocation->lineStartOffset = currentLineStartOffset();
ASSERT(tokenLocation->endOffset >= tokenLocation->lineStartOffset);
tokenRecord->m_endPosition = currentPosition();
RELEASE_ASSERT(token & ErrorTokenFlag);
return token;
}

The code is long, but this is the most important function in this article, so it is not omitted or shortened. Looking at it another way makes the flow much clearer, so it is worth reading together with the diagram below.

JavaScriptCore Deep Dive 3 - Lexical Analysis: Core Logic (figure 2)

After the switch statement above finishes, a JSToken has been produced. Most cases are straightforward and easy to understand, but several important methods deserve a closer look.

String Parsing

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
template <typename T>
template <bool shouldBuildStrings> ALWAYS_INLINE typename Lexer<T>::StringParseResult Lexer<T>::parseString(JSTokenData* tokenData, bool strictMode)
{
int startingOffset = currentOffset();
int startingLineStartOffset = currentLineStartOffset();
int startingLineNumber = lineNumber();
T stringQuoteCharacter = m_current;
shift();

const T* stringStart = currentSourcePtr();

// Traverse until the next matching quote is found.
while (m_current != stringQuoteCharacter)
{
if (UNLIKELY(m_current == '\\')) {
// Escape character.
if (stringStart != currentSourcePtr() && shouldBuildStrings)
append8(stringStart, currentSourcePtr() - stringStart);
shift();

// ASCII 0~127.
LChar escape = singleEscape(m_current);

// Most common escape sequences first.
if (escape) {
// If this is a common ASCII escape, shift directly.
if (shouldBuildStrings)record8(escape);
shift();
} else if (UNLIKELY(isLineTerminator(m_current)))
// Skip line terminators: \n and \r.
shiftLineTerminator();
else if (m_current == 'x')
{
// Parse hexadecimal escapes inside strings.
// \x must be followed by two hexadecimal digits, from \x00 to \xff.
shift();
if (!isASCIIHexDigit(m_current) || !isASCIIHexDigit(peek(1))) {
// This is not a valid hexadecimal escape.
m_lexErrorMessage = ASCIILiteral("\\x can only be followed by a hex character sequence");
return (atEnd() || (isASCIIHexDigit(m_current) && (m_code + 1 == m_codeEnd))) ? StringUnterminated : StringCannotBeParsed;
}

// Normal hexadecimal escape: \x00 ~ \xff.
T prev = m_current;
shift();
if (shouldBuildStrings)
record8(convertHex(prev, m_current));
shift();
}
else
{
// All remaining cases go through the slow path: parseStringSlowCase.
setOffset(startingOffset, startingLineStartOffset);
setLineNumber(startingLineNumber);
m_buffer8.shrink(0);
return parseStringSlowCase<shouldBuildStrings>(tokenData, strictMode);
}
stringStart = currentSourcePtr();
continue;
}

// Use the slow string parsing path.
if (UNLIKELY(characterRequiresParseStringSlowCase(m_current))) {
setOffset(startingOffset, startingLineStartOffset);
setLineNumber(startingLineNumber);
m_buffer8.shrink(0);
return parseStringSlowCase<shouldBuildStrings>(tokenData, strictMode);
}

shift();
}

// Confirm the string region and store it in m_buffer8.
if (currentSourcePtr() != stringStart && shouldBuildStrings)
append8(stringStart, currentSourcePtr() - stringStart);

if (shouldBuildStrings) {
// Create an identifier.
tokenData->ident = makeIdentifier(m_buffer8.data(), m_buffer8.size());
m_buffer8.shrink(0);
} else
tokenData->ident = 0;

return StringParsedSuccessfully;
}

The flow of parseStringSlowCase is very similar to parseString: it handles escape characters, line terminators, and finally creates an identifier. The difference is that parseStringSlowCase uses m_buffer16, while parseString uses m_buffer8.

1
2
3
4
5
typedef unsigned char LChar;
typedef uint16_t UChar;

Vector<LChar> m_buffer8;
Vector<UChar> m_buffer16;
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
49
50
51
52
53
54
55
56
57
58
59
60
template <typename T>
template <bool shouldBuildStrings> auto Lexer<T>::parseStringSlowCase(JSTokenData* tokenData, bool strictMode) -> StringParseResult
{
T stringQuoteCharacter = m_current;
shift();

const T* stringStart = currentSourcePtr();

while (m_current != stringQuoteCharacter) {
if (UNLIKELY(m_current == '\\')) {
// Special handling for escape characters.
if (stringStart != currentSourcePtr() && shouldBuildStrings)
append16(stringStart, currentSourcePtr() - stringStart);
shift();

LChar escape = singleEscape(m_current);

// Most common escape sequences first
if (escape) {
if (shouldBuildStrings)
record16(escape);
shift();
} else if (UNLIKELY(isLineTerminator(m_current)))
shiftLineTerminator();
else {
StringParseResult result = parseComplexEscape<shouldBuildStrings>(EscapeParseMode::String, strictMode, stringQuoteCharacter);
if (result != StringParsedSuccessfully)
return result;
}

stringStart = currentSourcePtr();
continue;
}

// Characters that need special handling.
// Fast check for characters that require special handling.
// Catches 0, \n, \r, 0x2028, and 0x2029 as efficiently
// as possible, and lets through all common ASCII characters.
if (UNLIKELY(((static_cast<unsigned>(m_current) - 0xE) & 0x2000))) {
// New-line or end of input is not allowed
if (atEnd() || isLineTerminator(m_current)) {
m_lexErrorMessage = ASCIILiteral("Unexpected EOF");
return atEnd() ? StringUnterminated : StringCannotBeParsed;
}
// Anything else is just a normal character
}
shift();
}

// Normal logic reaches here.
if (currentSourcePtr() != stringStart && shouldBuildStrings)
append16(stringStart, currentSourcePtr() - stringStart);
if (shouldBuildStrings)
tokenData->ident = makeIdentifier(m_buffer16.data(), m_buffer16.size());
else
tokenData->ident = 0;

m_buffer16.shrink(0);
return StringParsedSuccessfully;
}

After the start position, length, and content of the string are determined, let’s look at how identifiers are created:

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
template <typename CharType>
ALWAYS_INLINE const Identifier LiteralParser<CharType>::makeIdentifier(const LChar* characters, size_t length)
{
// If length is 0, return emptyIdentifier.
if (!length)
return m_exec->vm().propertyNames->emptyIdentifier;

// static const int MaximumCachableCharacter = 128;
if (characters[0] >= MaximumCachableCharacter)
return Identifier::fromString(&m_exec->vm(), characters, length);

// Handling for one-character strings. m_shortIdentifiers caches them in memory.
if (length == 1) {
if (!m_shortIdentifiers[characters[0]].isNull())
return m_shortIdentifiers[characters[0]];
m_shortIdentifiers[characters[0]] = Identifier::fromString(&m_exec->vm(), characters, length);
return m_shortIdentifiers[characters[0]];
}

// characters[0] < 128 && length > 1: cache through m_recentIdentifiers.

if (!m_recentIdentifiers[characters[0]].isNull() && Identifier::equal(m_recentIdentifiers[characters[0]].impl(), characters, length))
return m_recentIdentifiers[characters[0]];
m_recentIdentifiers[characters[0]] = Identifier::fromString(&m_exec->vm(), characters, length);
return m_recentIdentifiers[characters[0]];
}

No matter which path is taken, it eventually depends on Identifier::fromString. This method already touches the virtual machine. Think about it: creating an identifier must go through VM-level recording so that later access and repeated processing can reuse it. This is not a good place to keep digging, or we will get stuck in another swamp. Interested readers can continue from there.

Decimal Number Parsing

First, look at the DFA for decimal numbers:

JavaScriptCore Deep Dive 3 - Lexical Analysis: Decimal Number Parsing (figure 3)

Then the parsed decimal string is evaluated and stored in returnValue.

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
template <typename T>
ALWAYS_INLINE bool Lexer<T>::parseDecimal(double& returnValue)
{
// Optimization: most decimal values fit into 4 bytes.
uint32_t decimalValue = 0;

// Since parseOctal may be executed before parseDecimal,
// the m_buffer8 may hold ascii digits.
if (!m_buffer8.size())
{
const unsigned maximumDigits = 10;
int digit = maximumDigits - 1;
// Temporary buffer for the digits. Makes easier
// to reconstruct the input characters when needed.
LChar digits[maximumDigits];

// Walk digit by digit. For every character moved to the right,
// multiply decimalValue by 10 and add (m_current - '0').
do {
decimalValue = decimalValue * 10 + (m_current - '0');
digits[digit] = m_current;
shift();
--digit;
} while (isASCIIDigit(m_current) && digit >= 0);

if (digit >= 0 && m_current != '.' && (m_current | 0x20) != 'e') {
// If there is no decimal point and no exponent marker e, return decimalValue directly.
returnValue = decimalValue;
return true;
}

for (int i = maximumDigits - 1; i > digit; --i)
record8(digits[i]);
}

// If a non-digit character appears, the parse result is abnormal for the fast path.
while (isASCIIDigit(m_current)) {
record8(m_current);
shift();
}

return false;
}

Hexadecimal Number Parsing

First, look at how a hexadecimal number is recognized:

JavaScriptCore Deep Dive 3 - Lexical Analysis: Hexadecimal Number Parsing (figure 4)

Then the value of the hexadecimal number is calculated:

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
template <typename T>
ALWAYS_INLINE void Lexer<T>::parseHex(double& returnValue)
{
// Optimization: most hexadecimal values fit in 4 bytes.
uint32_t hexValue = 0;
int maximumDigits = 7;

// toASCIIHexValue : character < 'A' ? character - '0' : (character - 'A' + 10) & 0xF
// Shift hexValue left by 4 bits, compute the decimal value of the current hex character,
// and add it to hexValue.
do {
hexValue = (hexValue << 4) + toASCIIHexValue(m_current);
shift();
--maximumDigits;
} while (isASCIIHexDigit(m_current) && maximumDigits >= 0);

if (maximumDigits >= 0) {
returnValue = hexValue;
return;
}

// If maximumDigits is less than 0, 4 bytes are not enough.
// No more place in the hexValue buffer.
// The values are shifted out and placed into the m_buffer8 vector.
// Store the hexadecimal characters parsed earlier in m_buffer8.
for (int i = 0; i < 8; ++i) {
int digit = hexValue >> 28;
if (digit < 10)
record8(digit + '0');
else
record8(digit - 10 + 'a');
hexValue <<= 4;
}

// Continue appending the following hexadecimal characters to m_buffer8.
while (isASCIIHexDigit(m_current)) {
record8(m_current);
shift();
}

// Use parseIntOverflow to parse the hexadecimal number.
returnValue = parseIntOverflow(m_buffer8.data(), m_buffer8.size(), 16);
}

Octal Number Parsing

The approach is the same, so there is not much more to say:

JavaScriptCore Deep Dive 3 - Lexical Analysis: Octal Number Parsing (figure 5)
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
template <typename T>
ALWAYS_INLINE bool Lexer<T>::parseOctal(double& returnValue)
{
// Optimization: most octal values fit into 4 bytes.
uint32_t octalValue = 0;
const unsigned maximumDigits = 10;
int digit = maximumDigits - 1;
// Temporary buffer for the digits. Makes easier
// to reconstruct the input characters when needed.
LChar digits[maximumDigits];

do {
octalValue = octalValue * 8 + (m_current - '0');
digits[digit] = m_current;
shift();
--digit;
} while (isASCIIOctalDigit(m_current) && digit >= 0);

if (!isASCIIDigit(m_current) && digit >= 0) {
returnValue = octalValue;
return true;
}

for (int i = maximumDigits - 1; i > digit; --i)
record8(digits[i]);

while (isASCIIOctalDigit(m_current)) {
record8(m_current);
shift();
}

if (isASCIIDigit(m_current))
return false;

returnValue = parseIntOverflow(m_buffer8.data(), m_buffer8.size(), 8);
return true;
}

Integer Overflow in Arbitrary Bases

Next is the standard integer parsing process. Binary, octal, decimal, and hexadecimal integers can all be parsed through this function. radix represents the base.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double parseIntOverflow(const LChar* s, unsigned length, int radix)
{
double number = 0.0;
double radixMultiplier = 1.0;

for (const LChar* p = s + length - 1; p >= s; p--) {
if (radixMultiplier == std::numeric_limits<double>::infinity()) {
if (*p != '0') {
number = std::numeric_limits<double>::infinity();
break;
}
} else {
int digit = parseDigit(*p, radix);
number += digit * radixMultiplier;
}

radixMultiplier *= radix;
}

return number;
}

Decimal Points and Exponents

The floating-point parsing process can be represented by the following DFA:

JavaScriptCore Deep Dive 3 - Lexical Analysis: Decimal Points and Exponents (figure 6)
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
template <typename T>
ALWAYS_INLINE void Lexer<T>::parseNumberAfterDecimalPoint()
{
// record8: Vector<LChar> m_buffer8. Add the current character to m_buffer8.
record8('.');

// After the decimal point, as long as the character is a digit, add it to m_buffer8.
while (isASCIIDigit(m_current)) {
record8(m_current);
shift();
}
}

template <typename T>
ALWAYS_INLINE bool Lexer<T>::parseNumberAfterExponentIndicator()
{
record8('e');
shift();

// Determine the sign of the exponent part.
if (m_current == '+' || m_current == '-') {
record8(m_current);
shift();
}

// If it is not a digit, parsing fails.
if (!isASCIIDigit(m_current))
return false;

// As long as the character is a digit, add it to m_buffer8.
do {
record8(m_current);
shift();
} while (isASCIIDigit(m_current));

return true;
}

Multi-line Comment Parsing

The DFA for multi-line comments:

JavaScriptCore Deep Dive 3 - Lexical Analysis: Multi-line Comment Parsing (figure 7)
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
template <typename T>
ALWAYS_INLINE bool Lexer<T>::parseMultilineComment()
{
while (true)
{
// Find the closest */ after the opening /*. The * and / must be adjacent.
while (UNLIKELY(m_current == '*')) {
shift();
if (m_current == '/') {
shift();
return true;
}
}

// Reached the end, so this is an error.
if (atEnd()) return false;

if (isLineTerminator(m_current)) {
// End of line. Skip it.
shiftLineTerminator();
m_terminator = true;
} else{
// Skip the current character directly.
shift();
}
}
}

Example Update

For example, take this JavaScript code. It contains a function, a variable, and a function call:

1
2
3
4
5
6
7
8
function test(age){
if(age > 10){
console.log(age);
}
}

var age = 6 * 7;
test(age);

After lexical analysis with Esprima, the following result is produced:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
[
{
"type": "Keyword",
"value": "function"
},
{
"type": "Identifier",
"value": "test"
},
{
"type": "Punctuator",
"value": "("
},
{
"type": "Identifier",
"value": "age"
},
{
"type": "Punctuator",
"value": ")"
},
{
"type": "Punctuator",
"value": "{"
},
{
"type": "Keyword",
"value": "if"
},
{
"type": "Punctuator",
"value": "("
},
{
"type": "Identifier",
"value": "age"
},
{
"type": "Punctuator",
"value": ">"
},
{
"type": "Numeric",
"value": "10"
},
{
"type": "Punctuator",
"value": ")"
},
{
"type": "Punctuator",
"value": "{"
},
{
"type": "Identifier",
"value": "console"
},
{
"type": "Punctuator",
"value": "."
},
{
"type": "Identifier",
"value": "log"
},
{
"type": "Punctuator",
"value": "("
},
{
"type": "Identifier",
"value": "age"
},
{
"type": "Punctuator",
"value": ")"
},
{
"type": "Punctuator",
"value": ";"
},
{
"type": "Punctuator",
"value": "}"
},
{
"type": "Punctuator",
"value": "}"
},
{
"type": "Keyword",
"value": "var"
},
{
"type": "Identifier",
"value": "age"
},
{
"type": "Punctuator",
"value": "="
},
{
"type": "Numeric",
"value": "6"
},
{
"type": "Punctuator",
"value": "*"
},
{
"type": "Numeric",
"value": "7"
},
{
"type": "Punctuator",
"value": ";"
},
{
"type": "Identifier",
"value": "test"
},
{
"type": "Punctuator",
"value": "("
},
{
"type": "Identifier",
"value": "age"
},
{
"type": "Punctuator",
"value": ")"
},
{
"type": "Punctuator",
"value": ";"
}
]

Summary

After this process, a complete token in the JSC world is produced, and the whole world becomes quiet.

-------------本文结束 感谢您的阅读-------------
If this article helped you, your support encourages me to keep writing.

Title:JavaScriptCore Deep Dive 3 - Lexical Analysis

Author:lingyun

Published:2018-07-30 00:32

Updated:2026-10-08 00:23

Original link:https://tsuijunxi.github.io/en/2018/07/30/javascriptcore-deep-dive-3-lexical-analysis/

License: Attribution-NonCommercial-NoDerivatives 4.0 International Please keep the original link and author when sharing.