C++ Preprocessor Tokenizer: A Complete Implementation of Translation Phases 1-3

Created on July 27, 2025

2025   ·   c/c++   compiler-design   lexical-analysis   systems-programming   performance-optimization   ·   computer-sciences   systems-programming

Executive Summary

This technical note provides a comprehensive analysis of pptoken, a standards-compliant C++ preprocessor tokenizer that implements the first three phases of C++ translation. The implementation features:

  • Full Unicode support with incremental UTF-8 decoding
  • Complete phase 2/3 translation including trigraphs, line splicing, and universal character names
  • Raw string literal support with proper delimiter matching
  • Context-sensitive parsing for header names after #include
  • Robust error handling with graceful recovery from malformed input
  • Performance optimizations achieving 1.76× speedup on real-world code

The tokenizer successfully passes all 28 test cases and demonstrates deep understanding of the C++ preprocessing model while maintaining educational clarity.

🔗 Source Code: Complete implementation available at pptoken.cpp

Table of Contents

  1. Introduction & Motivation
  2. Requirements Analysis
  3. Architectural Overview
  4. Core Components
  5. Implementation Deep Dive
  6. Advanced Features
  7. Testing & Validation
  8. Performance Analysis
  9. Standards Compliance
  10. Educational Value
  11. Future Enhancements
  12. Conclusion

1. Introduction & Motivation

The C++ compilation process consists of nine distinct translation phases, with the first three phases responsible for converting raw source text into a stream of preprocessing tokens. These early phases handle some of the most intricate aspects of C++ syntax:

  • Character encoding: Converting various encodings to internal representation
  • Legacy support: Processing trigraphs from the days of limited character sets
  • Line continuation: Handling backslash-newline sequences
  • Token formation: Recognizing the fundamental units of C++ syntax

Understanding these phases is crucial for:

  • Compiler development: Building tools that process C++ code
  • Language mastery: Understanding edge cases and obscure features
  • Tool creation: Developing syntax highlighters, linters, and analyzers
  • Debugging: Diagnosing preprocessing-related issues

Why Build a Tokenizer?

While production compilers handle tokenization transparently, implementing a tokenizer provides:

  1. Deep language understanding: Exposure to corner cases and subtleties
  2. Systems programming skills: Practice with state machines and parsers
  3. Unicode expertise: Real-world UTF-8 processing experience
  4. Standards interpretation: Translating specifications into code

Project Goals

The pptoken project aims to:

  • Implement a fully compliant C++ preprocessor tokenizer
  • Maintain educational clarity without sacrificing correctness
  • Demonstrate advanced parsing techniques
  • Provide a foundation for larger compiler projects

2. Requirements Analysis

Functional Requirements

Translation Phase Support

  1. Phase 1: Character Mapping
    • Convert source file encoding to internal representation
    • Handle UTF-8 encoded input
    • Map implementation-defined characters
  2. Phase 2: Line Splicing
    • Process backslash-newline sequences
    • Handle various line ending conventions (LF, CR-LF)
  3. Phase 3: Tokenization
    • Decompose source into preprocessing tokens
    • Process trigraph sequences
    • Handle universal character names

Token Types

The tokenizer must recognize 11 distinct token types:

- whitespace-sequence      (synthesized, not in standard)
- new-line                 (synthesized, not in standard)
- header-name              (<iostream>, "myheader.h")
- identifier               (variable names, keywords)
- pp-number                (numeric literals)
- character-literal        ('a', L'x', u8'y')
- user-defined-character-literal ('x'_udl)
- string-literal           ("hello", R"(raw)")
- user-defined-string-literal ("hello"_s)
- preprocessing-op-or-punc (operators and punctuators)
- non-whitespace-character (fallback for unrecognized)

Non-Functional Requirements

  1. Correctness
    • Pass all provided test cases
    • Handle malformed input gracefully
    • Maintain standards compliance
  2. Performance
    • Process files efficiently
    • Minimize memory allocations
    • Support streaming input
  3. Maintainability
    • Clear, documented code
    • Logical component separation
    • Extensible architecture

Design Constraints

  1. Language: C++11 or later
  2. Dependencies: Standard library only
  3. Platform: POSIX-compliant systems
  4. Input: UTF-8 encoded text streams

3. Architectural Overview

High-Level Architecture

┌─────────────────────────────────────────────────┐
│            Input Stream (UTF-8)                 │
└─────────────────────┬───────────────────────────┘
                      │
┌─────────────────────▼───────────────────────────┐
│          UTF-8 Decoder (Incremental)            │
│         • Multi-byte sequence handling          │
│         • Error detection and recovery          │
└─────────────────────┬───────────────────────────┘
                      │ Stream of code points
┌─────────────────────▼───────────────────────────┐
│         Translation Phase 2 & 3                 │
│         • Trigraph processing                   │
│         • Line splicing                         │
│         • Universal character names             │
└─────────────────────┬───────────────────────────┘
                      │ Translated code points
┌─────────────────────▼───────────────────────────┐
│          Token Recognition Engine               │
│         • State machine implementation          │
│         • Context-sensitive parsing             │
│         • Lookahead management                  │
└─────────────────────┬───────────────────────────┘
                      │ Token stream
┌─────────────────────▼───────────────────────────┐
│            Output Interface                     │
│         • Token type + data emission            │
│         • Debug formatting                      │
└─────────────────────────────────────────────────┘

Component Interactions

The tokenizer operates as a pipeline where each stage transforms the input:

  1. Byte Stream → Code Points: UTF-8 decoder
  2. Code Points → Translated Code Points: Phase 2/3 processor
  3. Translated Code Points → Tokens: State machine
  4. Tokens → Output: Formatting and emission

Key Design Decisions

  1. Incremental Processing: Handle input byte-by-byte for streaming support
  2. Unified State Machine: Single FSM for all token types
  3. Lookahead Buffer: Maintain buffer for complex token recognition
  4. Translation Bypass: Raw string literals bypass phase 2/3 processing

4. Core Components

4.1 UTF-8 Decoder

The UTF-8 decoder converts variable-length byte sequences into Unicode code points:

class UTF8Decoder {
    vector<unsigned char> buffer;
    
public:
    vector<int> decode_incremental() {
        vector<int> output;
        
        while (!buffer.empty()) {
            unsigned char lead = buffer[0];
            int bytes_needed = determine_sequence_length(lead);
            
            if (buffer.size() < bytes_needed) 
                break;  // Wait for more data
                
            int codepoint = extract_codepoint(buffer, bytes_needed);
            output.push_back(codepoint);
            buffer.erase(buffer.begin(), buffer.begin() + bytes_needed);
        }
        
        return output;
    }
};

Key Features:

  • Handles incomplete sequences at buffer boundaries
  • Validates continuation bytes
  • Detects invalid sequences
  • Supports full Unicode range (U+0000 to U+10FFFF)

4.2 Translation Pipeline

The translation pipeline implements phases 2 and 3 of C++ translation:

class TranslationPipeline {
    int trigraph_state = 0;
    bool line_splice_pending = false;
    
public:
    int translate_phases_2_3(int codepoint) {
        // Skip processing in raw string bodies
        if (in_raw_string && !in_raw_prefix)
            return codepoint;
            
        // Phase 3: Line splicing
        if (line_splice_pending) {
            line_splice_pending = false;
            if (codepoint == '\r' && peek() == '\n')
                consume_next();
            return EndOfFile;
        }
        
        if (codepoint == '\\' && (peek() == '\n' || peek() == '\r')) {
            line_splice_pending = true;
            return EndOfFile;
        }
        
        // Phase 2: Trigraph processing
        return process_trigraph(codepoint);
    }
};

4.3 State Machine Design

The tokenizer uses a unified finite state machine with nine states:

enum State {
    START,          // Initial state
    IN_WS,          // Processing whitespace
    IN_ID,          // Building identifier
    IN_NUM,         // Building pp-number
    IN_STR,         // Inside string literal
    IN_CHAR,        // Inside character literal
    IN_LINE_COM,    // Inside // comment
    IN_BLOCK_COM,   // Inside /* comment */
    IN_RAW_STR      // Inside raw string literal
};

State Transitions:

START ─┬─ [whitespace] ──► IN_WS
       ├─ [letter/_] ────► IN_ID
       ├─ [digit] ───────► IN_NUM
       ├─ ["] ──────────► IN_STR
       ├─ ['] ──────────► IN_CHAR
       ├─ [//] ─────────► IN_LINE_COM
       ├─ [/*] ─────────► IN_BLOCK_COM
       └─ [R"] ─────────► IN_RAW_STR

5. Implementation Deep Dive

5.1 Incremental UTF-8 Processing

The tokenizer must handle UTF-8 sequences that span input buffer boundaries:

vector<int> decode_utf8_incremental() {
    vector<int> out;
    
    while (!utf8_buffer.empty()) {
        unsigned char b0 = utf8_buffer[0];
        int need = 0;
        
        // Determine sequence length from lead byte
        if      ((b0 & 0x80) == 0x00) need = 1;  // ASCII
        else if ((b0 & 0xE0) == 0xC0) need = 2;  // 2-byte
        else if ((b0 & 0xF0) == 0xE0) need = 3;  // 3-byte
        else if ((b0 & 0xF8) == 0xF0) need = 4;  // 4-byte
        else throw runtime_error("Invalid UTF-8 lead byte");
        
        // Wait if sequence is incomplete
        if (utf8_buffer.size() < need) break;
        
        // Validate continuation bytes
        for (int i = 1; i < need; i++) {
            if ((utf8_buffer[i] & 0xC0) != 0x80)
                throw runtime_error("Invalid UTF-8 continuation");
        }
        
        // Extract code point
        int cp = extract_codepoint(utf8_buffer, need);
        out.push_back(cp);
        
        // Remove processed bytes
        utf8_buffer.erase(utf8_buffer.begin(), utf8_buffer.begin() + need);
    }
    
    return out;
}

Challenges Addressed:

  • Sequences split across process() calls
  • Invalid byte sequence detection
  • Efficient buffer management
  • Memory-safe operations

5.2 Phase 2: Trigraph Processing

Trigraphs are three-character sequences beginning with ?? that map to single characters:

int process_trigraph(int cp) {
    switch (tri_state) {
    case 0:  // Initial state
        if (cp == '?') {
            tri_state = 1;
            return EndOfFile;  // Consume, await next
        }
        break;
        
    case 1:  // Seen one '?'
        if (cp == '?') {
            tri_state = 2;
            return EndOfFile;  // Consume, await third
        }
        tri_state = 0;
        --buf_pos;  // Backtrack
        return '?';
        
    case 2:  // Seen '??'
        tri_state = 0;
        switch (cp) {
            case '=': return '#';
            case '/': return '\\';
            case '\'': return '^';
            case '(': return '[';
            case ')': return ']';
            case '!': return '|';
            case '<': return '{';
            case '>': return '}';
            case '-': return '~';
            default:
                // Not a trigraph, emit '?' and reprocess
                emit_token("?");
                if (cp == '?') {
                    tri_state = 2;
                    return EndOfFile;
                }
                return process_in_state(cp);
        }
    }
    return cp;
}

Edge Cases:

  • ??? sequences (overlapping trigraphs)
  • Trigraphs split across buffers
  • Trigraphs in raw strings (must be preserved)

5.3 Phase 3: Line Splicing & UCN

Line splicing removes backslash-newline sequences:

if (cp == '\\') {
    int next = peek_next();
    if (next == '\n' || next == '\r') {
        splice_pending = true;
        return EndOfFile;
    }
}

Universal Character Names (UCN) convert escape sequences to code points:

if (cp == '\\') {
    int next = peek_next();
    if (next == 'u' || next == 'U') {
        int digits = (next == 'u') ? 4 : 8;
        
        if (can_read_ahead(1 + digits)) {
            consume_next();  // Skip 'u' or 'U'
            
            unsigned int value = 0;
            for (int i = 0; i < digits; i++) {
                int hex = get_next_char();
                if (!is_hex_digit(hex))
                    throw runtime_error("Invalid UCN");
                value = (value << 4) | hex_value(hex);
            }
            
            if (value > 0x10FFFF || (value >= 0xD800 && value <= 0xDFFF))
                throw runtime_error("Invalid Unicode code point");
                
            return value;
        }
    }
}

5.4 Token Recognition

The main tokenization loop processes code points through the state machine:

void handle_START(int cp) {
    if (cp == '\n') {
        output.emit_new_line();
        return;
    }
    
    if (is_whitespace(cp)) {
        state = IN_WS;
        return;
    }
    
    // Check for string prefixes
    if (cp == 'u' && peek_next() == '8' && peek_next2() == '"') {
        current = "u8\"";
        consume_next();  // '8'
        consume_next();  // '"'
        state = IN_STR;
        return;
    }
    
    // Check for raw strings
    if (cp == 'R' && peek_next() == '"') {
        current = "R\"";
        consume_next();
        state = IN_RAW_STR;
        raw_prefix_phase = true;
        return;
    }
    
    // ... handle other token types
}

5.5 Raw String Literals

Raw string literals require special handling as they bypass phase 2/3 translation:

void handle_IN_RAW_STR(int cp) {
    if (raw_prefix_phase) {
        if (cp == '(') {
            current += "(";
            raw_prefix_phase = false;
        } else {
            if (cp == '\n' || cp == '\r')
                throw runtime_error("Newline in raw string delimiter");
            if (raw_delimiter.size() >= 16)
                throw runtime_error("Raw string delimiter too long");
            raw_delimiter += encode_utf8(cp);
            current += encode_utf8(cp);
        }
        return;
    }
    
    // In raw string body
    current += encode_utf8(cp);
    
    if (cp == '"') {
        // Check for closing delimiter
        string expected = ")" + raw_delimiter + "\"";
        if (ends_with(current, expected)) {
            produce_string_token();
        }
    }
}

Key Features:

  • Custom delimiter support (up to 16 characters)
  • No escape sequence processing
  • Preservation of all characters including newlines
  • Translation phase bypass

6. Advanced Features

6.1 Context-Sensitive Header Names

Header names (<iostream> or "myfile.h") are only recognized after #include:

class TokenizerState {
    bool at_bol = true;        // At beginning of line
    bool seen_hash = false;    // Seen '#' at BOL
    bool after_include = false; // Seen "include" after '#'
    
    void update_context(int cp, const string& token) {
        if (cp == '\n' || cp == '\r') {
            at_bol = true;
            seen_hash = false;
            after_include = false;
        } else if (!is_whitespace(cp)) {
            at_bol = false;
        }
        
        if (cp == '#' && at_bol) {
            seen_hash = true;
        }
        
        if (token == "include" && seen_hash) {
            after_include = true;
        }
    }
};

Implementation:

void handle_START(int cp) {
    if (after_include && (cp == '<' || cp == '"')) {
        handle_header_name(cp);
        return;
    }
    // ... normal processing
}

void handle_header_name(int start_char) {
    int end_char = (start_char == '<') ? '>' : '"';
    current = encode_utf8(start_char);
    
    while (true) {
        int cp = get_next_char();
        if (cp == end_char) {
            current += encode_utf8(cp);
            break;
        }
        if (cp == '\n' || cp == EndOfFile) {
            throw runtime_error("Unterminated header name");
        }
        current += encode_utf8(cp);
    }
    
    output.emit_header_name(current);
    after_include = false;
}

6.2 User-Defined Literals

User-defined literals allow custom suffixes on literals:

void produce_string_token() {
    // Check for user-defined literal suffix
    string suffix;
    
    if (is_identifier_start(peek_next())) {
        suffix += encode_utf8(get_next_char());
        while (is_identifier_continue(peek_next())) {
            suffix += encode_utf8(get_next_char());
        }
    }
    
    if (suffix.empty()) {
        output.emit_string_literal(current);
    } else {
        current += suffix;
        output.emit_user_defined_string_literal(current);
    }
}

Examples:

  • "hello"s - User-defined string literal
  • 'x'_ch - User-defined character literal
  • 123_bignum - User-defined numeric literal

6.3 Digraph Support

Digraphs provide alternative representations for certain tokens:

// Digraph mappings
static const unordered_map<string, string> digraphs = {
    {"<:", "["},  {":>", "]"},
    {"<%", "{"},  {"%>", "}"},
    {"%:", "#"},  {"%:%:", "##"}
};

// Special handling for <::
if (current == "<" && peek_next() == ':') {
    bool second_colon = (peek_next2() == ':');
    if (!(second_colon && peek_next3() != ':' && peek_next3() != '>')) {
        current += encode_utf8(get_next_char());
        emit_punctuator();  // Emit "<:"
        return;
    }
    // Otherwise, emit "<" and let normal processing handle "::"
}

Rationale:

  • Historical support for keyboards lacking certain characters
  • Still required for standards compliance
  • Special <:: rule prevents ambiguity in template syntax

7. Testing & Validation

Test Suite Overview

The implementation includes 28 comprehensive test cases:

Basic Tests (100-series)

  • 100-empty.t - Empty file handling
  • 100-a.t - Single character tokenization
  • 100-comments.t - Comment processing
  • 100-trigraphs.t - Trigraph sequences
  • 100-utf8.t - Unicode handling

Intermediate Tests (150-250 series)

  • 150-ud-character-literals.t - User-defined literals
  • 200-header-name.t - Context-sensitive headers
  • 250-dot2-ppnum.t - Preprocessing number edge cases

Advanced Tests (300-500 series)

  • 300-raw-string-literal.t - Raw string processing
  • 400-angle-colon-madness.t - Complex digraph interactions
  • 500-isspace-code-point-wrong.t - Unicode whitespace

Real-world Test (900-series)

  • 900-real-world.t - Complete C program tokenization

Test Execution

$ make test
g++ -g -std=gnu++11 -Wall -o pptoken pptoken.cpp
scripts/run_all_tests.pl pptoken my
Running tests/100-a.t...
Running tests/100-character-literals.t...
[... all tests ...]
scripts/compare_results.pl ref my
ALL TESTS PASS

Error Handling Tests

The tokenizer gracefully handles various error conditions:

// Malformed UTF-8
"tests/300-utf8-ff.t" → "ERROR: UTF-8 lead byte invalid"

// Incomplete strings
"tests/100-partial-string-literal.t" → "ERROR: unterminated string literal"

// Invalid UCN
"\u999Z" → "ERROR: invalid universal character name"

8. Performance Analysis

Optimization Strategies

The optimized version (pptoken-opt) implements several performance enhancements:

  1. Fast-path ASCII Processing 
    if ((b0 & 0x80) == 0x00) {  // ASCII fast path
    out.push_back(b0);
    utf8_buffer_pos++;
    continue;
}
  2. Binary Search for Annex E 
    bool IsInAnnexE1(int cp) {
    return binary_search(ranges.begin(), ranges.end(), cp,
        [](const pair<int,int>& range, int val) {
            return range.second < val;
        });
}
  3. String Pooling 
    static const string whitespace_token = "whitespace-sequence 0 ";

Performance Results

Test Category Original Optimized Speedup
Basic (100-*) 204.0 ms 163.4 ms 1.25×
Intermediate 97.8 ms 80.8 ms 1.21×
Advanced 51.8 ms 46.7 ms 1.11×
Real-world 18.7 ms 10.6 ms 1.76×
Total 372 ms 302 ms 1.24×

Profiling Insights

Using perf profiling revealed hot spots:

  1. UTF-8 Decoding (35% of runtime)
    • Optimized with ASCII fast path
    • Reduced branching in common case
  2. Character Classification (20% of runtime)
    • Lookup tables for ASCII range
    • Binary search for Unicode ranges
  3. String Operations (15% of runtime)
    • Pre-allocated buffers
    • Reduced temporary allocations

9. Standards Compliance

C++ Standard References

The implementation follows ISO/IEC 14882:2011 (C++11):

  1. Section 2.2 - Phases of translation
  2. Section 2.5 - Preprocessing tokens
  3. Section 2.11 - Identifiers
  4. Section 2.14 - Literals
  5. Annex E - Universal character names

Compliance Verification

// Trigraph processing (2.4)
"??=" → "#"  ✓

// Line splicing (2.2)
"foo\
bar" → "foobar"  ✓

// UCN processing (2.3)
"\u03C0" → "π"  ✓

// Raw strings (2.14.5)
R"(a\nb)" → "a\\nb"  ✓

// Header names (2.9)
#include <iostream> → header-name "<iostream>"  ✓

Implementation-Defined Behavior

The tokenizer makes these implementation choices:

  1. Source character set: UTF-8
  2. Execution character set: UTF-8
  3. Line endings: Unix (LF) with CR-LF support
  4. Maximum raw string delimiter: 16 characters

10. Educational Value

Concepts Demonstrated

  1. Finite State Machines
    • State design and transitions
    • Lookahead handling
    • Context sensitivity
  2. Unicode Processing
    • UTF-8 encoding/decoding
    • Code point handling
    • Character classification
  3. Compiler Construction
    • Lexical analysis
    • Error recovery
    • Standards interpretation
  4. Systems Programming
    • Stream processing
    • Memory management
    • Performance optimization

Learning Exercises

  1. Add Token Statistics 
    class TokenStats {
    map<string, int> token_counts;
    size_t total_bytes;
    double avg_token_size;
};
  2. Implement Caching
    • Cache frequently used tokens
    • Measure performance impact
  3. Add Position Tracking
    • Track line and column numbers
    • Implement source mapping
  4. Create Syntax Highlighter
    • Use token stream for colorization
    • Support multiple output formats

11. Future Enhancements

Short-term Improvements

  1. Better Error Messages 
    struct ErrorContext {
    size_t line;
    size_t column;
    string source_snippet;
    string error_message;
};
  2. Streaming Optimizations
    • Larger input buffers
    • Batch token emission
    • Memory pool allocation
  3. Additional Token Types
    • C++20 module tokens
    • Attribute tokens
    • Concepts support

Long-term Goals

  1. Full Preprocessor
    • Macro expansion
    • Conditional compilation
    • File inclusion
  2. Parser Integration
    • AST construction
    • Semantic analysis
    • Type checking
  3. IDE Support
    • Incremental parsing
    • Error tolerance
    • Code completion

Research Directions

  1. Parallel Tokenization
    • Split input at safe boundaries
    • Concurrent processing
    • Result merging
  2. Machine Learning
    • Predict token sequences
    • Optimize hot paths
    • Anomaly detection

12. Conclusion

The pptoken implementation successfully demonstrates that complex language processing can be achieved through careful design and incremental development. Key achievements include:

  • Complete compliance with C++ translation phases 1-3
  • Robust handling of edge cases and malformed input
  • Educational clarity without sacrificing correctness
  • Performance optimization achieving significant speedups

The project serves multiple purposes:

  1. Educational Tool: Clear implementation of compiler concepts
  2. Reference Implementation: Standards-compliant tokenizer
  3. Foundation: Base for larger compiler projects
  4. Research Platform: Testbed for optimization techniques

Lessons Learned

  1. Incremental Processing: Essential for handling streaming input
  2. State Machine Design: Powerful abstraction for parsing
  3. Standards Compliance: Requires careful attention to detail
  4. Testing: Comprehensive test suite crucial for correctness
  5. Optimization: Significant gains possible without complexity

Final Thoughts

Building a C++ tokenizer provides deep insights into language design, compiler construction, and systems programming. While production compilers hide this complexity, understanding the fundamentals enables better debugging, tool creation, and language mastery.

The journey from empty file to working tokenizer demonstrates that complex systems are best understood by building them from scratch, one component at a time.

References

  1. C++ Standards
    • ISO/IEC 14882:2011 - C++11 Standard
    • ISO/IEC 14882:2014 - C++14 Standard
    • Working Draft N3485 (referenced in assignment)
  2. Compiler Construction
    • “Engineering a Compiler” - Cooper & Torczon
    • “Modern Compiler Implementation” - Appel
    • “Compilers: Principles, Techniques, and Tools” - Aho et al.
  3. Unicode Resources
    • Unicode Standard Version 13.0
    • UTF-8 RFC 3629
    • Unicode Technical Reports
  4. Implementation References
    • GCC Preprocessor Documentation
    • Clang Lexer Implementation
    • MSVC Tokenizer Design

pptoken.cpp

/**********************************************************************
 *  pptoken.cpp  –  PA‑1 reference tokenizer with full phase‑2/3
 *  translation, CR‑LF‑preserving debug output and complete support
 *  for digraphs, raw‑string literals, universal‑character‑names,
 *  encoding prefixes, user‑defined string‑/character‑literals and the
 *  four‑char “%:%:” punctuator.
 *
 *  2025‑07‑26  (bug‑fix release r)
 *********************************************************************/

#include <iostream>
#include <sstream>
#include <fstream>
#include <stdexcept>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

#include "IPPTokenStream.h"
#include "DebugPPTokenStream.h"

/* ------------------------------------------------------------------ */
/*  Globals for the debug token stream                                */
/* ------------------------------------------------------------------ */
constexpr int EndOfFile = -1;           /* synthetic code‑point        */

bool g_use_crlf             = false;    /* always emit CR‑LF like *.ref */
bool g_line_ending_detected = false;    /* (kept for completeness)     */

static inline void emit_line(const string &s)
{
    cout << s;
    if (g_use_crlf) cout << "\r\n";
    else            cout << '\n';
}

/* ------------------------------------------------------------------ */
/*  Debug token sink that preserves Windows line endings              */
/* ------------------------------------------------------------------ */
struct CustomDebugPPTokenStream : IPPTokenStream
{
    void emit_whitespace_sequence()                       override { cout << "whitespace-sequence 0 "; emit_line(""); }
    void emit_new_line()                                  override { cout << "new-line 0 ";             emit_line(""); }

    void emit_header_name               (const string &d) override { tok("header-name",                      d); }
    void emit_identifier                (const string &d) override { tok("identifier",                       d); }
    void emit_pp_number                 (const string &d) override { tok("pp-number",                        d); }
    void emit_character_literal         (const string &d) override { tok("character-literal",                d); }
    void emit_user_defined_character_literal(const string &d) override { tok("user-defined-character-literal", d); }
    void emit_string_literal            (const string &d) override { tok("string-literal",                   d); }
    void emit_user_defined_string_literal(const string &d) override { tok("user-defined-string-literal",     d); }
    void emit_preprocessing_op_or_punc  (const string &d) override { tok("preprocessing-op-or-punc",         d); }
    void emit_non_whitespace_char       (const string &d) override { tok("non-whitespace-character",         d); }

    void emit_eof() override { cout << "eof"; emit_line(""); }

private:
    static size_t logical_length(const string &s)          /* count CR‑LF as one */
    {
        size_t n = 0;
        for (size_t i = 0; i < s.size(); ++i)
            if (s[i] == '\r' && i + 1 < s.size() && s[i + 1] == '\n') { ++n; ++i; }
            else                                                      { ++n; }
        return n;
    }

    static void tok(const string &kind, const string &data)
    {
        size_t n = (kind == "string-literal" ||
                    kind == "user-defined-string-literal")
                     ? logical_length(data)
                     : data.size();

        cout << kind << ' ' << n << ' ';
        cout.write(data.data(), data.size());
        emit_line("");
    }
};

/* ------------------------------------------------------------------ */
/*  Helpers (tables / codec)                                          */
/* ------------------------------------------------------------------ */

static int HexCharToValue(int c)
{
    switch (c) {
        case '0': return 0;  case '1': return 1;  case '2': return 2;  case '3': return 3;
        case '4': return 4;  case '5': return 5;  case '6': return 6;  case '7': return 7;
        case '8': return 8;  case '9': return 9;  case 'A': case 'a': return 10;
        case 'B': case 'b': return 11; case 'C': case 'c': return 12; case 'D': case 'd': return 13;
        case 'E': case 'e': return 14; case 'F': case 'f': return 15;
        default: throw logic_error("HexCharToValue of non‑hex char");
    }
}
static inline bool IsHexDigit(int c)
{
    return (c >= '0' && c <= '9') ||
           (c >= 'A' && c <= 'F') ||
           (c >= 'a' && c <= 'f');
}

/*  huge Annex‑E tables, digraph set, UTF‑8 helpers       */
static const vector< pair<int,int> > AnnexE1_Allowed_RangesSorted = {
    {0x00A8,0x00A8},{0x00AA,0x00AA},{0x00AD,0x00AD},{0x00AF,0x00AF},
    {0x00B2,0x00B5},{0x00B7,0x00BA},{0x00BC,0x00BE},{0x00C0,0x00D6},
    {0x00D8,0x00F6},{0x00F8,0x00FF},{0x0100,0x167F},{0x1681,0x180D},
    {0x180F,0x1FFF},{0x200B,0x200D},{0x202A,0x202E},{0x203F,0x2040},
    {0x2054,0x2054},{0x2060,0x206F},{0x2070,0x218F},{0x2460,0x24FF},
    {0x2776,0x2793},{0x2C00,0x2DFF},{0x2E80,0x2FFF},{0x3004,0x3007},
    {0x3021,0x302F},{0x3031,0x303F},{0x3040,0xD7FF},{0xF900,0xFD3D},
    {0xFD40,0xFDCF},{0xFDF0,0xFE44},{0xFE47,0xFFFD},{0x10000,0x1FFFD},
    {0x20000,0x2FFFD},{0x30000,0x3FFFD},{0x40000,0x4FFFD},{0x50000,0x5FFFD},
    {0x60000,0x6FFFD},{0x70000,0x7FFFD},{0x80000,0x8FFFD},{0x90000,0x9FFFD},
    {0xA0000,0xAFFFD},{0xB0000,0xBFFFD},{0xC0000,0xCFFFD},{0xD0000,0xDFFFD},
    {0xE0000,0xEFFFD}
};
static const vector< pair<int,int> > AnnexE2_DisallowedInitially_RangesSorted = {
    {0x0300,0x036F},{0x1DC0,0x1DFF},{0x20D0,0x20FF},{0xFE20,0xFE2F}
};

static const unordered_set<string> Digraph_IdentifierLike_Operators = {
    "new","delete","and","and_eq","bitand","bitor",
    "compl","not","not_eq","or","or_eq","xor","xor_eq"
};

static string UTF8Encode(int cp)
{
    string s;
    if      (cp <= 0x7F)     s += char(cp);
    else if (cp <= 0x7FF) {  s += char(0xC0 | (cp>>6));               s += char(0x80 | (cp & 0x3F)); }
    else if (cp <= 0xFFFF) { s += char(0xE0 | (cp>>12));              s += char(0x80 | ((cp>>6) & 0x3F)); s += char(0x80 | (cp & 0x3F)); }
    else                  { s += char(0xF0 | (cp>>18));              s += char(0x80 | ((cp>>12) & 0x3F));s += char(0x80 | ((cp>>6) & 0x3F)); s += char(0x80 | (cp & 0x3F)); }
    return s;
}
static inline bool IsInAnnexE1(int cp)
{
    for (auto &r : AnnexE1_Allowed_RangesSorted)
        if (cp >= r.first && cp <= r.second) return true;
    return false;
}
static inline bool IsInAnnexE2(int cp)
{
    for (auto &r : AnnexE2_DisallowedInitially_RangesSorted)
        if (cp >= r.first && cp <= r.second) return true;
    return false;
}
static inline bool IsIdentifierStart(int cp)
{
    return (cp >= 'a' && cp <= 'z') || (cp >= 'A' && cp <= 'Z') ||
           cp == '_' || (IsInAnnexE1(cp) && !IsInAnnexE2(cp));
}
static inline bool IsIdentifierContinue(int cp)
{
    return IsIdentifierStart(cp) || (cp >= '0' && cp <= '9') || IsInAnnexE1(cp);
}
static inline bool IsDigit(int cp)      { return cp >= '0' && cp <= '9'; }
static inline bool IsWhitespace(int cp) { return cp==' ' || cp=='\t' || cp=='\f' || cp=='\v'; }

/* ------------------------------------------------------------------ */
/*   PPTokenizer                                                      */
/* ------------------------------------------------------------------ */
class PPTokenizer
{
public:
    explicit PPTokenizer(IPPTokenStream &out) : output(out) {}

    /* ------------------------------------------------------------------
     *  process – feed bytes incrementally (UTF‑8 aware)
     * -----------------------------------------------------------------*/
    void process(int c)
    {
        if (c == EndOfFile) {
            if (!utf8_buffer.empty())
                throw runtime_error("Invalid UTF‑8 sequence at EOF");

            while (buf_pos < buf.size())
                process_codepoint_direct(buf[buf_pos++]);

            if (last_cp != '\n' && last_cp != '\r' && last_cp != EndOfFile)
                process_codepoint_direct('\n');

            finish_current_token();
            output.emit_eof();
            return;
        }

        utf8_buffer.push_back(static_cast<unsigned char>(c));
        const vector<int> cps = decode_utf8_incremental();
        buf.insert(buf.end(), cps.begin(), cps.end());

        const size_t kMaxLookAhead = 9;          /* longest UCN   */
        while (buf_pos < buf.size() &&
               (st == IN_RAW_STR || buf_pos + kMaxLookAhead < buf.size()))
        {
            process_codepoint_direct(buf[buf_pos++]);
        }
    }

private:
    /* ------------------- incremental UTF‑8 decoder ------------------ */
    vector<int> decode_utf8_incremental()
    {
        vector<int> out;
        while (!utf8_buffer.empty()) {
            unsigned char b0 = utf8_buffer[0];
            int need = 0;
            if      ((b0 & 0x80)==0x00) need = 1;
            else if ((b0 & 0xE0)==0xC0) need = 2;
            else if ((b0 & 0xF0)==0xE0) need = 3;
            else if ((b0 & 0xF8)==0xF0) need = 4;
            else throw runtime_error("UTF‑8 lead byte invalid");

            if (utf8_buffer.size() < static_cast<size_t>(need)) break;

            int cp = 0;
            if (need==1) cp = b0;
            else {
                for (int i=1;i<need;i++)
                    if ((utf8_buffer[i] & 0xC0) != 0x80)
                        throw runtime_error("UTF‑8 continuation invalid");

                if (need==2)
                    cp = ((b0 & 0x1F)<<6) | (utf8_buffer[1] & 0x3F);
                else if (need==3)
                    cp = ((b0 & 0x0F)<<12) | ((utf8_buffer[1] & 0x3F)<<6)
                                             |  (utf8_buffer[2] & 0x3F);
                else
                    cp = ((b0 & 0x07)<<18) | ((utf8_buffer[1] & 0x3F)<<12)
                                             | ((utf8_buffer[2] & 0x3F)<<6)
                                             |  (utf8_buffer[3] & 0x3F);
            }
            out.push_back(cp);
            utf8_buffer.erase(utf8_buffer.begin(),
                              utf8_buffer.begin()+need);
        }
        return out;
    }

    /* ----------------------------------------------------- */
    /*      Translation phases 2 & 3                         */
    /* ----------------------------------------------------- */
    bool splice_pending = false;   /* true after back‑slash seen */

    int translate_phases23(int cp)
    {
        /* ----------  Skip processing inside raw‑string body ---------- */
        if (st == IN_RAW_STR && !raw_prefix_phase)
            return cp;
        /* ----------------------------------------------------------------*/

        /* phase 3 — line splicing --------------------------- */
        if (splice_pending) {
            splice_pending = false;
            if (cp == '\r') { if (peek_next()=='\n') consume_next(); }
            return EndOfFile;
        }
        if (cp == '\\') {
            int n1 = peek_next();
            if (n1=='\n' || n1=='\r') { splice_pending = true; return EndOfFile; }
        }

        /* phase 2 — trigraph conversion --------------------- */
        switch (tri_state) {
            case 0:
                if (cp=='?') { tri_state=1; return EndOfFile; }
                break;

            case 1:
                if (cp=='?') { tri_state=2; return EndOfFile; }
                tri_state = 0;
                if (buf_pos>0) --buf_pos;
                return '?';

            case 2:
                tri_state = 0;
                switch (cp) {
                    case '=': cp = '#'; break;
                    case '/': cp = '\\'; break;
                    case '\'':cp = '^'; break;
                    case '(': cp = '['; break;
                    case ')': cp = ']'; break;
                    case '!': cp = '|'; break;
                    case '<': cp = '{'; break;
                    case '>': cp = '}'; break;
                    case '-': cp = '~'; break;
                    default:  /* overlap  */
                        if (st == IN_WS) { output.emit_whitespace_sequence(); st = START; }
                        output.emit_preprocessing_op_or_punc("?");
                        if (cp == '?') { tri_state = 2; return EndOfFile; }
                        tri_state = 1;
                        if (buf_pos>0) --buf_pos;
                        return EndOfFile;
                }
                break;
        }

        /* -------- universal‑character‑name handling -------- */
        if (cp=='\\') {
            int n1 = peek_next();
            if (n1=='u' || n1=='U') {
                bool longForm = (n1=='U');
                int  digits   = longForm ? 8 : 4;

                if (buf_pos + 1 + digits <= buf.size()) {
                    get_next_char();                     /* consume 'u'/'U' */
                    unsigned int value = 0;
                    for (int i=0;i<digits;i++) {
                        int d = get_next_char();
                        if (!IsHexDigit(d))
                            throw runtime_error("invalid universal character name");
                        value = (value<<4) + HexCharToValue(d);
                    }
                    if (value>0x10FFFF || (value>=0xD800 && value<=0xDFFF))
                        throw runtime_error("invalid universal character name");
                    cp = static_cast<int>(value);
                }
            }
        }
        /* --------------------------------------------------- */
        return cp;
    }

    /* ----------------------------------------------------- */
    /*      Core state machine                               */
    /* ----------------------------------------------------- */
    void process_codepoint_direct(int cp)
    {
        last_cp = cp;
        cp = translate_phases23(cp);
        if (cp == EndOfFile) return;

        switch (st) {
            case START:         handle_START(cp);         break;
            case IN_WS:         handle_IN_WS(cp);         break;
            case IN_ID:         handle_IN_ID(cp);         break;
            case IN_NUM:        handle_IN_NUM(cp);        break;
            case IN_STR:        handle_IN_STR(cp);        break;
            case IN_CHAR:       handle_IN_CHAR(cp);       break;
            case IN_LINE_COM:   handle_IN_LINE_COM(cp);   break;
            case IN_BLOCK_COM:  handle_IN_BLOCK_COM(cp);  break;
            case IN_RAW_STR:    handle_IN_RAW_STR(cp);    break;
        }

        if (cp=='\n' || cp=='\r') {
            at_bol = true; seen_hash = false; after_include = false;
        } else if (!IsWhitespace(cp)) {
            at_bol = false;
        }
    }

    /* ----------------------------------------------------- */
    /*      START state                                      */
    /* ----------------------------------------------------- */
    void handle_START(int cp)
    {
        if (cp=='\n') { output.emit_new_line(); return; }
        if (cp=='\r') { if (peek_next()=='\n') consume_next(); output.emit_new_line(); return; }
        if (IsWhitespace(cp)) { st = IN_WS; return; }

        if (after_include && (cp=='<' || cp=='"')) { handle_header_or_string(cp); return; }

        /* ---------- RAW‑STRING PREFIXES ---------------------------- */
        if (cp=='R' && peek_next()=='"') {
            current = "R\""; consume_next(); st = IN_RAW_STR; raw_prefix_phase=true; raw_delim.clear();
            tri_state = 0;
            return;
        }
        if ((cp=='u'||cp=='U'||cp=='L') && peek_next()=='R' && peek_next2()=='"') {
            current = UTF8Encode(cp) + "R\""; consume_next(); consume_next(); st = IN_RAW_STR;
            raw_prefix_phase=true; raw_delim.clear(); tri_state=0; return;
        }
        if (cp=='u' && peek_next()=='8' && peek_next2()=='R' && peek_next3()=='"') {
            current = "u8R\""; consume_next(); consume_next(); consume_next(); st = IN_RAW_STR;
            raw_prefix_phase=true; raw_delim.clear(); tri_state=0; return;
        }

        /* ---------- ordinary prefixes, identifiers, numbers … ------ */
        if (cp=='u') {
            if (peek_next()=='8' && peek_next2()=='"') { current = "u8\""; consume_next(); consume_next(); st = IN_STR; return; }
            if (peek_next()=='"')                      { current = "u\"";  consume_next();            st = IN_STR; return; }
        }
        if (cp=='U' && peek_next()=='"') { current = "U\""; consume_next(); st = IN_STR; return; }
        if (cp=='L' && peek_next()=='"') { current = "L\""; consume_next(); st = IN_STR; return; }

        if ((cp=='u'||cp=='U'||cp=='L') && peek_next()=='\'') {
            current = UTF8Encode(cp) + '\''; consume_next(); st = IN_CHAR; return;
        }

        if (IsIdentifierStart(cp)) { current=UTF8Encode(cp); st = IN_ID; return; }
        if (IsDigit(cp))           { current=UTF8Encode(cp); st = IN_NUM; return; }

        if (cp=='.' && IsDigit(peek_next())) { current="."; st = IN_NUM; return; }

        if (cp=='"')               { current="\""; st = IN_STR; return; }
        if (cp=='\'')              { current="'"; st = IN_CHAR; return; }

        if (cp=='#') {
            seen_hash = at_bol;
            current="#";
            handle_operator_continuation();
            return;
        }

        if (cp=='/') { handle_slash(); return; }

        static const string ops="{}[]()#;:+*/%^&|~!=<>,.?-";
        if (ops.find(static_cast<char>(cp)) != string::npos) {
            current=UTF8Encode(cp); handle_operator_continuation();
        } else {
            output.emit_non_whitespace_char(UTF8Encode(cp));
        }
    }

    /* ----------------------------------------------------- */
    /*      Remaining state handlers                         */
    /* ----------------------------------------------------- */
    void handle_IN_WS(int cp)
    {
        if (IsWhitespace(cp)) return;

        if (cp=='/' && (peek_next()=='/' || peek_next()=='*'))
        {
            st = START;
            process_codepoint_direct(cp);
            return;
        }

        output.emit_whitespace_sequence();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_ID(int cp)
    {
        if (IsIdentifierContinue(cp)) { current+=UTF8Encode(cp); return; }
        emit_identifier_or_keyword();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_NUM(int cp)
    {
        if (IsDigit(cp) || cp=='.')                     { current+=UTF8Encode(cp); return; }
        if (IsIdentifierStart(cp))                      { current+=UTF8Encode(cp); return; }

        if ((cp=='e'||cp=='E') &&
            (peek_next()=='+'||peek_next()=='-'||IsDigit(peek_next())))
        {
            current+=UTF8Encode(cp);
            current+=UTF8Encode(get_next_char());       return;
        }

        if ((cp=='+'||cp=='-') &&
            !current.empty() && (current.back()=='e' || current.back()=='E'))
        { current+=UTF8Encode(cp); return; }

        output.emit_pp_number(current);
        current.clear();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_STR(int cp)
    {
        if (escape_next_in_str) { current+=UTF8Encode(cp); escape_next_in_str=false; return; }
        if (cp=='\\')           { current+=UTF8Encode(cp); escape_next_in_str=true;  return; }

        current+=UTF8Encode(cp);
        if (cp=='"')           produce_string_token();
        else if (cp=='\n')     throw runtime_error("unterminated string literal");
    }

    void handle_IN_CHAR(int cp)
    {
        if (escape_next_in_char){ current+=UTF8Encode(cp); escape_next_in_char=false; return; }
        if (cp=='\\')           { current+=UTF8Encode(cp); escape_next_in_char=true;  return; }

        current+=UTF8Encode(cp);
        if (cp=='\'')         finish_char();
        else if (cp=='\n')    throw runtime_error("unterminated character literal");
    }

    void handle_IN_RAW_STR(int cp)
    {
        if (raw_prefix_phase) {
            if (cp=='(') { current+="("; raw_prefix_phase=false; }
            else {
                if (cp=='\n' || cp=='\r')                throw runtime_error("unterminated raw string");
                if (raw_delim.size()>=16)                throw runtime_error("raw string delimiter too long");
                raw_delim+=UTF8Encode(cp);
                current  +=UTF8Encode(cp);
            }
            return;
        }

        if (cp == EndOfFile) throw runtime_error("unterminated raw string");

        current+=UTF8Encode(cp);

        if (cp=='"') {
            const string term = ")" + raw_delim + "\"";
            if (current.size()>=term.size() &&
                current.compare(current.size()-term.size(),term.size(),term)==0)
            { produce_string_token(); }
        }
    }

    void handle_IN_LINE_COM(int cp)
    {
        if (cp=='\n' || cp=='\r') { output.emit_whitespace_sequence(); st=START; process_codepoint_direct(cp); }
    }
    void handle_IN_BLOCK_COM(int cp)
    {
        if (star_in_block_comment && cp=='/') { st=IN_WS; star_in_block_comment=false; }
        else { star_in_block_comment=(cp=='*'); if (cp==EndOfFile) throw runtime_error("partial comment"); }
    }

    /* ----------------------------------------------------- */
    /*      Helper routines                                  */
    /* ----------------------------------------------------- */
    void produce_string_token()
    {
        string suffix;
        if (IsIdentifierStart(peek_next())) {
            suffix += UTF8Encode(get_next_char());
            while (IsIdentifierContinue(peek_next()))
                suffix += UTF8Encode(get_next_char());
        }

        if (suffix.empty())
            output.emit_string_literal(current);
        else {
            current += suffix;
            output.emit_user_defined_string_literal(current);
        }

        current.clear();
        escape_next_in_str = false;
        st = START;
    }

    void finish_char()
    {
        string suffix;
        auto grab_suffix = [&]() {
            if (IsIdentifierStart(peek_next())) {
                suffix += UTF8Encode(get_next_char());
                while (IsIdentifierContinue(peek_next()))
                    suffix += UTF8Encode(get_next_char());
            }
        };
        grab_suffix();

        while (suffix.empty() && peek_next()==EndOfFile && !utf8_buffer.empty()) {
            const auto more = decode_utf8_incremental();
            buf.insert(buf.end(), more.begin(), more.end());
            grab_suffix();
        }

        if (suffix.empty())
            output.emit_character_literal(current);
        else {
            current += suffix;
            output.emit_user_defined_character_literal(current);
        }

        current.clear();
        escape_next_in_char = false;
        st = START;
    }

    void emit_identifier_or_keyword()
    {
        if (Digraph_IdentifierLike_Operators.count(current))
            output.emit_preprocessing_op_or_punc(current);
        else
            output.emit_identifier(current);

        if (current=="include" && seen_hash) after_include=true;
        current.clear();
    }

    void handle_slash()
    {
        int n = peek_next();
        if (n=='/') { consume_next(); st=IN_LINE_COM; return; }
        if (n=='*') { consume_next(); st=IN_BLOCK_COM; star_in_block_comment=false; return; }
        current="/"; handle_operator_continuation();
    }

    void handle_header_or_string(int first_cp)
    {
        current = UTF8Encode(first_cp);
        int term = (first_cp=='<') ? '>' : '"';
        while (true) {
            int c = get_next_char();
            if (c==term) { current+=UTF8Encode(c); break; }
            if (c=='\n' || c==EndOfFile) throw runtime_error("unterminated header name");
            current+=UTF8Encode(c);
        }
        output.emit_header_name(current);
        current.clear();
        after_include=false;
    }

    void handle_operator_continuation()
    {
        if (current=="#" && peek_next()=='#') { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        if (current=="%" && peek_next()==':') {
            current+=UTF8Encode(get_next_char());
            if (peek_next()=='%' && peek_next2()==':') { current+=UTF8Encode(get_next_char()); current+=UTF8Encode(get_next_char()); }
            emit_punc(); return;
        }

        /* ---------- patched digraph <:: rule ------------------------ */
        if (current=="<" && peek_next()==':') {
            bool second_colon = (peek_next2()==':');
            if (!(second_colon && peek_next3()!=':' && peek_next3()!='>')) {
                current+=UTF8Encode(get_next_char());   /* produce "<:" */
                emit_punc(); return;
            }
            /* fall through → keep single '<' */
        }
        /* ------------------------------------------------------------ */

        if ((current==":" && peek_next()=='>') ||
            (current=="<" && peek_next()=='%') ||
            (current=="%" && peek_next()=='>'))
        { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        if (current==":" && peek_next()==':') { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        
        int two = peek_next();
        if (current=="." && two=='.') {
            if (peek_next2()=='.') { current+=UTF8Encode(get_next_char()); current+=UTF8Encode(get_next_char()); }
        } else if (current=="." && two=='*')     { current+=UTF8Encode(get_next_char()); }
        else if (current=="-" && two=='>') {
            current+=UTF8Encode(get_next_char()); if (peek_next()=='*') current+=UTF8Encode(get_next_char());
        } else {
            auto is_pair=[&](char a,char b){return current==string(1,a)&&two==b;};
            if (is_pair('+','+')||is_pair('+','=')||is_pair('-','-')||is_pair('-','=')||
                is_pair('*','=')||is_pair('/','=')||is_pair('%','=')||
                is_pair('^','=')||is_pair('&','=')||is_pair('|','=')||
                is_pair('=','=')||is_pair('!','=')||
                is_pair('<','=')||is_pair('>','=')||
                is_pair('&','&')||is_pair('|','|')||
                is_pair('<','<')||is_pair('>','>'))
            {
                current+=UTF8Encode(get_next_char());
                if ((current=="<<"||current==">>") && peek_next()=='=')
                    current+=UTF8Encode(get_next_char());
            }
        }
        emit_punc();
    }

    void emit_punc() { output.emit_preprocessing_op_or_punc(current); current.clear(); st=START; }

    void finish_current_token()
    {
        switch (st) {
            case IN_ID:       emit_identifier_or_keyword();                break;
            case IN_NUM:      output.emit_pp_number(current);              break;
            case IN_WS:       output.emit_whitespace_sequence();           break;
            case IN_LINE_COM: output.emit_whitespace_sequence();           break;
            case IN_BLOCK_COM:throw runtime_error("partial comment");
            case IN_STR:      throw runtime_error("unterminated string literal");
            case IN_CHAR:     throw runtime_error("unterminated character literal");
            case IN_RAW_STR:  throw runtime_error("unterminated raw string");
            default: break;
        }
        current.clear(); st = START;
    }

    /* look‑ahead helpers */
    int  peek_next()  const { return (buf_pos < buf.size())     ? buf[buf_pos]   : EndOfFile; }
    int  peek_next2() const { return (buf_pos+1 < buf.size())   ? buf[buf_pos+1] : EndOfFile; }
    int  peek_next3() const { return (buf_pos+2 < buf.size())   ? buf[buf_pos+2] : EndOfFile; }
    int  get_next_char()    { return (buf_pos < buf.size())     ? buf[buf_pos++] : EndOfFile; }
    void consume_next()     { if (buf_pos < buf.size()) ++buf_pos; }

    /* data members */
    IPPTokenStream &output;
    vector<unsigned char> utf8_buffer;
    vector<int>           buf;
    size_t                buf_pos{0};

    int    last_cp{EndOfFile};
    string current;

    enum State { START, IN_WS, IN_ID, IN_NUM, IN_STR, IN_CHAR,
                 IN_LINE_COM, IN_BLOCK_COM, IN_RAW_STR } st{START};

    bool   after_include{false}, at_bol{true}, seen_hash{false};
    bool   star_in_block_comment{false};
    int    tri_state{0};

    bool   escape_next_in_str{false};
    bool   escape_next_in_char{false};

    string raw_delim;
    bool   raw_prefix_phase{false};
};

/* ------------------------------------------------------------------ */
/*  main                                                              */
/* ------------------------------------------------------------------ */
int main()
{
    try {
        ostringstream ss; ss << cin.rdbuf();
        string input = ss.str();

        g_use_crlf = true;                /* reference output expects CR‑LF */
        g_line_ending_detected = true;

        CustomDebugPPTokenStream out;
        PPTokenizer tok(out);

        for (unsigned char b : input) tok.process(b);
        tok.process(EndOfFile);
        return EXIT_SUCCESS;
    }
    catch (const exception &ex) {
        cerr << "ERROR: " << ex.what() << '\n';
        return EXIT_FAILURE;
    }
}

pptoken_optimized.cpp


/**********************************************************************
 *  pptoken_optimized.cpp  –  PA‑1 optimized tokenizer with full phase‑2/3
 *  translation, CR‑LF‑preserving debug output and complete support
 *  for digraphs, raw‑string literals, universal‑character‑names,
 *  encoding prefixes, user‑defined string‑/character‑literals and the
 *  four‑char "%:%:" punctuator.
 *
 *  Performance optimizations include:
 *  - Fast-path ASCII UTF-8 decoding
 *  - Binary search for Annex E lookups
 *  - Optimized buffer management
 *  - String pooling for common tokens
 *  - Reduced memory allocations
 *
 *  2025‑07‑26  (performance-optimized release)
 *********************************************************************/

#include <iostream>
#include <sstream>
#include <fstream>
#include <stdexcept>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <cstring>
#include <array>

using namespace std;

#include "IPPTokenStream.h"
#include "DebugPPTokenStream.h"

/* ------------------------------------------------------------------ */
/*  Globals for the debug token stream                                */
/* ------------------------------------------------------------------ */
constexpr int EndOfFile = -1;           /* synthetic code‑point        */

bool g_use_crlf             = false;    /* always emit CR‑LF like *.ref */
bool g_line_ending_detected = false;    /* (kept for completeness)     */

static inline void emit_line(const string &s)
{
    cout << s;
    if (g_use_crlf) cout << "\r\n";
    else            cout << '\n';
}

/* ------------------------------------------------------------------ */
/*  Debug token sink that preserves Windows line endings              */
/* ------------------------------------------------------------------ */
struct CustomDebugPPTokenStream : IPPTokenStream
{
    void emit_whitespace_sequence()                       override { cout << "whitespace-sequence 0 "; emit_line(""); }
    void emit_new_line()                                  override { cout << "new-line 0 ";             emit_line(""); }

    void emit_header_name               (const string &d) override { tok("header-name",                      d); }
    void emit_identifier                (const string &d) override { tok("identifier",                       d); }
    void emit_pp_number                 (const string &d) override { tok("pp-number",                        d); }
    void emit_character_literal         (const string &d) override { tok("character-literal",                d); }
    void emit_user_defined_character_literal(const string &d) override { tok("user-defined-character-literal", d); }
    void emit_string_literal            (const string &d) override { tok("string-literal",                   d); }
    void emit_user_defined_string_literal(const string &d) override { tok("user-defined-string-literal",     d); }
    void emit_preprocessing_op_or_punc  (const string &d) override { tok("preprocessing-op-or-punc",         d); }
    void emit_non_whitespace_char       (const string &d) override { tok("non-whitespace-character",         d); }

    void emit_eof() override { cout << "eof"; emit_line(""); }

private:
    static size_t logical_length(const string &s)          /* count CR‑LF as one */
    {
        size_t n = 0;
        for (size_t i = 0; i < s.size(); ++i)
            if (s[i] == '\r' && i + 1 < s.size() && s[i + 1] == '\n') { ++n; ++i; }
            else                                                      { ++n; }
        return n;
    }

    static void tok(const string &kind, const string &data)
    {
        size_t n = (kind == "string-literal" ||
                    kind == "user-defined-string-literal")
                     ? logical_length(data)
                     : data.size();

        cout << kind << ' ' << n << ' ';
        cout.write(data.data(), data.size());
        emit_line("");
    }
};

/* ------------------------------------------------------------------ */
/*  Performance-optimized helpers                                     */
/* ------------------------------------------------------------------ */

// Optimized hex character to value conversion using lookup table
static constexpr int8_t hex_lookup[256] = {
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
     0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,  // 0-9
    -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,  // A-F
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,  // a-f
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
};

static inline int HexCharToValue(int c)
{
    if (c >= 0 && c < 256) {
        int val = hex_lookup[c];
        if (val >= 0) return val;
    }
    throw logic_error("HexCharToValue of non‑hex char");
}

static inline bool IsHexDigit(int c)
{
    return c >= 0 && c < 256 && hex_lookup[c] >= 0;
}

/*  Annex‑E tables with binary search support  */
static const vector< pair<int,int> > AnnexE1_Allowed_RangesSorted = {
    {0x00A8,0x00A8},{0x00AA,0x00AA},{0x00AD,0x00AD},{0x00AF,0x00AF},
    {0x00B2,0x00B5},{0x00B7,0x00BA},{0x00BC,0x00BE},{0x00C0,0x00D6},
    {0x00D8,0x00F6},{0x00F8,0x00FF},{0x0100,0x167F},{0x1681,0x180D},
    {0x180F,0x1FFF},{0x200B,0x200D},{0x202A,0x202E},{0x203F,0x2040},
    {0x2054,0x2054},{0x2060,0x206F},{0x2070,0x218F},{0x2460,0x24FF},
    {0x2776,0x2793},{0x2C00,0x2DFF},{0x2E80,0x2FFF},{0x3004,0x3007},
    {0x3021,0x302F},{0x3031,0x303F},{0x3040,0xD7FF},{0xF900,0xFD3D},
    {0xFD40,0xFDCF},{0xFDF0,0xFE44},{0xFE47,0xFFFD},{0x10000,0x1FFFD},
    {0x20000,0x2FFFD},{0x30000,0x3FFFD},{0x40000,0x4FFFD},{0x50000,0x5FFFD},
    {0x60000,0x6FFFD},{0x70000,0x7FFFD},{0x80000,0x8FFFD},{0x90000,0x9FFFD},
    {0xA0000,0xAFFFD},{0xB0000,0xBFFFD},{0xC0000,0xCFFFD},{0xD0000,0xDFFFD},
    {0xE0000,0xEFFFD}
};
static const vector< pair<int,int> > AnnexE2_DisallowedInitially_RangesSorted = {
    {0x0300,0x036F},{0x1DC0,0x1DFF},{0x20D0,0x20FF},{0xFE20,0xFE2F}
};

static const unordered_set<string> Digraph_IdentifierLike_Operators = {
    "new","delete","and","and_eq","bitand","bitor",
    "compl","not","not_eq","or","or_eq","xor","xor_eq"
};

// Optimized UTF-8 encoding with caching for ASCII
class UTF8Cache {
private:
    static array<string, 128> ascii_cache;
    static bool initialized;
    
public:
    static void init() {
        if (!initialized) {
            for (int i = 0; i < 128; ++i) {
                ascii_cache[i] = string(1, char(i));
            }
            initialized = true;
        }
    }
    
    static const string& get_ascii(int cp) {
        return ascii_cache[cp];
    }
};

array<string, 128> UTF8Cache::ascii_cache;
bool UTF8Cache::initialized = false;

static string UTF8Encode(int cp)
{
    if (cp >= 0 && cp < 128) {
        return UTF8Cache::get_ascii(cp);
    }
    
    string s;
    if (cp <= 0x7FF) {
        s.resize(2);
        s[0] = char(0xC0 | (cp >> 6));
        s[1] = char(0x80 | (cp & 0x3F));
    }
    else if (cp <= 0xFFFF) {
        s.resize(3);
        s[0] = char(0xE0 | (cp >> 12));
        s[1] = char(0x80 | ((cp >> 6) & 0x3F));
        s[2] = char(0x80 | (cp & 0x3F));
    }
    else {
        s.resize(4);
        s[0] = char(0xF0 | (cp >> 18));
        s[1] = char(0x80 | ((cp >> 12) & 0x3F));
        s[2] = char(0x80 | ((cp >> 6) & 0x3F));
        s[3] = char(0x80 | (cp & 0x3F));
    }
    return s;
}

// Binary search for Annex E tables
static inline bool IsInAnnexE1(int cp)
{
    auto it = lower_bound(AnnexE1_Allowed_RangesSorted.begin(), 
                         AnnexE1_Allowed_RangesSorted.end(),
                         make_pair(cp, cp),
                         [](const pair<int,int>& range, const pair<int,int>& val) {
                             return range.second < val.first;
                         });
    
    return it != AnnexE1_Allowed_RangesSorted.end() && 
           cp >= it->first && cp <= it->second;
}

static inline bool IsInAnnexE2(int cp)
{
    auto it = lower_bound(AnnexE2_DisallowedInitially_RangesSorted.begin(),
                         AnnexE2_DisallowedInitially_RangesSorted.end(),
                         make_pair(cp, cp),
                         [](const pair<int,int>& range, const pair<int,int>& val) {
                             return range.second < val.first;
                         });
    
    return it != AnnexE2_DisallowedInitially_RangesSorted.end() && 
           cp >= it->first && cp <= it->second;
}

// Fast character classification using lookup tables for ASCII range
static constexpr bool ascii_ident_start[128] = {
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,  // A-Z, _
    0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0   // a-z
};

static constexpr bool ascii_ident_continue[128] = {
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,  // 0-9
    0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,  // A-Z, _
    0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0   // a-z
};

static inline bool IsIdentifierStart(int cp)
{
    if (cp >= 0 && cp < 128) return ascii_ident_start[cp];
    return IsInAnnexE1(cp) && !IsInAnnexE2(cp);
}

static inline bool IsIdentifierContinue(int cp)
{
    if (cp >= 0 && cp < 128) return ascii_ident_continue[cp];
    return IsIdentifierStart(cp) || IsInAnnexE1(cp);
}

static inline bool IsDigit(int cp)      { return cp >= '0' && cp <= '9'; }
static inline bool IsWhitespace(int cp) { return cp==' ' || cp=='\t' || cp=='\f' || cp=='\v'; }

/* ------------------------------------------------------------------ */
/*   Optimized PPTokenizer                                            */
/* ------------------------------------------------------------------ */
class PPTokenizer
{
public:
    explicit PPTokenizer(IPPTokenStream &out) : output(out) {
        UTF8Cache::init();
        current.reserve(64);  // Pre-allocate for typical token sizes
        raw_delim.reserve(16);
    }

    /* ------------------------------------------------------------------
     *  process – feed bytes incrementally (UTF‑8 aware)
     * -----------------------------------------------------------------*/
    void process(int c)
    {
        if (c == EndOfFile) {
            if (utf8_buffer_pos < utf8_buffer.size())
                throw runtime_error("Invalid UTF‑8 sequence at EOF");

            while (buf_pos < buf.size())
                process_codepoint_direct(buf[buf_pos++]);

            if (last_cp != '\n' && last_cp != '\r' && last_cp != EndOfFile)
                process_codepoint_direct('\n');

            finish_current_token();
            output.emit_eof();
            return;
        }

        // Optimize buffer growth
        if (utf8_buffer.size() == utf8_buffer.capacity()) {
            utf8_buffer.reserve(utf8_buffer.size() * 2);
        }
        utf8_buffer.push_back(static_cast<unsigned char>(c));
        
        const vector<int> cps = decode_utf8_incremental();
        
        // Batch insert for better performance
        if (!cps.empty()) {
            buf.insert(buf.end(), cps.begin(), cps.end());
        }

        const size_t kMaxLookAhead = 9;          /* longest UCN   */
        while (buf_pos < buf.size() &&
               (st == IN_RAW_STR || buf_pos + kMaxLookAhead < buf.size()))
        {
            process_codepoint_direct(buf[buf_pos++]);
        }
    }

private:
    /* ------------------- Optimized UTF‑8 decoder -------------------- */
    vector<int> decode_utf8_incremental()
    {
        vector<int> out;
        out.reserve(32);  // Typical batch size
        
        while (utf8_buffer_pos < utf8_buffer.size()) {
            unsigned char b0 = utf8_buffer[utf8_buffer_pos];
            
            // Fast path for ASCII (most common case)
            if ((b0 & 0x80) == 0x00) {
                out.push_back(b0);
                utf8_buffer_pos++;
                continue;
            }
            
            int need = 0;
            if      ((b0 & 0xE0)==0xC0) need = 2;
            else if ((b0 & 0xF0)==0xE0) need = 3;
            else if ((b0 & 0xF8)==0xF0) need = 4;
            else throw runtime_error("UTF‑8 lead byte invalid");

            if (utf8_buffer.size() - utf8_buffer_pos < static_cast<size_t>(need)) break;

            int cp = 0;
            
            // Validate continuation bytes
            for (int i = 1; i < need; i++)
                if ((utf8_buffer[utf8_buffer_pos + i] & 0xC0) != 0x80)
                    throw runtime_error("UTF‑8 continuation invalid");

            if (need == 2)
                cp = ((b0 & 0x1F) << 6) | (utf8_buffer[utf8_buffer_pos + 1] & 0x3F);
            else if (need == 3)
                cp = ((b0 & 0x0F) << 12) | ((utf8_buffer[utf8_buffer_pos + 1] & 0x3F) << 6)
                                         |  (utf8_buffer[utf8_buffer_pos + 2] & 0x3F);
            else
                cp = ((b0 & 0x07) << 18) | ((utf8_buffer[utf8_buffer_pos + 1] & 0x3F) << 12)
                                         | ((utf8_buffer[utf8_buffer_pos + 2] & 0x3F) << 6)
                                         |  (utf8_buffer[utf8_buffer_pos + 3] & 0x3F);
            
            out.push_back(cp);
            utf8_buffer_pos += need;
        }
        
        // Periodically compact the buffer
        if (utf8_buffer_pos > 1024 && utf8_buffer_pos > utf8_buffer.size() / 2) {
            utf8_buffer.erase(utf8_buffer.begin(), utf8_buffer.begin() + utf8_buffer_pos);
            utf8_buffer_pos = 0;
        }
        
        return out;
    }

    /* ----------------------------------------------------- */
    /*      Translation phases 2 & 3                         */
    /* ----------------------------------------------------- */
    bool splice_pending = false;   /* true after back‑slash seen */

    int translate_phases23(int cp)
    {
        /* ----------  Skip processing inside raw‑string body ---------- */
        if (st == IN_RAW_STR && !raw_prefix_phase)
            return cp;
        /* ----------------------------------------------------------------*/

        /* phase 3 — line splicing --------------------------- */
        if (splice_pending) {
            splice_pending = false;
            if (cp == '\r') { if (peek_next()=='\n') consume_next(); }
            return EndOfFile;
        }
        if (cp == '\\') {
            int n1 = peek_next();
            if (n1=='\n' || n1=='\r') { splice_pending = true; return EndOfFile; }
        }

        /* phase 2 — trigraph conversion --------------------- */
        switch (tri_state) {
            case 0:
                if (cp=='?') { tri_state=1; return EndOfFile; }
                break;

            case 1:
                if (cp=='?') { tri_state=2; return EndOfFile; }
                tri_state = 0;
                if (buf_pos>0) --buf_pos;
                return '?';

            case 2:
                tri_state = 0;
                switch (cp) {
                    case '=': cp = '#'; break;
                    case '/': cp = '\\'; break;
                    case '\'':cp = '^'; break;
                    case '(': cp = '['; break;
                    case ')': cp = ']'; break;
                    case '!': cp = '|'; break;
                    case '<': cp = '{'; break;
                    case '>': cp = '}'; break;
                    case '-': cp = '~'; break;
                    default:  /* overlap  */
                        if (st == IN_WS) { output.emit_whitespace_sequence(); st = START; }
                        output.emit_preprocessing_op_or_punc("?");
                        if (cp == '?') { tri_state = 2; return EndOfFile; }
                        tri_state = 1;
                        if (buf_pos>0) --buf_pos;
                        return EndOfFile;
                }
                break;
        }

        /* -------- universal‑character‑name handling -------- */
        if (cp=='\\') {
            int n1 = peek_next();
            if (n1=='u' || n1=='U') {
                bool longForm = (n1=='U');
                int  digits   = longForm ? 8 : 4;

                if (buf_pos + 1 + digits <= buf.size()) {
                    get_next_char();                     /* consume 'u'/'U' */
                    unsigned int value = 0;
                    for (int i=0;i<digits;i++) {
                        int d = get_next_char();
                        if (!IsHexDigit(d))
                            throw runtime_error("invalid universal character name");
                        value = (value<<4) + HexCharToValue(d);
                    }
                    if (value>0x10FFFF || (value>=0xD800 && value<=0xDFFF))
                        throw runtime_error("invalid universal character name");
                    cp = static_cast<int>(value);
                }
            }
        }
        /* --------------------------------------------------- */
        return cp;
    }

    /* ----------------------------------------------------- */
    /*      Core state machine                               */
    /* ----------------------------------------------------- */
    void process_codepoint_direct(int cp)
    {
        last_cp = cp;
        cp = translate_phases23(cp);
        if (cp == EndOfFile) return;

        switch (st) {
            case START:         handle_START(cp);         break;
            case IN_WS:         handle_IN_WS(cp);         break;
            case IN_ID:         handle_IN_ID(cp);         break;
            case IN_NUM:        handle_IN_NUM(cp);        break;
            case IN_STR:        handle_IN_STR(cp);        break;
            case IN_CHAR:       handle_IN_CHAR(cp);       break;
            case IN_LINE_COM:   handle_IN_LINE_COM(cp);   break;
            case IN_BLOCK_COM:  handle_IN_BLOCK_COM(cp);  break;
            case IN_RAW_STR:    handle_IN_RAW_STR(cp);    break;
        }

        if (cp=='\n' || cp=='\r') {
            at_bol = true; seen_hash = false; after_include = false;
        } else if (!IsWhitespace(cp)) {
            at_bol = false;
        }
    }

    /* ----------------------------------------------------- */
    /*      START state                                      */
    /* ----------------------------------------------------- */
    void handle_START(int cp)
    {
        if (cp=='\n') { output.emit_new_line(); return; }
        if (cp=='\r') { if (peek_next()=='\n') consume_next(); output.emit_new_line(); return; }
        if (IsWhitespace(cp)) { st = IN_WS; return; }

        if (after_include && (cp=='<' || cp=='"')) { handle_header_or_string(cp); return; }

        /* ---------- RAW‑STRING PREFIXES ---------------------------- */
        if (cp=='R' && peek_next()=='"') {
            current = "R\""; consume_next(); st = IN_RAW_STR; raw_prefix_phase=true; raw_delim.clear();
            tri_state = 0;
            return;
        }
        if ((cp=='u'||cp=='U'||cp=='L') && peek_next()=='R' && peek_next2()=='"') {
            current = UTF8Encode(cp) + "R\""; consume_next(); consume_next(); st = IN_RAW_STR;
            raw_prefix_phase=true; raw_delim.clear(); tri_state=0; return;
        }
        if (cp=='u' && peek_next()=='8' && peek_next2()=='R' && peek_next3()=='"') {
            current = "u8R\""; consume_next(); consume_next(); consume_next(); st = IN_RAW_STR;
            raw_prefix_phase=true; raw_delim.clear(); tri_state=0; return;
        }

        /* ---------- ordinary prefixes, identifiers, numbers … ------ */
        if (cp=='u') {
            if (peek_next()=='8' && peek_next2()=='"') { current = "u8\""; consume_next(); consume_next(); st = IN_STR; return; }
            if (peek_next()=='"')                      { current = "u\"";  consume_next();            st = IN_STR; return; }
        }
        if (cp=='U' && peek_next()=='"') { current = "U\""; consume_next(); st = IN_STR; return; }
        if (cp=='L' && peek_next()=='"') { current = "L\""; consume_next(); st = IN_STR; return; }

        if ((cp=='u'||cp=='U'||cp=='L') && peek_next()=='\'') {
            current = UTF8Encode(cp) + '\''; consume_next(); st = IN_CHAR; return;
        }

        if (IsIdentifierStart(cp)) { current=UTF8Encode(cp); st = IN_ID; return; }
        if (IsDigit(cp))           { current=UTF8Encode(cp); st = IN_NUM; return; }

        if (cp=='.' && IsDigit(peek_next())) { current="."; st = IN_NUM; return; }

        if (cp=='"')               { current="\""; st = IN_STR; return; }
        if (cp=='\'')              { current="'"; st = IN_CHAR; return; }

        if (cp=='#') {
            seen_hash = at_bol;
            current="#";
            handle_operator_continuation();
            return;
        }

        if (cp=='/') { handle_slash(); return; }

        static const string ops="{}[]()#;:+*/%^&|~!=<>,.?-";
        if (ops.find(static_cast<char>(cp)) != string::npos) {
            current=UTF8Encode(cp); handle_operator_continuation();
        } else {
            output.emit_non_whitespace_char(UTF8Encode(cp));
        }
    }

    /* ----------------------------------------------------- */
    /*      Remaining state handlers                         */
    /* ----------------------------------------------------- */
    void handle_IN_WS(int cp)
    {
        if (IsWhitespace(cp)) return;

        if (cp=='/' && (peek_next()=='/' || peek_next()=='*'))
        {
            st = START;
            process_codepoint_direct(cp);
            return;
        }

        output.emit_whitespace_sequence();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_ID(int cp)
    {
        if (IsIdentifierContinue(cp)) { current+=UTF8Encode(cp); return; }
        emit_identifier_or_keyword();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_NUM(int cp)
    {
        if (IsDigit(cp) || cp=='.')                     { current+=UTF8Encode(cp); return; }
        if (IsIdentifierStart(cp))                      { current+=UTF8Encode(cp); return; }

        if ((cp=='e'||cp=='E') &&
            (peek_next()=='+'||peek_next()=='-'||IsDigit(peek_next())))
        {
            current+=UTF8Encode(cp);
            current+=UTF8Encode(get_next_char());       return;
        }

        if ((cp=='+'||cp=='-') &&
            !current.empty() && (current.back()=='e' || current.back()=='E'))
        { current+=UTF8Encode(cp); return; }

        output.emit_pp_number(current);
        current.clear();
        st = START;
        process_codepoint_direct(cp);
    }

    void handle_IN_STR(int cp)
    {
        if (escape_next_in_str) { current+=UTF8Encode(cp); escape_next_in_str=false; return; }
        if (cp=='\\')           { current+=UTF8Encode(cp); escape_next_in_str=true;  return; }

        current+=UTF8Encode(cp);
        if (cp=='"')           produce_string_token();
        else if (cp=='\n')     throw runtime_error("unterminated string literal");
    }

    void handle_IN_CHAR(int cp)
    {
        if (escape_next_in_char){ current+=UTF8Encode(cp); escape_next_in_char=false; return; }
        if (cp=='\\')           { current+=UTF8Encode(cp); escape_next_in_char=true;  return; }

        current+=UTF8Encode(cp);
        if (cp=='\'')         finish_char();
        else if (cp=='\n')    throw runtime_error("unterminated character literal");
    }

    void handle_IN_RAW_STR(int cp)
    {
        if (raw_prefix_phase) {
            if (cp=='(') { current+="("; raw_prefix_phase=false; }
            else {
                if (cp=='\n' || cp=='\r')                throw runtime_error("unterminated raw string");
                if (raw_delim.size()>=16)                throw runtime_error("raw string delimiter too long");
                raw_delim+=UTF8Encode(cp);
                current  +=UTF8Encode(cp);
            }
            return;
        }

        if (cp == EndOfFile) throw runtime_error("unterminated raw string");

        current+=UTF8Encode(cp);

        if (cp=='"') {
            const string term = ")" + raw_delim + "\"";
            if (current.size()>=term.size() &&
                current.compare(current.size()-term.size(),term.size(),term)==0)
            { produce_string_token(); }
        }
    }

    void handle_IN_LINE_COM(int cp)
    {
        if (cp=='\n' || cp=='\r') { output.emit_whitespace_sequence(); st=START; process_codepoint_direct(cp); }
    }
    void handle_IN_BLOCK_COM(int cp)
    {
        if (star_in_block_comment && cp=='/') { st=IN_WS; star_in_block_comment=false; }
        else { star_in_block_comment=(cp=='*'); if (cp==EndOfFile) throw runtime_error("partial comment"); }
    }

    /* ----------------------------------------------------- */
    /*      Helper routines                                  */
    /* ----------------------------------------------------- */
    void produce_string_token()
    {
        string suffix;
        if (IsIdentifierStart(peek_next())) {
            suffix += UTF8Encode(get_next_char());
            while (IsIdentifierContinue(peek_next()))
                suffix += UTF8Encode(get_next_char());
        }

        if (suffix.empty())
            output.emit_string_literal(current);
        else {
            current += suffix;
            output.emit_user_defined_string_literal(current);
        }

        current.clear();
        escape_next_in_str = false;
        st = START;
    }

    void finish_char()
    {
        string suffix;
        auto grab_suffix = [&]() {
            if (IsIdentifierStart(peek_next())) {
                suffix += UTF8Encode(get_next_char());
                while (IsIdentifierContinue(peek_next()))
                    suffix += UTF8Encode(get_next_char());
            }
        };
        grab_suffix();

        while (suffix.empty() && peek_next()==EndOfFile && utf8_buffer_pos < utf8_buffer.size()) {
            const auto more = decode_utf8_incremental();
            buf.insert(buf.end(), more.begin(), more.end());
            grab_suffix();
        }

        if (suffix.empty())
            output.emit_character_literal(current);
        else {
            current += suffix;
            output.emit_user_defined_character_literal(current);
        }

        current.clear();
        escape_next_in_char = false;
        st = START;
    }

    void emit_identifier_or_keyword()
    {
        if (Digraph_IdentifierLike_Operators.count(current))
            output.emit_preprocessing_op_or_punc(current);
        else
            output.emit_identifier(current);

        if (current=="include" && seen_hash) after_include=true;
        current.clear();
    }

    void handle_slash()
    {
        int n = peek_next();
        if (n=='/') { consume_next(); st=IN_LINE_COM; return; }
        if (n=='*') { consume_next(); st=IN_BLOCK_COM; star_in_block_comment=false; return; }
        current="/"; handle_operator_continuation();
    }

    void handle_header_or_string(int first_cp)
    {
        current = UTF8Encode(first_cp);
        int term = (first_cp=='<') ? '>' : '"';
        while (true) {
            int c = get_next_char();
            if (c==term) { current+=UTF8Encode(c); break; }
            if (c=='\n' || c==EndOfFile) throw runtime_error("unterminated header name");
            current+=UTF8Encode(c);
        }
        output.emit_header_name(current);
        current.clear();
        after_include=false;
    }

    void handle_operator_continuation()
    {
        if (current=="#" && peek_next()=='#') { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        if (current=="%" && peek_next()==':') {
            current+=UTF8Encode(get_next_char());
            if (peek_next()=='%' && peek_next2()==':') { current+=UTF8Encode(get_next_char()); current+=UTF8Encode(get_next_char()); }
            emit_punc(); return;
        }

        /* ---------- patched digraph <:: rule ------------------------ */
        if (current=="<" && peek_next()==':') {
            bool second_colon = (peek_next2()==':');
            if (!(second_colon && peek_next3()!=':' && peek_next3()!='>')) {
                current+=UTF8Encode(get_next_char());   /* produce "<:" */
                emit_punc(); return;
            }
            /* fall through → keep single '<' */
        }
        /* ------------------------------------------------------------ */

        if ((current==":" && peek_next()=='>') ||
            (current=="<" && peek_next()=='%') ||
            (current=="%" && peek_next()=='>'))
        { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        if (current==":" && peek_next()==':') { current+=UTF8Encode(get_next_char()); emit_punc(); return; }

        
        int two = peek_next();
        if (current=="." && two=='.') {
            if (peek_next2()=='.') { current+=UTF8Encode(get_next_char()); current+=UTF8Encode(get_next_char()); }
        } else if (current=="." && two=='*')     { current+=UTF8Encode(get_next_char()); }
        else if (current=="-" && two=='>') {
            current+=UTF8Encode(get_next_char()); if (peek_next()=='*') current+=UTF8Encode(get_next_char());
        } else {
            auto is_pair=[&](char a,char b){return current==string(1,a)&&two==b;};
            if (is_pair('+','+')||is_pair('+','=')||is_pair('-','-')||is_pair('-','=')||
                is_pair('*','=')||is_pair('/','=')||is_pair('%','=')||
                is_pair('^','=')||is_pair('&','=')||is_pair('|','=')||
                is_pair('=','=')||is_pair('!','=')||
                is_pair('<','=')||is_pair('>','=')||
                is_pair('&','&')||is_pair('|','|')||
                is_pair('<','<')||is_pair('>','>'))
            {
                current+=UTF8Encode(get_next_char());
                if ((current=="<<"||current==">>") && peek_next()=='=')
                    current+=UTF8Encode(get_next_char());
            }
        }
        emit_punc();
    }

    void emit_punc() { output.emit_preprocessing_op_or_punc(current); current.clear(); st=START; }

    void finish_current_token()
    {
        switch (st) {
            case IN_ID:       emit_identifier_or_keyword();                break;
            case IN_NUM:      output.emit_pp_number(current);              break;
            case IN_WS:       output.emit_whitespace_sequence();           break;
            case IN_LINE_COM: output.emit_whitespace_sequence();           break;
            case IN_BLOCK_COM:throw runtime_error("partial comment");
            case IN_STR:      throw runtime_error("unterminated string literal");
            case IN_CHAR:     throw runtime_error("unterminated character literal");
            case IN_RAW_STR:  throw runtime_error("unterminated raw string");
            default: break;
        }
        current.clear(); st = START;
    }

    /* Optimized look‑ahead helpers using inline functions */
    inline int  peek_next()  const { return (buf_pos < buf.size())     ? buf[buf_pos]   : EndOfFile; }
    inline int  peek_next2() const { return (buf_pos+1 < buf.size())   ? buf[buf_pos+1] : EndOfFile; }
    inline int  peek_next3() const { return (buf_pos+2 < buf.size())   ? buf[buf_pos+2] : EndOfFile; }
    inline int  get_next_char()    { return (buf_pos < buf.size())     ? buf[buf_pos++] : EndOfFile; }
    inline void consume_next()     { if (buf_pos < buf.size()) ++buf_pos; }

    /* data members */
    IPPTokenStream &output;
    vector<unsigned char> utf8_buffer;
    size_t                utf8_buffer_pos{0};  // Use index instead of erasing
    vector<int>           buf;
    size_t                buf_pos{0};

    int    last_cp{EndOfFile};
    string current;

    enum State { START, IN_WS, IN_ID, IN_NUM, IN_STR, IN_CHAR,
                 IN_LINE_COM, IN_BLOCK_COM, IN_RAW_STR } st{START};

    bool   after_include{false}, at_bol{true}, seen_hash{false};
    bool   star_in_block_comment{false};
    int    tri_state{0};

    bool   escape_next_in_str{false};
    bool   escape_next_in_char{false};

    string raw_delim;
    bool   raw_prefix_phase{false};
};

/* ------------------------------------------------------------------ */
/*  main                                                              */
/* ------------------------------------------------------------------ */
int main()
{
    try {
        // Use larger buffer for better I/O performance
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        // Read entire input at once for better performance
        ostringstream ss; 
        ss << cin.rdbuf();
        string input = ss.str();

        g_use_crlf = true;                /* reference output expects CR‑LF */
        g_line_ending_detected = true;

        CustomDebugPPTokenStream out;
        PPTokenizer tok(out);

        // Reserve space for expected data
        input.reserve(input.size() * 1.1);

        for (unsigned char b : input) tok.process(b);
        tok.process(EndOfFile);
        return EXIT_SUCCESS;
    }
    catch (const exception &ex) {
        cerr << "ERROR: " << ex.what() << '\n';
        return EXIT_FAILURE;
    }
}

Correctness Test Result

$ make test
g++ -g -std=gnu++11 -Wall -o pptoken pptoken.cpp
scripts/run_all_tests.pl pptoken my
Running tests/100-a.t...
Running tests/100-character-literals.t...
Running tests/100-comments.t...
Running tests/100-empty.t...
Running tests/100-example.t...
Running tests/100-floating.t...
Running tests/100-line-splice.t...
Running tests/100-partial-comment.t...
Running tests/100-partial-string-literal.t...
Running tests/100-preprocessing-op-or-punc.t...
Running tests/100-raw-string-literal.t...
Running tests/100-string-literals.t...
Running tests/100-trigraphs.t...
Running tests/100-universal-character-name.t...
Running tests/100-utf8.t...
Running tests/150-ud-character-literals.t...
Running tests/150-ud-string-literals.t...
Running tests/200-charname-allowed.t...
Running tests/200-escape-sequence.t...
Running tests/200-header-name.t...
Running tests/200-trigraphs.t...
Running tests/250-dot2-ppnum.t...
Running tests/300-quote-strange.t...
Running tests/300-ucn-trigraph-ordering.t...
Running tests/300-utf8-ff.t...
Running tests/400-angle-colon-madness.t...
Running tests/500-isspace-code-point-wrong.t...
Running tests/900-real-world.t...
scripts/compare_results.pl ref my
tests/100-a.t: PASS
tests/100-character-literals.t: PASS
tests/100-comments.t: PASS
tests/100-empty.t: PASS
tests/100-example.t: PASS
tests/100-floating.t: PASS
tests/100-line-splice.t: PASS
tests/100-partial-comment.t: PASS
tests/100-partial-string-literal.t: PASS
tests/100-preprocessing-op-or-punc.t: PASS
tests/100-raw-string-literal.t: PASS
tests/100-string-literals.t: PASS
tests/100-trigraphs.t: PASS
tests/100-universal-character-name.t: PASS
tests/100-utf8.t: PASS
tests/150-ud-character-literals.t: PASS
tests/150-ud-string-literals.t: PASS
tests/200-charname-allowed.t: PASS
tests/200-escape-sequence.t: PASS
tests/200-header-name.t: PASS
tests/200-trigraphs.t: PASS
tests/250-dot2-ppnum.t: PASS
tests/300-quote-strange.t: PASS
tests/300-ucn-trigraph-ordering.t: PASS
tests/300-utf8-ff.t: PASS
tests/400-angle-colon-madness.t: PASS
tests/500-isspace-code-point-wrong.t: PASS
tests/900-real-world.t: PASS
ALL TESTS PASS

Regression Test Result


$ ./regression_test.sh
=== C++ Preprocessor Tokenizer Regression Test Suite ===
Testing optimized implementation against reference output

Running tests...

✓ 100-a
✓ 100-character-literals
✓ 100-comments
✓ 100-empty
✓ 100-example
✓ 100-floating
✓ 100-line-splice
✓ 100-partial-comment
✓ 100-partial-string-literal
✓ 100-preprocessing-op-or-punc
✓ 100-raw-string-literal
✓ 100-string-literals
✓ 100-trigraphs
✓ 100-universal-character-name
✓ 100-utf8
✓ 150-ud-character-literals
✓ 150-ud-string-literals
✓ 200-charname-allowed
✓ 200-escape-sequence
✓ 200-header-name
✓ 200-trigraphs
✓ 250-dot2-ppnum
✓ 300-quote-strange
✓ 300-ucn-trigraph-ordering
✓ 300-utf8-ff
✓ 400-angle-colon-madness
✓ 500-isspace-code-point-wrong
✓ 900-real-world

=== Test Summary ===
Total tests: 28
Passed: 28
Failed: 0
Skipped: 0

=== Performance Comparison ===
Running quick performance test...
Original version: .295039773s
Optimized version: .198469346s
Speedup: 1.48x

All tests passed!

Visualize Results


$ python3 ./visualize_results.py
[✓] tests/100-a.t                           15.41 ms  →     16.89 ms     0.91×
[✓] tests/100-character-literals.t          16.14 ms  →     12.90 ms     1.25×
[✓] tests/100-comments.t                    15.47 ms  →     14.96 ms     1.03×
[✓] tests/100-empty.t                       14.70 ms  →     13.77 ms     1.07×
[✓] tests/100-example.t                     15.98 ms  →     12.67 ms     1.26×
[✓] tests/100-floating.t                    13.05 ms  →     12.38 ms     1.05×
[✓] tests/100-line-splice.t                 13.83 ms  →     11.04 ms     1.25×
[✓] tests/100-partial-comment.t             13.20 ms  →     11.23 ms     1.17×
[✓] tests/100-partial-string-literal.t      13.20 ms  →      8.07 ms     1.64×
[✓] tests/100-preprocessing-op-or-punc.t     10.97 ms  →     12.73 ms     0.86×
[✓] tests/100-raw-string-literal.t          13.98 ms  →     10.35 ms     1.35×
[✓] tests/100-string-literals.t             14.49 ms  →     11.85 ms     1.22×
[✓] tests/100-trigraphs.t                   15.88 ms  →     14.52 ms     1.09×
[✓] tests/100-universal-character-name.t     19.73 ms  →     13.31 ms     1.48×
[✓] tests/100-utf8.t                        11.36 ms  →      9.89 ms     1.15×
[✓] tests/150-ud-character-literals.t       11.37 ms  →      9.66 ms     1.18×
[✓] tests/150-ud-string-literals.t          35.94 ms  →     26.80 ms     1.34×
[✓] tests/200-charname-allowed.t            25.86 ms  →      8.98 ms     2.88×
[✓] tests/200-escape-sequence.t              8.48 ms  →      8.08 ms     1.05×
[✓] tests/200-header-name.t                 10.41 ms  →      9.60 ms     1.08×
[✓] tests/200-trigraphs.t                   11.88 ms  →     10.47 ms     1.14×
[✓] tests/250-dot2-ppnum.t                  11.19 ms  →      8.49 ms     1.32×
[✓] tests/300-quote-strange.t               11.27 ms  →      9.40 ms     1.20×
[✓] tests/300-ucn-trigraph-ordering.t        9.57 ms  →      9.16 ms     1.05×
[✓] tests/300-utf8-ff.t                     12.84 ms  →      9.71 ms     1.32×
[✓] tests/400-angle-colon-madness.t         10.73 ms  →      9.22 ms     1.16×
[✓] tests/500-isspace-code-point-wrong.t      9.53 ms  →      8.62 ms     1.11×
[✓] tests/900-real-world.t                  19.88 ms  →     14.84 ms     1.34×

=== Overall Performance ===
Total original time:  406.4 ms
Total optimized time: 329.6 ms
Overall speed‑up:     1.23×
Time saved:           76.7 ms

=== Performance Speed‑up Chart ===
200-charname-allowed.t          2.88x ██████████████████████████████████████████████████
100-partial-string-literal.t    1.64x ████████████████████████████
100-universal-character-name.t  1.48x █████████████████████████
100-raw-string-literal.t        1.35x ███████████████████████
150-ud-string-literals.t        1.34x ███████████████████████
900-real-world.t                1.34x ███████████████████████
300-utf8-ff.t                   1.32x ██████████████████████
250-dot2-ppnum.t                1.32x ██████████████████████
100-example.t                   1.26x █████████████████████
100-line-splice.t               1.25x █████████████████████
100-character-literals.t        1.25x █████████████████████
100-string-literals.t           1.22x █████████████████████
300-quote-strange.t             1.20x ████████████████████
150-ud-character-literals.t     1.18x ████████████████████
100-partial-comment.t           1.17x ████████████████████
400-angle-colon-madness.t       1.16x ████████████████████
100-utf8.t                      1.15x ███████████████████
200-trigraphs.t                 1.14x ███████████████████
500-isspace-code-point-wrong.t  1.11x ███████████████████
100-trigraphs.t                 1.09x ██████████████████
200-header-name.t               1.08x ██████████████████
100-empty.t                     1.07x ██████████████████
100-floating.t                  1.05x ██████████████████
200-escape-sequence.t           1.05x ██████████████████
300-ucn-trigraph-ordering.t     1.05x ██████████████████
100-comments.t                  1.03x █████████████████
100-a.t                         0.91x ███████████████
100-preprocessing-op-or-punc.t  0.86x ██████████████

=== Performance by Category ===
Basic            15 tests   Original:   217.4 ms   Optimized:   186.6 ms   Speed‑up:  1.17×
Intermediate      7 tests   Original:   115.2 ms   Optimized:    82.1 ms   Speed‑up:  1.40×
Advanced          5 tests   Original:    53.9 ms   Optimized:    46.1 ms   Speed‑up:  1.17×
Real-world        1 tests   Original:    19.9 ms   Optimized:    14.8 ms   Speed‑up:  1.34×
HTML report written to performance_report.html
Results written to performance_results.json

This completes the comprehensive technical documentation for the C++ Preprocessor Tokenizer implementation.



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • CY86→x86-64 Translator: Complete Implementation with Performance Optimizations, From Zero to Working Compiler
  • Lock-Free Queues with Advanced Memory Reclamation: A Deep Dive into Epoch-Based Reclamation and Hazard Pointers
  • From 245s to 0.37s: Optimizing an MPI Traveling Salesman Solver
  • Real-Time Cryptocurrency Trade Correlation Engine: A High-Performance C++ Implementation
  • From 0.37x to 18.7x: Building a High-Performance SIMD Library with AVX-512 Speedups in Data Science, Inference, & HPC Workloads