83856


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

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

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

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

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


CC BY-SA 4.0
2021-11-28T12:05:23.817
83849
2021-12-03T15:52:21.160
2021-11-28T12:23:19.953
35121
35121
question
c#
C#のSpracheパッケージで括弧を2つ以上含むある程度複雑な式をパースする方法


[公式のサンプル](https://github.com/sprache/Sprache/blob/develop/samples/LinqyCalculator/ExpressionParser.cs)に既に存在するので、そちらを参照すればよいのですが、一応自分なりの解説をしておきます。

[ここ](https://dai1741.github.io/maximum-
algo-2012/docs/parsing/)を参考に、提示の例を解析する最低限のBNFを書くと、以下のようになります。

[code]

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

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

あとは、[公式](https://github.com/sprache/Sprache)からたどれるドキュメントを参考にSpracheで表現すると、以下になります。

[code]

    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);
    }
    
[/code]

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


CC BY-SA 4.0
2021-11-28T20:27:45.103
83856
2021-11-29T11:41:06.867
2021-11-29T11:41:06.867
43506
43506
83849
answer


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

[code]

        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);
    
[/code]


CC BY-SA 4.0
2021-12-03T15:52:21.160
83947
2021-12-03T15:52:21.160
35121
83849
answer