6

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

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

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

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

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

谢谢！

4

1 回答 1

7

通常这涉及两个步骤：词法分析（词法分析的缩写）和解析。

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

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
}

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

于 2012-09-17T18:58:04.423 回答