Синтаксический анализ

Синтаксический анализатор (Parser) преобразует последовательность токенов в абстрактное синтаксическое дерево (AST). Это дерево отражает иерархическую структуру программы согласно грамматике языка.

Основные концепции

AbstractSyntaxTree (AST) - Абстрактное синтаксическое дерево

AST представляет синтаксическую структуру кода в виде дерева:

public class AbstractSyntaxTree
{
    public Token Token { get; init; }                      // Токен узла
    public AbstractSyntaxTree[] Branches { get; init; }    // Дочерние узлы
}

Пример для выражения "2 + 3":

       [+]
      /   \
    [2]   [3]

В коде:

var ast = new AbstractSyntaxTree
{
    Token = new Token { Type = TOKEN_PLUS, Content = "+" },
    Branches = new[]
    {
        new AbstractSyntaxTree { Token = new Token { Type = TOKEN_NUMBER, Content = "2" } },
        new AbstractSyntaxTree { Token = new Token { Type = TOKEN_NUMBER, Content = "3" } }
    }
};

ParserContext - Контекст парсинга

ParserContext отслеживает состояние парсера во время разбора:

public class ParserContext
{
    public int Position { get; set; }              // Текущая позиция в массиве токенов
    public List<string> Errors { get; init; }      // Список ошибок
    public Dictionary<string, object?> UserContext { get; init; } // Пользовательские данные
}

Основные методы:

// Получить текущий токен
Token? CurrentToken(Token[] tokens);

// Продвинуться на следующий токен
void Advance();

// Добавить ошибку
void AddError(string message);

// Создать копию контекста (для backtracking)
ParserContext Clone();

ParserResult - Результат парсинга

public class ParserResult
{
    public bool IsSuccess { get; set; }
    public AbstractSyntaxTree? Ast { get; set; }
    public List<string> Errors { get; set; } = new();
}

Создание парсера

Базовая настройка

using SynLex.SyntacticAnalysis;

var parser = new Parser()
    .AddRule(rule1)
    .AddRule(rule2)
    .AddRule(rule3);

var result = parser.Analyze(tokens);

IParserRule - Интерфейс правила парсера

public interface IParserRule
{
    int Priority { get; }           // Приоритет правила (больше = выше)
    bool StopOnMatch { get; }       // Прекратить применение правил после совпадения
    
    bool TryApply(
        Token[] tokens,             // Массив токенов
        ParserContext context,      // Контекст парсинга
        out AbstractSyntaxTree? ast // Результирующее дерево
    );
}

Правило должно:

Проверить, подходят ли токены с позиции context.Position
Если подходят - создать AST, продвинуть позицию и вернуть true
Если не подходят - оставить контекст без изменений и вернуть false

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

SimpleParserRule - Одиночный токен

Преобразует один токен в AST:

// Числа
var numberRule = new SimpleParserRule(TOKEN_NUMBER);

// Идентификаторы
var identifierRule = new SimpleParserRule(TOKEN_IDENTIFIER);

// Применение
var result = parser.Analyze(new[] { numberToken });
// result.Ast.Token == numberToken

SequenceParserRule - Последовательность

Проверяет последовательность типов токенов:

// Объявление переменной: "let" identifier "=" expression
var varDeclRule = new SequenceParserRule(
    new[] { TOKEN_LET, TOKEN_IDENTIFIER, TOKEN_ASSIGN },
    TOKEN_VAR_DECL  // Тип результирующего узла
);

// Парсинг: "let x = 5"
// Результат: AST с типом TOKEN_VAR_DECL и тремя ветками

BinaryOperatorRule - Бинарные операторы

Обрабатывает инфиксные операторы с приоритетами:

// Арифметические операторы
var addRule = new BinaryOperatorRule(TOKEN_PLUS, priority: 10);
var multRule = new BinaryOperatorRule(TOKEN_MULT, priority: 20);

// Парсинг: "2 + 3 * 4"
// Результат:
//       [+]
//      /   \
//    [2]   [*]
//         /   \
//       [3]   [4]

Приоритет операторов:

Больший приоритет = теснее связывание
Умножение (20) связывает сильнее сложения (10)

GroupParserRule - Группировка скобками

Обрабатывает выражения в скобках:

// Круглые скобки
var parenRule = new GroupParserRule(TOKEN_LPAREN, TOKEN_RPAREN);

// Парсинг: "(2 + 3) * 4"
// Скобки создают группу, меняя приоритет

VariantParserRule - Альтернативы

Пробует несколько вариантов правил:

// Expression может быть: число ИЛИ идентификатор ИЛИ группа в скобках
var exprRule = new VariantParserRule(
    new IParserRule[]
    {
        new SimpleParserRule(TOKEN_NUMBER),
        new SimpleParserRule(TOKEN_IDENTIFIER),
        new GroupParserRule(TOKEN_LPAREN, TOKEN_RPAREN)
    }
);

Приоритет и порядок применения

Система приоритетов

Парсер применяет правила в порядке убывания приоритета:

public class HighPriorityRule : IParserRule
{
    public int Priority => 100;  // Применится первым
    // ...
}

public class LowPriorityRule : IParserRule
{
    public int Priority => 10;   // Применится позже
    // ...
}

Стандартные приоритеты:

Унарные операторы: 100
Умножение/деление: 20
Сложение/вычитание: 10
Присваивание: 5
Группировка: 0 (применяется всегда)

StopOnMatch - Прекращение обработки

public class TerminalRule : IParserRule
{
    public bool StopOnMatch => true;  // Не пробовать другие правила после совпадения
    // ...
}

Когда использовать:

Для терминальных символов (числа, идентификаторы)
Для однозначных конструкций
Для оптимизации производительности

Backtracking - Откат

Если правило не подошло, парсер откатывает изменения контекста:

public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
{
    // Сохраняем позицию
    int startPosition = context.Position;
    
    // Пробуем разобрать
    if (/* условие не выполнено */)
    {
        // Откатываем позицию
        context.Position = startPosition;
        ast = null;
        return false;
    }
    
    // Успешно - создаем AST
    ast = new AbstractSyntaxTree { /* ... */ };
    return true;
}

Пример с альтернативами:

// Пробуем: if-statement | while-statement | return-statement
if (!TryParseIf(context, out ast) &&
    !TryParseWhile(context, out ast) &&
    !TryParseReturn(context, out ast))
{
    // Ни одно не подошло - ошибка
    context.AddError("Expected statement");
    return false;
}

Рекурсивный спуск

Parser использует алгоритм рекурсивного спуска для обработки вложенных структур.

Пример - арифметическое выражение:

expression := term (('+' | '-') term)*
term := factor (('*' | '/') factor)*
factor := number | '(' expression ')'

Реализация:

public class ExpressionRule : IParserRule
{
    public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
    {
        // Парсим первый term
        if (!TryParseTerm(tokens, context, out var left))
        {
            ast = null;
            return false;
        }
        
        // Парсим ('+' | '-') term
        while (context.CurrentToken(tokens)?.Type is TOKEN_PLUS or TOKEN_MINUS)
        {
            var op = context.CurrentToken(tokens)!;
            context.Advance();
            
            if (!TryParseTerm(tokens, context, out var right))
            {
                context.AddError("Expected term after operator");
                ast = null;
                return false;
            }
            
            // Создаем бинарный узел
            left = new AbstractSyntaxTree
            {
                Token = op,
                Branches = new[] { left, right }
            };
        }
        
        ast = left;
        return true;
    }
}

Пользовательские правила

Простое правило

// Парсинг присваивания: identifier '=' expression
public class AssignmentRule : IParserRule
{
    public int Priority => 5;
    public bool StopOnMatch => false;
    
    public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
    {
        ast = null;
        int startPos = context.Position;
        
        // Проверяем identifier
        var current = context.CurrentToken(tokens);
        if (current?.Type != TOKEN_IDENTIFIER)
            return false;
        
        var identifier = current;
        context.Advance();
        
        // Проверяем '='
        current = context.CurrentToken(tokens);
        if (current?.Type != TOKEN_ASSIGN)
        {
            context.Position = startPos;  // Откат
            return false;
        }
        
        var assignOp = current;
        context.Advance();
        
        // Парсим expression (рекурсивно)
        if (!TryParseExpression(tokens, context, out var expr))
        {
            context.Position = startPos;  // Откат
            context.AddError("Expected expression after '='");
            return false;
        }
        
        // Создаем AST
        ast = new AbstractSyntaxTree
        {
            Token = assignOp,
            Branches = new[]
            {
                new AbstractSyntaxTree { Token = identifier },
                expr
            }
        };
        
        return true;
    }
    
    private bool TryParseExpression(Token[] tokens, ParserContext context, 
                                    out AbstractSyntaxTree? ast)
    {
        // Делегируем парсинг выражения другому правилу
        var exprParser = new Parser().AddRule(new ExpressionRule());
        // ... (упрощено)
    }
}

Правило с пользовательским контекстом

public class FunctionDeclRule : IParserRule
{
    public int Priority => 50;
    public bool StopOnMatch => false;
    
    public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
    {
        // Сохраняем текущую функцию в контексте
        var previousFunc = context.UserContext.GetValueOrDefault("currentFunction");
        context.UserContext["currentFunction"] = "myFunction";
        
        // Парсим тело функции...
        
        // Восстанавливаем предыдущее значение
        context.UserContext["currentFunction"] = previousFunc;
        
        ast = /* ... */;
        return true;
    }
}

Обработка ошибок

Добавление ошибок

if (context.CurrentToken(tokens)?.Type != TOKEN_SEMICOLON)
{
    var token = context.CurrentToken(tokens);
    context.AddError($"Expected ';' but found '{token?.Content}' at {token?.Position}");
    return false;
}

Восстановление после ошибок

public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
{
    // Пробуем разобрать statement
    if (!TryParseStatement(tokens, context, out ast))
    {
        // Пропускаем токены до следующей точки синхронизации
        while (context.Position < tokens.Length &&
               context.CurrentToken(tokens)?.Type != TOKEN_SEMICOLON)
        {
            context.Advance();
        }
        
        // Пропускаем ';'
        if (context.CurrentToken(tokens)?.Type == TOKEN_SEMICOLON)
            context.Advance();
        
        return false;
    }
    
    return true;
}

Проверка результата

var result = parser.Analyze(tokens);

if (!result.IsSuccess)
{
    Console.Error.WriteLine("Parsing errors:");
    foreach (var error in result.Errors)
    {
        Console.Error.WriteLine($"  - {error}");
    }
    return;
}

var ast = result.Ast!;
// Продолжаем работу с деревом

Вариативный парсинг

Парсер может генерировать несколько вариантов AST для неоднозначных грамматик:

var parser = new Parser()
    .AddRule(new AmbiguousRule())
    .EnableVariantParsing();  // Включить вариативность

var result = parser.Analyze(tokens);

if (result.IsSuccess && result.Variants != null)
{
    Console.WriteLine($"Found {result.Variants.Count} variants:");
    foreach (var variant in result.Variants)
    {
        PrintTree(variant);
    }
}

Когда использовать:

При разборе естественного языка
Для неоднозначных грамматик
При генерации вариантов интерпретации

Оптимизация производительности

1. Используйте StopOnMatch

// ✅ Быстро - не пробует другие правила
public class NumberRule : IParserRule
{
    public bool StopOnMatch => true;
    // ...
}

2. Правильная расстановка приоритетов

// ✅ Часто встречающиеся правила с высоким приоритетом
var parser = new Parser()
    .AddRule(new NumberRule { Priority = 100 })
    .AddRule(new IdentifierRule { Priority = 99 })
    .AddRule(new RareConstructRule { Priority = 10 });

3. Минимизируйте backtracking

// ❌ Много backtracking
var rule = new VariantParserRule(
    new[] { rule1, rule2, rule3, rule4, rule5 }
);

// ✅ Проверяем первый токен для быстрого отсева
public bool TryApply(Token[] tokens, ParserContext context, out AbstractSyntaxTree? ast)
{
    var current = context.CurrentToken(tokens);
    
    // Быстрая проверка по первому токену
    if (current?.Type != TOKEN_EXPECTED)
    {
        ast = null;
        return false;
    }
    
    // Продолжаем только если первый токен подходит
    // ...
}

Полный пример

Калькулятор с приоритетами операторов

using SynLex;
using SynLex.LexicalAnalysis;
using SynLex.SyntacticAnalysis;

// Типы токенов
const int TOKEN_NUMBER = 1;
const int TOKEN_PLUS = 2;
const int TOKEN_MINUS = 3;
const int TOKEN_MULT = 4;
const int TOKEN_DIV = 5;
const int TOKEN_LPAREN = 6;
const int TOKEN_RPAREN = 7;

// Лексер
var lexer = new Lexer()
    .AddRule(new WhitespaceLexerRule())
    .AddRule(new RegexLexerRule(@"\d+", TOKEN_NUMBER))
    .AddRule(new SimpleSublineLexerRule(new[] { "+" }, TOKEN_PLUS))
    .AddRule(new SimpleSublineLexerRule(new[] { "-" }, TOKEN_MINUS))
    .AddRule(new SimpleSublineLexerRule(new[] { "*" }, TOKEN_MULT))
    .AddRule(new SimpleSublineLexerRule(new[] { "/" }, TOKEN_DIV))
    .AddRule(new SimpleSublineLexerRule(new[] { "(" }, TOKEN_LPAREN))
    .AddRule(new SimpleSublineLexerRule(new[] { ")" }, TOKEN_RPAREN));

// Парсер
var parser = new Parser()
    .AddRule(new SimpleParserRule(TOKEN_NUMBER) { Priority = 100, StopOnMatch = true })
    .AddRule(new GroupParserRule(TOKEN_LPAREN, TOKEN_RPAREN) { Priority = 90 })
    .AddRule(new BinaryOperatorRule(TOKEN_MULT) { Priority = 20 })
    .AddRule(new BinaryOperatorRule(TOKEN_DIV) { Priority = 20 })
    .AddRule(new BinaryOperatorRule(TOKEN_PLUS) { Priority = 10 })
    .AddRule(new BinaryOperatorRule(TOKEN_MINUS) { Priority = 10 });

// Использование
var lexResult = lexer.Analyze("(2 + 3) * 4");
if (!lexResult.IsSuccess)
{
    Console.WriteLine("Lexer errors:");
    lexResult.Errors.ForEach(Console.WriteLine);
    return;
}

var parseResult = parser.Analyze(lexResult.Tokens!);
if (!parseResult.IsSuccess)
{
    Console.WriteLine("Parser errors:");
    parseResult.Errors.ForEach(Console.WriteLine);
    return;
}

// Печатаем дерево
PrintTree(parseResult.Ast!, indent: 0);

void PrintTree(AbstractSyntaxTree node, int indent)
{
    Console.WriteLine(new string(' ', indent * 2) + $"[{node.Token.Content}]");
    foreach (var branch in node.Branches)
    {
        PrintTree(branch, indent + 1);
    }
}

/* Вывод:
[*]
  [+]
    [2]
    [3]
  [4]
*/

Лучшие практики

1. Явная грамматика

Документируйте грамматику в комментариях:

/*
Grammar:
    program := statement*
    statement := assignment | if_statement | while_statement
    assignment := IDENTIFIER '=' expression ';'
    if_statement := 'if' '(' expression ')' block ('else' block)?
    expression := term (('+' | '-') term)*
    term := factor (('*' | '/') factor)*
    factor := NUMBER | IDENTIFIER | '(' expression ')'
*/

2. Проверяйте контекст

// ✅ Всегда проверяйте границы
if (context.Position >= tokens.Length)
{
    ast = null;
    return false;
}

var token = context.CurrentToken(tokens);

3. Используйте вспомогательные методы

private bool Expect(Token[] tokens, ParserContext context, int expectedType, out Token? token)
{
    token = context.CurrentToken(tokens);
    
    if (token?.Type != expectedType)
    {
        context.AddError($"Expected token type {expectedType}, got {token?.Type}");
        return false;
    }
    
    context.Advance();
    return true;
}

Следующие шаги

После создания парсера:

Изучите Компиляцию для преобразования AST в результат
См. Примеры для готовых парсеров
Ознакомьтесь с Архитектурой для понимания алгоритмов