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:
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 | function foo(x) { |
After syntax analysis, we get a simplified parse tree like this:
Syntax Tree Nodes
Before diving into the details of the syntax tree, let’s first look at its nodes:
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:
- Sequential structures, such as
ClassDeclNodeandDeclarationStateMentNode.- Conditional structures, such as
IFElseNodeandSwitchNode.- Loop structures, such as
WhileNode,ForNode, andDoWhileNode.- Another major node is
ScopeNode, which describes scope regions.ExpressionNode: an expression node. Its child nodes mainly describe different expressions:
ConstantNode, a constant node, from which string, boolean, integer, and floating-point nodes are derived.BinaryOpNode, a binary operator node, from which addition, subtraction, multiplication, division, modulo, left shift, right shift, and similar operator nodes are derived.- There are also regular-expression nodes,
thisnodes,supernodes, 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 | class ParserArenaFreeable { |
ParserArenaFreeableobjects are freed when the arena is deleted.- Destructors are not called. Clients must not call
deleteon 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 | ExpressionNode* createString(const JSTokenLocation& location, const Identifier* 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 | class ParserArenaDeletable { |
ParserArenaDeletableobjects are deleted when the arena is deleted.- Destructors can be called. Clients must not call
deletedirectly on such objects.
If you want to explore the memory-allocation mechanism further, look
at ParserArena.
- Two important allocation methods:
1 | void* allocateFreeable(size_t size) |
ParserArenadestructor:
First, call the destructor for every object in
m_deletableObjects. Then release every address previously
recorded in m_freeablePools.
1 | ParserArena::~ParserArena() |
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 | class ASTBuilder |
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; hereUnsafeVectorOverflowis used. Both eventually lead toCRASH().- The fourth parameter is the minimum capacity. We do not pass it here, so the default value
16is used.
Operand: BinaryOperand
1 | typedef int BinaryOperand; |
Binary Operation Structure
1 | struct BinaryOpInfo |
Assignment Structure
1 | struct AssignmentInfo |
Operator is an enum:
1 | enum Operator |
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 | enum class SourceParseMode : uint8_t |
The internal call flow of parse is roughly:
1 | parse |
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 | parse |
parseInner
1 | // Perform syntax analysis and generate the abstract syntax tree. |
parseSourceElements
1 | template <typename LexerType> |
parseStatementListItem
1 | template <typename LexerType> |
parseStatement
Basic statement parsing is performed through switch
branches:
1 | template <typename LexerType> |
parseExpression
1 | template <typename LexerType> |
parseAssignmentExpression
Now let’s focus on assignment-expression parsing:
parseAssignmentExpression.
1 | template <typename LexerType> |
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 | class DeclarationStatement : public StatementNode { |
The amount of code involved in parsing a JavaScript variable declaration already exceeded my expectations.
parseVariableDeclaration
1 | template <typename LexerType> |
parseVariableDeclarationList
1 | template <typename LexerType> |
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 | { |
WhileNode
1 | class WhileNode : public StatementNode { |
parseWhileStatement
1 | template <typename LexerType> |
Example
1 | while(a > 0){ |
After syntax analysis with Esprima, the result is:
1 | { |
IfElseNode
1 | class IfElseNode : public StatementNode { |
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 | if(con1){} |
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 | if(con1) xxx; |
parseIfStatement
1 | template <typename LexerType> |
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?
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 finalelse?
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 | class SwitchNode : public StatementNode, public VariableEnvironmentNode |
parseSwitchStatement
1 | template <typename LexerType> |
1 | template <typename LexerType> |
Most of the logic can be understood from the comments. The puzzling
part is that case clauses are parsed twice:
1 | TreeClauseList firstClauses = 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.