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?