Tokens

Tokens in CDTk

Tokens are the foundation of every compiler. They represent patterns in the input text, such as numbers, identifiers, or operators. In CDTk, a TokenSet is used to define all tokens for your language, serving as the first step in the compilation pipeline.

---

What Are Tokens?

A token consists of:

• A name: A unique identifier for the token type.
• A regex pattern: Determines which text the token matches.

For example:

• "Identifier" matches myVariable.
• "Number" matches 42 or 3.14.
• "Plus" matches +.

CDTk processes the input text by converting it into a sequence of tokens. For instance:

var tokens = new TokenSet
{
    new Token("Identifier", @"[A-Za-z_][A-Za-z0-9_]*"),
    new Token("Number", @"\d+"),
    new Token("Plus", @"\+"),
    new Token("Equals", @"=")
};

// Input: x = 42
// Output Tokens: Identifier("x"), Equals("="), Number("42")

---

Defining Tokens with TokenSet

In CDTk, all tokens are grouped into a TokenSet, which is used to tokenize input text. Here’s how to define one:

var tokens = new TokenSet
{
    new Token("Identifier", @"[A-Za-z_][A-Za-z0-9_]*"),  // Matches variable names
    new Token("Number", @"\d+"),                        // Matches integers
    new Token("Plus", @"\+"),                           // Matches +
    new Token("Equals", @"="),                          // Matches =
    new Token("Whitespace", @"\s+").Ignore()            // Skips whitespace
};

Key Features

• Name: Tokens must have a unique name for identification.
• Regex Pattern: Defines the text pattern to match.
• Order Matters: Tokens are matched in the order they are defined in the TokenSet.

---

Common Token Patterns

Here are some common token definitions for different programming constructs:

Identifiers and Keywords

Identifiers and keywords often share similar patterns but must be carefully prioritized:

new Token("Keyword", @"if|while|return"),  // Matches keywords
new Token("Identifier", @"[A-Za-z_][A-Za-z0-9_]*")  // Matches variable names and labels

Numbers

new Token("Integer", @"\d+");                  // Whole numbers
new Token("Float", @"\d+\.\d+([eE][+-]?\d+)?"); // Floating-point numbers with optional scientific notation
new Token("Hexadecimal", @"0[xX][0-9A-Fa-f]+");

Strings

new Token("String", @"""([^""\\]|\\.)*""");   // Double-quoted strings
new Token("Char", @"'([^'\\]|\\.)'");         // Single-quoted characters

Operators and Delimiters

new Token("Equals", @"==");    // Equality operator
new Token("Assign", @"=");     // Assignment operator
new Token("Plus", @"\+");      // Plus operator
new Token("LParen", @"\(");    // Left parenthesis
new Token("Semicolon", @";");  // Semicolon

Comments and Whitespace

new Token("Whitespace", @"\s+").Ignore();    // Ignore spaces
new Token("LineComment", @"//.*").Ignore();  // Skip // comments
new Token("BlockComment", @"/\*.*?\*/").Ignore();  // Skip /* ... */ comments

---

Ignoring Tokens

Sometimes, you want the compiler to recognize tokens like whitespace or comments but exclude them from the output token stream. CDTk makes this easy with the .Ignore() method:

var tokens = new TokenSet
{
    new Token("Whitespace", @"\s+").Ignore(),
    new Token("LineComment", @"//.*").Ignore(),
    new Token("BlockComment", @"/\*.*?\*/").Ignore()
};

Ignored tokens:

• Simplify parsing by removing unnecessary matches.
• Keep the focus on meaningful tokens in the token stream.

---

Token Ordering

Token order matters in a TokenSet, especially when regex patterns overlap. Define more specific tokens before generic ones to avoid unexpected matches.

Example: Overlapping Patterns

// Incorrect Order
new Token("Identifier", @"\w+");   // Matches everything, including "if"
new Token("Keyword", @"if");       // Will never match because "Identifier" captures it

// Correct Order
new Token("Keyword", @"if");       
new Token("Identifier", @"\w+");   // Matches non-keywords

Best Practice

Always test overlapping token patterns and prioritize the most specific matches first.

---

Advanced Techniques

Unicode Support

Support identifiers and symbols across multiple languages or alphabets:

new Token("UnicodeIdentifier", @"[\p{L}_][\p{L}\p{N}_]*");  // Letters and numbers

Context-Aware Tokens

Define tokens that adapt to context:

new Token("TemplateStart", @"<(?=\w)");  // Match '<' only before word characters
new Token("LessThan", @"<");             // Match standalone '<'

---

Avoiding Token Pitfalls

1. Greedy Patterns

Regex patterns are greedy by default and match the largest possible substring. Use non-greedy qualifiers ? when necessary:

new Token("String", @""".*?""");  // Matches until the closest closing quote

2. Misordered Patterns

Ensure specific patterns (e.g., keywords) appear above general ones (e.g., identifiers).

3. Testing and Validation

Test all token patterns in edge cases to identify conflicts or unexpected matches.

---

Best Practices

1. Use Descriptive Names: Name tokens after their purpose, not abbreviations.

   new Token("LeftParenthesis", @"\(");  // Clear
   new Token("LP", @"\(");               // Ambiguous

2. Test Regular Expressions: Validate patterns using tools like Regex101 or Regexr.

3. Avoid Overlap Conflicts: Ensure that your tokens prioritize specific over general patterns.

4. Handle Edge Cases: Address scenarios like Unicode, large numbers, or scientific notation.

---

Next Steps

Ready to move on? Here’s what to explore next:

• Define grammars for tokenized input: Rules
• Learn about mappings for code generation: Mapping
• Explore the full compilation pipeline: Learn