Сверхсильный парсер для сбалансированных вложенных скобок

Question

Я изо всех сил пытаюсь придумать парсер сверхдержавы для набора частичных входов ниже (вложенные сбалансированные скобки с разделителем '|').

Произвольный текст может входить в паренсы, включая пробелы, другие токены и "()". Только '|', '(', ')', должны иметь здесь особое значение (перевод строки также заканчивает последовательность). Чтобы быть действительным, каждая сбалансированная, заключенная в скобки группа должна иметь '|' и по крайней мере один символ, который не является "(" или ")".

В идеале синтаксический анализатор должен разбивать каждый входной элемент на список с элементами (терминальной) строкой или массивом строк следующим образом:

Действительно:

(a|)                    ->      { "a", "" }
(a | b)                 ->      { "a", "b" }
(a | b.c())             ->      { "a", "b.c()" }
(aa | bb cc )           ->      { "aa" "bb cc" }
(a | b | c #dd)         ->      { "a", "b", "c #dd"}
((a | b) | $c)          ->      { { "a", "b" }, "$c" }
((a | b) | (c | d))     ->      { { "a", "b" }, { "c", "d" } }
(((a | b) | c) | d)     ->      { { { "a", "b" }, "c" }, "d" }
...

Invalid / игнорируется:

()
())
(()
(|)
(|())
(.)
(())
(()|())
(abc)
(a bc)
(a.bc())
...

Мои токены (для целей здесь) следующие:

public enum Tokens
{        
    [Token(Example = "(")]
    LParen,

    [Token(Example = ")")]
    RParen,

    [Token(Example = "|")]
    Pipe,

    [Token(Description = "everything-else")]
    String
} 

Answer 1

Это было сложно, в основном из-за пробелов, которые нужно сохранить, но я смог придумать парсер, отвечающий вашим потребностям. Во-первых, я должен был изменить Tokens немного перечислим:

public enum Tokens
{
    None,
    String,
    Number,

    [Token(Example = "()")]
    OpenCloseParen,

    [Token(Example = "(")]
    LParen,

    [Token(Example = ")")]
    RParen,

    [Token(Example = "#")]
    Hash,

    [Token(Example = "$")]
    Dollar,

    [Token(Example = "|")]
    Pipe,

    [Token(Example = ".")]
    Dot,

    [Token(Example = " ")]
    Whitespace,
}

Далее мы можем построить следующее Tokenizer:

var tokenizer = new TokenizerBuilder<Tokens>()
    .Match(Span.EqualTo("()"), Tokens.OpenCloseParen)
    .Match(Character.EqualTo('('), Tokens.LParen)
    .Match(Character.EqualTo(')'), Tokens.RParen)
    .Match(Character.EqualTo('#'), Tokens.Hash)
    .Match(Character.EqualTo('$'), Tokens.Dollar)
    .Match(Character.EqualTo('.'), Tokens.Dot)
    .Match(Character.EqualTo('|'), Tokens.Pipe)
    .Match(Character.EqualTo(' '), Tokens.Whitespace)
    .Match(Span.MatchedBy(Character.AnyChar), Tokens.String)
    .Match(Numerics.Natural, Tokens.Number)
    .Build();

Затем создайте классы моделей для хранения выходных данных (возможно, вы можете придумать более подходящие имена для них, поскольку я не совсем уверен, что это за данные, которые вы анализируете):

public abstract class Node
{
}

public class TextNode : Node
{
    public string Value { get; set; }
}

public class Expression : Node
{
    public Node[] Nodes { get; set; }
}

Затем мы создаем парсеры:

public static class MyParsers
{
    /// <summary>
    /// Parses any whitespace (if any) and returns a resulting string
    /// </summary>
    public readonly static TokenListParser<Tokens, string> OptionalWhitespace =
        from chars in Token.EqualTo(Tokens.Whitespace).Many().OptionalOrDefault()
        select chars == null ? "" : new string(' ', chars.Length);

    /// <summary>
    /// Parses a valid text expression
    /// e.g. "abc", "a.c()", "$c", etc.
    /// </summary>
    public readonly static TokenListParser<Tokens, Node> TextExpression =
        from tokens in
            Token.EqualTo(Tokens.OpenCloseParen)
            .Or(Token.EqualTo(Tokens.Hash))
            .Or(Token.EqualTo(Tokens.Dollar))
            .Or(Token.EqualTo(Tokens.Dot))
            .Or(Token.EqualTo(Tokens.Number))
            .Or(Token.EqualTo(Tokens.String))
            .Or(Token.EqualTo(Tokens.Whitespace))
            .Many()
        // if this side of the pipe is all whitespace, return null
        select (Node) (
            tokens.All(x => x.ToStringValue() == " ") 
            ? null
            : new TextNode {
                Value = string.Join("", tokens.Select(t => t.ToStringValue())).Trim()
            }
        );

    /// <summary>
    /// Parses a full expression that may contain text expressions or nested sub-expressions
    /// e.g. "(a | b)", "( (a.c() | b) | (123 | c) )", etc.
    /// </summary>
    public readonly static TokenListParser<Tokens, Node> Expression =
        from leadWs in OptionalWhitespace
        from lp in Token.EqualTo(Tokens.LParen)
        from nodes in TextExpression
            .Or(Parse.Ref(() => Expression))
            .ManyDelimitedBy(Token.EqualTo(Tokens.Pipe))
            .OptionalOrDefault()
        from rp in Token.EqualTo(Tokens.RParen)
        from trailWs in OptionalWhitespace
        where nodes.Length > 1 && nodes.Any(node => node != null) // has to have at least two sides and one has to be non-null
        select (Node)new Expression {
            Nodes = nodes.Select(node => node ?? new TextNode { Value = "" }).ToArray()
        };
}

И, наконец, мы можем использовать токенизатор вместе с парсерами для анализа вашего ввода:

string input = "(a b | c.())";
var tokens = tokenizer.Tokenize(input);

var result = MyParsers.Expression.TryParse(tokens);
if (result.HasValue)
{
    // input is valid
    var expression = (Expression)result.Value;

    // do what you need with it here, i.e. loop through the nodes, output the text, etc.
}
else
{
    // not valid
}

Это работает практически для всех ваших тестовых случаев, кроме таких, как этот (()|()) где пара открытия / закрытия - это значение по обе стороны трубы. Существует также, вероятно, лучший способ выполнить некоторые операции синтаксического анализа, поскольку я сам привыкаю к ​​Superpower, но я думаю, что это хорошая основа для начала, так что вы можете оптимизировать ее и / или интегрировать все ваши крайние случаи в Это.

РЕДАКТИРОВАТЬ

Это был пробел, который все испортил. Я должен был добавить больше проверок пробелов в пределах Expression синтаксический анализатор, а также должен был добавить условие для проверки непустого TextExpression а затем также проверьте, что может быть пустым. Это было для обработки случаев, когда одна сторона трубы пуста. Вот рабочий парсер:

public readonly static TokenListParser<Tokens, Node> Expression =
    from _1 in OptionalWhitespace
    from lp in Token.EqualTo(Tokens.LParen)
    from _2 in OptionalWhitespace
    from nodes in 
        TextExpression.Where(node => node != null) // check for actual text node first
        .Or(Expression)
        .Or(TextExpression) // then check to see if it's empty
        .ManyDelimitedBy(Token.EqualTo(Tokens.Pipe))
    from _3 in OptionalWhitespace
    from rp in Token.EqualTo(Tokens.RParen)
    from _4 in OptionalWhitespace
    where nodes.Length > 1 && nodes.Any(node => node != null) // has to have at least two sides and one has to be non-null
    select (Node)new Expression {
        Nodes = nodes.Select(node => node ?? new TextNode { Value = "" }).ToArray()
    };