C# Abstract Syntax Tree Example: Compiler for a numeric expression, C#

Language: Layout:

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Runtime.Serialization;
using System.Text;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            string input = string.Empty;
            Console.WriteLine("Input an expression, for example: (2.11*-3*(5+7.18+9.23))+---1+++(-+-+--(1+2))*(-+-3+4)*(5+6)+3*(2+1)");
            
            input = "(2.11*-3*(5+7.18+9.23))+---1+++(-+-+--(1+2))*(-+-3+4)*(5+6)+3*(2+1)";

//while (true)
            {
                //Console.WriteLine();
                //Console.Write("Input (q = quit): ");
                //FlushConsole();
                //input = Console.ReadLine();

//if (input == "q")
                //{
                //    break;
                //}

try
                {
                    Parser interpreter = new Parser(input);
                    Expression node = interpreter.Parse();

Console.WriteLine(string.Format("Tree graph:{0}{1}", Environment.NewLine, node.Accept(new GraphBuilder())));
                    Console.WriteLine(string.Format("Value: {0}", node.Accept(new ValueBuilder())));
                    Console.WriteLine(string.Format("Lisp form: {0}", node.Accept(new LispFormBuilder())));
                }
                catch (InvalidSyntaxException ex)
                {
                    Console.WriteLine(ex.Message);
                }
                catch (Exception ex)
                {
                    Console.WriteLine(ex);
                }
            }
        }

static void FlushConsole()
        {
            while (Console.KeyAvailable)
            {
                Console.ReadKey(false);
            }
        }
    }

internal class Parser
    {
        private Token curToken;
        private int curPos;
        private int charCount;
        private char curChar;
        public string Text { get; private set; }

public Parser(string text)
        {
            this.Text = string.IsNullOrEmpty(text) ? string.Empty : text;
            this.charCount = this.Text.Length;
            this.curToken = Token.None();

this.curPos = -1;
            this.Advance();
        }

internal Expression Parse()
        {
            this.NextToken();
            Expression node = this.GrabExpr();
            this.ExpectToken(TokenType.None);
            return node;
        }

private Token ExpectToken(TokenType tokenType)
        {
            if (this.curToken.Type == tokenType)
            {
                return this.curToken;
            }
            else
            {
                throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Expected {1} but {2} is given.", this.curPos, tokenType, this.curToken.Type.ToString()));
            }
        }

private Expression GrabExpr()
        {
            Expression left = this.GrabTerm();

while (this.curToken.Type == TokenType.Plus
                || this.curToken.Type == TokenType.Minus)
            {
                Token op = this.curToken;
                this.NextToken();
                Expression right = this.GrabTerm();
                left = new BinOp(op, left, right);
            }

return left;
        }

private Expression GrabTerm()
        {
            Expression left = this.GrabFactor();

while (this.curToken.Type == TokenType.Multiply
                || this.curToken.Type == TokenType.Divide)
            {
                Token op = this.curToken;
                this.NextToken();
                Expression right = this.GrabFactor();
                left = new BinOp(op, left, right);
            }

return left;
        }

private Expression GrabFactor()
        {
            if (this.curToken.Type == TokenType.Plus
                || this.curToken.Type == TokenType.Minus)
            {
                Expression node = this.GrabUnaryExpr();
                return node;
            }
            else if (this.curToken.Type == TokenType.LeftParenthesis)
            {
                Expression node = this.GrabBracketExpr();
                return node;
            }
            else
            {
                Token token = this.ExpectToken(TokenType.Number);
                this.NextToken();
                return new Num(token);
            }
        }

private Expression GrabUnaryExpr()
        {
            Token op;

if (this.curToken.Type == TokenType.Plus)
            {
                op = this.ExpectToken(TokenType.Plus);
            }
            else
            {
                op = this.ExpectToken(TokenType.Minus);
            }

this.NextToken();

if (this.curToken.Type == TokenType.Plus
                || this.curToken.Type == TokenType.Minus)
            {
                Expression expr = this.GrabUnaryExpr();
                return new UnaryOp(op, expr);
            }
            else
            {
                Expression expr = this.GrabFactor();
                return new UnaryOp(op, expr);
            }
        }

private Expression GrabBracketExpr()
        {
            this.ExpectToken(TokenType.LeftParenthesis);
            this.NextToken();
            Expression node = this.GrabExpr();
            this.ExpectToken(TokenType.RightParenthesis);
            this.NextToken();
            return node;
        }

private void NextToken()
        {
            if (this.curChar == char.MinValue)
            {
                this.curToken = Token.None();
                return;
            }

if (this.curChar == ' ')
            {
                while (this.curChar != char.MinValue && this.curChar == ' ')
                {
                    this.Advance();
                }

if (this.curChar == char.MinValue)
                {
                    this.curToken = Token.None();
                    return;
                }
            }

if (this.curChar == '+')
            {
                this.curToken = new Token(TokenType.Plus, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar == '-')
            {
                this.curToken = new Token(TokenType.Minus, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar == '*')
            {
                this.curToken = new Token(TokenType.Multiply, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar == '/')
            {
                this.curToken = new Token(TokenType.Divide, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar == '(')
            {
                this.curToken = new Token(TokenType.LeftParenthesis, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar == ')')
            {
                this.curToken = new Token(TokenType.RightParenthesis, this.curChar.ToString());
                this.Advance();
                return;
            }

if (this.curChar >= '0' && this.curChar <= '9')
            {
                string num = string.Empty;
                while (this.curChar >= '0' && this.curChar <= '9')
                {
                    num += this.curChar.ToString();
                    this.Advance();
                }

if (this.curChar == '.')
                {
                    num += this.curChar.ToString();
                    this.Advance();

if (this.curChar >= '0' && this.curChar <= '9')
                    {
                        while (this.curChar >= '0' && this.curChar <= '9')
                        {
                            num += this.curChar.ToString();
                            this.Advance();
                        }
                    }
                    else
                    {
                        throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}.", this.curPos, this.curChar));
                    }
                }

this.curToken = new Token(TokenType.Number, num);
                return;
            }

throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}.", this.curPos, this.curChar));
        }

private void Advance()
        {
            this.curPos += 1;

if (this.curPos < this.charCount)
            {
                this.curChar = this.Text[this.curPos];
            }
            else
            {
                this.curChar = char.MinValue;
            }
        }
    }

[Serializable]
    internal class InvalidSyntaxException : Exception
    {
        public InvalidSyntaxException()
        {
        }

public InvalidSyntaxException(string message) : base(message)
        {
        }

public InvalidSyntaxException(string message, Exception innerException) : base(message, innerException)
        {
        }

protected InvalidSyntaxException(SerializationInfo info, StreamingContext context) : base(info, context)
        {
        }
    }

internal class GraphBuilder : INodeVisitor
    {
        private static string ReplaceLastChar(string str, char rep = ' ')
        {
            if (!string.IsNullOrEmpty(str))
            {
                return str.Substring(0, str.Length - 1) + rep.ToString();
            }
            else
            {
                return "";
            }
        }

const Char SPACE = ' ';
        const Char L_TURN = '┌';
        const Char V_PIPE = '│';
        const Char R_TURN = '└';
        const string TAB = "    ";
        const string H_PIPE = "──";

private StringBuilder sb;
        private Stack<string> indentStack;
        private Stack<BranchOriental> orientalStack;

public GraphBuilder()
        {
            this.sb = new StringBuilder();

this.indentStack = new Stack<string>();
            this.orientalStack = new Stack<BranchOriental>();

this.indentStack.Push(string.Empty);
            this.orientalStack.Push(BranchOriental.None);
        }

public object VisitBinOp(Token op, INode left, INode right)
        {
            BranchOriental legacyOriental = this.orientalStack.Pop();
            string legacyIndent = this.indentStack.Pop();

if (legacyOriental == BranchOriental.Left)
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + L_TURN);
                this.orientalStack.Push(BranchOriental.Left);
                left.Accept(this);
            }
            else
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE);
                this.orientalStack.Push(BranchOriental.Left);
                left.Accept(this);
            }

if (legacyOriental == BranchOriental.Left)
            {
                sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")");
            }
            else
            {
                sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")");
            }

if (legacyOriental == BranchOriental.Right)
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN);
                this.orientalStack.Push(BranchOriental.Right);
                right.Accept(this);
            }
            else
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE);
                this.orientalStack.Push(BranchOriental.Right);
                right.Accept(this);
            }

return this.sb.ToString();
        }

public object VisitNum(Token num)
        {
            BranchOriental legacyOriental = this.orientalStack.Pop();
            string legacyIndent = this.indentStack.Pop();

if (legacyOriental == BranchOriental.Left)
            {
                sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + "  " + num.ToString());
            }
            else
            {
                sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + "  " + num.ToString());
            }

return this.sb.ToString();
        }

public object VisitUnaryOp(Token op, INode node)
        {
            BranchOriental legacyOriental = this.orientalStack.Pop();
            string legacyIndent = this.indentStack.Pop();

if (legacyOriental == BranchOriental.Right)
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN);
                this.orientalStack.Push(BranchOriental.Right);
                node.Accept(this);
            }
            else
            {
                this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + R_TURN);
                this.orientalStack.Push(BranchOriental.Right);
                node.Accept(this);
            }

return this.sb.ToString();
        }

internal enum BranchOriental
        {
            None,
            Left,
            Right
        }
    }

internal class ValueBuilder : INodeVisitor
    {
        public object VisitBinOp(Token op, INode left, INode right)
        {
            switch (op.Type)
            {
                case TokenType.Plus:
                    return (decimal)left.Accept(this) + (decimal)right.Accept(this);
                case TokenType.Minus:
                    return (decimal)left.Accept(this) - (decimal)right.Accept(this);
                case TokenType.Multiply:
                    return (decimal)left.Accept(this) * (decimal)right.Accept(this);
                case TokenType.Divide:
                    return (decimal)left.Accept(this) / (decimal)right.Accept(this);
                default:
                    throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString()));
            }
        }

public object VisitNum(Token num)
        {
            return decimal.Parse(num.Value);
        }

public object VisitUnaryOp(Token op, INode node)
        {
            switch (op.Type)
            {
                case TokenType.Plus:
                    return (decimal)node.Accept(this);
                case TokenType.Minus:
                    return -(decimal)node.Accept(this);
                default:
                    throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString()));
            }
        }
    }

internal class LispFormBuilder : INodeVisitor
    {
        public object VisitBinOp(Token op, INode left, INode right)
        {
            return "(" + op.ToString() + " " + left.Accept(this) + " " + right.Accept(this) + ")";
        }

public object VisitNum(Token num)
        {
            return num.ToString();
        }

public object VisitUnaryOp(Token op, INode node)
        {
            return "(" + op.ToString() + " " + node.Accept(this) + ")";
        }
    }

internal interface INode
    {
        object Accept(INodeVisitor visitor);
    }

internal interface INodeVisitor
    {
        object VisitNum(Token num);
        object VisitUnaryOp(Token op, INode node);
        object VisitBinOp(Token op, INode left, INode right);
    }

internal abstract class Expression : INode
    {
        abstract public object Accept(INodeVisitor visitor);
    }

internal class Num : Expression
    {
        internal Token Token { get; private set; }

public Num(Token token)
        {
            this.Token = token;
        }

override public object Accept(INodeVisitor visitor)
        {
            return visitor.VisitNum(this.Token);
        }
    }

internal class UnaryOp : Expression
    {
        internal Token Op { get; private set; }
        internal Expression Node { get; private set; }

public UnaryOp(Token op, Expression node)
        {
            this.Op = op;
            this.Node = node;
        }

override public object Accept(INodeVisitor visitor)
        {
            return visitor.VisitUnaryOp(this.Op, this.Node);
        }
    }

internal class BinOp : Expression
    {
        internal Token Op { get; private set; }
        internal Expression Left { get; private set; }
        internal Expression Right { get; private set; }

public BinOp(Token op, Expression left, Expression right)
        {
            this.Op = op;
            this.Left = left;
            this.Right = right;
        }

override public object Accept(INodeVisitor visitor)
        {
            return visitor.VisitBinOp(this.Op, this.Left, this.Right);
        }
    }

internal class Token
    {
        public TokenType Type { get; private set; }
        public string Value { get; private set; }

public Token(TokenType type, string value)
        {
            this.Type = type;
            this.Value = value;
        }

internal static Token None()
        {
            return new Token(TokenType.None, "");
        }

public override string ToString()
        {
            return this.Value;
        }
    }

internal enum TokenType
    {
        None,
        Plus,
        Minus,
        Multiply,
        Divide,
        Number,
        LeftParenthesis,
        RightParenthesis
    }
}

Show compiler warnings [ + ] Show input
Compilation time: 0,16 sec, absolute running time: 0,11 sec, cpu time: 0,09 sec, average memory usage: 16 Mb, average nr of threads: 3