ExpressionConverter: WPF UniversalConverter

ExpressionConverter.cs

//
// ExpressionConverter
//
// Syntax
//
// Top = '$' CStr | . Expr .
// CStr = cs { '{' . Expr . '}' cs }*
// Expr = Lor . '?' . Expr . ':' . Expr
// Expr = Lor
// Lor = Land { . '||' . Lor }
// Land = Equal { . '&&' . Land }
// Equal = Comp . [ '==' '!=' ] . Comp
// Equal = Comp
// Comp = Shift . [ 'lt' 'le' 'gt' 'ge' ] . Shift
// Comp = Shift
// Shift = Add { . [ 'sl' 'sr' ] . Shift }
// Add =  Mult { . [ '+' '-' ] . Add }
// Mult = Unary { . [ '*' '/' '%' ] . Mult }
// Unary = [ '+' '-' '!' '~' ] . Factor
// Unary = Factor
// Factor = '`' Str '`'
// Factor = '$' '`' CStr '`'
// Factor = '(' . Tuple . ')'
// Factor = Ltrl
// Factor = Id . '(' . Tuple . ')'
// Factor = Id
// Tuple = Expr { . ',' . Tuple }
// Str = '`' s '`'
// FactCStr = '$' '`' CStr '`'
// Id = 'v' 
//

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;

namespace SoloLearn
{
    class Program
    {
        static void Main(string[] args)
        {
            Test("format(`a {0} {1} b)`, 1, 2 )");
            Test("i(2.5)");
            Test("+2");
            Test("1*2");
            Test("1");
            Test("12");
            Test("12.3");
            Test("0x1f");
            Test("#fff");
            Test("v0");
            Test("(1)");
            Test("1==2");
            Test("1 + 2 * 3");
            Test("2 + 3 + 4");
            Test("2 * 3 * 5");
            Test("12 / 3 / 2");
            Test("12 * ( 3 + 2) sl 3");
            Test("1++2");
            Test("1--2");
        }
        
        static void Test(string expr)
        {
            Console.Write(
                $"{expr} = ");
            Console.WriteLine(
                $"{Parser.Parse(expr)?.Eval()}");
        }
    }
    
    public class Parser
    {
        public static AST Parse(string expr)
            => new Parser(expr).Parse();
        
        static readonly Regex reVal = new Regex(@"^v([0-9]+)");
        static readonly Regex reId = new Regex(@"^[a-zA-Z_][a-zA-Z_0-9]*");
        static readonly Regex reHex = new Regex(@"\G0x([0-9a-fA-F]+)");
        static readonly Regex reBin = new Regex(@"\G0b([01]+)");
        static readonly Regex reCol = new Regex(@"\G#([0-9a-fA-F]+)");
        static readonly Regex reNum = new Regex(@"\G(?:0|[1-9][0-9]*)");
        static readonly Regex reDec = new Regex(@"\G[.][0-9]+");

        static class Tokens
        {
            public static char End = '\0';
            
            public static char Lor = MakeToken('|');
            public static char Land = MakeToken('&');
            public static char ShiftL = MakeToken('<');
            public static char ShiftR = MakeToken('>');
            public static char Equal = MakeToken('=');
            public static char NEqual = MakeToken('!');
            public static char LEqual = MakeToken('(');
            public static char GEqual = MakeToken(')');
            
            public static char MakeToken(char c)
                => (char)~(int)c;
        }
        
        string _expr;
        int _pos;
        char _token;
        
        char Token => _token;
        
        //[MethodImpl(MethodImplOptions.NoInlining)]
        void Log()
        {
            //Console.WriteLine($"{new StackFrame(1, true).GetMethod().Name}");
        }

        Parser(string expr)
        {
            _expr = expr;
            _pos = -1;
            Next();
        }
        
        AST Parse()
        {
            var e = Top();
            Consume(Tokens.End);
            return e;
        }

        private Exception Error()
            => new ArgumentException($"syntax errer at {_pos}, {(int)_token}:{_token}");
        
        private void Next()
        {
            _pos = Math.Min(_pos + 1, _expr.Length);
            ReadToken();
        }
        
        private void ReadToken()
        {
            _token = (_pos < _expr.Length) ? _expr[_pos] : Tokens.End;
        }
                
        IEnumerable<char> RepeatToken()
        {
            while (true)
                yield return Token;
        }
       
        [DebuggerStepThrough]
        TR BinaryOperations<TR>(
            char[] ops,
            Func<TR> operand,
            Func<TR, char, TR, TR> operate)
        {
            var acc = operand();
            WS();
            while (Optional(ops, out char op))
            {
                WS();
                acc = operate(acc, op, operand());
                WS();
            }
            return acc;
        }
            
        [DebuggerStepThrough]
        TR BinaryOperations<TR>(
            string[] ops,
            Func<TR> operand,
            Func<TR, string, TR, TR> operate)
        {
            var acc = operand();
            WS();
            while (Optional(ops, out string op))
            {
                WS();
                acc = operate(acc, op, operand());
                WS();
            }
            return acc;
        }
                
        [DebuggerStepThrough]
        TR CompareOperation<TR>(
            char[] ops,
            Func<TR> operand,
            Func<TR, char, TR, TR> operate)
        {
            var lhs = operand();
            WS();
            if (Optional(ops, out char op))
            {
                WS();
                var rhs = operand();
                return operate(lhs, op, rhs);
            }
            return lhs;
        }
                
        [DebuggerStepThrough]
        TR CompareOperation<TR>(
            string[] ops,
            Func<TR> operand,
            Func<TR, string, TR, TR> operate)
        {
            var lhs = operand();
            WS();
            if (Optional(ops, out string op))
            {
                WS();
                var rhs = operand();
                return operate(lhs, op, rhs);
            }
            return lhs;
        }
                
        T[] Any<T>(params T[] tokens)
            => tokens;
        
        bool Match(char token)
            => token == Token;
        
        bool Match(char[] tokens)
            => tokens.Contains(Token);
        
        void Consume(char token)
        {
            if (!Match(token))
                throw Error();
            Next();
        }
        
        void Consume(char[] tokens)
        {
            if (!Match(tokens))
                throw Error();
            Next();
        }
                   
        bool Optional(char token)
        {
            if (!Match(token))
                return false;
            Next();
            return true;
        }
        
        bool Optional(char[] tokens)
        {
            if (!Match(tokens))
                return false;
            Next();
            return true;
        }
        
        bool Optional(char[] ops, out char op)
        {
            op = Token;
            if (!Match(ops))
                return false;
            Next();
            return true;
        }
        
        bool Optional(string[] ops, out string op)
        {
            string op_;
            op = op_ = "" + Token;
            if (!ops.Any(x => x.StartsWith(op_)))
                return false;
            Next();
            if (ops.Contains(op_))
                return true;
            op = op_ += Token;
            Next();
            if (ops.Contains(op_))
                return true;
            throw Error();
        }
        
        void WS()
        {
            bool isWhiteSpace(char c)
                => Any(' ', '\r', '\n', '\t').Contains(c);
            
            RepeatToken()
                .TakeWhile(isWhiteSpace)
                .ForEach(_ => Next());
        }

        // Top = '$' CStr | . Expr .
        AST Top()
        {
            Log();
            if (Optional('$'))
            {
                return CStr();
            }
            else
            {
                WS();
                var e = Expr();
                WS();
                return e;
            }
        }
        
        // CStr = cs { '{' . Expr . '}' cs }*
        AST CStr()
        {
            Log();
            var strs = new List<string>();
            var exps = new List<AST>();
            strs.Add(CS());
            while (Optional('{'))
            {
                WS();
                exps.Add(Expr());
                WS();
                Consume('}');
                strs.Add(CS());
            }
            return AST.CStr(strs, exps);
        }
        
        // Expr = Lor . '?' . Expr . ':' . Expr
        // Expr = Lor
        AST Expr()
        {
            Log();
            var e1 = Lor();
            WS();
            
            if (Optional('?'))
            {
                WS();
                var e2 = Expr();
                WS();
                Consume(':');
                WS();
                var e3 = Expr();
                return AST.Cond(e1, e2, e3);
            }
                        
            return e1;
        }

// Lor = Land { . '||' . Lor }
        AST Lor()
        {
            Log();
            return BinaryOperations(
                Any("||"),
                Land,
                (l, op, r) => AST.Lor(l, r));
        }
        
// Land = Equal { . '&&' . Land }
        AST Land()
        {
            Log();
            return  BinaryOperations(
                Any("&&"),
                Equal,
                (l, op, r) => AST.Land(l, r));
        }

// Equal = Comp . [ '==' '=' '!=' ] . Comp
// Equal = Comp
        AST Equal()
        {
            Log();
            return CompareOperation(
                Any("==", "!="),
                () => Comp(),
                (lhs, op, rhs) =>
                    (op == "!=") ?
                        AST.NEqual(lhs, rhs) :
                        AST.Equal(lhs, rhs));
        }
        
// Comp = Shift . [ 'lt' 'le' 'gt' 'ge' ] . Shift
// Comp = Shift
        AST Comp()
        {
            Log();
            return CompareOperation(
                Any("lt", "le", "gt", "ge"),
                () => Shift(),
                (lhs, op, rhs) =>
                    (op == "lt") ?
                        AST.Less(lhs, rhs) :
                    (op == "le") ?
                        AST.LEqual(lhs, rhs) :
                    (op == "gt") ?
                        AST.Greater(lhs, rhs) :
                    AST.GEqual(lhs, rhs));
        }

// Shift = Add { . [ 'sl' 'sr' ] . Shift }
        AST Shift()
        {
            Log();
            return BinaryOperations(
                Any("sl", "sr"),
                Add,
                (l, op, r) =>
                    op == "sl" ?
                        AST.ShiftL(l, r) :
                    AST.ShiftR(l, r));
        }

// Add =  Mult { . [ '+' '-' ] . Add }
        AST Add()
        {
            Log();
            return BinaryOperations(
                Any('+', '-'),
                Mult,
                (l, op, r) =>
                    op == '+' ? AST.Add(l, r) :
                    AST.Sub(l, r));
        }

// Mult = Unary { . [ '*' '/' '%' ] . Mult }
        AST Mult()
        {
            Log();
            return BinaryOperations(
                Any('*', '/', '%'),
                Unary,
                (l, op, r) =>
                    op == '*' ? AST.Mult(l, r) :
                    op == '/' ? AST.Div(l, r) :
                    AST.Mod(l, r));
        }

// Unary = [ '+' '-' '!' '~' ] . Factor
// Unary = Factor
        AST Unary()
        {
            Log();
            var t = Token;
            if (Optional(Any('+', '-', '!', '~')))
            {
                WS();
                var f = Factor();
                switch (t)
                {
                    case '+':
                        return AST.Plus(f);
                    case '-':
                        return AST.Minus(f);
                    case '!':
                        return AST.Negate(f);
                    case '~':
                        return AST.Compliment(f);
                }
            }
            return Factor();
        }
        
// Factor = '`' Str '`'
// Factor = '$' '`' CStr '`'
// Factor = '(' . Expr . ')'
// Factor = '(' . Expr { . ',' . Expr }+ . ')'
// Factor = Value
// Factor = Ltrl
// Factor = Id . '(' . ')'
// Factor = Id . '(' . Expr { . ',' . Expr }+ . ')'
        AST Factor()
        {
            Log();
            var t = Token;
            switch (t)
            {
                case '`':
                {
                    Next();
                    var s = Str();
                    Consume('`');
                    return AST.Const(s);
                }
                case '$':
                {
                    Next();
                    Consume('`');
                    var s = CStr();
                    Consume('`');
                    return s;
                }
                case '(':
                {
                    Next();
                    WS();
                    var e = Expr();
                    WS();
                    if (Token != ',')
                    {
                        Consume(')');
                        return e;
                    }
                    var list = new List<AST>();
                    list.Add(e);
                    while (Optional(','))
                    {
                        WS();
                        list.Add(Expr());
                        WS();
                    }
                    Consume(')');
                    return e;
                }
            }
            if (TryLiteral(out var lit))
            {
                return AST.Const(lit);
            }
            if (TryValue(out var vid))
            {
                return AST.Value(vid);
            }
            if (TryId(out var id))
            {
                WS();
                Consume('(');
                WS();
                var list = new List<AST>();
                if (Optional(')'))
                {
                    return AST.Func(id, list);
                }
                list.Add(Expr());
                WS();
                while (Optional(','))
                {
                    WS();
                    list.Add(Expr());
                    WS();
                }
                Consume(')');
                return AST.Func(id, list);
            }
            throw Error();
        }
        
        string CS()
        {
            Log();
            var sb = new StringBuilder();
            int p = _pos;
            int len = _expr.Length;
            
            char curr()
                => p == len ? Tokens.End : _expr[p];
            char next()
                => p + 1 >= len ? Tokens.End : _expr[p + 1];
            
            while(p < len)
            {
                var c = curr();
                switch (c)
                {
                    case '`':
                    case '{':
                        if (next() != c) goto accept;
                        p++;
                        break;
                    case '}':
                        if (next() != c)
                        {
                            _pos = p;
                            throw Error();
                        }
                        break;
                }
                sb.Append(c);
                p++;
            }
            
            accept:
            _pos = p;
            ReadToken();
            return sb.ToString();
            
        }
        
// Str = '`' s '`'
        string Str()
        {
            Log();
            var sb = new StringBuilder();
            int p = _pos;
            int len = _expr.Length;
            
            char curr()
                => p == len ? Tokens.End : _expr[p];
            char next()
                => p + 1 >= len ? Tokens.End : _expr[p + 1];
            
            while(p < len)
            {
                var c = curr();
                switch (c)
                {
                    case '`':
                        if (next() != c) goto accept;
                        p++;
                        break;
                }
                sb.Append(c);
                p++;
            }
            
            accept:
            _pos = p;
            ReadToken();
            return sb.ToString();
        }
        
// Id = 'v' 
        bool TryValue(out int id)
        {
            Log();
            
            var m = reVal.Match(_expr, _pos);
            if (!m.Success)
            {
                id = 0;
                return false;
            }
            
            _pos += m.Value.Length;
            ReadToken();
            id = int.Parse(m.Groups[1].Value);
            return true;
        }

        bool TryId(out string id)
        {
            Log();
            
            var m = reId.Match(_expr, _pos);
            if (!m.Success)
            {
                id = null;
                return false;
            }
            
            _pos += m.Value.Length;
            ReadToken();
            id = m.Value;
            return true;
        }

// int = /0|[1-9][0-9]*/
// hex = /0x[0-9a-fA-F]+/
// bin = /0b[01]+/
// col = /#[0-9a-fA-F]+/
// real = /(0|[1-9][0-9]*)(\.[0-9]+)?/
        bool TryLiteral(out object lit)
        {
            Log();
            
            Match m;
            if ((m = reHex.Match(_expr, _pos)).Success)
            {
                var v = m.Value;
                _pos += v.Length;
                ReadToken();
                lit = Convert.ToInt32(v, 16);
                return true;
            }
            if ((m = reBin.Match(_expr, _pos)).Success)
            {
                var v = m.Value;
                _pos += v.Length;
                ReadToken();
                lit = Convert.ToInt32(v, 2);
                return true;
            }
            if ((m = reCol.Match(_expr, _pos)).Success)
            {
                var v = m.Value;
                _pos += v.Length;
                ReadToken();
                lit = System.Drawing.ColorTranslator.FromHtml(v).ToArgb();
                return true;
            }
            if ((m = reNum.Match(_expr, _pos)).Success)
            {
                var n = m.Value;
                _pos += n.Length;
                if ((m = reDec.Match(_expr, _pos)).Success)
                {
                    var d = m.Value;
                    _pos += d.Length;
                    ReadToken();
                    lit = decimal.Parse(n + d);
                    return true;
                }
                lit = int.Parse(n);
                ReadToken();
                return true;
            }
            lit = null;
            return false;
        }
    }
    
    public interface IAST
    {
        dynamic Eval();
    }
    
    public class AST : IAST
    {
        Func<dynamic> _eval;
        
        AST(Func<dynamic> eval)
        {
            _eval = eval;
        }
        
        public dynamic Eval() => _eval();
        
        private static Exception Error()
            => new ArgumentException($"syntax errer");

        public static AST CStr(List<string> ss, List<AST> es) => new AST(() =>
        {
            if (!ss.Any()) return null;
            var sb = new StringBuilder();
            sb.Append(ss.First());
            ss.Skip(1)
                .Zip(es, (s, e) => (s: s, e: e))
                .ForEach(zip =>
                {
                    sb.Append(zip.e.Eval());
                    sb.Append(zip.s);
                });
            return sb.ToString();
        });
        
        public static AST Cond(AST e, AST t, AST f) => new AST(() =>
        {
            dynamic b = e.Eval();
            return (b == true) ? t.Eval() : f.Eval();
        });
        
        public static AST Lor(AST l, AST r) => new AST(() => l.Eval() || r.Eval());

        public static AST Land(AST l, AST r) => new AST(() => l.Eval() && r.Eval());

        public static AST Bor(AST l, AST r) => new AST(() => l.Eval() | r.Eval());

        public static AST Bxor(AST l, AST r) => new AST(() => l.Eval() ^ r.Eval());

        public static AST Band(AST l, AST r) => new AST(() => l.Eval() & r.Eval());

        public static AST Equal(AST l, AST r) => new AST(() => l.Eval() == r.Eval());

        public static AST NEqual(AST l, AST r) => new AST(() => l.Eval() != r.Eval());

        public static AST Less(AST l, AST r) => new AST(() => l.Eval() < r.Eval());
        
        public static AST LEqual(AST l, AST r) => new AST(() => l.Eval() <= r.Eval());

        public static AST Greater(AST l, AST r) => new AST(() => l.Eval() > r.Eval());

        public static AST GEqual(AST l, AST r) => new AST(() => l.Eval() >= r.Eval());

        public static AST ShiftL(AST l, AST r) => new AST(() => l.Eval() << r.Eval());

        public static AST ShiftR(AST l, AST r) => new AST(() => l.Eval() >> r.Eval());

        public static AST Add(AST l, AST r) => new AST(() => l.Eval() + r.Eval());

        public static AST Sub(AST l, AST r) => new AST(() => l.Eval() - r.Eval());

        public static AST Mult(AST l, AST r) => new AST(() => l.Eval() * r.Eval());

        public static AST Div(AST l, AST r) => new AST(() => l.Eval() / r.Eval());

        public static AST Mod(AST l, AST r) => new AST(() => l.Eval() % r.Eval());

        public static AST Plus(AST r) => new AST(() => +r.Eval());

        public static AST Minus(AST r) => new AST(() => -r.Eval());

        public static AST Negate(AST r) => new AST(() => !r.Eval());

        public static AST Compliment(AST r) => new AST(() => ~r.Eval());

        public static AST Const<T>(T v) => new AST(() => v);

        public static AST Func(string id, List<AST> list)
        {
            switch (id)
            {
                case "i":
                    if (list.Count != 1) throw Error();
                    return new AST(() => (int)list[0].Eval());
                case "format":
                    if (list.Count == 0) throw Error();
                    return new AST(() => string.Format(
                        list[0].Eval(),
                        list.Skip(1).Select(x => x.Eval()).ToArray()));
                default:
                    throw Error();
            }
        }

        public static AST Tuple(List<AST> list) => null;
        
        public static AST Value(int id) => null;
    }
    
    public static class EnumrableEx
    {
        public static IEnumerable<T> Do<T>(
            this IEnumerable<T> source, Action<T> action)
        {
            foreach (var item in source)
            {
                action(item);
                yield return item;
            }
        }
        
        public static void ForEach<T>(
            this IEnumerable<T> source, Action<T> action)
        {
            foreach (var item in source)
            {
                action(item);
            }
        }
        
        public static void ForEach<T>(
            this IEnumerable<T> source, Action<T, int> action)
        {
            int index = 0;
            foreach (var item in source)
            {
                action(item, index++);
            }
        }
    }
}