6

今後のプロジェクトの一環として、特定のドメイン オブジェクトをタグまたはタグの組み合わせに適用できるように設定したいと考えています。

次のように、ユーザーがこれらの組み合わせを人間が読める方法で入力できるようにしたいと思います。

  • 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 に適用されます

入力されたテキストの 1 つの文字列からこの種のロジック解析を行うためのツールセットは存在しますか? バックグラウンドでタグを特定の区別 ({}、[] など) で定義して、より簡単に解析できるようにすることもできます。

ユーザーが特定の組み合わせを入力しなくても、人間が読めるテキストをそれらの異なる組み合わせのセットに解析するのが最善の方法であると思っています。

ありがとう！

4

1 に答える 1

7

通常、これにはlexing ( lexical analysisの略) とparsingの2 つのステップが含まれます。

最初のステップでは、入力文字列がtokensと呼ばれる字句項目のシーケンスに変換されます。この目的のために、さまざまなタイプのトークンの列挙型を宣言できます。たとえば、次のようになります。

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 に答える