Documentation

This is a fast and clean look of what the library is, helping you to understand the whole library:

Examples

This is an example of the expression grammar notation and its implementation

Expressions

E ← T | T Eopt
T ← F | F Topt
F ← N | '(' E ')'
N ← '0' | '1'
Eopt ← '+' E | '-' E 
Topt ← '*' T | '/' T

Implementaton

Implementation consists of two phases :
  • grammar definiton
  • function definiton
Grammar definiton is very simple & pretty straight-forward, since it only requres the proper grammar of the language to defined (preferabyl LL(1), but this is not the strict rule).

Terminals

        internal static Terminal<char>[] _ = { '(', ')', '+', '-', '*', '/' };

Nonterminals

        internal static Nonterminal<char> E = "E[t]";
        internal static Nonterminal<char> Eopt = "E'[t]";
        internal static Nonterminal<char> T = "T[t]";
        internal static Nonterminal<char> Topt = "T'[t]";
        internal static Nonterminal<char> F = "F[t]";
        internal static Nonterminal<char> N = "N[t]";

Grammar

        static Nonterminals()
        {
            E.Definition = new Rules<char>
            {
                () => T[false] + Eopt[true]
            };
            T.Definition = return new Rules<char>
            {
                () => F[false] + Topt[true]
            };
            Eopt.Definition = new Rules<char>
            {
                () => '+' + T[false] + Eopt[true],
                () => '-' + T[false] + Eopt[true]
            };
            Topt.Definition = new Rules<char>
            {
                () => '*' + F[false] + Topt[true],
                () => '/' + F[false] + Topt[true],
            };
            F.Definition = return new Rules<char>
            {
                () => N[false],
                () => '(' + E[false] + ')'
            };
            N.Definition = return new Rules<char>
            {
                () => '0',
                () => '1'
            };
        }

AST

        internal static Expression<char, Expression> E = "E[t]";
        internal static Expression<char, Expression> Eopt = "E'[t]";
        internal static Expression<char, Expression> T = "T[t]";
        internal static Expression<char, Expression> Topt = "T'[t]";
        internal static Expression<char, Expression> F = "F[t]";

        static Expressions()
        {
            E.Eval = (a, b) =>
            {
                if (b[0].Context.Token.Equals(Nonterminals.T) && (b[1] == null || b[1].Context.Token.Equals(Nonterminals.Eopt)))
                {
                    return Eopt[T[a, b[0]], b[1]];
                }
                throw new NotSupportedException("Input token is not supported");
            };
            T.Eval = (a, b) =>
            {
                if (b[0].Context.Token.Equals(Nonterminals.F) && (b[1] == null || b[1].Context.Token.Equals(Nonterminals.Topt)))
                {
                    return Topt[F[a, b[0]], b[1]];
                }
                throw new NotSupportedException("Input token is not supported");
            };
            Eopt.Eval = (a, b) =>
            {
                if (b[0].Context.Token.Equals('+') && b[1].Context.Token.Equals(Nonterminals.T) && (b[2] == null || b[2].Context.Token.Equals(Nonterminals.Eopt)))
                {
                    return Eopt[new Plus(a, T[a, b[1]]), b[2]];
                }
                if (b[0].Context.Token.Equals('-') && b[1].Context.Token.Equals(Nonterminals.T) && (b[2] == null || b[2].Context.Token.Equals(Nonterminals.Eopt)))
                {
                    return Eopt[new Minus(a, T[a, b[1]]), b[2]];
                }
                throw new NotSupportedException("Input token is not supported");
            };
            Topt.Eval = (a, b) =>
            {
                if (b[0].Context.Token.Equals('*') && b[1].Context.Token.Equals(Nonterminals.F) && (b[2] == null || b[2].Context.Token.Equals(Nonterminals.Topt)))
                {
                    return Topt[new Mul(a, F[a, b[1]]), b[2]];
                }
                if (b[0].Context.Token.Equals('/') && b[1].Context.Token.Equals(Nonterminals.F) && (b[2] == null || b[2].Context.Token.Equals(Nonterminals.Topt)))
                {
                    return Topt[new Div(a, F[a, b[1]]), b[2]];
                }
                throw new NotSupportedException("Input token is not supported");
            };
            F.Eval = (a, b) =>
            {
                if (b[0].Context.Token.Equals(Nonterminals.N))
                {
                    return new Number(b[0].Context.ToString());
                }
                if (b[0].Context.Token.Equals('(') && b[1].Context.Token.Equals(Nonterminals.E) && b[2].Context.Token.Equals(')'))
                {
                    return new Group(E[a, b[1]]);
                }
                throw new NotSupportedException("Input token is not supported");
            };
        }

Classes

Tree classes doing the all the magic
  • Expression
  • Group
  • Plus
  • Minus
  • Mul
  • Div
  • Number

Expression

    public abstract class Expression
    {
        private readonly List<Expression> _children;

        public abstract double Eval();

        internal void Add(Expression expression)
        {
            _children.Add(expression);
        }
        internal void AddRange(IEnumerable<Expression> expressions)
        {
            _children.AddRange(expressions);
        }
        protected Expression()
        {
            _children = new List<Expression>();
        }
        internal IEnumerable<Expression> Children
        {
            get
            {
                return _children;
            }
        }
        public static implicit operator double(Expression value)
        {
            return value.Eval();
        }
    }

Group

    internal class Group : Expression
    {
        private Expression _expression;

        public Group(Expression expression)
        {
            _expression = expression;
        }
        public override double Eval()
        {
            return _expression;
        }
    }

Plus

    internal class Plus : Expression
    {
        private Expression _a;
        private Expression _b;

        public Plus(Expression a, Expression b)
        {
            _a = a;
            _b = b;
            Add(_a);
            Add(_b);
        }
        public override double Eval()
        {
            return _a + _b;
        }
    }

Minus

    internal class Minus : Expression
    {
        private Expression _a;
        private Expression _b;

        public Minus(Expression a, Expression b)
        {
            _a = a;
            _b = b;
            Add(_a);
            Add(_b);
        }
        public override double Eval()
        {
            return _a - _b;
        }
    }

Mul

    internal class Mul : Expression
    {
        private Expression _a;
        private Expression _b;

        public Mul(Expression a, Expression b)
        {
            _a = a;
            _b = b;
            Add(_a);
            Add(_b);
        }
        public override double Eval()
        {
            return _a * _b;
        }
    }

Div

    internal class Div : Expression
    {
        private Expression _a;
        private Expression _b;

        public Div(Expression a, Expression b)
        {
            _a = a;
            _b = b;
            Add(_a);
            Add(_b);
        }
        public override double Eval()
        {
            return _a / _b;
        }
    }

Number

    internal class Number : Expression
    {
        private double _value;

        public Number(string text)
        {
            double value;
            if (!double.TryParse(text, NumberStyles.Float, CultureInfo.InvariantCulture.NumberFormat, out value))
            {
                throw new NotSupportedException("Initialization of the incorrect double value is not supported");
            }
            _value = value;
        }
        public override double Eval()
        {
            return _value;
        }
    }

Last edited Nov 22, 2010 at 10:43 PM by hack2root, version 14

Comments

No comments yet.