如何解析人类输入的逻辑属性,例如this和(那个或那个)？

Question

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

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

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

是否存在工具集来从一个输入文本字符串中解析这种逻辑？我可以用一定的区别({},[]等)定义幕后的标签,这样它们也可以更容易地解析出来.

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

谢谢!

Answer 1

通常,这涉及两个步骤:lexing(词法分析的简称)和解析.

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

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

和一个令牌类:

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 and (tag-b or tag-c)转换为一系列Token实例.您可以使用正则表达式来识别各种项目,例如@"\s*\(\s*",可以使用正则表达式来识别开括号.完成的序列看起来像这样:

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

完成此序列后,需要在其上运行解析器.解析像这样的表达式有很多策略; 一开始,我向你推荐递归下降解析器.

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

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
}

请注意,这是一个非常简化的示例.但是,它最灵活:您可以扩展此算法以完全解析您想要的任何语言.