Compiler Internals: Lexer and Parser

Relevant source files

The following files were used as context for generating this wiki page:

• Jurassic/Compiler/Parser/Parser.cs
• Jurassic/Compiler/Lexer/Lexer.cs
• Jurassic/Compiler/Statements/Statement.cs
• Jurassic/Compiler/MethodGenerator/MethodGenerator.cs
• Jurassic/Compiler/Emit/OptimizationInfo.cs
• Jurassic/Compiler/Parser/AstNode.cs
• Jurassic/Compiler/Statements/ForInStatement.cs
• Jurassic/Compiler/Statements/BlockStatement.cs
• Unit Tests/Real-world/RealWorldTests.cs

The Jurassic compiler transforms JavaScript source code into .NET CIL (Common Intermediate Language). This process begins with two fundamental stages: lexical analysis (lexing) and syntactic analysis (parsing). The lexer breaks the raw source code into a sequence of tokens, and the parser consumes these tokens to construct an Abstract Syntax Tree (AST). This AST provides a structured, hierarchical representation of the code that is then used by the MethodGenerator to emit CIL.

The overall compilation flow is orchestrated by MethodGenerator subclasses, which initialize and run the parser. The parser, in turn, uses the lexer to process the source code.

Sources: Jurassic/Compiler/MethodGenerator/MethodGenerator.cs:100-104, Jurassic/Compiler/Parser/Parser.cs:33-41, README.md:14-15

High-Level Compilation Flow

The following diagram illustrates the initial stages of the compilation process, from source code to the Abstract Syntax Tree.

Lexer (Lexical Analyzer)

The Lexer class is responsible for tokenizing the JavaScript source code. It reads the character stream from a ScriptSource and converts it into a sequence of Token objects.

Sources: Jurassic/Compiler/Parser/Parser.cs:33-36

Key Components and Logic

• Lexer(ScriptSource source): The constructor takes a ScriptSource as input, which provides access to the JavaScript code.
• NextToken(): This is the core method of the lexer. Each call reads from the source and returns the next recognized token, skipping over whitespace.
• ParserExpressionState: A crucial property that helps the lexer disambiguate tokens. For example, the / character can be the start of a regular expression literal or a division operator. The Parser sets this state to guide the lexer.
  • Literal: The next token can be a literal (e.g., regex, number).
  • Operator: The next token is expected to be an operator.
  • TemplateContinuation: Used when parsing template literals with substitutions.
• StrictMode: A boolean property that, when true, enforces strict mode rules during lexing, such as disallowing octal literals.

The lexer identifies various token types, including:

• IdentifierToken
• PunctuatorToken (e.g., (, ), {, }, +, -)
• KeywordToken (e.g., if, for, var)
• StringLiteralToken
• NumericLiteralToken
• RegularExpressionLiteral
• WhiteSpaceToken (including line terminators)

Sources: Jurassic/Compiler/Parser/Parser.cs:34-36, Jurassic/Compiler/Parser/Parser.cs:150-163, Jurassic/Compiler/Parser/Parser.cs:93-99

Parser (Syntactic Analyzer)

The Parser class consumes the token stream from the Lexer and builds an Abstract Syntax Tree (AST). The root of this tree is a Statement object, typically a BlockStatement, which represents the entire script or function body.

Sources: Jurassic/Compiler/Parser/Parser.cs:15-16, Jurassic/Compiler/Parser/Parser.cs:384-386

Parsing Strategy

The parser uses a combination of parsing techniques:

1. Recursive Descent for Statements: Methods like ParseStatement(), ParseIf(), ParseFor(), and ParseBlock() recursively call each other to parse the statement structure of the language.
2. Pratt Parser (Operator-Precedence) for Expressions: The ParseExpression() method uses an operator-precedence parsing algorithm to handle the complexities of expression evaluation order. It maintains an operator lookup table to manage precedence and associativity.

This hybrid approach allows it to handle both the block structure of statements and the complex, nested nature of expressions efficiently.

Sources: Jurassic/Compiler/Parser/Parser.cs:417-431, Jurassic/Compiler/Parser/Parser.cs:1700-1896

Key Components and Logic

• Parser(Lexer lexer, ...): The constructor initializes the parser with a Lexer, CompilerOptions, and the initial Scope.
• Parse(): The main entry point. It first handles the directive prologue (like "use strict";) and then parses the remaining statements into a BlockStatement.
• Expect(Token token): A helper method that consumes the next token, throwing a SyntaxErrorException if it doesn't match the expected token.
• Scope Management: The parser manages lexical scopes (function, block, with, catch). It uses a ScopeContext helper class to push and pop scopes as it enters and leaves corresponding language constructs. This is critical for resolving variable references correctly.
• MethodOptimizationHints: While parsing, the parser gathers information about the code, such as whether it contains eval, with statements, or references to arguments. This information is stored in a MethodOptimizationHints object and used later by the code generator to apply possible optimizations.

Sources: Jurassic/Compiler/Parser/Parser.cs:33-41, Jurassic/Compiler/Parser/Parser.cs:384-415, Jurassic/Compiler/Parser/Parser.cs:178-186, Jurassic/Compiler/Parser/Parser.cs:302-321, Jurassic/Compiler/Parser/Parser.cs:115-118

Parser-Lexer Interaction

The following sequence diagram shows how the Parser and Lexer interact to process a simple expression like a = 1;.

Abstract Syntax Tree (AST)

The AST is the hierarchical tree structure representing the parsed code. It is composed of nodes that inherit from the AstNode base class. The two main categories of nodes are Statement and Expression.

Sources: Jurassic/Compiler/Parser/AstNode.cs, Jurassic/Compiler/Statements/Statement.cs

AST Node Hierarchy

The parser constructs a tree of nodes representing the program's structure. Statement nodes represent actions, while Expression nodes represent values.

The diagram below shows a simplified class hierarchy for some common AST nodes.

Each node class is responsible for generating its corresponding CIL via the GenerateCode() method. For example, ForInStatement generates the CIL for a for-in loop, including getting an enumerator for the target object and iterating over its properties.

Sources: Jurassic/Compiler/Statements/ForInStatement.cs:59-112

Integration with Code Generation

The parsing process is tightly integrated with the subsequent code generation and optimization phases.

OptimizationInfo

The Parser works with an OptimizationInfo object, which acts as a context for code generation. This object holds stateful information required during the AST walk for CIL emission.

Key properties managed by the parser and used during code generation include:

Property	Description
StrictMode	Indicates if the current scope is in strict mode.
SourceSpan	Tracks the source code location for debugging purposes.
MethodOptimizationHints	Collects hints about the code (e.g., use of eval, with) to enable/disable optimizations.
ReturnTarget / ReturnVariable	Manages the target label and variable for return statements within a function.
breakOrContinueStack	A stack to manage targets for break and continue statements, supporting labels.

Sources: Jurassic/Compiler/Emit/OptimizationInfo.cs

MethodGenerator

The MethodGenerator is the top-level driver for the compilation of a script or function. It performs the following steps:

1. Instantiates a Parser with the correct source, options, and scope.
2. Calls the parser's Parse() method to generate the AST.
3. Optionally runs an optimization pass on the AST.
4. Initializes an OptimizationInfo object.
5. Creates a .NET DynamicMethod and an ILGenerator.
6. Walks the AST, calling GenerateCode() on each node to emit CIL.
7. Creates a delegate from the completed dynamic method.

Sources: Jurassic/Compiler/MethodGenerator/MethodGenerator.cs:100-128

Conclusion

The lexer and parser are the cornerstones of the Jurassic compilation pipeline. The Lexer systematically deconstructs raw JavaScript text into a stream of meaningful tokens. The Parser then intelligently assembles these tokens into a structured Abstract Syntax Tree. This AST is not just a representation of the code but is an active participant in the next phase, where each node generates its own .NET CIL. This architecture creates a clean separation of concerns between understanding the language's syntax and emitting executable code.