Gentle introduction into compilers. Part 1: Lexical analysis and Scanner

Stages Common to All Compilers

Compilers translate programs from one language into another. To do that, a compiler must first grasp the meaning of the source program it receives and then recreate that logic in the target language. These two jobs are quite different in nature, which is why compilers are typically broken down into two large parts: a front-end and a back-end. The front-end is responsible for understanding the source code, while the back-end handles the transformation into the target language.

Each of these parts consists of a chain of phases. Each phase takes the output from the one before it, processes it, and produces a new representation that it passes along to the next phase. The front-end is made up of three primary stages: lexical analysis, syntax analysis, and semantic analysis. The first stage takes raw source code, which is just a stream of characters, and groups those characters into meaningful units called tokens—things like variable names, keywords, and punctuation. The second stage checks whether the way these tokens are arranged makes grammatical sense and creates an Abstract Syntax Tree (AST) from them. The final stage, semantic analysis, verifies that the AST respects the language's rules, such as type checking and name resolution.

This article zeroes in on the very first step: lexical analysis. The main character here is the scanner, also known as a recognizer.

A Look at Languages and Their Grammars

To understand how a scanner works, we first need to discuss the difference between natural and formal languages, as well as their grammars. Natural languages, such as English or French, developed organically over time and are primarily used for everyday communication. Formal languages, on the other hand, are deliberately engineered by people for specific purposes. Programming languages are formal languages used to express computational tasks, and mathematical notation is another example, used to represent relationships between numbers.

Both types of languages can be defined by a grammar. A grammar is essentially a set of rules that dictates how to string together symbols—whether those are characters, words, or whole sentences—to form valid expressions according to the language's syntax. The grammar of a natural language is wildly complex and is generally **uncovered** through extensive research and observation of how people actually speak. In contrast, the grammar of a formal language (a formal grammar) tends to be much simpler and is **specified** by its creators. Depending on the kind of symbols the rules apply to, we can differentiate between several types of grammar.

The **lexical grammar** outlines the vocabulary of a language, which is every single token that is permitted. For instance, in JavaScript, the alphabet includes both \ and d. However, the grammar does not have a rule that allows \ to be immediately followed by d to form a legitimate token when it appears outside of a regular expression literal. So, if you try to run the code \d as a standalone statement, you'll get the invalid token syntax error:

\d
Uncaught SyntaxError: Invalid or unexpected token

On the other hand, the **syntactical grammar** determines the structure of a language, which is essentially how tokens are arranged to form valid statements. For example, the JavaScript lexical grammar recognizes both var and const as distinct tokens, but it doesn't contain a rule saying that var can be immediately followed by const. As a result, running the following code triggers an unexpected token syntax error:

var const
Uncaught SyntaxError: Unexpected token const

That statement is structurally invalid according to the ECMAScript syntactical grammar. The parser doesn't expect to see the const token right after the var token in that context. It's also worth noting the difference in the error phrasing: unexpected versus invalid.

Understanding Lexical Analysis

Lexical analysis kicks off the compiler's process of making sense of the input program. Its job is to take the raw source code and break it down into smaller substrings known as tokens, then assign each token to its appropriate role, or token class. The component that carries out this task is the scanner, sometimes called a lexical analyzer. It consumes the character stream and groups those characters into tokens based on the rules found in the lexical grammar, which is also called the lexical specification. If the scanner comes across a sequence of characters that doesn't fit any rule, it's an error. That's precisely what occurred with our \d example, which resulted in the Invalid or unexpected token message.

When a scanner successfully identifies a token, it also assigns it a syntactic category. The list of available categories in ECMAScript is fairly long. It includes broad categories like Identifier, NumericLiteral, and StringLiteral, as well as more specific ones like the keywords ConstKeyword, LetKeyword, and IfKeyword.

Typically, the output of the lexical analysis is a sequence of tokens. Each token comes with its associated class and the specific substring it was built from, which is referred to as a lexeme:

{class: SyntaxKind.ConstKeyword, lexeme: ‘const’}

For those interested in the full set of ECMAScript tokens, the TypeScript implementation lists them in the SyntaxKind enumeration, up to the // Parse tree nodes comment.

There are different ways to implement a lexical analyzer. One approach is to have it scan the whole source file in one go, generating the complete set of tokens up front. However, this is not very common in practice because it uses up a lot of memory unnecessarily. A more typical implementation is to have the scanner work on demand, producing a single token each time the parser requests one. TypeScript's scanner works this way. Beyond that, the TS scanner has another distinctive trait. JavaScript's syntax contains a few constructs, such as regular expressions and template literals, that create a bit of parsing ambiguity. This means the scanner might recognize a different set of tokens depending on where it is in the parsing process. Because the parser tells the scanner which context it's in when asking for a token, the TypeScript scanner can be described as parser-driven. This particular nuance is something I'll get into in the Multiple goal symbols section.

Token definitions

To illustrate how grammar rules operate, consider the familiar scenario of variable declarations in JavaScript. A variable can be introduced with the const keyword, as shown below:

const v = 3

For the sake of simplicity, let’s suppose the initializer is limited to a numeric literal. Reading the source, you immediately recognize the const keyword, the variable named v, the assignment operator =, and the numeric literal 3 serving as the initial value. The scanner, however, perceives the input differently. Because ECMAScript defines program source in terms of Unicode symbols, the compiler encounters this exact sequence of code points:

c   o    n    s    t        v        =       3
99, 111, 110, 115, 116, 32, 118, 32, 61, 32, 51

Its task is to segment the expression into tokens and classify each one, yielding the token list that follows:

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

Were let used in place of const, the first token would be identified as SyntaxKind.LetKeyword. Following the links on each token class will direct you to their definitions within the TypeScript source. After recognizing a token, the scanner saves its lexeme in the tokenValue property, retrievable via the getTokenValue method.

Regular grammars explained

ECMAScript relies on regular grammar to define how Unicode symbol sequences are recognized as tokens. In the Chomsky hierarchy of grammars, regular grammar represents the most constrained category, offering the least expressive capability. It is sufficient for outlining token construction but falls short of describing sentence-level structure. The upside of such restrictions is that the grammar becomes easier to specify and process. Given that token definition and parsing are the focus here, this grammar type fits perfectly.

The upcoming installment of this series will introduce context-free grammar (type 2). This grammar class supports recursive patterns and serves to outline program structure, such as statements. The remaining two categories in the Chomsky hierarchy—unrestricted and context-sensitive grammars—possess greater power than types 2 and 3, yet they are impractical because efficient parsers for them are hard to construct.

A key observation: many instructional texts **skip regular grammar** when covering scanners and instead describe **lexical specifications via regular expressions**. Since ECMAScript’s design embraces regular grammar for this role, that’s the approach I’ll follow here.

Exploring the grammar structure

Let’s examine how to build the grammar and rules that enable TypeScript to detect the token list mentioned earlier. For clarity, here’s that list again, and our task is to formulate rules for recognizing each token in the statement:

const v = 3
{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

Grammar rules are expressed through productions. A production acts as a substitution rule, dictating the possible replacements that can be applied iteratively to create novel symbol sequences. Since JavaScript allows variable declarations with either const or let, we can establish the following production for the Keyword symbol:

Keyword ::
    const
    let

The Keyword rule contains two productions, specifying that it may be substituted by the strings const or let. Here, Keyword acts as a synthetic entity called a nonterminal symbol, indicating it has productions and can undergo substitution—this replacement process doesn’t conclude with it. Such substitutions are termed derivations. The replacements const and let are terminals because they lack further derivations. Terminal symbols, having no productions, represent the actual strings present in the source code. The non-terminal symbols in a grammar exist solely to define replacement rules and never appear as valid tokens in the source program. ECMAScript specifies numerous other productions for the Keyword nonterminal, including if, else, for, do, while, function, class, and more.

ECMAScript adopts this ad-hoc notation for grammar definitions:

non_terminal_symbol ::
  symbol1 symbol2  (production rule 1, Symbol1 followed by Symbol2)
  symbol3 symbol4  (production rule 2, Symbol3 followed by Symbol4)

The element preceding the :: is termed the left-hand side, while the one following is the right-hand side. For regular and context-free grammars, the production rule’s **left-hand side** must be a nonterminal symbol. The **right-hand side** can include both terminals and non-terminals, though regular grammar limits it to either:

• exclusively terminals
• or terminals plus a single non-terminal, positioned strictly at the start (left-linear) or strictly at the end (right-linear):

non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   (right-linear)
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   (left-linear)

Context-free grammar eases these constraints, permitting any mix of terminals and non-terminals on the right-hand side. Both RG and CFG allow multiple alternative productions—or alternations—for any given left-hand side symbol:

non_terminal_symbol ::
  production rule 1
  production rule 2
  ...
  production rule n

Alternative grammar notations also exist, such as the Backus–Naur form (BNF), which employs this syntax:

nonterminal_symbol ::= symbol1 | symbol2

Thus, our rule for the Keyword would appear in BNF as:

Keyword ::= const | let

Other notation variants swap ::= for ->, rendering the rule as:

Keyword -> const | let

ECMAScript, in this context, uses its own format as outlined above. The specifics of its grammar notation are detailed in the Grammar Notation section, which I highly recommend reviewing. Essential points include:

Terminal symbols …are shown in ****fixed width**** font, nonterminal symbols are shown in italic type… One or more alternative right-hand sides for the nonterminal follow on succeeding lines… The definition of a nonterminal is introduced by the name of the nonterminal followed by one or more colons. ECMAScript uses double semicolon to denote lexical grammar and single semicolon for the syntactic grammar.

Applying production rules

Applying a production rule involves replacing an occurrence of the rule’s left-hand side with its right-hand side. That description is dense, so let’s work through an instance. Imagine you aim to define a language of reserved words. The grammar starts with the nonterminal symbol ReservedWord. ECMAScript specifies these productions for it:

ReservedWord ::
  Keyword
  FutureReservedWord
  NullLiteral
  BooleanLiteral

but we’ll concentrate solely on Keyword for now:

ReservedWord ::
  Keyword

Previously, we defined the Keyword grammar like so:

Keyword ::
    const
    let

Thus, by first substituting ReservedWord with Keyword, and subsequently replacing Keyword with its productions, we derive a language containing two words—const and let. Such a language is **finite**, as it can contain at most 2 distinct strings. In contrast, all real-world languages are **infinite**, because the number of strings they can generate is unbounded. We’ll explore the rationale for this shortly when we examine the grammar for identifiers.

In the grammar above, ReservedWord serves as the **start symbol**, since it initiates the string generation process. ECMAScript’s grammar identifies multiple start symbols , referring to them as goal symbols. The reasoning behind this will become clear later in this article.

The sequence of steps—beginning with the start symbol ReservedWord and ending with the strings const or let—is known as **derivation**. A derivation for a given string is an ordered application of grammar rules that transforms the start symbol into that string. It serves as proof that the string is part of the grammar’s language. For instance, we can confirm const is valid because ReservedWord expands to Keyword, and that nonterminal further expands to the specific strings const or let.

Recursive nature of the grammar

To illustrate how recursion manifests in the grammar, consider what are typically called identifiers — the names we assign to variables. In the earlier example const v = 3, the token v falls under the Identifier category. According to ECMAScript, the Identifier is formally defined as:

Identifier ::
    IdentifierName but not ReservedWord

The key insight here is that reserved words form a subset of __IdentifierName__. This implies that the rules governing the recognition of both identifier names and reserved words are identical. Consequently, when a scanner encounters an IdentifierName, it must check whether that name appears in the reserved word list. If it does not, the token is classified as an Identifier; otherwise, it receives the appropriate class from the ReservedWord category. This exact behavior is implemented in the TypeScript compiler’s getIdentifierToken function. The reserved words list primarily consists of keywords such as const, let, if, else, and for, as previously seen, along with the literals null, true, and false.

How, then, is the grammar for IdentifierName structured? You are likely aware that certain characters, such as digits, cannot appear at the start of a variable name, yet the name itself may contain a much wider range of characters, including numbers. This distinction necessitates separating the rules for the initial character from those for subsequent characters. As a result, the grammar requires two non-terminal symbols arranged sequentially:

IdentifierName ::
    IdentifierStart IdentifierPart

A crucial point is that both IdentifierStart and IdentifierPart represent **exactly one** character from the Unicode code point sets defined for those positions. Without delving into specifics, if you are interested further, this resource on valid JavaScript variable names in ECMAScript 5 is worth reading. Since each expansion of IdentifierStart and IdentifierPart yields **one** character, the definition above, if taken literally, would restrict all identifier names to exactly two characters in length. That outcome is obviously incorrect. The actual definition in the ECMAScript grammar reads as follows:

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

Let's unpack this. The first production indicates that an identifier name may consist of a single character drawn from the set defined by IdentifierStart. By repeatedly applying the second production, you can see how it expands to accommodate any number of characters, beginning with IdentifierStart and followed by any sequence of IdentifierPart:

IdentifierStart IdentifierPart IdentifierPart … IdentifierPart

This is where recursion proves invaluable. By continually substituting IdentifierName with the second production IdentifierName IdentifierPart, it becomes possible to match strings of arbitrary length.

Interestingly, some grammar notations introduce non-standard repetition operators, such as * or {…}, which would allow the grammar to be written differently:

IdentifierName ::
    IdentifierStart IdentifierPart*
IdentifierName ::
    IdentifierStart {IdentifierPart}

Significance of white-space

In certain parts of the grammar, white-space is critical for the scanner to distinguish between tokens. Consider the following code and the tokens it produces:

newObject
{class: SyntaxKind.Identifier, lexeme: 'newObject'}

Here, newObject is categorized as an Identifier. This occurs through the recursive derivation of the IdentifierPart production, as shown above. Because each character in newObject belongs to the set defined for IdentifierPart, the scanner treats the entire sequence as a single token. Now examine a similar example:

new Object
{class: SyntaxKind.NewKeyword, lexeme: 'new'}
{class: SyntaxKind.Identifier, lexeme: 'Object'}

Despite containing the same characters, the presence of a space causes these to be parsed as two distinct tokens. The scanner splits them because, when attempting to derive IdentifierPart, the space is not a valid character for that production. It therefore generates an IdentifierName token with the lexeme new, which is three characters long. The scanner then consults its list of keywords, finds new, and assigns it the NewKeyword category (the details of that lookup will be covered later).

Characters such as (, which cannot serve as IdentifierPart, similarly act as token boundaries:

if(s=3){...}
IfKeyword OpenParenToken ...

White-space is also formally listed as a distinct token class within the InputElementDiv goal symbol:

InputElementDiv::
    WhiteSpace
    LineTerminator
    ...

Defining assignment operators and number literals rules

So far, I have demonstrated the grammar for the const keyword and the identifier v. The remaining pieces are the equals sign and the numeral 3:

ConstToken Identifier = 3

The equals sign is employed in JavaScript for assigning values to variables. There exists a wide array of assignment operators, all systematically grouped under the AssignmentOperator symbol:

AssignmentOperator : one of
    *= /= %= += -= <<= >>= >>>= &= ^= |= **=

Finally, the number 3 needs to be accounted for. JavaScript numbers appear in numerous forms: a decimal literal with a fractional part like 1.58, binary literals such as 0b11, hexadecimal literals like 0x11, and exponent notation such as 5e2. It makes sense to encompass all these variations under a single NumericLiteral symbol:

NumericLiteral::
  DecimalLiteral
  BinaryIntegerLiteral
  OctalIntegerLiteral
  HexIntegerLiteral

These, too, are non-terminal symbols. By following the linked references, you can trace each non-terminal down to its terminal characters.

Multiple goal symbols

We previously learned that the derivation process begins with a goal (or start) symbol. The ECMAScript lexical grammar, however, introduces complexity by defining several such goal symbols. Take the following code snippet:

/foo/g

Suppose the ECMAScript scanner starts deriving tokens for this statement using the primary goal symbol InputElementDiv, whose productions are:

InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator
    RightBracePunctuator

The scanner would then produce the following token stream:

/             foo            /             g
DivPunctuator IdentifierName DivPunctuator IdentifierName

But anyone with sufficient JavaScript experience knows that /foo/g is a regexp literal. It therefore should be recognized as a single RegularExpressionLiteral token, according to the following grammar rule:

RegularExpressionLiteral ::
/ RegularExpressionBody / RegularExpressionFlags

There is no path from the InputElementDiv goal symbol to a RegularExpressionLiteral. Hence, a distinct goal symbol named InputElementRegExp must be introduced, containing a production for the regexp literal:

InputElementRegExp ::
    WhiteSpace
    ...
    RegularExpressionLiteral

With this goal symbol, the scanner correctly identifies /foo/g as a RegularExpressionLiteral. A natural question follows: how does the scanner know which goal symbol to employ during tokenization? As I noted earlier, the parser dictates the context. The parser requests tokens sequentially from the scanner, and when the current parsing context permits the InputElementRegExp goal symbol, it instructs the scanner to recognize tokens **under that goal symbol**.

For instance, suppose the parser is currently processing a PrimaryExpression, which has this grammar:

PrimaryExpression :
    this
    IdentifierLiteral
    …
    RegularExpressionLiteral

Since the grammar allows a regular expression literal to derive from a primary expression, the parser selects InputElementRegExp as the goal symbol for the scanner. The TypeScript compiler implements this by triggering a re-scan of the current token when it determines that the current context allows a goal symbol other than the primary InputElementDiv. Additional goal symbols are defined by ECMAScript; for further details, refer to this detailed StackOverflow answer.

Regular expressions

In some cases, the lexical grammar is expressed using repetition operators rather than recursion. For example, the Java 8 grammar defines the IdentifierChars symbol—equivalent to the recursive IdentifierName production in ECMAScript—like this:

IdentifierChars:
    JavaLetter {JavaLetterOrDigit}
JavaLetter:
    any Unicode character that is a "Java letter"
JavaLetterOrDigit:
    any Unicode character that is a "Java letter-or-digit"

The parentheses around JavaLetterOrDigit indicate repetition, as explained in the grammar documentation:

The syntax {x} on the right-hand side of a production denotes zero or more occurrences of x.

This style of grammar specification has a distinctive quality: by replacing every nonterminal (except the root) with its right-hand side, you can produce a single production for the root that contains only terminals. This simplified expression can then be readily turned into a **regular expression**. For IdentifierChars, that would yield the following:

[range of Java letter][range of Java letter-or-digit]*

Employing repetition operators in regular grammar, instead of recursive structures, is uncommon. When the grammar adheres to the standard recursive notation, mechanically converting it to a regular expression is far from trivial: one must first translate the grammar into a non-deterministic finite automaton (NFA, discussed later), and then convert that NFA into a regular expression. Yet often, a plausible regular expression can be derived through straightforward “logical deduction”.

Both a regular grammar and a regular expression are capable of describing a sequence of characters drawn from a fixed set, and they are effectively interchangeable. For this reason, regular expressions are frequently chosen over regular grammars to specify lexical rules. This is the approach taken by lexical analyzer generators, such as Flex.

Finite automata

Finite automata (FA) represent a third formalism for specifying lexical patterns, alongside regular grammars and regular expressions. All three approaches serve the same fundamental purpose — identifying sets of character sequences. Their independent origins explain why three distinct formalisms exist. For describing how a scanner works, FA offers the most intuitive mental model, and we’ll rely on it here.

A useful way to grasp the automaton concept is to think of a character-by-character algorithm for word recognition. Consider recognizing the const token. The logic would test for c, then o, then n, continuing until the final character t. Representing each step of this program as a transition diagram yields the following:

In the diagram, each automaton state appears as a circle. This discussion focuses exclusively on automata with a finite number of states — hence the term finite automaton. The double-lined circle marks the what’s called an **accepting state**, and an automaton may contain multiple such states. When the input is fully consumed and the automaton rests in an accepting state, that input qualifies as a valid character sequence.

Finite automata come in two flavors: deterministic (DFA) and non-deterministic (NFA). The key distinction is that in a DFA, each input character uniquely dictates the next state — hence the deterministic label. In contrast, an NFA may permit several possible resulting states for a given input, which is why it’s non-deterministic:

A DFA only changes state in response to reading input. An NFA, however, can be designed to shift to a new state without consuming any input at all. Conversion algorithms between the two types exist, and they hold equivalent expressive power — every DFA can be considered a special case of an NFA.

The scanner occasionally faces ambiguity. The operators =, /=, *=, and += are all valid tokens individually, yet how does the scanner determine whether += represents a single += token or a + token followed by a = token? The longest match wins rule settles this: the string += becomes one token, which at runtime serves as the addition assignment operator.

DFA implementation

DFAs find expression in two common scanner implementations: table-driven and hand-coded. Tools dedicated to scanner generation, such as Flex, typically produce table-driven scanners. Because a DFA’s deterministic nature ensures a single next state per input and eliminates backtracking, it’s the preferred model for generated scanners. The typical pipeline converts a lexical specification — whether regular grammar or regular expression — into an NFA, then transforms that NFA into a DFA. The diagram below illustrates this workflow:

Yet most commercial and open-source compilers opt for hand-coded scanners instead. These manual implementations outpace generated ones since they can strip away overhead that generated scanners necessarily include. The TypeScript compiler employs this hand-coded approach. In such a scanner, the explicit grammar-to-DFA conversion often becomes unnecessary; a developer can implement the scanning algorithm directly from the lexical specification, and a natural byproduct is that the implementation behaves like a DFA.

Both scanner types simulate the DFA in essentially the same manner. They pull in each successive input character and replicate the DFA transition that character triggers. After reading a character, the scanner checks for possible transitions; if one exists, it follows the transition into a new state. When no transition is available, the scanner examines whether the current state accepts. An accepting state leads to word recognition and the return of a lexeme alongside its syntactic category to the calling procedure. If the current state does not accept, the scanner looks back to see whether an accepting state appeared earlier on the path. Finding one causes the scanner to rewind its internal character position to that point and declare success; otherwise, it signals an error.

TypeScript scanner details

You can inspect TypeScript’s scanner implementation in the scanner.ts file. The scan method houses the main DFA emulation logic — reading input and moving between states. Its core consists of an infinite while loop that examines the current input character, processes every transition from that character, updates the position, and returns the token class upon recognition:

const pos;
while (true) {
    tokenPos = pos;
    if (pos >= end) {
        return token = SyntaxKind.EndOfFileToken;
    }
    let ch = text.charCodeAt(pos);
    switch(ch) {
        case CharacterCodes.exclamation:
            ...
            pos++;
            return token = SyntaxKind.ExclamationToken;
        case CharacterCodes.openParen:
            ...
            pos++;
            return token = SyntaxKind.OpenParenToken;
        ...

The absence of backtracking confirms its DFA emulation.

Here’s a concrete example. ECMAScript establishes a distinct set of punctuators, including the following:

Punctuator ::
    !  !=  !==  -  --  -=

Converting this rule into regular expressions proves straightforward:

/!==|!=|!|--|-=|-/

Feeding that into a conversion tool produces a DFA:

Every state except the start state is an accepting state — a reflection of what the grammar and regular expression prescribe.

TypeScript translates the DFA into the following code:

case CharacterCodes.exclamation:
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        if (text.charCodeAt(pos + 2) === CharacterCodes.equals) {
            pos += 3;
            return token = SyntaxKind.ExclamationEqualsEqualsToken;
        }
        pos += 2
        return token = SyntaxKind.ExclamationEqualsToken;
    }
    pos++;
    return token = SyntaxKind.ExclamationToken;
case CharacterCodes.plus:
    if (text.charCodeAt(pos + 1) === CharacterCodes.plus) {
        pos += 2;
        return token = SyntaxKind.PlusPlusToken;
    }
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        pos += 2
        return token = SyntaxKind.PlusEqualsToken;
    }
    pos++;
    return token = SyntaxKind.PlusToken;

The TS implementation and the DFA share a goal: the scanner attempts to match the longest possible string.

Keyword handling

ECMAScript, as we’ve noted, categorizes keywords such as const, let, and if under its Keyword designation. One possibility is crafting explicit regular expressions for each keyword and adding corresponding DFA paths. Because the grammar defines keywords as a subset of identifiers:

Identifier:
    IdentifierName but not ReservedWord

a different tactic works: treat keywords as identifiers initially, then check whether a matched identifier qualifies as a keyword. TypeScript follows this exact path. The scanner stores all keywords and other literal tokens in the textToToken map, and once an identifier is found, it looks up that map to determine the correct token class, whether that class turns out to be a keyword or not:

default:
    if (isIdentifierStart(ch, languageVersion)) {
        pos++;
        while (isIdentifierPart(ch = text.charCodeAt(pos))) pos++;
        tokenValue = text.substring(tokenPos, pos);
        return token = getIdentifierToken();
function getIdentifierToken(): SyntaxKind {
    if (...) {
        return token = textToToken.get(tokenValue);
    }
    return token = SyntaxKind.Identifier;

Credits

A heartfelt thank-you goes to sepp2k for assisting me in assembling the whole picture and for offering a technical review of this article.

Additional thanks to Mohamed Hegazy, whose technical review helped ensure accuracy in the TypeScript implementation portions.

Further reading

A second part is currently in the works, delving into the theory of context-free grammar, AST construction, and parser implementation algorithms. That installment will demonstrate how the TypeScript parser is built and which algorithms it relies on. Follow along to stay updated on its release.

For deeper exploration, these resources come highly recommended:

• Stanford CS143 (Compilers)
• Engineering: A Compiler