c# - 如何解析人为输入的逻辑属性，例如这个和(那个或另一个)？

Question

作为即将进行的项目的一部分，我想对其进行设置，以便某个域对象可以应用于标签或标签组合。

我希望能够让用户以人类可读的方式输入这些组合，类似于:

• tag-a and (tag-b or tag-c) --> 适用于tag-a+tag-b or tag-a+tag-c
• tag-d or (tag-e and tag-f) --> 适用于tag-d or tag-e+tag-f

是否存在从一串输入文本中进行这种逻辑解析的工具集？我可以在幕后定义具有一定区别的标签({}、[] 等)，这样它们也可以更容易地被解析出来。

只是想知道最好的方法是将人类可读的文本解析为那些不同的组合集，而无需用户输入每个特定组合。

谢谢!

Answer 1

通常这涉及两个步骤:词法分析(词法分析的缩写)和解析。

在第一步中，输入字符串被转换为一系列词汇项，称为标记。为此，您可以为不同类型的 token 声明一个枚举类型，例如:

public enum TokenType
{
    OpenParenthesis,
    CloseParenthesis,
    And,
    Or,
    Tag
}

还有一个 token 类:

sealed class Token
{
    public TokenType Type { get; private set; }
    public string Item { get; private set; }
    public Token(TokenType type, string item) { Type = type; Item = item; }
}

现在您编写一个算法来转换输入字符串，例如tag-a 和(tag-b 或 tag-c)，变成一系列 Token 实例。您可以使用正则表达式来识别各种项目，例如 @"\s*\(\s*" 将是识别左括号的正则表达式。完成的序列看起来像这个:

• new Token(TokenType.Tag, "tag-a")
• 新 token (TokenType.And, null)
• 新 token (TokenType.OpenParenthesis, null)
• new Token(TokenType.Tag, "tag-b")
• new Token(TokenType.Or, null)
• new Token(TokenType.Tag, "tag-c")
• 新 token (TokenType.CloseParenthesis, null)

一旦你有了这个序列，你需要在它上面运行一个解析器。有很多解析此类表达式的策略；一开始，我向您推荐recursive descent parser .

当然，您需要一些类来包含解析树:

abstract class Node { }
enum BooleanOperator { And, Or }
sealed class BooleanNode : Node
{
    public BooleanOperator Operator { get; private set; }
    public Node Left { get; private set; }
    public Node Right { get; private set; }
    public BooleanNode(BooleanOperator op, Node left, Node right)
    {
        Operator = op;
        Left = left;
        Right = right;
    }
}
sealed class TagNode : Node
{
    public string Tag { get; private set; }
    public TagNode(string tag) { Tag = tag; }
}

然后递归下降解析器可能看起来像这样:

public static Node ParseExpression(Token[] tok)
{
    int i = 0;
    return parseExpressionBoolOr(tok, ref i);
}
private static Node parseExpressionBoolOr(Token[] tok, ref int i)
{
    var left = parseExpressionBoolAnd(tok, ref i);
    while (tok[i].Type == TokenType.Or)
    {
        i++;
        var right = parseExpressionBoolAnd(tok, ref i);
        left = new BooleanNode(BooleanOperator.Or, left, right);
    }
    return left;
}
private static Node parseExpressionBoolAnd(Token[] tok, ref int i)
{
    var left = parseExpressionPrimary(tok, ref i);
    while (tok[i].Type == TokenType.And)
    {
        i++;
        var right = parseExpressionPrimary(tok, ref i);
        left = new BooleanNode(BooleanOperator.And, left, right);
    }
    return left;
}
private static Node parseExpressionPrimary(Token[] tok, ref int i)
{
    if (tok[i].Type == TokenType.OpenParenthesis)
    {
        i++;
        var node = parseExpressionBoolOr(tok, ref i);
        if (tok[i].Type != TokenType.CloseParenthesis)
            throw new InvalidOperationException();  // or customised parse exception
        return node;
    }
    else if (tok[i].Type == TokenType.Tag)
    {
        var node = new TagNode(tok[i].Item);
        i++;
        return node;
    }
    else
        throw new InvalidOperationException();  // or customised parse exception
}

请注意，这是一个大大简化的示例。但是，它具有最大的灵 active :您可以扩展此算法以解析任何您想要的语言。