Комбинаторный парсер — это мощный и гибкий инструмент для реализации синтаксического анализа в различных языках программирования, включая C#. В отличие от традиционных парсеров, использующих такие методы, как LL или LR, комбинаторный подход строится на основе маленьких функций-комбинаторов, которые сочетаются для создания сложного синтаксического анализатора. Эта статья представляет практическое руководство по созданию комбинаторного парсера на языке C#.
Синтаксический анализ — один из ключевых этапов компиляции, предназначенный для проверки и трансформации входной строки (обычно исходного кода) в структурированное представление, называемое синтаксическим деревом. Комбинаторные парсеры привлекают к себе внимание благодаря своей эффективности и легкости понимания.
- Простота: Маленькие, независимые функции-комбинаторы объединяются для формирования сложного синтаксического анализатора.
- Модульность: Легко расширять и поддерживать код, так как каждый комбинатор отвечает за конкретную часть правила.
- Повторное использование: Комбинаторы можно переиспользовать в разных контекстах.
- Комбинатор: Функция, которая берет один или несколько парсеров и создает новый.
- Парсер-корневой: Начальный парсер для анализа строки.
- Лексемы: Минимальные синтаксические единицы, например, токены или символы.
Для иллюстрации создадим простой парсер для языка выражений. Язык будет включать целые числа, операции сложения (+) и умножения (*), а также скобки для задания приоритета.
В этом разделе мы построим комбинаторный парсер на языке C#, используя его функциональные возможности. Подойдут и другие подходы, но в данном случае выбран функциональный стиль.
Токен — это минимальная синтаксическая единица. В нашем случае это цифры, операторы и скобки.
using System;
public enum TokenType
{
Number,
Plus,
Multiply,
LeftParen,
RightParen,
Eof
}
public struct Token
{
public TokenType Type;
public string Value;
public Token(TokenType type, string value)
{
Type = type;
Value = value;
}
public override string ToString()
{
return $"{Type}({Value})";
}
}
Лексер (или лексический анализатор) разбивает строку на токены.
public class Lexer
{
private readonly string _input;
private int _position;
public Lexer(string input)
{
_input = input;
_position = 0;
}
public Token NextToken()
{
SkipWhitespace();
if (_position >= _input.Length) return new Token(TokenType.Eof, "");
char currentChar = _input[_position];
switch (currentChar)
{
case '+':
_position++;
return new Token(TokenType.Plus, "+");
case '*':
_position++;
return new Token(TokenType.Multiply, "*");
case '(':
_position++;
return new Token(TokenType.LeftParen, "(");
case ')':
_position++;
return new Token(TokenType.RightParen, ")");
default:
if (char.IsDigit(currentChar))
{
var start = _position;
while (_position < _input.Length && char.IsDigit(_input[_position]))
{
_position++;
}
var number = _input.Substring(start, _position - start);
return new Token(TokenType.Number, number);
}
throw new Exception($"Unexpected character: {currentChar}");
}
}
private void SkipWhitespace()
{
while (_position < _input.Length && char.IsWhiteSpace(_input[_position]))
{
_position++;
}
}
}
Комбинаторы — это функции, которые обрабатывают токены и возвращают результат анализа или ошибку.
using System;
using System.Collections.Generic;
public class Parser<T>
{
private readonly Func<Token[], (T result, Token[] remaining)> _parseFunc;
public Parser(Func<Token[], (T result, Token[] remaining)> parseFunc)
{
_parseFunc = parseFunc;
}
public (T Result, Token[] Remaining) Parse(Token[] tokens)
{
return _parseFunc(tokens);
}
}
- P: Парсер, который пытается применить другой парсер и продолжает анализ.
- S: Сочетатель (sequence), совмещающий два парсера последовательно.
- A: Альтернатор (alternative), который пытается применить любой из нескольких парсеров.
public static Parser<T> P<T>(Func<Token[], (T, Token[])> parseFunc) =>
new Parser<T>(parseFunc);
public static Parser<S> S<T1, T2, S>(Parser<T1> p1, Parser<T2> p2, Func<T1, T2, S> combine)
{
return P(tokens =>
{
var (result1, remaining1) = p1.Parse(tokens);
var (result2, remaining2) = p2.Parse(remaining1);
return (combine(result1, result2), remaining2);
});
}
public static Parser<T> A<T>(params Parser<T>[] parsers)
{
return P(tokens =>
{
foreach (var parser in parsers)
{
var (result, remaining) = parser.Parse(tokens);
if (remaining.Length > 0 && remaining[0].Type != TokenType.Eof)
{
return (result, remaining);
}
}
throw new Exception("No alternative matched");
});
}
Теперь определим конкретные парсеры для нашего языка выражений.
public static Parser<int> NumberParser()
{
return P(tokens =>
{
if (tokens.Length == 0 || tokens[0].Type != TokenType.Number)
throw new Exception("Expected number");
int value = int.Parse(tokens[0].Value);
var remainingTokens = tokens.Skip(1).ToArray();
return (value, remainingTokens);
});
}
public static Parser<int> ParenthesesParser(Parser<int> parser)
{
return P(tokens =>
{
if (tokens.Length == 0 || tokens[0].Type != TokenType.LeftParen)
throw new Exception("Expected '('");
var remainingTokens = tokens.Skip(1).ToArray();
var (result, remainingAfterExpr) = parser.Parse(remainingTokens);
if (remainingAfterExpr.Length == 0 || remainingAfterExpr[0].Type != TokenType.RightParen)
throw new Exception("Expected ')'");
var finalRemaining = remainingAfterExpr.Skip(1).ToArray();
return (result, finalRemaining);
});
}
public static Parser<int> ExpressionParser()
{
// Парсеры для операций
var termParser = Parsers.TermParser();
var plusParser = P(term => S(term, tokens =>
{
if (tokens[0].Type != TokenType.Plus)
throw new Exception("Expected '+'");
var remainingTokens = tokens.Skip(1).ToArray();
return new Parser<int>(result =>
{
var (_, remainingAfterPlus) = termParser.Parse(remainingTokens);
return result + remainingAfterPlus;
}).Parse(remainingTokens);
})).Parse;
var multiplyParser = P(term => S(term, tokens =>
{
if (tokens[0].Type != TokenType.Multiply)
throw new Exception("Expected '*'");
var remainingTokens = tokens.Skip(1).ToArray();
return new Parser<int>(result =>
{
var (_, remainingAfterMultiply) = termParser.Parse(remainingTokens);
return result * remainingAfterMultiply;
}).Parse(remainingTokens);
})).Parse;
// Основной парсер выражений
return S(term => Parsers.ParenthesesParser(term).Parse, plusParser, multiplyParser);
}
public static class Parsers
{
public static Parser<int> TermParser()
{
return A(NumberParser(), parentheses =>
ParenthesesParser(ExpressionParser()));
}
}
Теперь можно использовать наш комбинаторный парсер для анализа строк выражений.
public static void Main(string[] args)
{
string input = "3 + (2 * 5)";
Lexer lexer = new Lexer(input);
List<Token> tokens = new List<Token>();
Token token;
do
{
token = lexer.NextToken();
tokens.Add(token);
} while (token.Type != TokenType.Eof);
Parser<int> parser = ExpressionParser();
try
{
var (_, remaining) = parser.Parse(tokens.ToArray());
Console.WriteLine("Parsing successful!");
}
catch (Exception e)
{
Console.WriteLine($"Parsing failed: {e.Message}");
}
}
Мы создали простой комбинаторный парсер для языка выражений с использованием C#. Преимуществами этого подхода являются его модульность, повторное использование и легкость понимания. Комбинаторные парсеры могут быть расширены для обработки более сложных языков и синтаксисов, что делает их универсальным инструментом в арсенале разработчика.
Конечно, создание комбинаторного парсера — это лишь начало. Рассмотрение ошибок, оптимизация производительности и обработка сложных языковых конструкций потребуют более глубокого погружения в тему. Надеюсь, данное руководство помогло вам начать работать с комбинаторными парсерами на C# и дало понимание базовых принципов их работы.
- Обработка ошибок: Как улучшить пользовательский опыт при возникновении синтаксических ошибок.
- Парсер генераторы: Использование библиотек, таких как
FParsec, для создания парсеров в C#. - Оптимизация производительности: Техники ускорения работы комбинаторных парсеров.
- Применение к реальным языкам: Разработка парсеров для более сложных и практических языков программирования.
Комбинаторные парсеры — это мощный инструмент, который может существенно упростить работу над проектами компиляции или интерпретации. Использование их в C# позволяет разработчикам создавать гибкие, модульные и легко поддерживаемые парсеры для широкого спектра приложений.

