JavaScriptCore Deep Dive 4 - Syntax Analysis

Preface

In JavaScriptCore Deep Dive 3 - Lexical Analysis, we mentioned that Lexer exists as a member of Parser. Its main purpose is to provide one JSToken after another to Parser. The dependency diagram is shown below:

JavaScriptCore Deep Dive 4 - Syntax Analysis: Preface (figure 1)

As you can see, the lexical-analysis article spent a lot of space and still only covered the upper half of the diagram. Even so, many things were only touched lightly, and many details were not covered, because the source code is simply too large and my ability is limited.

There is still a long road ahead.

In any case, the lexical-analysis article laid some groundwork for our continued analysis. Now let’s move on and try to finish the lower half of the diagram in this article.

Note: some source-code snippets are trimmed to keep the code clear and easier to analyze. This does not mean the removed logic is unimportant. If you want the full implementation, I recommend reading the corresponding files in the source project.

Syntax Analysis Overview

In compiler theory, syntax analysis can generally be divided into top-down and bottom-up approaches:

  • Top-down analysis: builds the parse tree from the top, or root node, toward the bottom, or leaf nodes. Recursive descent parsing is the common form of top-down parsing. It may require backtracking and can be inefficient, so predictive analysis is introduced. By looking ahead a fixed number of symbols, k, in the input, it chooses the correct production. The most typical example is LL(1) grammar, which eliminates ambiguity, left recursion, and backtracking. Based on LL(1), one may further compute FIRST, FOLLOW, and SELECT sets, then introduce a predictive parsing table to choose productions.
  • Bottom-up analysis: builds the parse tree from the bottom, or leaf nodes, toward the top, or root node. The common framework for bottom-up syntax analysis is shift-reduce parsing. LR grammars are the largest class of grammars for which corresponding shift-reduce parsers can be constructed. Representative forms include LR(0), SLR, LR(1), and LALR.

The JavaScript syntax analysis discussed here uses recursive descent. It is suitable for handwritten parsers and is relatively simple. Recursive descent imposes some restrictions on the grammar, but it is still a mainstream parsing approach because it can be highly controlled by developers and has advantages in producing error messages.

Syntax Tree

The input of JavaScriptCore’s lexical analysis is a stream of JSToken values, and the output of syntax analysis is a parse tree.

For example, suppose we have the following JavaScript code:

1
2
3
4
5
6
7
8
9
10
function foo(x) {
var sum = 0;
if (x > 10) {
while(x > 0){
sum += x;
x--;
}
}
return sum;
}

After syntax analysis, we get a simplified parse tree like this:

JavaScriptCore Deep Dive 4 - Syntax Analysis: Syntax Tree (figure 2)

Syntax Tree Nodes

Before diving into the details of the syntax tree, let’s first look at its nodes:

JavaScriptCore Deep Dive 4 - Syntax Analysis: Syntax Tree Nodes (figure 3)

High-resolution version

The diagram contains most nodes in the syntax tree. The most important nodes are clearly ExpressionNode and StatementNode, and most nodes in the diagram inherit from one of them.

  • StatementNode: a basic statement node. Its child nodes mainly describe language structures:
    1. Sequential structures, such as ClassDeclNode and DeclarationStateMentNode.
    2. Conditional structures, such as IFElseNode and SwitchNode.
    3. Loop structures, such as WhileNode, ForNode, and DoWhileNode.
    4. Another major node is ScopeNode, which describes scope regions.
  • ExpressionNode: an expression node. Its child nodes mainly describe different expressions:
    1. ConstantNode, a constant node, from which string, boolean, integer, and floating-point nodes are derived.
    2. BinaryOpNode, a binary operator node, from which addition, subtraction, multiplication, division, modulo, left shift, right shift, and similar operator nodes are derived.
    3. There are also regular-expression nodes, this nodes, super nodes, and so on.

Node Memory Management

ParserArenaFreeable and ParserArenaDeletable

From the diagram, most Node classes eventually trace back to ParserArenaFreeable. This class overloads C++’s new operator to implement its own memory-management strategy instead of relying on the default new and delete object mechanism.

If you are familiar with C++, you will notice that this is very similar to placement new/delete. It repeatedly uses a larger dynamically allocated memory block to construct objects of different types, or arrays of those objects. For example, it can first allocate a sufficiently large character array, then construct objects or arrays on top of it as needed. It does not worry about allocation failure during object construction because it does not allocate memory at that point; it only calls the object’s constructor.

1
2
3
4
5
6
7
8
9
class ParserArenaFreeable {
public:
void* operator new(size_t, ParserArena&);
};

inline void* ParserArenaFreeable::operator new(size_t size, ParserArena& parserArena)
{
return parserArena.allocateFreeable(size);
}
  • ParserArenaFreeable objects are freed when the arena is deleted.
  • Destructors are not called. Clients must not call delete on such objects.

Therefore, if a node inherits from ParserArenaFreeable, do not implement cleanup logic in its destructor. Even if you write one, it will not be called.

For example, a StringNode is created like this, where ParserArena& m_parserArena is used:

1
2
3
4
ExpressionNode* createString(const JSTokenLocation& location, const Identifier* string)
{
return new (m_parserArena) StringNode(location, *string);
}

There is also ParserArenaDeletable, which is similar to ParserArenaFreeable, except that its destructor can be called. If a node needs its destructor to run and perform release logic, it can inherit from ParserArenaDeletable.

1
2
3
4
5
 class ParserArenaDeletable {
public:
virtual ~ParserArenaDeletable() { }
void* operator new(size_t, ParserArena&);
};
  • ParserArenaDeletable objects are deleted when the arena is deleted.
  • Destructors can be called. Clients must not call delete directly on such objects.

If you want to explore the memory-allocation mechanism further, look at ParserArena.

  1. Two important allocation methods:
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
void* allocateFreeable(size_t size)
{
// Byte alignment.
size_t alignedSize = alignSize(size);

// If the current memory block is not enough, expand it and record
// the allocated address in m_freeablePools.
if ((m_freeablePoolEnd - m_freeableMemory) < alignedSize))
allocateFreeablePool();

// Allocate address.
void* block = m_freeableMemory;

// Update available address.
m_freeableMemory += alignedSize;

return block;
}

void* allocateDeletable(size_t size)
{
// First call allocateFreeable to allocate memory.
ParserArenaDeletable* deletable = static_cast<ParserArenaDeletable*>(allocateFreeable(size));

// Add the allocated address to m_deletableObjects so destructors can be called later.
m_deletableObjects.append(deletable);

// Return address.
return deletable;
}
  1. ParserArena destructor:

First, call the destructor for every object in m_deletableObjects. Then release every address previously recorded in m_freeablePools.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ParserArena::~ParserArena()
{
deallocateObjects();
}

inline void ParserArena::deallocateObjects()
{
// Call destructors.
size_t size = m_deletableObjects.size();
for (size_t i = 0; i < size; ++i)
m_deletableObjects[i]->~ParserArenaDeletable();

if (m_freeablePoolEnd)
fastFree(freeablePool());

// Release all allocated memory blocks.
size = m_freeablePools.size();
for (size_t i = 0; i < size; ++i)
fastFree(m_freeablePools[i]);
}

ASTBuilder

ASTBuilder is used to build the AST. It mainly contains:

  • A virtual machine, m_vm.
  • The memory-management class ParserArena.
  • A source-code object, SourceCode.
  • Scope information.
  • Four stack containers.
1
2
3
4
5
6
7
8
9
10
11
12
13
class ASTBuilder
{
...
VM* m_vm;
ParserArena& m_parserArena;
SourceCode* m_sourceCode;
Scope m_scope;
Vector<BinaryOperand, 10, UnsafeVectorOverflow> m_binaryOperandStack;
Vector<AssignmentInfo, 10, UnsafeVectorOverflow> m_assignmentInfoStack;
Vector<std::pair<int, int>, 10, UnsafeVectorOverflow> m_binaryOperatorStack;
Vector<std::pair<int, JSTextPosition>, 10, UnsafeVectorOverflow> m_unaryTokenStack;
int m_evalCount;
}

Vector

Vector is different from STL’s vector. It is a utility class in WebKit’s base library, located at:

webkit-master/Source/WTF/wtf/Vector.h

Its template parameters are declared as follows:

1
template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow, size_t minCapacity = 16>
  • The first parameter is the stored data type.
  • The second parameter is capacity.
  • The third parameter is the overflow handler. The default is CrashOnOverflow; here UnsafeVectorOverflow is used. Both eventually lead to CRASH().
  • The fourth parameter is the minimum capacity. We do not pass it here, so the default value 16 is used.

Operand: BinaryOperand

1
typedef int BinaryOperand;

Binary Operation Structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct BinaryOpInfo 
{
BinaryOpInfo() {}
BinaryOpInfo(const JSTextPosition& otherStart, const JSTextPosition& otherDivot, const JSTextPosition& otherEnd, bool rhsHasAssignment)
: start(otherStart)
, divot(otherDivot)
, end(otherEnd)
, hasAssignment(rhsHasAssignment)
{
}
BinaryOpInfo(const BinaryOpInfo& lhs, const BinaryOpInfo& rhs)
: start(lhs.start)
, divot(rhs.start)
, end(rhs.end)
, hasAssignment(lhs.hasAssignment || rhs.hasAssignment)
{
}
JSTextPosition start;
JSTextPosition divot;
JSTextPosition end;
bool hasAssignment;
};

Assignment Structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct AssignmentInfo 
{
AssignmentInfo() {}
AssignmentInfo(ExpressionNode* node, const JSTextPosition& start, const JSTextPosition& divot, int initAssignments, Operator op)
: m_node(node)
, m_start(start)
, m_divot(divot)
, m_initAssignments(initAssignments)
, m_op(op)
{
}
ExpressionNode* m_node;
JSTextPosition m_start;
JSTextPosition m_divot;
int m_initAssignments;
Operator m_op;
};

Operator is an enum:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
enum Operator
{
OpEqual,
OpPlusEq,
OpMinusEq,
OpMultEq,
OpDivEq,
OpPlusPlus,
OpMinusMinus,
OpAndEq,
OpXOrEq,
OpOrEq,
OpModEq,
OpLShift,
OpRShift,
OpURShift
};

Parse Stack

JavaScriptCore’s syntax analysis starts from parse. The core of parse is parseInner, whose two parameter types are Identifier and SourceParseMode. Identifier was mentioned earlier and represents an identifier. SourceParseMode is an enum:

1
2
3
4
5
6
7
8
9
10
11
12
13
enum class SourceParseMode : uint8_t 
{
NormalFunctionMode,
GeneratorBodyMode,
GeneratorWrapperFunctionMode,
GetterMode,
SetterMode,
MethodMode,
ArrowFunctionMode,
ProgramMode,
ModuleAnalyzeMode,
ModuleEvaluateMode
};

The internal call flow of parse is roughly:

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
parse
└──parseInner
└──parseArrowFunctionSingleExpressionBodySourceElements (arrow function)
└──parseModuleSourceElements (module import/export)
└──parseGeneratorFunctionSourceElements
└──parseSourceElements
└──parseStatementListItem (statement list)
└──parseVariableDeclaration (var/let declarations)
└──parseClassDeclaration (class declaration)
└──parseFunctionDeclaration (function declaration)
└──parseExpressionOrLabelStatement (expression or label)
└──parseStatement (basic statement)
└──parseBlockStatement
└──parseVariableDeclaration
└──parseFunctionDeclaration
└──parseIfStatement
└──parseDoWhileStatement
└──parseWhileStatement
└──parseForStatement
└──parseContinueStatement
└──parseBreakStatement
└──parseReturnStatement
└──parseWithStatement
└──parseSwitchStatement
└──parseThrowStatement
└──parseTryStatement
└──parseExpressionOrLabelStatement
└──parseExpressionStatement
└──parseExpression

Some statements are nested inside one another. For example, parseIfStatement can continue calling parseStatement. Since the codebase is large and cannot be analyzed one by one, this article focuses on the following path:

1
2
3
4
5
6
7
8
9
parse
└──parseInner
└──parseSourceElements
└──parseStatementListItem (statement list)
└──parseStatement (basic statement)
└──parseVariableDeclaration
└──parseWhileStatement
└──parseExpressionStatement
└──parseExpression

parseInner

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
// Perform syntax analysis and generate the abstract syntax tree.
// Some code is omitted for clarity.
template <typename LexerType>
String Parser<LexerType>::parseInner(const Identifier& calleeName, SourceParseMode parseMode)
{
String parseError = String();

// Define ASTBuilder.
ASTBuilder context(const_cast<VM*>(m_vm), m_parserArena, const_cast<SourceCode*>(m_source));

// Set scope.
ScopeRef scope = currentScope();
scope->setIsLexicalScope();
SetForScope<FunctionParsePhase> functionParsePhasePoisoner(m_parserState.functionParsePhase, FunctionParsePhase::Body);

...

if (!calleeName.isNull())
scope->declareCallee(&calleeName);
if (m_lexer->isReparsingFunction())
m_statementDepth--;

// Start parsing and generate a syntax-tree node.
SourceElements* sourceElements = nullptr;

// Core logic.
if (!hasError())
{
if (isArrowFunctionBodyExpression)
// Arrow function.
sourceElements = parseArrowFunctionSingleExpressionBodySourceElements(context);
else if (isModuleParseMode(parseMode))
// Module import/export.
sourceElements = parseModuleSourceElements(context, parseMode);
else
{
if (parseMode == SourceParseMode::GeneratorWrapperFunctionMode)
sourceElements = parseGeneratorFunctionSourceElements(context, CheckForStrictMode);
else
// Basic statement parsing.
sourceElements = parseSourceElements(context, CheckForStrictMode);
}
}

...

didFinishParsing(sourceElements, scope->takeFunctionDeclarations(), varDeclarations, WTFMove(sloppyModeHoistedFunctions), features, context.numConstants());

return parseError;
}

parseSourceElements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename LexerType>
template <class TreeBuilder> TreeSourceElements Parser<LexerType>::parseSourceElements(TreeBuilder& context, SourceElementsMode mode)
{
const unsigned lengthOfUseStrictLiteral = 12; // "use strict".length
TreeSourceElements sourceElements = context.createSourceElements();
bool seenNonDirective = false;
const Identifier* directive = 0;
unsigned directiveLiteralLength = 0;
auto savePoint = createSavePoint();
bool hasSetStrict = false;

// Main logic is in parseStatementListItem.
while (TreeStatement statement = parseStatementListItem(context, directive, &directiveLiteralLength)) {
...

// Add syntax node to ASTBuilder.
context.appendStatement(sourceElements, statement);
}

propagateError();
return sourceElements;
}

parseStatementListItem

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
template <typename LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseStatementListItem(TreeBuilder& context, const Identifier*& directive, unsigned* directiveLiteralLength)
{
DepthManager statementDepth(&m_statementDepth);
m_statementDepth++;
TreeStatement result = 0;
bool shouldSetEndOffset = true;
switch (m_token.m_type)
{
case CONSTTOKEN:
// Variable declaration parsing.
result = parseVariableDeclaration(context, DeclarationType::ConstDeclaration);
break;
case LET: {
bool shouldParseVariableDeclaration = true;
if (shouldParseVariableDeclaration)
result = parseVariableDeclaration(context, DeclarationType::LetDeclaration);
else {
bool allowFunctionDeclarationAsStatement = true;
result = parseExpressionOrLabelStatement(context, allowFunctionDeclarationAsStatement);
}

break;
}
case CLASSTOKEN:
// Class declaration parsing.
result = parseClassDeclaration(context);
break;
case FUNCTION:
// Function declaration parsing.
result = parseFunctionDeclaration(context);
break;
case IDENT:
case YIELD: {
// Expression or label parsing.
bool allowFunctionDeclarationAsStatement = true;
result = parseExpressionOrLabelStatement(context, allowFunctionDeclarationAsStatement);
break;
}
default:
// Ordinary statement parsing.
m_statementDepth--; // parseStatement() increments the depth.
result = parseStatement(context, directive, directiveLiteralLength);
shouldSetEndOffset = false;
break;
}
}

if (result && shouldSetEndOffset)
context.setEndOffset(result, m_lastTokenEndPosition.offset);

return result;
}

parseStatement

Basic statement parsing is performed through switch branches:

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
template <typename LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseStatement(TreeBuilder& context, const Identifier*& directive, unsigned* directiveLiteralLength)
{
DepthManager statementDepth(&m_statementDepth);
m_statementDepth++;
directive = 0;
int nonTrivialExpressionCount = 0;
failIfStackOverflow();
TreeStatement result = 0;
bool shouldSetEndOffset = true;
bool parentAllowsFunctionDeclarationAsStatement = m_immediateParentAllowsFunctionDeclarationInStatement;
m_immediateParentAllowsFunctionDeclarationInStatement = false;

switch (m_token.m_type)
{
case OPENBRACE:
result = parseBlockStatement(context);
shouldSetEndOffset = false;
break;
case VAR:
result = parseVariableDeclaration(context, DeclarationType::VarDeclaration);
break;
case FUNCTION: {
DepthManager statementDepth(&m_statementDepth);
m_statementDepth = 1;
result = parseFunctionDeclaration(context);
break;
}
case SEMICOLON: {
JSTokenLocation location(tokenLocation());
next();
result = context.createEmptyStatement(location);
break;
}
case IF:
result = parseIfStatement(context);
break;
case DO:
result = parseDoWhileStatement(context);
break;
case WHILE:
result = parseWhileStatement(context);
break;
case FOR:
result = parseForStatement(context);
break;
case CONTINUE:
result = parseContinueStatement(context);
break;
case BREAK:
result = parseBreakStatement(context);
break;
case RETURN:
result = parseReturnStatement(context);
break;
case WITH:
result = parseWithStatement(context);
break;
case SWITCH:
result = parseSwitchStatement(context);
break;
case THROW:
result = parseThrowStatement(context);
break;
case TRY:
result = parseTryStatement(context);
break;
case DEBUGGER:
result = parseDebuggerStatement(context);
break;
case EOFTOK:
case CASE:
case CLOSEBRACE:
case DEFAULT:
// These tokens imply the end of a set of source elements.
return 0;
case IDENT:
case YIELD: {
bool allowFunctionDeclarationAsStatement = false;
result = parseExpressionOrLabelStatement(context, allowFunctionDeclarationAsStatement);
break;
}
case STRING:
directive = m_token.m_data.ident;
if (directiveLiteralLength)
*directiveLiteralLength = m_token.m_location.endOffset - m_token.m_location.startOffset;
nonTrivialExpressionCount = m_parserState.nonTrivialExpressionCount;
FALLTHROUGH;
default:
TreeStatement exprStatement = parseExpressionStatement(context);
if (directive && nonTrivialExpressionCount != m_parserState.nonTrivialExpressionCount)
directive = 0;
result = exprStatement;
break;
}

if (result && shouldSetEndOffset)
context.setEndOffset(result, m_lastTokenEndPosition.offset);
return result;
}

parseExpression

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
template <typename LexerType>
template <class TreeBuilder> TreeExpression Parser<LexerType>::parseExpression(TreeBuilder& context)
{
failIfStackOverflow();
JSTokenLocation location(tokenLocation());

// Parse the first expression.
TreeExpression node = parseAssignmentExpression(context);
context.setEndOffset(node, m_lastTokenEndPosition.offset);

// If this is not a comma, parsing is complete.
if (!match(COMMA)) return node;

// If a comma is matched, continue parsing to the right.
next();
m_parserState.nonTrivialExpressionCount++;
m_parserState.nonLHSCount++;

TreeExpression right = parseAssignmentExpression(context);
context.setEndOffset(right, m_lastTokenEndPosition.offset);

// An assignment expression may be a comma-separated expression,
// such as b, 2 + 3, c + 5, d >> 1.
typename TreeBuilder::Comma head = context.createCommaExpr(location, node);
typename TreeBuilder::Comma tail = context.appendToCommaExpr(location, head, head, right);

// Match commas from left to right. If successful, keep parsing.
while (match(COMMA)) {
next(TreeBuilder::DontBuildStrings);
right = parseAssignmentExpression(context);
context.setEndOffset(right, m_lastTokenEndPosition.offset);
tail = context.appendToCommaExpr(location, head, tail, right);
}
context.setEndOffset(head, m_lastTokenEndPosition.offset);
return head;
}

parseAssignmentExpression

Now let’s focus on assignment-expression parsing: parseAssignmentExpression.

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
template <typename LexerType>
template <typename TreeBuilder> TreeExpression Parser<LexerType>::parseAssignmentExpression(TreeBuilder& context, ExpressionErrorClassifier& classifier)
{
failIfStackOverflow();
JSTextPosition start = tokenStartPosition();
JSTokenLocation location(tokenLocation());
int initialAssignmentCount = m_parserState.assignmentCount;
int initialNonLHSCount = m_parserState.nonLHSCount;
bool maybeAssignmentPattern = match(OPENBRACE) || match(OPENBRACKET);
bool wasOpenParen = match(OPENPAREN);
bool isValidArrowFunctionStart = match(OPENPAREN) || match(IDENT);
SavePoint savePoint = createSavePoint();
size_t usedVariablesSize = 0;
if (wasOpenParen) {
usedVariablesSize = currentScope()->currentUsedVariablesSize();
currentScope()->pushUsedVariableSet();
}

if (match(YIELD) && !isYIELDMaskedAsIDENT(currentScope()->isGenerator()))
return parseYieldExpression(context);

// Parse the left-hand side.
TreeExpression lhs = parseConditionalExpression(context);

// Arrow-function parsing. Sometimes an arrow function is assigned to a variable:
// var a = (a) => a + 2;
if (isValidArrowFunctionStart && !match(EOFTOK))
{
bool isArrowFunctionToken = match(ARROWFUNCTION);
if (!lhs || isArrowFunctionToken) {
SavePointWithError errorRestorationSavePoint = createSavePointForError();
restoreSavePoint(savePoint);
if (isArrowFunctionParameters()) {
if (wasOpenParen)
currentScope()->revertToPreviousUsedVariables(usedVariablesSize);
return parseArrowFunctionExpression(context);
}
restoreSavePointWithError(errorRestorationSavePoint);
if (isArrowFunctionToken)
failDueToUnexpectedToken();
}
}

...

if (initialNonLHSCount != m_parserState.nonLHSCount) {
return lhs;
}

int assignmentStack = 0;
Operator op;
bool hadAssignment = false;
while (true)
{
// Parse operator.
switch (m_token.m_type)
{
case EQUAL: op = OpEqual; break;
case PLUSEQUAL: op = OpPlusEq; break;
case MINUSEQUAL: op = OpMinusEq; break;
case MULTEQUAL: op = OpMultEq; break;
case DIVEQUAL: op = OpDivEq; break;
case LSHIFTEQUAL: op = OpLShift; break;
case RSHIFTEQUAL: op = OpRShift; break;
case URSHIFTEQUAL: op = OpURShift; break;
case ANDEQUAL: op = OpAndEq; break;
case XOREQUAL: op = OpXOrEq; break;
case OREQUAL: op = OpOrEq; break;
case MODEQUAL: op = OpModEq; break;
default:
goto end;
}
m_parserState.nonTrivialExpressionCount++;
hadAssignment = true;

context.assignmentStackAppend(assignmentStack, lhs, start, tokenStartPosition(), m_parserState.assignmentCount, op);
start = tokenStartPosition();
m_parserState.assignmentCount++;
next(TreeBuilder::DontBuildStrings);

// Parse.
lhs = parseAssignmentExpression(context);
if (initialNonLHSCount != m_parserState.nonLHSCount) {
break;
}

}
end:
if (hadAssignment)
m_parserState.nonLHSCount++;

if (!TreeBuilder::CreatesAST)
return lhs;

while (assignmentStack)
lhs = context.createAssignment(location, assignmentStack, lhs, initialAssignmentCount, m_parserState.assignmentCount, lastTokenEndPosition());

return lhs;
}

StatementNode

Next, we will analyze several subclasses of StatementNode in detail. In a sense, this also lays the groundwork for later bytecode generation.

DeclarationStatement

1
2
3
4
5
6
7
8
class DeclarationStatement : public StatementNode {
public:
DeclarationStatement(const JSTokenLocation&, ExpressionNode*);
private:
void emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;

ExpressionNode* m_expr;
};

The amount of code involved in parsing a JavaScript variable declaration already exceeded my expectations.

parseVariableDeclaration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseVariableDeclaration(TreeBuilder& context, DeclarationType declarationType, ExportType exportType)
{
ASSERT(match(VAR) || match(LET) || match(CONSTTOKEN));
JSTokenLocation location(tokenLocation());
int start = tokenLine();
int end = 0;
int scratch;
TreeDestructuringPattern scratch1 = 0;
TreeExpression scratch2 = 0;
JSTextPosition scratch3;
bool scratchBool;
// Core logic is in parseVariableDeclarationList.
TreeExpression variableDecls = parseVariableDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3, VarDeclarationContext, declarationType, exportType, scratchBool);
propagateError();
failIfFalse(autoSemiColon(), "Expected ';' after variable declaration");

return context.createDeclarationStatement(location, variableDecls, start, end);
}

parseVariableDeclarationList

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
template <typename LexerType>
template <class TreeBuilder> TreeExpression Parser<LexerType>::parseVariableDeclarationList(TreeBuilder& context, int& declarations, TreeDestructuringPattern& lastPattern, TreeExpression& lastInitializer, JSTextPosition& identStart, JSTextPosition& initStart, JSTextPosition& initEnd, VarDeclarationListContext declarationListContext, DeclarationType declarationType, ExportType exportType, bool& forLoopConstDoesNotHaveInitializer)
{
TreeExpression head = 0;
TreeExpression tail = 0;
const Identifier* lastIdent;
JSToken lastIdentToken;
AssignmentContext assignmentContext = assignmentContextFromDeclarationType(declarationType);
do
{
lastIdent = 0;
lastPattern = TreeDestructuringPattern(0);
JSTokenLocation location(tokenLocation());
next();
TreeExpression node = 0;
declarations++;
bool hasInitializer = false;
if (matchSpecIdentifier())
{
// Get variable identifier.
JSTextPosition varStart = tokenStartPosition();
JSTokenLocation varStartLocation(tokenLocation());
identStart = varStart;
// Get Identifier information from JSToken.
const Identifier* name = m_token.m_data.ident;
lastIdent = name;
lastIdentToken = m_token;
// Get next JSToken.
next();

// Whether this is an equals sign. If so, the variable is initialized
// immediately after declaration.
hasInitializer = match(EQUAL);

// Declare a variable in the current scope and check whether
// the declaration is legal.
DeclarationResultMask declarationResult = declareVariable(name, declarationType);

if (hasInitializer) {
// If there is an equals sign.
JSTextPosition varDivot = tokenStartPosition() + 1;
initStart = tokenStartPosition();
next(TreeBuilder::DontBuildStrings); // consume '='
propagateError();

// Parse the expression on the right side of '='.
TreeExpression initializer = parseAssignmentExpression(context);
initEnd = lastTokenEndPosition();
lastInitializer = initializer;

// Create an assignment.
node = context.createAssignResolve(location, *name, initializer, varStart, varDivot, lastTokenEndPosition(), assignmentContext);
}
else
{
...
if (declarationType == DeclarationType::VarDeclaration)
// Empty variable declaration.
node = context.createEmptyVarExpression(varStartLocation, *name);
else
// Empty let declaration.
node = context.createEmptyLetExpression(varStartLocation, *name);
}
}
...

if (node)
{
if (!head) head = node;
else if (!tail) {
head = context.createCommaExpr(location, head);
tail = context.appendToCommaExpr(location, head, head, node);
} else
tail = context.appendToCommaExpr(location, head, tail, node);
}
} while (match(COMMA));
...
return head;
}

Example

A piece of JavaScript code containing a variable declaration and assignment:

1
var age = 6 * 7;

After syntax analysis with Esprima, the result is:

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
{
"type": "Program",
"body": [
{
"type": "VariableDeclaration",
"declarations": [
{
"type": "VariableDeclarator",
"id": {
"type": "Identifier",
"name": "age"
},
"init": {
"type": "BinaryExpression",
"operator": "*",
"left": {
"type": "Literal",
"value": 6,
"raw": "6"
},
"right": {
"type": "Literal",
"value": 7,
"raw": "7"
}
}
}
],
"kind": "var"
}
],
"sourceType": "script"
}

WhileNode

1
2
3
4
5
6
7
8
9
10
11
class WhileNode : public StatementNode {
public:
WhileNode(const JSTokenLocation&, ExpressionNode*, StatementNode*);

private:
void emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;

ExpressionNode* m_expr;
StatementNode* m_statement;
};

parseWhileStatement

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 LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseWhileStatement(TreeBuilder& context)
{
ASSERT(match(WHILE));
JSTokenLocation location(tokenLocation());
int startLine = tokenLine();
next();

// Confirm the left parenthesis after while.
handleProductionOrFail(OPENPAREN, "(", "start", "while loop condition");
semanticFailIfTrue(match(CLOSEPAREN), "Must provide an expression as a while loop condition");
// Parse the condition expression inside parentheses.
TreeExpression expr = parseExpression(context);
failIfFalse(expr, "Unable to parse while loop condition");
int endLine = tokenLine();
// Confirm the right parenthesis after while.
handleProductionOrFail(CLOSEPAREN, ")", "end", "while loop condition");

const Identifier* unused = 0;
startLoop();
// Parse the while-loop body.
TreeStatement statement = parseStatement(context, unused);
endLoop();

failIfFalse(statement, "Expected a statement as the body of a while loop");
return context.createWhileStatement(location, expr, statement, startLine, endLine);
}

Example

1
2
3
while(a > 0){
a--;
}

After syntax analysis with Esprima, the result is:

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
{
"type": "Program",
"body": [
{
"type": "WhileStatement",
"test": {
"type": "BinaryExpression",
"operator": ">",
"left": {
"type": "Identifier",
"name": "a"
},
"right": {
"type": "Literal",
"value": 0,
"raw": "0"
}
},
"body": {
"type": "BlockStatement",
"body": [
{
"type": "ExpressionStatement",
"expression": {
"type": "UpdateExpression",
"operator": "--",
"argument": {
"type": "Identifier",
"name": "a"
},
"prefix": false
}
}
]
}
}
],
"sourceType": "script"
}

IfElseNode

1
2
3
4
5
6
7
8
9
10
11
12
13
class IfElseNode : public StatementNode {
public:
IfElseNode(const JSTokenLocation&, ExpressionNode* condition, StatementNode* ifBlock, StatementNode* elseBlock);

private:
void emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;
bool tryFoldBreakAndContinue(BytecodeGenerator&, StatementNode* ifBlock,
Label*& trueTarget, FallThroughMode&);

ExpressionNode* m_condition;
StatementNode* m_ifBlock;
StatementNode* m_elseBlock;
};

I used to think parsing an if statement should be simple. After reading parseIfStatement, I realized it is not as easy as I imagined.

An if statement like this is relatively easy to understand, and a syntax tree is naturally good at representing it:

1
2
if(con1){}
else{}

But the following structure is more troublesome because it is not as straightforward for the syntax tree to express. It needs to be converted into a standard tree form. The conversion process is shown in the code and diagrams below.

1
2
3
4
5
if(con1) xxx;   
else if(con2) xxx;
...
else if(conn) xxx;
else xxx;

parseIfStatement

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
template <typename LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseIfStatement(TreeBuilder& context)
{
// Locate the if JSToken.
JSTokenLocation ifLocation(tokenLocation());
int start = tokenLine();

// Confirm the left parenthesis after if.
next();
handleProductionOrFail2(OPENPAREN, "(", "start", "'if' condition");

// Parse the condition expression inside parentheses.
TreeExpression condition = parseExpression(context);

// Confirm the matching right parenthesis.
int end = tokenLine();
handleProductionOrFail2(CLOSEPAREN, ")", "end", "'if' condition");

const Identifier* unused = 0;
m_immediateParentAllowsFunctionDeclarationInStatement = true;
TreeStatement trueBlock = parseStatement(context, unused);
failIfFalse(trueBlock, "Expected a statement as the body of an if block");

// If there is no else block, create the if statement and return directly.
if (!match(ELSE))
return context.createIfStatement(ifLocation, condition, trueBlock, 0, start, end);

// Parse the else block.
Vector<TreeExpression> exprStack;
Vector<std::pair<int, int>> posStack;
Vector<JSTokenLocation> tokenLocationStack;
Vector<TreeStatement> statementStack;

// Find the final else, not else if.
bool trailingElse = false;
do
{
// Record current else position.
JSTokenLocation tempLocation = tokenLocation();
next();

// If if is not matched, this is the final else. Parse it and finish the loop.
if (!match(IF))
{
const Identifier* unused = 0;
m_immediateParentAllowsFunctionDeclarationInStatement = true;
// Parse statements inside else.
TreeStatement block = parseStatement(context, unused);

// Put it into statementStack for later use.
statementStack.append(block);
// Mark that the final else exists.
trailingElse = true;
break;
}

// If if is matched.
int innerStart = tokenLine();
next();

// Confirm the left parenthesis after else if.
handleProductionOrFail2(OPENPAREN, "(", "start", "'if' condition");

// Parse the condition expression inside else if.
TreeExpression innerCondition = parseExpression(context);

// Confirm the right parenthesis after else if.
int innerEnd = tokenLine();
handleProductionOrFail2(CLOSEPAREN, ")", "end", "'if' condition");

const Identifier* unused = 0;
m_immediateParentAllowsFunctionDeclarationInStatement = true;

// Parse statements inside else if.
TreeStatement innerTrueBlock = parseStatement(context, unused);

// Add the else position to tokenLocationStack.
tokenLocationStack.append(tempLocation);
// Add the else-if condition expression to exprStack.
exprStack.append(innerCondition);
// Add position information.
posStack.append(std::make_pair(innerStart, innerEnd));
// Put the statement block into statementStack for later use.
statementStack.append(innerTrueBlock);
} while (match(ELSE));

// If there is no final else, meaning the chain ends with else if.
if (!trailingElse)
{
TreeExpression condition = exprStack.last();
exprStack.removeLast();
TreeStatement trueBlock = statementStack.last();
statementStack.removeLast();
std::pair<int, int> pos = posStack.last();
posStack.removeLast();
JSTokenLocation elseLocation = tokenLocationStack.last();
tokenLocationStack.removeLast();
TreeStatement ifStatement = context.createIfStatement(elseLocation, condition, trueBlock, 0, pos.first, pos.second);
context.setEndOffset(ifStatement, context.endOffset(trueBlock));
statementStack.append(ifStatement);
}

// The purpose of this loop is to turn the information after else into a falseBlock.
while (!exprStack.isEmpty())
{
// Extract condition expression.
TreeExpression condition = exprStack.last();
exprStack.removeLast();

// Extract falseBlock.
TreeStatement falseBlock = statementStack.last();
statementStack.removeLast();

// Extract trueBlock.
TreeStatement trueBlock = statementStack.last();
statementStack.removeLast();

// Extract position information.
std::pair<int, int> pos = posStack.last();
posStack.removeLast();
JSTokenLocation elseLocation = tokenLocationStack.last();
tokenLocationStack.removeLast();

// Create TreeStatement.
TreeStatement ifStatement = context.createIfStatement(elseLocation, condition, trueBlock, falseBlock, pos.first, pos.second);
context.setEndOffset(ifStatement, context.endOffset(falseBlock));
statementStack.append(ifStatement);
}

// Create the top-level ifStatement.
return context.createIfStatement(ifLocation, condition, trueBlock, statementStack.last(), start, end);
}

After all this, it may still feel confusing. Why does an ifStatement need to be so complex? Why so many stacks? Why so many loops?

  • First, what is the purpose of the final while (!exprStack.isEmpty()) loop?
JavaScriptCore Deep Dive 4 - Syntax Analysis: parseIfStatement (figure 4)

As shown in the diagram, its purpose is to transform if ... else if ... else if ... else into a standard if ... else structure, making it easier for the syntax tree to process.

  • Second, why does if (!trailingElse) need special handling when there is no final else?
JavaScriptCore Deep Dive 4 - Syntax Analysis: parseIfStatement (figure 5)

With the first point as context, this becomes easier to understand. It converts the non-standard if ... else if ... else if structure, which does not contain a final else, into a standard if ... else if ... else if ... else structure, so the loop in the first point can handle it uniformly.

At this point, reading the code again should make things much clearer.

Example

You can go here and enter an if statement yourself.

SwitchNode

1
2
3
4
5
6
7
8
9
10
11
class SwitchNode : public StatementNode, public VariableEnvironmentNode
{
public:
SwitchNode(const JSTokenLocation&, ExpressionNode*, CaseBlockNode*, VariableEnvironment&, FunctionStack&&);

private:
void emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;

ExpressionNode* m_expr;
CaseBlockNode* m_block;
};

parseSwitchStatement

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
template <typename LexerType>
template <class TreeBuilder> TreeStatement Parser<LexerType>::parseSwitchStatement(TreeBuilder& context)
{
JSTokenLocation location(tokenLocation());
int startLine = tokenLine();
next();

// Confirm the left parenthesis after switch.
handleProductionOrFail(OPENPAREN, "(", "start", "subject of a 'switch'");
// Parse the expression inside switch parentheses.
TreeExpression expr = parseExpression(context);
int endLine = tokenLine();
// Confirm the right parenthesis after switch.
handleProductionOrFail(CLOSEPAREN, ")", "end", "subject of a 'switch'");

// Confirm the left brace of switch.
handleProductionOrFail(OPENBRACE, "{", "start", "body of a 'switch'");
AutoPopScopeRef lexicalScope(this, pushScope());
lexicalScope->setIsLexicalScope();
lexicalScope->preventVarDeclarations();

// m_switchDepth++.
startSwitch();

// Iterate and parse case clauses.
TreeClauseList firstClauses = parseSwitchClauses(context);

// Parse default clause.
TreeClause defaultClause = parseSwitchDefaultClause(context);

// Iterate again and parse case clauses.
TreeClauseList secondClauses = parseSwitchClauses(context);

// m_switchDepth--.
endSwitch();

// Confirm the right brace of switch.
handleProductionOrFail(CLOSEBRACE, "}", "end", "body of a 'switch'");

// Create a SwitchStatement from the parsed caseClauses and defaultClause.
TreeStatement result = context.createSwitchStatement(location, expr, firstClauses, defaultClause, secondClauses, startLine, endLine, lexicalScope->finalizeLexicalEnvironment(), lexicalScope->takeFunctionDeclarations());

popScope(lexicalScope, TreeBuilder::NeedsFreeVariableInfo);
return result;
}
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 LexerType>
template <class TreeBuilder> TreeClauseList Parser<LexerType>::parseSwitchClauses(TreeBuilder& context)
{
if (!match(CASE)) return 0;
unsigned startOffset = tokenStart();
next();

// Parse the constant expression for case.
TreeExpression condition = parseExpression(context);

// Confirm the colon after the expression.
consumeOrFail(COLON, "Expected a ':' after switch clause expression");

// Parse the body statements for this case.
TreeSourceElements statements = parseSourceElements(context, DontCheckForStrictMode);

// Create a Clause from the case expression and statements.
TreeClause clause = context.createClause(condition, statements);
context.setStartOffset(clause, startOffset);

// Build linked list.
TreeClauseList clauseList = context.createClauseList(clause);
TreeClauseList tail = clauseList;

// Continue until no case is matched.
while (match(CASE)) {
startOffset = tokenStart();
next();
TreeExpression condition = parseExpression(context);
consumeOrFail(COLON, "Expected a ':' after switch clause expression");
TreeSourceElements statements = parseSourceElements(context, DontCheckForStrictMode);
clause = context.createClause(condition, statements);
context.setStartOffset(clause, startOffset);
tail = context.createClauseList(tail, clause);
}
return clauseList;
}

Most of the logic can be understood from the comments. The puzzling part is that case clauses are parsed twice:

1
2
TreeClauseList firstClauses = parseSwitchClauses(context);
TreeClauseList secondClauses = parseSwitchClauses(context);

The reason is that in switch syntax, the position of default is uncertain. It may appear at the beginning, at the end, in the middle, or may not exist at all. It effectively splits all case clauses in the switch into two halves. To avoid letting default interrupt a single case-parsing loop, JavaScriptCore performs two passes: one before default and one after it. The logic is clear and easy to understand.

Summary

Syntax analysis involves a large amount of material, so this article is relatively long. I may continue updating it later and add more detailed analysis.

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

Title:JavaScriptCore Deep Dive 4 - Syntax Analysis

Author:lingyun

Published:2018-08-02 00:32

Updated:2026-10-08 00:23

Original link:https://tsuijunxi.github.io/en/2018/08/02/javascriptcore-deep-dive-4-syntax-analysis/

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