LL(1) Recursive Descent Parser

ASTGeneratorAndEvaluator.cs

//
// AST Generator & Evaluator
//   based on Recursive Descent Parser without back-tracking
//
// Syntax
//
// E := T { [ '+' '-'' ] E }
// T := U { [ '*' '/' '%' ] T }
// U := [ '+' '-' '' ] F
// F := '(' E ')' | [ '0' '1' ... '9' ]
//

using System;
using System.Linq;

namespace SoloLearn
{
    class Program
    {
        static void Main(string[] args)
        {
            var perser = new ExprParser();
            var expr = Console.ReadLine();
            if (!string.IsNullOrEmpty(expr))
            {
                ExprTree ast = perser.Parse(expr);
                dynamic result = ast.Eval();
                Console.WriteLine($"Result: {result}");
            }
        }
    }
    
    public class ExprParser
    {
        private const char End = '\0';
        
        private class Context
        {
            private string _expr;
            private int _pos;
            
            public char Token
                => _expr
                    .Skip(_pos)
                    .DefaultIfEmpty(End)
                    .First();
            
            public Context(string expr)
            {
                _expr = expr;
                _pos = expr
                    .TakeWhile(x => x == ' ')
                    .Count();
            }
     
            public void NextToken()
            {
                _pos = Math.Min(_pos + 1, _expr.Length);
                _pos += _expr
                    .Skip(_pos)
                    .TakeWhile(x => x == ' ')
                    .Count();
            }
        }
        
        public ExprTree Parse(string expr)
        {
            var ctx = new Context(expr);
            var ast = new ExprTree();
            
            E(ctx, ast);
            
            if (ctx.Token != End) throw Error();
            
            ast.Flatten();
            
            return ast;
        }
                
        private Exception Error()
            => new ArgumentException("syntax errer");
        
        private INode E(Context ctx, ExprTree ast)
        {
            var acc = T(ctx, ast);
            while (true)
            {
                switch (ctx.Token)
                {
                    case '+':
                        ctx.NextToken();
                        acc = ast.Add(acc, E(ctx, ast));
                        break;
                        
                    case '-':
                        ctx.NextToken();
                        acc = ast.Subtract(acc, E(ctx, ast));
                        break;
                        
                    default:
                        return acc;
                }
            }
        }
        
        private INode T(Context ctx, ExprTree ast)
        {
            var acc = U(ctx, ast);
            while (true)
            {
                switch (ctx.Token)
                {
                    case '*':
                        ctx.NextToken();
                        acc = ast.Multiply(acc, T(ctx, ast));
                        break;
                        
                    case '/':
                        ctx.NextToken();
                        acc = ast.Divide(acc, T(ctx, ast));
                        break;
                        
                    case '%':
                        ctx.NextToken();
                        acc = ast.Modulo(acc, T(ctx, ast));
                        break;
                        
                    default:
                        return acc;
                }
            }
        }
        
        private INode U(Context ctx, ExprTree ast)
        {
            var t = ctx.Token;
            switch (ctx.Token)
            {
                case '+':
                case '-':
                    ctx.NextToken();
                    break;
            }
            
            var v = F(ctx, ast);
            
            if (t == '-') v = ast.Negate(v);
            
            return v;
        }
        
        private INode F(Context ctx, ExprTree ast)
        {
            switch (ctx.Token)
            {
                case '(':
                    {
                        ctx.NextToken();
                        var v = E(ctx, ast);
                        if (ctx.Token != ')') throw Error();
                        ctx.NextToken();
                        return v;
                    }
                    
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    {
                        var v = ast.Constant(ctx.Token - '0');
                        ctx.NextToken();
                        return v;
                    }
                    
                default:
                    throw Error();
            }
        }
    }
    
    public interface INode
    {
        dynamic Eval(ExprTree.Context ctx);
    }
    
    public class ExprTree
    {
        private INode _root;
        
        public class Context
        {}
    
        public ExprTree()
        {}
        
        public void Flatten()
        {}
        
        //
        // TODO: Impliment without recursion.
        //
        public dynamic Eval()
        {
            var ctx = new Context();
            return _root.Eval(ctx);
        }
        
        public INode Add(INode a, INode b)
            => _root = new AddNode(a, b);
        
        public INode Subtract(INode a, INode b)
            => _root = new SubtractNode(a, b);
        
        public INode Multiply(INode a, INode b)
            => _root = new MultiplyNode(a, b);
        
        public INode Divide(INode a, INode b)
            => _root = new DivideNode(a, b);
        
        public INode Modulo(INode a, INode b)
            => _root = new ModuloNode(a, b);
        
        public INode Negate(INode a)
            => _root = new NegateNode(a);
        
        public INode Constant(int c)
            => _root = new ConstantNode(c);
        
        private abstract class Binary
        {
            public INode A { get; }
            public INode B { get; }
            
            public Binary(INode a, INode b)
            {
                A = a;
                B = b;
            }
        }
        
        private abstract class Unary
        {
            public INode A { get; }
            
            public Unary(INode a)
            {
                A = a;
            }
        }
        
        private class AddNode : Binary, INode
        {
            public AddNode(INode a, INode b)
                : base(a, b)
            {}
            
            public dynamic Eval(Context ctx)
                => A.Eval(ctx) + B.Eval(ctx);
        }
        
        private class SubtractNode : Binary, INode
        {
            public SubtractNode(INode a, INode b)
                : base(a, b)
            {}
            
            public dynamic Eval(Context ctx)
                => A.Eval(ctx) - B.Eval(ctx);
        }
        
        private class MultiplyNode : Binary, INode
        {
            public MultiplyNode(INode a, INode b)
                : base(a, b)
            {}
            
            public dynamic Eval(Context ctx)
                => A.Eval(ctx) * B.Eval(ctx);
        }
        
        private class DivideNode : Binary, INode
        {
            public DivideNode(INode a, INode b)
                : base(a, b)
            {}
            
            public dynamic Eval(Context ctx)
                => A.Eval(ctx) / B.Eval(ctx);
        }
        
        private class ModuloNode : Binary, INode
        {
            public ModuloNode(INode a, INode b)
                : base(a, b)
            {}
            
            public dynamic Eval(Context ctx)
                => A.Eval(ctx) % B.Eval(ctx);
        }
        
        private class NegateNode : Unary, INode
        {
            public NegateNode(INode a)
                : base(a)
            {}
            
            public dynamic Eval(Context ctx)
                => -A.Eval(ctx);
        }
        
        private class ConstantNode : INode
        {
            public dynamic C { get; }
            
            public ConstantNode(int c)
            {
                C = (decimal)c;
            }
            
            public dynamic Eval(Context ctx) => C;
        }
    }
}

ExprCalculator.cs

//
// Recursive Descent Parser
//     without back-tracking
//
// Syntax
//
// E := T { [ '+' '-'' ] E }
// T := U { [ '*' '/' '%' ] T }
// U := [ '+' '-' '' ] F
// F := '(' E ')' | [ '0' '1' ... '9' ]
//

using System;
using System.Linq;

namespace SoloLearn
{
    class Program
    {
        static void Main(string[] args)
        {
            var calculator = new Calculator();
            var expr = Console.ReadLine();
            if (!string.IsNullOrEmpty(expr))
            {
                var result = calculator.Calc(expr);
                Console.WriteLine($"Result: {result}");
            }
        }
    }
    
    class Calculator
    {
        private const char End = '\0';
        
        private string _expr;
        private int _pos;
        
        private char Token
            => _expr
                .Skip(_pos)
                .DefaultIfEmpty(End)
                .First();
        
        public int Calc(string expr)
        {
            Initialize(expr);
            
            var v = E();
            
            if (Token != End) throw Error();
            
            return v;
        }
        
        private void Initialize(string expr)
        {
            _expr = expr;
            _pos = expr
                .TakeWhile(x => x == ' ')
                .Count();
        }
        
        private void NextToken()
        {
            _pos = Math.Min(_pos + 1, _expr.Length);
            _pos += _expr
                .Skip(_pos)
                .TakeWhile(x => x == ' ')
                .Count();
        }
        
        private Exception Error()
            => new ArgumentException("syntax errer");
        
        private int E()
        {
            var acc = T();
            while (true)
            {
                switch (Token)
                {
                    case '+':
                        NextToken();
                        acc += E();
                        break;
                        
                    case '-':
                        NextToken();
                        acc -= E();
                        break;
                        
                    default:
                        return acc;
                }
            }
        }
        
        private int T()
        {
            var acc = U();
            while (true)
            {
                switch (Token)
                {
                    case '*':
                        NextToken();
                        acc *= T();
                        break;
                        
                    case '/':
                        NextToken();
                        acc /= T();
                        break;
                        
                    case '%':
                        NextToken();
                        acc %= T();
                        break;
                        
                    default:
                        return acc;
                }
            }
        }
        
        private int U()
        {
            var t = Token;
            switch (Token)
            {
                case '+':
                case '-':
                    NextToken();
                    break;
            }
            
            var v = F();
            
            if (t == '-') v = -v;
            
            return v;
        }
        
        private int F()
        {
            switch (Token)
            {
                case '(':
                    {
                        NextToken();
                        var v = E();
                        if (Token != ')') throw Error();
                        NextToken();
                        return v;
                    }
                    
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    {
                        var v = Token - '0';
                        NextToken();
                        return v;
                    }
                    
                default:
                    throw Error();
            }
        }
    }
}