0

例として、「(3+2*(4+5)+2)+1」のように括弧が多重に含まれる式を正しくパースするにはどのようにすればよいでしょうか?
Expression型のパーサにより、上記のような文字列で与えられた式をラムダ式にパースしたいのですが、Spracheによって括弧をどのように処理すればよいのか見当がつきません

概念的には
・一番優先度の低い演算子を見つけ、左右の項を評価し、演算子を適用するExpressionを返す関数を用意
・左右の項の評価には上記の関数を使用し、再帰的に評価していく
という流れで実装できるのだろうと理解していますが、「(3+2*(4+5)+2)」+「1」という風に適切な位置の演算子を見つける方法がわかりません。

演算子を見つける際に括弧に囲まれた位置の演算子をスキップする方法がわからないため、下記のような括りだし方になってしまいます。
「(3」+「2*(4+5)+2)」

よい方法を教えていただけないでしょうか?

(※一応Spracheを使用せずに自前で書いた実装では上記のような式もパース出来たのですが、より簡便にライブラリを使用した実装を行いたく、Spracheを利用しての実装を試みております。
Spracheの他によい構文解析のライブラリがあればそちらをご教授いただく形でも問題ありません。)

2 件の回答 2

1

公式のサンプルに既に存在するので、そちらを参照すればよいのですが、一応自分なりの解説をしておきます。

ここを参考に、提示の例を解析する最低限のBNFを書くと、以下のようになります。

<expr>   ::= <term> [ '+' <term> ]*
<term>   ::= <factor> [ '*' <factor> ]*
<factor> ::= <number> | '(' <expr> ')'
<number> :== 1つ以上の数字

<factor>内の<expr>部分が、括弧の処理になります。

あとは、公式からたどれるドキュメントを参考にSpracheで表現すると、以下になります。

using Sprache;

Console.WriteLine(Calculator.Expr.Parse("(3+2*(4+5)+2)+1"));

static class Calculator
{
    static Parser<int> Factor =
        (from lparen in Parse.Char('(')
         from expr in Expr
         from rparen in Parse.Char(')')
         select expr).XOr(Parse.Number.Select(int.Parse));
    static Parser<int> Term = Parse.ChainOperator(Parse.Char('*'), Factor, (op, left, right) => left * right);
    public static Parser<int> Expr = Parse.ChainOperator(Parse.Char('+'), Term, (op, left, right) => left + right);
}

構造を示すのが目的なので、単に解釈と同時に計算する実装としています。

1
  • ありがとうございます!提示していただいた公式のサンプルを見て解決いたしました!(自分の調査不足でした、すいません……)
    – spi8823
    Commented 2021年12月3日 15:48
0

いただいた回答で解決いたしました
&&等比較演算子も含めた自分なりの完全なコードを書きましたのでメモとして追記しておきます

    public static void Test()
    {
        var expression = logicalParser.Parse("5*(1 -2)>0 && true && b");
        var result = Expression.Lambda<Func<bool>>(expression).Compile().Invoke();
    }

    private static Dictionary<string, object> dictionary = new Dictionary<string, object>()
    {
        {"b", true },
        {"i", 4 },
    };

    private static T GetOrAddValue<T>(string key) where T : struct
    {
        if (dictionary.TryGetValue(key, out var value))
        {
            if (value is T t)
                return t;
            else
                return default(T);
        }
        else
        {
            var addValue = default(T);
            dictionary.Add(key, addValue);
            return addValue;
        }
    }
                

    private static Parser<ExpressionType> addParser = from op in Char('+').Token() select ExpressionType.Add;
    private static Parser<ExpressionType> subtractParser = from op in Char('-').Token() select ExpressionType.Subtract;
    private static Parser<ExpressionType> multiplyParser = from op in Char('*').Token() select ExpressionType.Multiply;
    private static Parser<ExpressionType> divideParser = from op in Char('/').Token() select ExpressionType.Divide;
    private static Parser<ExpressionType> moduloParser = from op in Char('%').Token() select ExpressionType.Modulo;

    private static Parser<ExpressionType> equal = from op in String("==").Token() select ExpressionType.Equal;
    private static Parser<ExpressionType> notEqual = from op in String("!=").Token() select ExpressionType.NotEqual;
    private static Parser<ExpressionType> greater = from op in String(">").Token() select ExpressionType.GreaterThan;
    private static Parser<ExpressionType> greaterOrEqual = from op in String(">=").Token() select ExpressionType.GreaterThanOrEqual;
    private static Parser<ExpressionType> less = from op in String("<").Token() select ExpressionType.LessThan;
    private static Parser<ExpressionType> lessOrEqual = from op in String("<=").Token() select ExpressionType.LessThanOrEqual;

    private static Parser<ExpressionType> andParser = from op in String("&&").Token() select ExpressionType.AndAlso;
    private static Parser<ExpressionType> orParser = from op in String("||").Token() select ExpressionType.OrElse;

    private static Parser<Expression> bracketParser = from open in Char('(').Token()
                                                      from content in Ref(() => logicalParser)
                                                      from close in Char(')').Token()
                                                      select content;


    private static Parser<Expression> digitParser = from digits in Digit.AtLeastOnce().Token().Text()
                                                    select Expression.Constant(int.Parse(digits));
    private static Parser<Expression> trueParser = from str in String("true").Token()
                                                   select Expression.Constant(true);
    private static Parser<Expression> falseParser = from str in String("false").Token()
                                                    select Expression.Constant(false);
    private static Parser<Expression> constantParser = digitParser.Or(trueParser).Or(falseParser);
    private static Parser<Expression> boolValueParser = (from key in Letter.AtLeastOnce().Token().Text().Except(String("true").Or(String("false")))
                                                           select Expression.Constant(GetOrAddValue<bool>(key))).Or(trueParser).Or(falseParser);
    private static Parser<Expression> digitValueParser = (from key in Letter.AtLeastOnce().Token().Text().Except(String("true").Or(String("false")))
                                                          select Expression.Constant(GetOrAddValue<int>(key))).Or(digitParser);

    private static Parser<Expression> arithmetic1Parser = ChainOperator(addParser.Or(subtractParser).Or(moduloParser), constantParser.Or(bracketParser).Or(digitValueParser), Expression.MakeBinary);
    private static Parser<Expression> arithmetic2Parser = ChainOperator(multiplyParser.Or(divideParser).Or(moduloParser), arithmetic1Parser.Or(digitValueParser), Expression.MakeBinary);
    private static Parser<Expression> comparisonParser = ChainOperator(equal.Or(notEqual).Or(greater).Or(greaterOrEqual).Or(less).Or(lessOrEqual), arithmetic2Parser.Or(digitValueParser), Expression.MakeBinary);
    private static Parser<Expression> logicalParser = ChainOperator(andParser.Or(orParser), boolValueParser.Or(comparisonParser), Expression.MakeBinary);

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。