Open in app

Sign in

Write

Sign in

Calculating 1 + 1 in JavaScript — Part 4

Peter Smith
Compilers
Published in
12 min readMar 29, 2021

I’m a compiler enthusiast who has been learning how the V8 JavaScript Engine works. Of course, the best way to learn something is to write about it, so that’s why I’m sharing my experiences here. I hope this might be interesting to others too.

This is the fourth part in a series that dives into how the V8 JavaScript Engine computes the expression 1 + 1. This may seem like a simple task, but it utilizes a large portion of the JavaScript run-time environment. In previous blog posts, we saw:

Now, in Part 4 we’ll learn how 1 + 1 is parsed to validate it against the official JavaScript grammar, with the goal of creating an in-memory Abstract Syntax Tree (AST).

The ECMAScript Grammar

As you probably know, the JavaScript language is officially defined by the ECMAScript Standard, also known as ECMA-262. However, unless you’ve studied the standard you probably didn’t know that chapters 12–15 spend roughly 200 pages (out of 860) defining the syntax of the language using a detailed Context Free Grammar.

  • Chapter 12 — Provides the grammar for all the possible expressions in the JavaScript language, including an extensive list of mathematical and logical operators.
  • Chapter 13 — Provides the grammar for statements (such as if, then, and while) and declarations (such as let and const).
  • Chapter 14 — Provides the grammar for function and class definitions.
  • Chapter 15 — Provides the grammar for top-level scripts and modules.

If you study these chapters, you’ll see the entire definition of the grammatical syntax of the language, describing the valid ordering of tokens in a JavaScript program. However, there’s nothing in these chapters to describe the actual meaning of a valid program. Instead, the semantics of the language is described in the later chapters of the specification (and not discussed in this blog post either).

The Grammar for 1 + 1

Let’s take a quick journey through JavaScript’s syntactical grammar to see how 1 + 1 will be parsed, at least on the theoretical level (we’ll later see how it’s done in V8). The grammar starts with the Script symbol, initiating a long chain of grammar rules used to derive a valid JavaScript program.

For the sake of illustration, we’ll only show the sequence of rules relevant when parsing 1 + 1. As with any context free grammar, the symbols on the right hand side are either terminals, representing tokens in our language (such as 1 or +), or are non-terminals, which can be recursively replaced using other rules.

That’s a long chain of rules for a simple expression, but it’s even longer for realistic programs. We’ve only seen the relevant rules for our 1 + 1 example. You’re strongly encouraged to click on the hyperlinks (above), and you’ll see a larger set of rules, including operators such as &&, &, |, ||, *, or +.

The Abstract Syntax Tree (AST)

One of the goals of parsing the input tokens is to create an Abstract Syntax Tree. This provides the compiler with an in-memory representation of the program, which is much easier to manipulate than a one-dimensional sequence of tokens. The AST is optimally designed so that tree-traversal algorithms can validate the input program, optimize the program structure, and eventually generate byte codes.

The AST is an n-ary tree, with each node representing some portion of the input program. Nodes have various properties describing the program in more detail (for example, variable names or integer values), and usually have child nodes to reflect the nesting structure of the program.

In V8, all of the AST nodes are defined as C++ classes in src/ast/ast.h, with AstNode being the parent class for all other node types. Each class contains internal fields for decorating the node (with variable names, or literal values), as well as pointers to child AST nodes.

The following diagram shows a portion of the class hierarchy for AST nodes. Note that Statement is a sub-class of AstNode, with each of its sub-classes representing a different type of JavaScript statement. As we’ll see later, we’ll be using ExpressionStatement in our 1 + 1 example.

Here’s another portion of the class hierarchy, focusing on the Expression class, which is also a sub-class of AstNode. Each of the sub-classes represents a different type of JavaScript expression. We’ll be using the Literal class in our example.

The AST For 1 + 1

For our particular 1 + 1 example, the AST is quite simple, with only three nodes involved: FunctionLiteral, ExpressionStatement, and Literal.

At the top of the AST is the FunctionLiteral node. Our expression doesn’t look like a function, but V8 has wrapped the expression this way to make byte code compilation more feasible. In our case, the function has zero formal parameters, with zero JavaScript object properties expected.

At the second level is an ExpressionStatement node, which is the single item in a list of Statement nodes referenced by the FunctionLiteral's body field. If this was a more typical function, we’d expect to see multiple Statement nodes in that list.

Finally, the ExpressionStatement's expression_ field refers to the one-and-only expression node. In our case, the 1 + 1 expression will be “folded” into the single small integer value of 2 (we’ll see this shortly).

To help understand how each of these AST nodes is represented in memory, here’s a heavily abbreviated (and annotated) version of the Literal C++ class, which is capable of storing literal values of any type (numbers, strings, booleans etc).

class Literal final : public Expression {public:  // All the possible literal types
  enum Type {
    kSmi,
    kHeapNumber,
    kBigInt,
    kString,
    kBoolean,
    kUndefined,
    kNull,
    kTheHole,
  };  // Return the type of this Literal
  Type type() const { ... }  // Methods for testing the Literal type
  bool IsNumber() const { ... }
  bool IsString() const { ... }  // Methods for fetching the Literal value in various ways
  AstRawString* AsRawPropertyName() { ... }
  Smi AsSmiLiteral() { ... }
  double AsNumber() { ... }
  AstBigInt AsBigInt() { ... }
  AstRawString* AsRawString() { ... }
  bool ToBooleanIsTrue();
  bool ToBooleanIsFalse() { ... }
  bool ToUint32(uint32_t* value) const;private:  // C++ union for storing the value.
  union {
    const AstRawString* string_;
    int smi_;
    double number_;
    AstBigInt bigint_;
    bool boolean_;
  };
};

The basic structure of Literal includes a type-tag to distinguish the various possible values, followed by a range of accessor functions for fetching the value itself. Finally, the private section of the class allows for storage of each type of value. For the full source code, see src/ast/ast.h.

Zone Memory Allocation

One interesting fact we’ve glossed over in our discussion of AST nodes is exactly where in memory they’re stored. We already know about the JavaScript heap (from Part 1 of this series), but that’s not where the AST nodes are stored. Instead, the concept of a Zone comes into play.

The Zone class provides very fast allocation of small blocks of memory, such as AST nodes. However, rather than using a garbage collection algorithm, or explicit delete calls to deallocate the memory, the entire zone is discarded at once. This makes sense when think of an AST being created incrementally, being held in memory for a period of time, and then being discarded when the AST is no longer required. There’s no concept of partially deallocating an AST.

To allocate blocks of memory from the Zone, the AstNodeFactory class (using the “factory” pattern) provides convenience methods for creating different types of AST node. For example, here’s part of the ExpressionFromLiteral() method that recognizes the next scanner token as a Token::SMI, fetches the integer value from that token, then creates a new Literal node with that integer value.

...
case Token::SMI: {
  uint32_t value = scanner()->smi_value();
  return factory()->NewSmiLiteral(value, pos);
}
...

Now that we’ve seen the ECMAScript grammar, and we’ve learned how the AST is constructed, we have enough knowledge to step through the process of parsing 1 + 1. As we learned in Part 3, this input will be streamed from the scanner to the parser as a sequence of Token::SMI (value 1), Token::ADD, and Token::SMI (value 1).

Recursive Descent Parsing of 1 + 1

To construct an AST, the V8 JavaScript Engine uses the Recursive Descent parsing technique. This is one of the easiest parsing algorithms to understand, as it simply uses recursive method calls to emulate the chain of grammar rules. That is, each non-terminal in our syntactical grammar is mapped to a C++ method. When called, the method looks ahead at the next scanner token (or tokens) to decide how to proceed, recursively calling other C++ methods as it descends through the grammar.

Let’s see how this is done in our 1 + 1 example.

Recursively Parsing Downwards

We’ll start our journey from within the CompileTopLevel() method, which calls upon ParseProgram() to convert the sequence of scanner tokens into an AST. To achieve this goal, the method initializes the scanner, then recursively invokes DoParseProgram() (we’ll see a lot of recursive calls in this discussion!).

...
scanner_.Initialize();
FunctionLiteral* result = DoParseProgram(isolate, info);
...

If we think back to the ECMAScript grammar we saw earlier, the DoParseProgram() method is equivalent to the ScriptBody rule. In particular, it includes code for parsing a StatementList, which is a sequence of zero or more StatementListItem items:

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

At the end of the DoParseProgram() method, there’s code for creating a new FunctionLiteral AST node, which incorporates our list of Statement nodes. This new node should look familiar, as it’s the first of three nodes we’re expecting to see in our final AST.

result = factory()->NewScriptOrEvalFunctionLiteral(... body ...);

To continue recursively, the ParseStatementListItem() method is called. This method, like many others we’re about to see, uses a consistent pattern of checking the next scanner token, then determining which additional method to call recursively. For example, if Token::CLASS is the next token in the input stream, we consume that token and recursively call ParseClassDeclaration().

...
switch (peek()) {
  case Token::FUNCTION:
    return ParseHoistableDeclaration(...);  case Token::CLASS:
    Consume(Token::CLASS);
    return ParseClassDeclaration(...);  case Token::VAR:
  case Token::CONST:
    return ParseVariableStatement(...);  case Token::LET:
    return ...  case Token::ASYNC:
    return ...  default:
    break;
}/* none of the tokens match, continue along rule chain */
return ParseStatement(...)

In our simple 1 + 1 example, none of these look-ahead tokens are relevant, so we continue to the default case of calling ParseStatement(). In fact, this pattern continues for a while with more recursive calls:

This list should look remarkably similar to the ECMAScript grammar we saw earlier. Perhaps the only discrepancy is that some rules are very similar, such as ExpressionStatement and LabelledStatement, so they’re merged into a single ParseExpressionOrLabelledStatement() method capable of handling both.

Once we reach ParseBinaryExpression(), the pattern changes slightly because many different grammar rules, from LogicalOrExpression down to ExponentiationExpression, are merged into a single C++ method. As we’ll discuss shortly, this is handled by passing in a precedence parameter, and using precedence rules to group sub-expressions together as appropriate.

Finally, we continue down the grammar rule chain by calling more C++ methods:

Parsing the Literals

Once we reach the ParsePrimaryExpression() method, the recursion ends. We no longer have any more rules to apply, and we’re now ready to identify 1 as a literal value. Here’s the relevant part of the code:

...
if (Token::IsLiteral(token)) {
  return impl()->ExpressionFromLiteral(Next(), beg_pos);
}
...

Within the ExpressionFromLiteral() method, there’s code for fetching the token’s SMI value (1), and then using the AST factory to create a new Literal AST node, as we saw earlier.

...
case Token::SMI: {
  uint32_t value = scanner()->smi_value();
  return factory()->NewSmiLiteral(value, pos);
}
...

The return value from this code has type Expression *, which will now be passed back up the C++ call stack.

Parsing of Binary Expressions With Precedence

As we’ve now reached the bottom of the call stack, and we’re returning from the long list of recursive methods, it’s not just a simple matter of immediately returning. Each method must decide whether it’s appropriate to consume more input tokens, or whether its job is complete and returning to the caller is the correct approach.

To see why this matters, consider the expression: 1 + 2 * 3. If we’ve already seen 1 + 2, the question to be asked is whether 1 + 2 is a complete expression, or whether there’s more to evaluate. Clearly it should evaluate 2 * 3 first, before adding 1, so we need the consume the remaining tokens to form the binary expression 2 * 3 before returning to produce the binary-expression 1 + (2 * 3).

To state this another way, consider the ECMAScript rule we saw earlier:

AdditiveExpression ::= AdditiveExpression + MultiplicativeExpression

Given our example, we need to fully evaluate MultiplicativeExpression, before “returning” to the previous method to evaluate the AdditiveExpression.

Inside V8, this is all done with the ParseBinaryExpression() method, which expects the operator precedence as an argument. When parsing of the expression has completed, the precedence value of the next token is checked to see if it’s higher. If so, parsing continues at the same level in the grammar, in this case by calling ParseBinaryContinuation().

Here’s the relevant code:

    ...
    x = ParseUnaryExpression();
  }  int prec1 = Token::Precedence(peek(), accept_IN_);
  if (prec1 >= prec) {
    return ParseBinaryContinuation(x, prec, prec1);
  }
  return x;
}

In our 1 + 1 example, ParseBinaryExpression() was called with prec equal to 6, and since the precedence of + is 12, we decide that prec1 > prec and the expression should continue at the same level in the grammar. We therefore call ParseBinaryContinuation() rather than returning up the stack.

Constant Folding

Another thing that ParseBinaryContinuation() does is attempt to “fold” constants, simplifying the expression at compile time. We already have a Literal for the first 1, the operator +, and a second Literal for the second 1. We then call ShortcutNumericLiteralBinaryExpression() with all of these values to see if they can be folded into a single Literal.

Here’s the relevant code:

...
if ((*x)->IsNumberLiteral() && y->IsNumberLiteral()) {
  double x_val = (*x)->AsLiteral()->AsNumber();
  double y_val = y->AsLiteral()->AsNumber();  switch (op) {
    case Token::ADD:
      *x = factory()->NewNumberLiteral(x_val + y_val, pos);
      return true;
    ...

To summarize, if both of the expressions are literal numbers, then we add them together and replace them with a single Literal containing the sum.

Finishing Up

We’ve now seen the entire expression, with no further input tokens remaining, except for the final Token::EOS marking the end of the input stream. As each recursive C++ method returns, it checks the next token but only sees Token::EOS, causing it to return immediately.

Although this is fairly routine by now, there’s one interesting case worth mentioning. In the ParseExpressionOrLabelledStatement() method, the Literal AST node, with value of 2 is wrapped in an ExpressionStatement AST node:

return factory()->NewExpressionStatement(expr, pos);

Finally, as we saw earlier, a FunctionalLiteral AST node is created, wrapping the ExpressionStatement. This leads us back to the AST diagram we’ve been expecting to see:

Next Time…

We’ve now seen a large part of the process involved in parsing 1 + 1, including allocation of data on the JavaScript heap, caching of byte codes, scanning of tokens, and now parsing against the ECMAScript grammar. In the next blog post, will continue by examining how 1 + 1 (actually, now 2) is restructured into a function, which will later be converted to byte codes.

JavaScript
Compilers
V8
V8 Engine

--

--

Peter Smith
Compilers

Written by Peter Smith

223 Followers
Editor for

Principal Software Engineer

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams