Эффективные парсеры и токенизаторы строк на C#

enum State { Initial, Sign, Integer, Fraction, Exponent }
 
State state = State.Initial;
foreach (char c in input)
{
    switch (state)
    {
        case State.Initial:
            if (c == '-' || c == '+')
                state = State.Sign;
            else if (char.IsDigit(c))
                state = State.Integer;
            else
                throw new FormatException();
            break;
        // другие состояния
    }
}

public class Token
{
    public TokenType Type { get; }
    public string Value { get; }
    
    public Token(TokenType type, string value)
    {
        Type = type;
        Value = value;
    }
}
 
public class Tokenizer
{
    private readonly string _input;
    private int _position;
    
    public Tokenizer(string input)
    {
        _input = input;
        _position = 0;
    }
    
    public Token NextToken()
    {
        if (_position >= _input.Length)
            return null; // Конец ввода
            
        char c = _input[_position];
        
        // Распознавание токенов
        if (char.IsWhiteSpace(c))
        {
            return ReadWhitespace();
        }
        else if (char.IsLetter(c))
        {
            return ReadIdentifier();
        }
        // Другие типы токенов
        
        // Если символ не распознан
        _position++;
        return new Token(TokenType.Unknown, c.ToString());
    }
    
    // Методы для чтения конкретных типов токенов
}

   +
  / \
 2   *
    / \
   3   4

abstract class ExpressionNode { }
 
class BinaryOperationNode : ExpressionNode
{
    public ExpressionNode Left { get; }
    public ExpressionNode Right { get; }
    public string Operator { get; }
    
    // Конструктор и методы
}
 
class NumberNode : ExpressionNode
{
    public double Value { get; }
    
    // Конструктор и методы
}

A -> B -> D
|    |
v    v
C <- E

class TokenNode
{
    public Token Token { get; }
    public List<TokenNode> Dependencies { get; } = new List<TokenNode>();
    
    // Методы для управления зависимостями
}

E → E + T | E - T | T
T → T * F | T / F | F
F → (E) | digit

E → T E'
E' → + T E' | - T E' | ε
T → F T'
T' → * F T' | / F T' | ε
F → (E) | digit

// Пример использования библиотеки парсер-комбинаторов
var digit = Parse.Digit.AtLeastOnce().Text().Select(int.Parse);
var add = Parse.Char('+').Token();
var expr = from left in digit
          from op in add
          from right in digit
          select new { Left = left, Right = right, Op = "+" };

string input = "яблоко,груша,апельсин";
string[] fruits = input.Split(',');
// результат: ["яблоко", "груша", "апельсин"]

string input = "яблоко,,груша, ,апельсин";
string[] fruits = input.Split(new[] { ',', ' ' }, 
    StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
// результат: ["яблоко", "груша", "апельсин"]

string code = "var x = 10; // задаем переменную";
var tokens = Regex.Matches(code, @"(\w+)|([=;])|(\d+)|(//.*)");
 
foreach (Match match in tokens)
{
    if (match.Success)
        Console.WriteLine(match.Value);
}

private static readonly Regex TokenPattern = new Regex(
    @"(\w+)|([=;])|(\d+)|(//.*))", 
    RegexOptions.Compiled
);

// Неэффективно: создаёт много промежуточных строк
string result = "";
for (int i = 0; i < 10000; i++)
    result += i.ToString();
 
// Эффективно: изменяет буфер без создания промежуточных строк
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++)
    sb.Append(i);
string result = sb.ToString();

using (StreamReader reader = new StreamReader("bigfile.txt"))
{
    string line;
    while ((line = reader.ReadLine()) != null)
    {
        // Обработка строки без загрузки всего файла в память
        ProcessLine(line);
    }
}

string text = "Парсинг строк в C# может быть очень эффективным";
 
// Работа с подстрокой без выделения памяти
ReadOnlySpan<char> span = text.AsSpan();
ReadOnlySpan<char> word = span.Slice(0, 7); // "Парсинг"
 
// Поиск в Span
int spaceIndex = span.IndexOf(' ');

public struct SpanTokenizer
{
    private ReadOnlySpan<char> _remaining;
    private readonly char[] _separators;
 
    public SpanTokenizer(ReadOnlySpan<char> text, char[] separators)
    {
        _remaining = text;
        _separators = separators;
    }
 
    public bool MoveNext(out ReadOnlySpan<char> token)
    {
        if (_remaining.IsEmpty)
        {
            token = default;
            return false;
        }
 
        int separatorIndex = _remaining.IndexOfAny(_separators);
        
        if (separatorIndex < 0)
        {
            token = _remaining;
            _remaining = default;
            return true;
        }
 
        token = _remaining.Slice(0, separatorIndex);
        _remaining = _remaining.Slice(separatorIndex + 1);
        return true;
    }
}

string input = "hello,world,from,c#";
var tokenizer = new SpanTokenizer(input.AsSpan(), new[] { ',' });
 
while (tokenizer.MoveNext(out var token))
{
    Console.WriteLine(token.ToString());
}

public enum TokenType { Identifier, Number, Operator, Symbol, Whitespace, Unknown }
 
public class Token
{
    public TokenType Type { get; }
    public string Value { get; }
 
    public Token(TokenType type, string value)
    {
        Type = type;
        Value = value;
    }
}
 
public class Tokenizer
{
    private readonly string _input;
    private int _position;
 
    public Tokenizer(string input)
    {
        _input = input;
        _position = 0;
    }
 
    private char CurrentChar => _position < _input.Length ? _input[_position] : '\0';
    private void Advance() => _position++;
 
    public List<Token> Tokenize()
    {
        List<Token> tokens = new List<Token>();
 
        while (_position < _input.Length)
        {
            char c = CurrentChar;
 
            if (char.IsWhiteSpace(c))
            {
                tokens.Add(new Token(TokenType.Whitespace, c.ToString()));
                Advance();
            }
            else if (char.IsLetter(c))
            {
                tokens.Add(ReadIdentifier());
            }
            else if (char.IsDigit(c))
            {
                tokens.Add(ReadNumber());
            }
            else if ("+-*/=;".Contains(c))
            {
                tokens.Add(new Token(TokenType.Operator, c.ToString()));
                Advance();
            }
            else
            {
                tokens.Add(new Token(TokenType.Unknown, c.ToString()));
                Advance();
            }
        }
 
        return tokens;
    }
 
    private Token ReadIdentifier()
    {
        StringBuilder sb = new StringBuilder();
        while (_position < _input.Length && char.IsLetterOrDigit(CurrentChar))
        {
            sb.Append(CurrentChar);
            Advance();
        }
        return new Token(TokenType.Identifier, sb.ToString());
    }
 
    private Token ReadNumber()
    {
        StringBuilder sb = new StringBuilder();
        while (_position < _input.Length && char.IsDigit(CurrentChar))
        {
            sb.Append(CurrentChar);
            Advance();
        }
        return new Token(TokenType.Number, sb.ToString());
    }
}

private Token ReadString()
{
    StringBuilder sb = new StringBuilder();
    Advance(); // Пропускаем открывающую кавычку
 
    while (_position < _input.Length && CurrentChar != '"')
    {
        if (CurrentChar == '\\' && _position + 1 < _input.Length)
        {
            Advance(); // Пропускаем обратный слеш для экранированных символов
        }
        sb.Append(CurrentChar);
        Advance();
    }
 
    if (_position < _input.Length) 
        Advance(); // Пропускаем закрывающую кавычку
 
    return new Token(TokenType.String, sb.ToString());
}

string input = "var x = 42 + 8;";
Tokenizer tokenizer = new Tokenizer(input);
var tokens = tokenizer.Tokenize();
 
foreach (var token in tokens)
{
    Console.WriteLine($"{token.Type}: {token.Value}");
}

public class TokenPool
{
    private readonly Queue<Token> _pool = new Queue<Token>();
    private readonly int _maxPoolSize;
 
    public TokenPool(int maxPoolSize = 1000)
    {
        _maxPoolSize = maxPoolSize;
    }
 
    public Token GetToken(TokenType type, string value)
    {
        if (_pool.Count > 0)
        {
            var token = _pool.Dequeue();
            token.Reset(type, value);  // Метод для сброса свойств
            return token;
        }
        return new Token(type, value);
    }
 
    public void ReturnToken(Token token)
    {
        if (_pool.Count < _maxPoolSize)
            _pool.Enqueue(token);
    }
}

public class Token
{
    public TokenType Type { get; private set; }
    public string Value { get; private set; }
 
    public Token(TokenType type, string value)
    {
        Type = type;
        Value = value;
    }
 
    internal void Reset(TokenType type, string value)
    {
        Type = type;
        Value = value;
    }
}

// Без интернирования: две разные ссылки на одинаковые строки
string s1 = new string(new[] { 'H', 'e', 'l', 'l', 'o' });
string s2 = new string(new[] { 'H', 'e', 'l', 'l', 'o' });
bool areRefEqual = object.ReferenceEquals(s1, s2);  // false
 
// С интернированием: одна ссылка на уникальную строку
string i1 = string.Intern(s1);
string i2 = string.Intern(s2);
bool areInternedRefEqual = object.ReferenceEquals(i1, i2);  // true

public bool IsValidCharacter(string text, int index)
{
    if (index < text.Length && char.IsHighSurrogate(text[index]))
    {
        // Проверяем, что за высоким суррогатом следует низкий
        return index + 1 < text.Length && char.IsLowSurrogate(text[index + 1]);
    }
    return true;
}
 
public ReadOnlySpan<char> GetCharacterAt(ReadOnlySpan<char> text, int index)
{
    if (index < text.Length && char.IsHighSurrogate(text[index]) && 
        index + 1 < text.Length && char.IsLowSurrogate(text[index + 1]))
    {
        return text.Slice(index, 2);  // Возвращаем пару символов
    }
    return text.Slice(index, 1);
}

// "é" может быть представлен как один символ или как "e" + акцент
string s1 = "\u00E9";  // Предварительно составленная форма
string s2 = "\u0065\u0301";  // Разложенная форма
 
bool areEqual = s1 == s2;  // false, разное представление
bool areNormalizedEqual = s1.Normalize() == s2.Normalize();  // true

public interface ITokenRecognizer
{
    bool TryRecognize(string input, int position, out Token token, out int newPosition);
}
 
public class NumberRecognizer : ITokenRecognizer
{
    public bool TryRecognize(string input, int position, out Token token, out int newPosition)
    {
        // Логика распознавания чисел
        // ...
    }
}
 
public class Tokenizer
{
    private readonly List<ITokenRecognizer> _recognizers = new List<ITokenRecognizer>();
    
    public void AddRecognizer(ITokenRecognizer recognizer)
    {
        _recognizers.Add(recognizer);
    }
    
    public List<Token> Tokenize(string input)
    {
        // Используем все распознаватели для токенизации
        // ...
    }
}

public class CompositeRecognizer : ITokenRecognizer
{
    private readonly List<ITokenRecognizer> _children = new List<ITokenRecognizer>();
    
    public void Add(ITokenRecognizer recognizer)
    {
        _children.Add(recognizer);
    }
    
    public bool TryRecognize(string input, int position, out Token token, out int newPosition)
    {
        foreach (var recognizer in _children)
        {
            if (recognizer.TryRecognize(input, position, out token, out newPosition))
                return true;
        }
        
        token = null;
        newPosition = position;
        return false;
    }
}

public abstract class TokenizerHandler
{
    protected TokenizerHandler _successor;
    
    public void SetSuccessor(TokenizerHandler successor)
    {
        _successor = successor;
    }
    
    public abstract bool TryHandle(string input, int position, out Token token, out int newPosition);
}
 
public class WhitespaceHandler : TokenizerHandler
{
    public override bool TryHandle(string input, int position, out Token token, out int newPosition)
    {
        if (position < input.Length && char.IsWhiteSpace(input[position]))
        {
            // Обработка пробелов
            // ...
            return true;
        }
        
        if (_successor != null)
            return _successor.TryHandle(input, position, out token, out newPosition);
            
        token = null;
        newPosition = position;
        return false;
    }
}

public IEnumerable<string[]> ParseCsv(string csvContent, char separator = ',')
{
    int position = 0;
    while (position < csvContent.Length)
    {
        yield return ParseCsvLine(csvContent, ref position, separator);
        
        // Пропускаем разделитель строк
        if (position < csvContent.Length && csvContent[position] == '\n')
            position++;
        if (position > 0 && position < csvContent.Length && 
            csvContent[position - 1] == '\r' && csvContent[position] == '\n')
            position++;
    }
}
 
private string[] ParseCsvLine(string csvContent, ref int position, char separator)
{
    List<string> fields = new List<string>();
    StringBuilder currentField = new StringBuilder();
    bool inQuotes = false;
    
    while (position < csvContent.Length && csvContent[position] != '\r' && csvContent[position] != '\n')
    {
        char currentChar = csvContent[position++];
        
        if (currentChar == '"')
        {
            // Проверяем на экранированную кавычку (двойная кавычка)
            if (position < csvContent.Length && csvContent[position] == '"')
            {
                currentField.Append('"');
                position++;
            }
            else
            {
                inQuotes = !inQuotes;
            }
        }
        else if (currentChar == separator && !inQuotes)
        {
            fields.Add(currentField.ToString());
            currentField.Clear();
        }
        else
        {
            currentField.Append(currentChar);
        }
    }
    
    fields.Add(currentField.ToString());
    return fields.ToArray();
}

enum JsonTokenType { BeginObject, EndObject, BeginArray, EndArray, 
                     PropertyName, StringValue, NumberValue, 
                     BooleanValue, NullValue, Colon, Comma }
 
enum JsonParserState { Initial, InObject, InArray, AfterPropertyName, 
                       AfterValue, AfterArrayElement }
 
public class JsonParser
{
    // Реализация парсера на основе конечного автомата
    // ...
}

// Опасное регулярное выражение с потенциальной проблемой производительности
Regex.IsMatch("аааааааааааааааааааб", @"(a+)+b");
// На длинных последовательностях может работать экстремально долго

private static readonly Regex SimplePattern = new Regex(@"\w+|\d+|[+\-*/()]", RegexOptions.Compiled);
 
public List<Token> HighLevelTokenize(string input)
{
    var matches = SimplePattern.Matches(input);
    List<Token> tokens = new List<Token>();
    
    foreach (Match match in matches)
    {
        // Дополнительная обработка конкретных токенов
        if (decimal.TryParse(match.Value, out _))
            tokens.Add(new Token(TokenType.Number, match.Value));
        else if ("+-*/()".Contains(match.Value))
            tokens.Add(new Token(TokenType.Operator, match.Value));
        else
            tokens.Add(new Token(TokenType.Identifier, match.Value));
    }
    
    return tokens;
}

public class IncrementalJsonParser
{
    private readonly StringBuilder _buffer = new StringBuilder();
    private int _openBraces;
    private bool _inString;
    private bool _escaped;
    
    public IEnumerable<string> ParseChunk(string chunk)
    {
        _buffer.Append(chunk);
        
        int startPos = 0;
        for (int i = 0; i < _buffer.Length; i++)
        {
            char c = _buffer[i];
            
            if (_inString)
            {
                if (_escaped)
                {
                    _escaped = false;
                }
                else if (c == '\\')
                {
                    _escaped = true;
                }
                else if (c == '"')
                {
                    _inString = false;
                }
            }
            else if (c == '"')
            {
                _inString = true;
            }
            else if (c == '{')
            {
                _openBraces++;
            }
            else if (c == '}')
            {
                _openBraces--;
                
                if (_openBraces == 0)
                {
                    // Нашли полный объект JSON
                    string jsonObject = _buffer.ToString(startPos, i - startPos + 1);
                    yield return jsonObject;
                    startPos = i + 1;
                }
            }
        }
        
        // Удаляем обработанные данные из буфера
        if (startPos > 0)
        {
            _buffer.Remove(0, startPos);
        }
    }
}

public List<Token> ParallelTokenize(string input, int chunkSize = 10000)
{
    if (input.Length <= chunkSize)
        return Tokenize(input);
    
    // Разбиваем входную строку на части
    int chunkCount = (input.Length + chunkSize - 1) / chunkSize;
    var chunkedResults = new List<Token>[chunkCount];
    
    Parallel.For(0, chunkCount, i =>
    {
        int start = i * chunkSize;
        int length = Math.Min(chunkSize, input.Length - start);
        string chunk = input.Substring(start, length);
        
        // Здесь мы просто токенизируем каждый фрагмент отдельно
        chunkedResults[i] = Tokenize(chunk);
    });
    
    // Объединяем результаты (может потребовать дополнительной обработки граничных случаев)
    return chunkedResults.SelectMany(tokens => tokens).ToList();
}

// Простой DSL для описания грамматики арифметических выражений
var number = Rule.Pattern(@"\d+").Transform(s => double.Parse(s));
var plus = Rule.Literal("+");
var minus = Rule.Literal("-");
var multiply = Rule.Literal("*");
var divide = Rule.Literal("/");
var lparen = Rule.Literal("(");
var rparen = Rule.Literal(")");
 
// Определяем правила рекурсивно
var expr = Rule.Deferred<double>();
var factor = Rule.Deferred<double>();
var term = Rule.Deferred<double>();
 
expr.Define(
    from t in term
    from op in plus.Or(minus).Optional()
    from e in expr.Optional()
    select op.HasValue && e.HasValue
        ? (op.Value == "+" ? t + e.Value : t - e.Value)
        : t
);
 
factor.Define(
    number
    .Or(from _ in lparen
        from e in expr
        from __ in rparen
        select e)
);
 
term.Define(
    from f in factor
    from op in multiply.Or(divide).Optional()
    from t in term.Optional()
    select op.HasValue && t.HasValue
        ? (op.Value == "*" ? f * t.Value : f / t.Value)
        : f
);
 
// Использование парсера
double result = expr.Parse("2 + 3 * 4");  // 14

public ref struct HighPerformanceTokenizer
{
    private ReadOnlySpan<char> _text;
 
    public HighPerformanceTokenizer(ReadOnlySpan<char> text)
    {
        _text = text;
    }
 
    public bool TryReadToken(out TokenType type, out ReadOnlySpan<char> value)
    {
        // Пропускаем пробелы
        int index = 0;
        while (index < _text.Length && char.IsWhiteSpace(_text[index]))
            index++;
 
        if (index == _text.Length)
        {
            type = TokenType.Unknown;
            value = default;
            return false;
        }
 
        // Определяем тип токена
        char c = _text[index];
        if (char.IsLetter(c))
        {
            // Идентификатор
            int start = index;
            while (index < _text.Length && char.IsLetterOrDigit(_text[index]))
                index++;
 
            type = TokenType.Identifier;
            value = _text.Slice(start, index - start);
            _text = _text.Slice(index);
            return true;
        }
        
        // Другие типы токенов...
        
        type = TokenType.Unknown;
        value = _text.Slice(index, 1);
        _text = _text.Slice(index + 1);
        return true;
    }
}

// Пример использования SIMD
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
 
public bool ContainsDigit(ReadOnlySpan<char> text)
{
    if (Sse2.IsSupported && text.Length >= Vector128<ushort>.Count)
    {
        Vector128<ushort> zero = Vector128<ushort>.Zero;
        Vector128<ushort> nine = Vector128.Create((ushort)'9');
        
        for (int i = 0; i <= text.Length - Vector128<ushort>.Count; i += Vector128<ushort>.Count)
        {
            Vector128<ushort> chunk = Vector128.LoadUnsafe(ref Unsafe.As<char, ushort>(ref Unsafe.AsRef(text[i])));
            Vector128<ushort> ltZero = Sse2.CompareLessThan(chunk, Vector128.Create((ushort)'0'));
            Vector128<ushort> gtNine = Sse2.CompareGreaterThan(chunk, nine);
            Vector128<ushort> notDigit = Sse2.Or(ltZero, gtNine);
            
            if (Sse2.MoveMask(notDigit.AsByte()) != 0xFFFF)
                return true;
        }
        
        // Обработка оставшихся символов
    }
    
    // Fallback для маленьких последовательностей или платформ без SSE2
    foreach (char c in text)
    {
        if (c >= '0' && c <= '9')
            return true;
    }
    
    return false;
}

public ref struct CsvRowParser
{
    private ReadOnlySpan<char> _line;
    private readonly char _delimiter;
    
    public CsvRowParser(ReadOnlySpan<char> line, char delimiter = ',')
    {
        _line = line;
        _delimiter = delimiter;
    }
    
    public bool TryGetNextField(out ReadOnlySpan<char> field)
    {
        if (_line.IsEmpty)
        {
            field = default;
            return false;
        }
        
        bool inQuotes = false;
        int start = 0;
        int i;
        
        for (i = 0; i < _line.Length; i++)
        {
            char c = _line[i];
            
            if (c == '"')
            {
                if (inQuotes && i + 1 < _line.Length && _line[i + 1] == '"')
                {
                    // Экранированная кавычка внутри кавычек
                    i++;
                }
                else
                {
                    inQuotes = !inQuotes;
                }
            }
            else if (c == _delimiter && !inQuotes)
            {
                break;
            }
        }
        
        field = _line.Slice(start, i - start);
        
        if (i < _line.Length)
            _line = _line.Slice(i + 1);
        else
            _line = ReadOnlySpan<char>.Empty;
            
        return true;
    }
}

// Пример использования ML.NET для классификации токенов
public class MlTokenClassifier
{
    private PredictionEngine<TokenFeature, TokenPrediction> _predictor;
    
    // Инициализация модели и настройка предиктора
    
    public TokenType ClassifyToken(string tokenValue, TokenContext context)
    {
        var features = new TokenFeature
        {
            Value = tokenValue,
            PreviousToken = context.PreviousToken,
            Position = context.Position
            // Другие признаки
        };
        
        var prediction = _predictor.Predict(features);
        return prediction.PredictedType;
    }
}