A completely overkill BrainFuck lexer/parser

Question

I'll need to build a syntax tree (AST) for Rubberduck, but since VBA has dozens of tokens and complex rules, I needed a simpler language to play with first, so I thought BrainFuck would be a perfect candidate.

The result is completely overkill for BF, but the exercise was very educational.

Lexer

The lexer reads the code as a string or stream input, and yields tokens - a trivia token can span multiple characters, instruction tokens are all single-character:

using BrainFuck.Tokens;

namespace BrainFuck
{
    /// <summary>
    /// An object responsible for tokenizing an input stream.
    /// </summary>
    public sealed class Lexer
    {
        /// <summary>
        /// Yields tokens from the input stream.
        /// </summary>
        /// <param name="input">Any stream of BrainFuck source code.</param>
        public IEnumerable<Token> Tokenize(System.IO.Stream input)
        {
            var reader = new System.IO.StreamReader(input);
            var currentTokenPosition = Span.Empty;
            var currentTriviaSpan = Span.Empty;
            var builder = new StringBuilder();

            var tokenCount = 0;

            while (reader.Peek() > 0)
            {
                var current = (char) reader.Read();
                var next = (char) reader.Peek();

                if (IsNewLine(current, next))
                {
                    builder.Append(current);
                    currentTriviaSpan = currentTriviaSpan.NextLine;
                    currentTokenPosition = currentTokenPosition.NewLine;

                    if (Environment.NewLine.Length == 2)
                    {
                        current = (char) reader.Read();
                        builder.Append(current);
                    }

                    continue;
                }

                Token token;
                if (IsToken(currentTokenPosition, tokenCount, current, out token))
                {
                    // if we were building a trivia token, we need to yield it first:
                    if (builder.Length != 0)
                    {
                        yield return new TriviaToken(currentTriviaSpan, tokenCount, builder.ToString());
                        tokenCount++;
                    }

                    yield return token;
                    tokenCount++;

                    currentTriviaSpan = currentTokenPosition.Next;
                    currentTokenPosition = currentTriviaSpan.End;
                    builder.Clear();
                }
                else
                {
                    builder.Append(current);
                }

                if (next != 0)
                {
                    currentTriviaSpan = currentTriviaSpan.NextColumn;
                }
            }

            if (builder.Length != 0)
            {
                currentTriviaSpan = currentTriviaSpan.PreviousColumn;
                yield return new TriviaToken(currentTriviaSpan, tokenCount, builder.ToString());
                builder.Clear();
            }
        }

        /// <summary>
        /// Returns tokens from input string.
        /// </summary>
        /// <param name="input">BrainFuck source code</param>
        public IEnumerable<Token> Tokenize(string input)
        {
            using (var stream = new System.IO.MemoryStream())
            {
                var writer = new System.IO.StreamWriter(stream, Encoding.Default);
                writer.Write(input);
                writer.Flush();
                stream.Position = 0;

                var tokens = Tokenize(stream).ToList();
                writer.Dispose();

                return tokens;
            }
        }

        private static bool IsNewLine(char character, char next)
        {
            return new string(new[] {character, next}).Equals(Environment.NewLine)
                   || Environment.NewLine.Equals(character.ToString());
        }

        private static readonly IDictionary<string, Func<Span, int, Token>>
            TokenFactories = new Dictionary<string, Func<Span, int, Token>>
            {
                {MoveLeftToken.Token, (span, index) => new MoveLeftToken(span, index)},
                {MoveRightToken.Token, (span, index) => new MoveRightToken(span, index)},
                {BeginLoopToken.Token, (span, index) => new BeginLoopToken(span, index)},
                {EndLoopToken.Token, (span, index) => new EndLoopToken(span, index)},
                {IncrementToken.Token, (span, index) => new IncrementToken(span, index)},
                {DecrementToken.Token, (span, index) => new DecrementToken(span, index)},
                {InputToken.Token, (span, index) => new InputToken(span, index)},
                {OutputToken.Token, (span, index) => new OutputToken(span, index)},
            };

        private static bool IsToken(Span position, int index, char input, out Token token)
        {
            Func<Span, int, Token> factory;
            if (TokenFactories.TryGetValue(input.ToString(), out factory))
            {
                token = factory.Invoke(position, index);
                return true;
            }

            token = null;
            return false;
        }
    }

}

Parser

The parser processes tokens and generates a parse tree.

using BrainFuck.Syntax;
using BrainFuck.Tokens;

namespace BrainFuck
{
    public class Parser
    {
        private static readonly Dictionary<TokenType, Func<SyntaxTree>> SyntaxTrees =
            new Dictionary<TokenType, Func<SyntaxTree>>
            {
                {TokenType.Trivia, () => new TriviaSyntax()},
                {TokenType.Increment, () => new IncrementInstructionSyntax()},
                {TokenType.Decrement, () => new DecrementInstructionSyntax()},
                {TokenType.MoveLeft, () => new MoveLeftInstructionSyntax()},
                {TokenType.MoveRight, () => new MoveRightInstructionSyntax()},
                {TokenType.Input, () => new InputInstructionSyntax()},
                {TokenType.Output, () => new OutputInstructionSyntax()},
            };

        public SyntaxTree Parse(Token[] tokens)
        {
            var index = 0;
            var depth = 0;
            return Parse(tokens, ref index, ref depth);
        }

        private static SyntaxTree Parse(IReadOnlyList<Token> tokens, ref int index, ref int depth, SyntaxTree root = null)
        {
            if(root == null)
            {
                root = new SyntaxTree();
            }

            Token previousToken = null;
            SyntaxTree currentTree = null;
            SyntaxTree previousTree = null;

            while(index < tokens.Count)
            {
                var token = tokens[index];
                index++;

                Func<SyntaxTree> treeFactory;
                if(SyntaxTrees.TryGetValue(token.Type, out treeFactory))
                {
                    // trivia or instruction token
                    if(previousToken?.Type == token.Type)
                    {
                        previousTree?.Add(token);
                    }
                    else
                    {
                        if (previousTree != null)
                        {
                            root.Add(previousTree);
                        }

                        currentTree = treeFactory.Invoke();
                        currentTree.Add(token);
                    }
                }
                else
                {
                    // control flow token
                    if(previousTree != null)
                    {
                        root.Add(previousTree);
                    }
                    switch(token.Type)
                    {
                        case TokenType.BeginLoop:
                            depth++;
                            currentTree = Parse(tokens, ref index, ref depth, new LoopBlockSyntax { token });
                            break;

                        case TokenType.EndLoop:
                            if(depth == 0)
                            {
                                throw new IllegalTokenException(token);
                            }
                            depth--;

                            root.Add(token);
                            return root;

                        default:
                            throw new IllegalTokenException(token);
                    }
                }

                previousToken = token;
                previousTree = currentTree;
            }

            if (previousTree != null)
            {
                root.Add(previousTree);
            }
            return root;
        }
    }
}

Interpreter

The interpreter traverses the parse tree and executes all instructions.

using BrainFuck.Syntax;

namespace BrainFuck
{
    public class Interpreter
    {
        private readonly ExecutionContext _context;

        public Interpreter(ExecutionContext context)
        {
            _context = context;
        }

        public void Execute(SyntaxTree tree)
        {
            foreach (var instruction in tree.Children)
            {
                (instruction as IInstruction)?.Execute(_context);
            }
        }
    }
}

---

LoopBlockInstruction

The loop instruction overrides the default "execute instruction once for each token" behavior:

using System;

namespace BrainFuck.Syntax
{
    public sealed class LoopBlockSyntax : InstructionSyntaxTree
    {
        private const int MaxIterations = short.MaxValue;

        protected override void ExecuteOnce(ExecutionContext context)
        {
            throw new NotSupportedException();
        }

        public override void Execute(ExecutionContext context)
        {
            var iterations = 0;
            while(context.IsTrue())
            {
                foreach (var instruction in Children)
                {
                    (instruction as IInstruction)?.Execute(context);
                }

                if (iterations == MaxIterations) { throw new InfiniteLoopException(); }
                iterations++;
            }
        }
    }

    public class InfiniteLoopException : Exception
    {
    }
}

IncrementInstructionSyntax

The other syntax tree implementations are dead simple:

namespace BrainFuck.Syntax
{
    public sealed class IncrementInstructionSyntax : InstructionSyntaxTree
    {
        protected override void ExecuteOnce(ExecutionContext context)
        {
            context.Increment();
        }
    }
}

---

InstructionSyntaxTree

The base class for all instructions:

using System.Linq;

namespace BrainFuck.Syntax
{
    public abstract class InstructionSyntaxTree : SyntaxTree, IInstruction
    {
        protected abstract void ExecuteOnce(ExecutionContext context);

        public virtual void Execute(ExecutionContext context)
        {
            // ReSharper disable once UnusedVariable; instruction is the same for every token unless method is overridden.
            foreach (var instruction in Tokens)
            {
                ExecuteOnce(context);
            }
        }

        public override string ToString()
        {
            return $"{GetType().Name} x{Tokens.Count()}";
        }
    }
}

---

ExecutionContext

The interpreter needs a context to work with:

using System;
using System.Text;

namespace BrainFuck
{
    public class ExecutionContext
    {
        public ExecutionContext(int memorySize = short.MaxValue, Func<int> onInput = null)
        {
            _onInput = onInput;
            _memory = new int[memorySize];
            _stdOutput = new StringBuilder();
        }

        private readonly int[] _memory;
        private readonly Func<int> _onInput;
        private readonly StringBuilder _stdOutput;

        private int _pointer;
        public int Pointer => _pointer;

        public int Value => _memory[_pointer];

        public string StdOut => _stdOutput.ToString();

        public bool IsTrue(int position = -1)
        {
            return (position == -1 ? _memory[_pointer] : _memory[position]) != 0;
        }

        public void MoveLeft()
        {
            if (_pointer == 0)
            {
                _pointer = _memory.Length;
            }
            else
            {
                _pointer--;
            }
        }

        public void MoveRight()
        {
            if (_pointer == _memory.Length)
            {
                _pointer = 0;
            }
            else
            {
                _pointer++;
            }
        }

        public void Increment()
        {
            _memory[_pointer] += 1;
        }

        public void Decrement()
        {
            _memory[_pointer] -= 1;
        }

        public void Output()
        {
            _stdOutput.Append((char)_memory[_pointer]);
        }

        public void Input()
        {
            _memory[_pointer] = _onInput?.Invoke() ?? Console.Read();
        }
    }
}

I would include the Token class as well, but I think this post is long enough already. The project is on GitHub if you need additional context.

So, how's my first real C# 6.0 program?

Answer 1

Additional C#6.0 Modifications

How C#6.0 would you like it to be? You still have a few places you can use more C#6.0:

I'm going to work bottom-to-top in your post:

---

Usually, I don't support using expression-bodied members on void methods, but this class would benefit from a few of them:

public class ExecutionContext
{
    public ExecutionContext(int memorySize = short.MaxValue, Func<int> onInput = null)
    {
        _onInput = onInput;
        _memory = new int[memorySize];
        _stdOutput = new StringBuilder();
    }

    private readonly int[] _memory;
    private readonly Func<int> _onInput;
    private readonly StringBuilder _stdOutput;

    private int _pointer;
    public int Pointer => _pointer;

    public int Value => _memory[_pointer];

    public string StdOut => _stdOutput.ToString();

    public bool IsTrue(int position = -1)
    {
        return (position == -1 ? _memory[_pointer] : _memory[position]) != 0;
    }

    public void MoveLeft()
    {
        if (_pointer == 0)
        {
            _pointer = _memory.Length;
        }
        else
        {
            _pointer--;
        }
    }

    public void MoveRight()
    {
        if (_pointer == _memory.Length)
        {
            _pointer = 0;
        }
        else
        {
            _pointer++;
        }
    }

    public void Increment()
    {
        _memory[_pointer] += 1;
    }

    public void Decrement()
    {
        _memory[_pointer] -= 1;
    }

    public void Output()
    {
        _stdOutput.Append((char)_memory[_pointer]);
    }

    public void Input()
    {
        _memory[_pointer] = _onInput?.Invoke() ?? Console.Read();
    }
}

We'll start with:

public void Increment()
{
    _memory[_pointer] += 1;
}

public void Decrement()
{
    _memory[_pointer] -= 1;
}

As:

public void Increment() => _memory[_pointer]++;
public void Decrement() => _memory[_pointer]--;

Sidebar: I don't see a need for a private field here:

private int _pointer;
public int Pointer => _pointer;

Why not just use a property with a private setter?

We can do two things with this one:

public bool IsTrue(int position = -1)
{
    return (position == -1 ? _memory[_pointer] : _memory[position]) != 0;
}

First, replace the return with:

return _memory[position == -1 ? _pointer : position] != 0;

Then, expression-body member that thing:

public bool IsTrue(int position = -1) => _memory[position == -1 ? _pointer : position] != 0;

But, the next question is, why are you using -1 as a special case? Make it nullable and we can do one more thing with it:

public bool IsTrue(int? position = null) => _memory[position ?? _pointer] != 0;

Nice and short.

---

Next, we'll look at:

public abstract class InstructionSyntaxTree : SyntaxTree, IInstruction
{
    protected abstract void ExecuteOnce(ExecutionContext context);

    public virtual void Execute(ExecutionContext context)
    {
        // ReSharper disable once UnusedVariable; instruction is the same for every token unless method is overridden.
        foreach (var instruction in Tokens)
        {
            ExecuteOnce(context);
        }
    }

    public override string ToString()
    {
        return $"{GetType().Name} x{Tokens.Count()}";
    }
}

You can make ToString() use expression-bodied members:

public override string ToString() => $"{GetType().Name} x{Tokens.Count()}";

---

There's one potential problem with this, and we can make it more C#6.0 at the same time, what happens if context is null?

public sealed class IncrementInstructionSyntax : InstructionSyntaxTree
{
    protected override void ExecuteOnce(ExecutionContext context)
    {
        context.Increment();
    }
}

Well, we can fix that with ?. (as I assume you know):

protected override void ExecuteOnce(ExecutionContext context) => context?.Increment();

---

The last thing I want to look at is the Dictionary, you can now use the new C#6.0 dictionary initializer syntax instead of the following:

private static readonly Dictionary<TokenType, Func<SyntaxTree>> SyntaxTrees =
    new Dictionary<TokenType, Func<SyntaxTree>>
    {
        {TokenType.Trivia, () => new TriviaSyntax()},
        {TokenType.Increment, () => new IncrementInstructionSyntax()},
        {TokenType.Decrement, () => new DecrementInstructionSyntax()},
        {TokenType.MoveLeft, () => new MoveLeftInstructionSyntax()},
        {TokenType.MoveRight, () => new MoveRightInstructionSyntax()},
        {TokenType.Input, () => new InputInstructionSyntax()},
        {TokenType.Output, () => new OutputInstructionSyntax()},
    };

Instead of that ugliness, we have a new slightly less ugliness:

private static readonly Dictionary<TokenType, Func<SyntaxTree>> SyntaxTrees =
    new Dictionary<TokenType, Func<SyntaxTree>>
    {
        [TokenType.Trivia] = () => new TriviaSyntax(),
        [TokenType.Increment] = () => new IncrementInstructionSyntax(),
        [TokenType.Decrement] = () => new DecrementInstructionSyntax(),
        [TokenType.MoveLeft] = () => new MoveLeftInstructionSyntax(),
        [TokenType.MoveRight] = () => new MoveRightInstructionSyntax(),
        [TokenType.Input] = () => new InputInstructionSyntax(),
        [TokenType.Output] = () => new OutputInstructionSyntax(),
    };

Instead of {key, value} we can use [key] = value, which seems to make a little more sense. (It's still a bit ugly to read when the value is a Func, but it's still a bit clearer.

---

Next, you used readonly on your IDictionary and whatnot, but that only blocks reassignment. Consumers can still call .Add and .Remove on them. The easiest way to fix that is to make the readonly field a readonly property by replacing = with =>.

---

Experimental (C#7.0) Modifications

Now I want to talk about how C#7.0 will improve your code, since it's in RC mode right now.

First and foremost I think my favourite feature of C#7.0 is the new way out parameters are handled. In C#6.0 my favourite feature was expression-bodied members, and this has the same idea to it: shortening and simplifying code.

Let's take a look at how C#7.0 changes this. In your code (C#6.0) you have the following:

Token token;
if (IsToken(currentTokenPosition, tokenCount, current, out token))

Now this is what we've been doing since out parameters were introduced, because this was all we had. Enter C#7.0. Instead of having to declare token before we use it, we can declare it as we use it:

if (IsToken(currentTokenPosition, tokenCount, current, out Token token))

Now token is in scope inside our if statement, as we would expect. As of this writing token is out-of-scope outside the if statement, it's unclear if that will be adjusted before final release. (Personally, I like it as it is.)

The same thing here:

Func<Span, int, Token> factory;
if (TokenFactories.TryGetValue(input.ToString(), out factory))

That simply becomes

if (TokenFactories.TryGetValue(input.ToString(), out Func<Span, int, Token> factory))

Pretty nifty, and much simpler.

---

The next C#7.0 feature to talk about is local functions. These are declared inside another function with the same regular function syntax. I'm not sure what Microsoft's recommendation on using them will be, but I would suggest you could put that entire IsToken function inside the Tokenize function. Syntax is as follows:

public string SomeFunction(int parameter)
{
    string localFunction(int someParameter)
    {
        return string.Format("0", someParameter);
    }

    return localFunction(parameter);
}

Obviously not particularly useful in this case, but you can see how you could move IsToken to be a function in Tokenize. (Not that it's recommended, just that it's possible.)

---

C#7.0 added support for expression-bodied exceptions:

protected override void ExecuteOnce(ExecutionContext context)
{
    throw new NotSupportedException();
}

Can simply be:

protected override void ExecuteOnce(ExecutionContext context) => throw new NotSupportedException();

The other new features (that I've experimented with so far) are not really all that handy to you, so I'll not describe them.

---

Conclusion

This is all I can manage to look at when it's 0130 in the morning, but I hope it finds you well and you don't hate me for pointing out things I'm sure you already know.

Answer 2

The static BrainFuck.Parser.Parse method could use a bit of abstraction.

By extracting a simple overloaded method:

private static void AddIfNotNull(SyntaxTree tree, Token token)
{
    tree?.Add(token);
}

private static void AddIfNotNull(SyntaxTree root, SyntaxTree tree)
{
    if (tree != null)
    {
        root.Add(tree);
    }
}

And now with just a few more comments the body of the while loop becomes crystal-clear, with all the null-checking boilerplate gone:

private static SyntaxTree Parse(IReadOnlyList<Token> tokens, ref int index, ref int depth, SyntaxTree parent = null)
{
    if(parent == null) { parent = new SyntaxTree(); }

    Token previousToken = null;
    SyntaxTree currentTree = null;
    SyntaxTree previousTree = null;

    while(index < tokens.Count)
    {
        var token = tokens[index];
        index++;

        Func<SyntaxTree> treeFactory;
        if(SyntaxTrees.TryGetValue(token.Type, out treeFactory))
        {
            // trivia or instruction token
            if(previousToken?.Type == token.Type)
            {
                // same token as before, add to previous tree:
                AddIfNotNull(previousTree, token);
            }
            else
            {
                // new token, add previous tree to root and get a new tree:
                AddIfNotNull(parent, previousTree);

                currentTree = treeFactory.Invoke();
                AddIfNotNull(currentTree, token);
            }
        }
        else
        {
            // new control flow token, add previous tree to root:
            AddIfNotNull(parent, previousTree);

            switch(token.Type)
            {
                case TokenType.BeginLoop:
                    depth++;
                    // note: recursive
                    currentTree = Parse(tokens, ref index, ref depth, new LoopBlockSyntax { token });
                    break;

                case TokenType.EndLoop:
                    if(depth == 0) { throw new IllegalTokenException(token); }
                    depth--;

                    AddIfNotNull(parent, token);
                    return parent;

                default:
                    throw new IllegalTokenException(token);
            }
        }

        previousToken = token;
        previousTree = currentTree;
    }

    AddIfNotNull(parent, previousTree);
    return parent;
}

Because of the recursive handling of the BeginLoop token, the name root for the optional parameter isn't ideal; parent is a better term, for the actual root is the parent only at depth 0.

---

The LoopBlockSyntax is stepping on toes here:

private const int MaxIterations = short.MaxValue;

Instead of this:

if (iterations == MaxIterations) { throw new InfiniteLoopException(); }

You could do this:

if (iterations == context.Size) { throw new InfiniteLoopException(); }

By simply adding a Size property to the ExecutionContext:

public int Size => _memory.Length;

That way the loop is sure to be able traverse the entire tape... an arbitrary limitation, really - but just like _memory.Length anyway.