← Назад

Примеры

Калькулятор арифметических выражений

Полный пример парсера и вычислителя математических выражений с приоритетом операций.

Определение токенов

// Типы токенов
const int TOKEN_WHITESPACE = 0;
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;

// Типы узлов AST
const int AST_NUMBER = 100;
const int AST_ADD = 101;
const int AST_SUB = 102;
const int AST_MULT = 103;
const int AST_DIV = 104;
const int AST_NEG = 105; // унарный минус

Лексер

using SynLex;
using SynLex.LexicalAnalysis;
using SynLex.LexicalAnalysis.Rules;

var lexer = new Lexer()
    .AddRule(new SimpleSublineLexerRule(
        new[] { " ", "\t", "\n", "\r" }, 
        TOKEN_WHITESPACE))
    .AddRule(new RegexLexerRule(@"\d+(\.\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));

string expression = "2 + 3 * (4 - 1)";
var lexResult = lexer.Analyze(expression);

// Фильтруем пробелы
var tokens = lexResult.Tokens!
    .Where(t => t.Type != TOKEN_WHITESPACE)
    .ToList();

Парсер с приоритетом операций

using SynLex.SyntacticAnalysis;

// Правило для числа
class NumberRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        if (tokens.Count == 1 && tokens[0].Type == TOKEN_NUMBER)
        {
            return (new Token(tokens[0].Content, AST_NUMBER, tokens[0].Position), []);
        }
        return (null, []);
    }
}

// Правило для скобок: (expr)
class ParenRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        if (tokens.Count >= 3 && 
            tokens[0].Type == TOKEN_LPAREN && 
            tokens[^1].Type == TOKEN_RPAREN)
        {
            return (tokens[0], [(1, tokens.Count - 1)]);
        }
        return (null, []);
    }
}

// Бинарная операция с приоритетом
class BinaryOpRule : IParserRule
{
    private readonly int[] _operators;
    private readonly Dictionary<int, int> _astTypes;

    public BinaryOpRule(int[] operators, Dictionary<int, int> astTypes)
    {
        _operators = operators;
        _astTypes = astTypes;
    }

    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        int depth = 0;
        // Ищем оператор справа налево (правая ассоциативность для +/-)
        for (int i = tokens.Count - 1; i >= 1; i--)
        {
            var token = tokens[i];
            
            // Отслеживаем вложенность скобок
            if (token.Type == TOKEN_RPAREN) depth++;
            else if (token.Type == TOKEN_LPAREN) depth--;
            else if (depth == 0 && _operators.Contains(token.Type))
            {
                var astType = _astTypes[token.Type];
                var resultToken = new Token(token.Content, astType, token.Position);
                return (resultToken, [(0, i), (i + 1, tokens.Count)]);
            }
        }
        return (null, []);
    }
}

var parser = new Parser()
    .AddRule(new NumberRule())
    .AddRule(new ParenRule())
    // Низкий приоритет: + и -
    .AddRule(new BinaryOpRule(
        [TOKEN_PLUS, TOKEN_MINUS],
        new Dictionary<int, int> {
            { TOKEN_PLUS, AST_ADD },
            { TOKEN_MINUS, AST_SUB }
        }))
    // Высокий приоритет: * и /
    .AddRule(new BinaryOpRule(
        [TOKEN_MULT, TOKEN_DIV],
        new Dictionary<int, int> {
            { TOKEN_MULT, AST_MULT },
            { TOKEN_DIV, AST_DIV }
        }));

var parseResult = parser.Analyze(tokens);

Компилятор (вычислитель)

using SynLex.Compilation;

class CalculatorRule : IEvaluatorRule<double>
{
    public CompilerRuleResult<double> Apply(AbstractSyntaxTree ast, EvaluatorContext context)
    {
        switch (ast.Token.Type)
        {
            case AST_NUMBER:
                return new CompilerRuleResult<double>(true, double.Parse(ast.Token.Content));

            case AST_ADD:
                var left = (double)context.CompiledBranches[0];
                var right = (double)context.CompiledBranches[1];
                return new CompilerRuleResult<double>(true, left + right);

            case AST_SUB:
                left = (double)context.CompiledBranches[0];
                right = (double)context.CompiledBranches[1];
                return new CompilerRuleResult<double>(true, left - right);

            case AST_MULT:
                left = (double)context.CompiledBranches[0];
                right = (double)context.CompiledBranches[1];
                return new CompilerRuleResult<double>(true, left * right);

            case AST_DIV:
                left = (double)context.CompiledBranches[0];
                right = (double)context.CompiledBranches[1];
                if (Math.Abs(right) < 1e-10)
                    throw new DivideByZeroException();
                return new CompilerRuleResult<double>(true, left / right);

            default:
                return CompilerRuleResult<double>.Fail;
        }
    }
}

var evaluator = new Evaluator<double>()
    .AddRule(new CalculatorRule());

var result = evaluator.Compile(parseResult.Ast!);
Console.WriteLine($"{expression} = {result.Result}"); // 2 + 3 * (4 - 1) = 11

JSON Parser

Парсер для упрощённого JSON (строки, числа, массивы, объекты).

Токены

const int TOKEN_LBRACE = 10;    // {
const int TOKEN_RBRACE = 11;    // }
const int TOKEN_LBRACKET = 12;  // [
const int TOKEN_RBRACKET = 13;  // ]
const int TOKEN_COLON = 14;     // :
const int TOKEN_COMMA = 15;     // ,
const int TOKEN_STRING = 16;    // "text"
const int TOKEN_NUMBER = 17;    // 123
const int TOKEN_TRUE = 18;      // true
const int TOKEN_FALSE = 19;     // false
const int TOKEN_NULL = 20;      // null

const int AST_OBJECT = 100;
const int AST_ARRAY = 101;
const int AST_PAIR = 102;
const int AST_STRING = 103;
const int AST_NUMBER = 104;
const int AST_BOOL = 105;
const int AST_NULL = 106;

Лексер

var lexer = new Lexer()
    .AddRule(CommonLexerRules.Whitespace(0))
    .AddRule(new SimpleSublineLexerRule(new[] { "{" }, TOKEN_LBRACE))
    .AddRule(new SimpleSublineLexerRule(new[] { "}" }, TOKEN_RBRACE))
    .AddRule(new SimpleSublineLexerRule(new[] { "[" }, TOKEN_LBRACKET))
    .AddRule(new SimpleSublineLexerRule(new[] { "]" }, TOKEN_RBRACKET))
    .AddRule(new SimpleSublineLexerRule(new[] { ":" }, TOKEN_COLON))
    .AddRule(new SimpleSublineLexerRule(new[] { "," }, TOKEN_COMMA))
    .AddRule(new SimpleSublineLexerRule(new[] { "true" }, TOKEN_TRUE))
    .AddRule(new SimpleSublineLexerRule(new[] { "false" }, TOKEN_FALSE))
    .AddRule(new SimpleSublineLexerRule(new[] { "null" }, TOKEN_NULL))
    .AddRule(CommonLexerRules.DoubleQuotedString(TOKEN_STRING))
    .AddRule(CommonLexerRules.Float(TOKEN_NUMBER));

Парсер

// Объект: { "key": value, ... }
class ObjectRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        if (tokens.Count >= 2 && 
            tokens[0].Type == TOKEN_LBRACE && 
            tokens[^1].Type == TOKEN_RBRACE)
        {
            var subsets = new List<(int, int)>();
            // Разбиваем по запятым между парами
            int start = 1;
            for (int i = 1; i < tokens.Count - 1; i++)
            {
                if (tokens[i].Type == TOKEN_COMMA)
                {
                    subsets.Add((start, i));
                    start = i + 1;
                }
            }
            if (start < tokens.Count - 1)
                subsets.Add((start, tokens.Count - 1));

            return (new Token("{}", AST_OBJECT, tokens[0].Position), subsets);
        }
        return (null, []);
    }
}

// Пара: "key": value
class PairRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        if (tokens.Count >= 3 &&
            tokens[0].Type == TOKEN_STRING &&
            tokens[1].Type == TOKEN_COLON)
        {
            return (
                new Token(":", AST_PAIR, tokens[1].Position),
                [(0, 1), (2, tokens.Count)]
            );
        }
        return (null, []);
    }
}

// Простые значения
class ValueRule : IParserRule
{
    public (Token? token, List<(int, int)> subsets) Apply(
        IReadOnlyList<Token> tokens, ParserContext context)
    {
        if (tokens.Count != 1) return (null, []);

        var token = tokens[0];
        int astType = token.Type switch
        {
            TOKEN_STRING => AST_STRING,
            TOKEN_NUMBER => AST_NUMBER,
            TOKEN_TRUE or TOKEN_FALSE => AST_BOOL,
            TOKEN_NULL => AST_NULL,
            _ => -1
        };

        if (astType < 0) return (null, []);
        return (new Token(token.Content, astType, token.Position), []);
    }
}

var parser = new Parser()
    .AddRule(new ValueRule())
    .AddRule(new ObjectRule())
    .AddRule(new PairRule());
    // ... добавить ArrayRule аналогично ObjectRule

Компилятор в Dictionary/List

class JsonEvaluatorRule : IEvaluatorRule<object?>
{
    public CompilerRuleResult<object?> Apply(AbstractSyntaxTree ast, EvaluatorContext context)
    {
        switch (ast.Token.Type)
        {
            case AST_STRING:
                var str = ast.Token.Content.Trim('"');
                return new CompilerRuleResult<object?>(true, str);

            case AST_NUMBER:
                return new CompilerRuleResult<object?>(true, double.Parse(ast.Token.Content));

            case AST_BOOL:
                return new CompilerRuleResult<object?>(true, ast.Token.Content == "true");

            case AST_NULL:
                return new CompilerRuleResult<object?>(true, null);

            case AST_OBJECT:
                var obj = new Dictionary<string, object?>();
                foreach (var pair in context.CompiledBranches.Cast<KeyValuePair<string, object?>>())
                    obj[pair.Key] = pair.Value;
                return new CompilerRuleResult<object?>(true, obj);

            case AST_PAIR:
                var key = (string)context.CompiledBranches[0]!;
                var value = context.CompiledBranches[1];
                return new CompilerRuleResult<object?>(true, new KeyValuePair<string, object?>(key, value));

            case AST_ARRAY:
                return new CompilerRuleResult<object?>(true, context.CompiledBranches.ToList());

            default:
                return CompilerRuleResult<object?>.Fail;
        }
    }
}

var evaluator = new Evaluator<object?>()
    .AddRule(new JsonEvaluatorRule());

Простой язык программирования

Минимальный интерпретатор с переменными и условиями.

Грамматика

program    := statement*
statement  := assignment | if-stmt | print
assignment := identifier '=' expr ';'
if-stmt    := 'if' '(' expr ')' '{' statement* '}'
print      := 'print' '(' expr ')' ';'
expr       := number | identifier | expr op expr
op         := '+' | '-' | '*' | '/'

Пример кода

x = 10;
y = 20;
if (x < y) {
    print(x + y);
}

Реализация (схема)

// Лексер с ключевыми словами
var lexer = new Lexer()
    .AddRule(CommonLexerRules.Whitespace(TOKEN_WS))
    .AddRule(CommonLexerRules.Keyword(
        new[] { "if", "print" }, TOKEN_KEYWORD))
    .AddRule(CommonLexerRules.Identifier(TOKEN_ID))
    .AddRule(CommonLexerRules.Integer(TOKEN_NUM))
    .AddRule(new SimpleSublineLexerRule(
        new[] { "=", ";", "(", ")", "{", "}", "+", "-", "*", "/", "<", ">" },
        TOKEN_PUNCT));

// Парсер с правилами для каждой конструкции
var parser = new Parser()
    .AddRule(new AssignmentRule())
    .AddRule(new IfStatementRule())
    .AddRule(new PrintStatementRule())
    .AddRule(new ExpressionRule());

// Интерпретатор с окружением переменных
class InterpreterRule : IEvaluatorRule<object>
{
    private Dictionary<string, object> _env = new();

    public CompilerRuleResult<object> Apply(AbstractSyntaxTree ast, EvaluatorContext context)
    {
        switch (ast.Token.Type)
        {
            case AST_ASSIGN:
                var varName = ast.Branches.First().Token.Content;
                var value = context.CompiledBranches[1];
                _env[varName] = value;
                return new CompilerRuleResult<object>(true, value);

            case AST_VARIABLE:
                return new CompilerRuleResult<object>(true, _env[ast.Token.Content]);

            case AST_IF:
                var condition = (bool)context.CompiledBranches[0];
                if (condition)
                {
                    // Выполняем тело if
                    foreach (var stmt in context.CompiledBranches.Skip(1))
                        ; // выполнено
                }
                return new CompilerRuleResult<object>(true, null!);

            // ... другие случаи
        }
    }
}

Виртуальная машина: байт-код для калькулятора

Компиляция AST калькулятора в стековые инструкции.

Байт-код компилятор

using SynLex.VirtualMachine;

var compiler = new BytecodeCompiler()
    .AddRule(AST_NUMBER, ast => new List<Instruction>
    {
        new(OpCode.Push, double.Parse(ast.Token.Content))
    })
    .AddRule(AST_ADD, ast => new List<Instruction> { new(OpCode.Add) })
    .AddRule(AST_SUB, ast => new List<Instruction> { new(OpCode.Sub) })
    .AddRule(AST_MULT, ast => new List<Instruction> { new(OpCode.Mul) })
    .AddRule(AST_DIV, ast => new List<Instruction> { new(OpCode.Div) });

var instructions = compiler.Compile(ast);

Выполнение

var vm = new VirtualMachine()
    .AddRule(VMBuiltinRules.PushRule())
    .AddRule(VMBuiltinRules.AddRule())
    .AddRule(VMBuiltinRules.SubRule())
    .AddRule(VMBuiltinRules.MulRule())
    .AddRule(VMBuiltinRules.DivRule());

var result = vm.Execute(instructions);
Console.WriteLine($"Результат VM: {result.Value}");

---

Проект: SynLex
Раздел: Примеры использования

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