← Назад

Архитектура

Общая архитектура

SynLex построен на принципах модульности и расширяемости. Каждый компонент решает одну задачу и может быть заменён пользовательской реализацией.

Конвейер обработки

┌─────────────────┐
│  Исходный текст │
│    (String)     │
└────────┬────────┘
         │
         ↓
    ┌────────┐
    │ Lexer  │ ← ILexerRule[]
    └────┬───┘
         │
         ↓
┌────────────────┐
│  Token Stream  │
│   (Token[])    │
└────────┬───────┘
         │
         ↓
    ┌────────┐
    │ Parser │ ← IParserRule[]
    └────┬───┘
         │
         ↓
┌────────────────┐
│      AST       │
│ (AbstractSynt  │
│  axTree)       │
└────────┬───────┘
         │
         ↓
  ┌──────────────┐
  │ Evaluator<T> │ ← IEvaluatorRule<T>[]
  └──────┬───────┘
         │
         ↓
┌────────────────┐
│  Результат T   │
└────────────────┘

Компонент: Lexer

Назначение

Преобразует текстовый поток в последовательность токенов с сохранением информации о позиции.

Ключевые классы

Lexer

• Хранит список правил (ILexerRule[])
• Последовательно применяет правила к каждой позиции
• Отслеживает строки и столбцы для TextPosition
• Возвращает LexerResult с токенами или ошибками

Token

public readonly struct Token(string content, int type, TextPosition position)
{
    public string Content { get; }
    public int Type { get; }
    public TextPosition Position { get; }
}

TextPosition

public readonly struct TextPosition(int line, int column)
{
    public int Line { get; }
    public int Column { get; }
}

ILexerRule интерфейс

public interface ILexerRule
{
    (int shift, Token? token) Apply(
        string content, 
        int position, 
        Dictionary<string, object> context
    );
}

• shift: количество символов для сдвига позиции
• token: распознанный токен или null
• context: пользовательский контекст для хранения состояния

Встроенные правила

SimpleSublineLexerRule

• Использует Trie для быстрого поиска
• Находит самое длинное совпадение из списка вариантов
• Идеален для ключевых слов и операторов

RegexLexerRule (в CommonLexerRules)

• Применяет регулярное выражение
• Поддерживает сложные паттерны
• Подходит для чисел, идентификаторов, строк

Компонент: Parser

Назначение

Строит иерархическое AST из плоского потока токенов с поддержкой backtracking.

Ключевые классы

Parser

• Хранит правила парсинга (IParserRule[])
• Поддерживает backtracking при неудаче
• Может возвращать множество вариантов AST (EnableVariants = true)

ParserContext

public class ParserContext
{
    public int Position { get; set; }
    public List<string> Errors { get; }
    public Dictionary<string, object> UserContext { get; }
    
    public Token? CurrentToken(IReadOnlyList<Token> tokens);
    public void Advance();
    public void AddError(string message);
    public ParserContext Clone(); // для backtracking
}

AbstractSyntaxTree

public class AbstractSyntaxTree(Token token, params AbstractSyntaxTree[] branches)
{
    public Token Token { get; }
    public ICollection<AbstractSyntaxTree> Branches { get; }
}

IParserRule интерфейс

public interface IParserRule
{
    bool StopOnMatch => false; // блокирует дальнейший перебор
    
    (Token? token, List<(int minIndex, int maxIndex)> subsets) Apply(
        IReadOnlyList<Token> tokens, 
        ParserContext context
    );
}

• token: синтаксический токен (тип узла AST)
• subsets: диапазоны для рекурсивного парсинга подвыражений

Алгоритм парсинга

1. Пробуем каждое правило в порядке добавления
2. При успехе: обрабатываем subsets рекурсивно
3. При неудаче: восстанавливаем позицию (backtracking) и пробуем следующее
4. Если EnableVariants = true: собираем все успешные варианты
5. Иначе: возвращаем первый успешный вариант

Компонент: Evaluator

Назначение

Преобразует AST в конечный результат типа T через систему правил.

Ключевые классы

Evaluator

• Хранит правила компиляции (IEvaluatorRule<T>[])
• Рекурсивно обходит AST снизу вверх
• Может генерировать множество результатов (EnableVariants = true)

EvaluatorContext

public class EvaluatorContext
{
    public Dictionary<string, object> UserContext { get; }
    public List<object> CompiledBranches { get; set; } // результаты подузлов
}

IEvaluatorRule интерфейс

public interface IEvaluatorRule<T>
{
    CompilerRuleResult<T> Apply(
        AbstractSyntaxTree ast, 
        EvaluatorContext context
    );
}

CompilerRuleResult

public readonly struct CompilerRuleResult<T>(bool success, T value)
{
    public bool Success { get; }
    public T Value { get; }
}

Алгоритм компиляции

1. Компилируем все дочерние узлы (branches) рекурсивно
2. Помещаем результаты в context.CompiledBranches
3. Применяем правила к текущему узлу
4. При EnableVariants = true: генерируем все комбинации

Компонент: VirtualMachine

Назначение

Выполнение байт-кода с настраиваемыми инструкциями.

Ключевые классы

VirtualMachine

• Интерпретатор инструкций
• Управляет стеком и переменными
• Применяет правила выполнения

VMExecutionContext

public class VMExecutionContext
{
    public int InstructionPointer { get; set; }
    public Stack<object> Stack { get; }
    public Dictionary<string, object> Variables { get; }
    public List<Instruction> Code { get; set; }
}

Instruction

public record Instruction(OpCode OpCode, params object[] Operands);

IVMExecutionRule интерфейс

public interface IVMExecutionRule
{
    bool CanExecute(Instruction instruction);
    VMExecutionResult Execute(Instruction instruction, VMExecutionContext context);
}

Утилиты

Trie (префиксное дерево)

Используется в SimpleSublineLexerRule для эффективного поиска ключевых слов:

var trie = new Trie()
    .Add("if")
    .Add("else")
    .Add("while");

int depth = trie.ContainStartMaxDepth("if (x > 0)"); // 2

Алгоритм:

• O(m) для добавления строки длины m
• O(n) для поиска в тексте длины n
• Минимальное потребление памяти через общие префиксы

Паттерны проектирования

Fluent API

Все компоненты поддерживают цепочку вызовов:

var lexer = new Lexer()
    .AddRule(rule1)
    .AddRule(rule2)
    .AddRule(rule3);

Result Pattern

Вместо исключений возвращаются результаты с флагом успеха:

var result = lexer.Analyze(text);
if (!result.IsSuccess)
{
    foreach (var error in result.Errors)
        Console.WriteLine(error);
}

Visitor Pattern (косвенно)

Evaluator обходит AST снизу вверх, применяя правила к каждому узлу.

Strategy Pattern

Правила (ILexerRule, IParserRule, IEvaluatorRule) - это стратегии обработки.

Расширяемость

Создание собственных правил

Лексер:

public class CustomLexerRule : ILexerRule
{
    public (int shift, Token? token) Apply(string content, int position, Dictionary<string, object> context)
    {
        // Ваша логика
    }
}

Парсер:

public class CustomParserRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(IReadOnlyList<Token> tokens, ParserContext context)
    {
        // Ваша логика
    }
}

Компилятор:

public class CustomEvaluatorRule<T> : IEvaluatorRule<T>
{
    public CompilerRuleResult<T> Apply(AbstractSyntaxTree ast, EvaluatorContext context)
    {
        // Ваша логика
    }
}

Производительность

Оптимизации

1. Trie для ключевых слов - O(n) вместо O(n*m) для множественных строк
2. Структуры данных - Token и TextPosition как readonly struct (stack allocation)
3. Backtracking с клонированием контекста - изоляция веток парсинга
4. Ленивое вычисление - правила применяются только когда нужно

Узкие места

• Вариативный парсинг - экспоненциальный рост при неоднозначных грамматиках
• Регулярные выражения - могут быть медленными для сложных паттернов
• Рекурсивный обход AST - глубокие деревья требуют больше стека

Безопасность типов

Все компоненты строго типизированы:

• Evaluator<T> - гарантирует тип результата
• Token.Type и OpCode - int для производительности (но можно использовать enum)
• Результаты - record с readonly свойствами

---

Проект: SynLex
Раздел: Архитектура

© 2026 Alexander Izmailov. Все права защищены.