4
\$\begingroup\$

In a completely overkill BrainFuck lexer/parser I've presented the lexer, parser, interpreter and syntax tree classes. With this post I'd like to go over the lower-level Token and Span mechanics.

Each token has a Type property that returns a TokenType enum value:

namespace BrainFuck.Tokens
{
    public enum TokenType
    {
        Trivia,
        MoveLeft,
        MoveRight,
        BeginLoop,
        EndLoop,
        Increment,
        Decrement,
        Input,
        Output,
    }
}

A Token represents one or more characters in the BrainFuck source code input; BF lexer makes the TriviaToken the only token that can actually span more than a single character, but all tokens have the possibility of being represented with multiple characters. Here's the Token class:

using System;
using System.Collections.Generic;

namespace BrainFuck.Tokens
{
    /// <summary>
    /// A base class for all language tokens.
    /// </summary>
    public abstract class Token : IEquatable<Token>, IComparable<Token>
    {
        private static readonly IDictionary<TokenType, string> Tokens =
            new Dictionary<TokenType, string>
        {
            [TokenType.MoveLeft] = MoveLeftToken.Token,
            [TokenType.MoveRight] = MoveRightToken.Token,
            [TokenType.BeginLoop] = BeginLoopToken.Token,
            [TokenType.EndLoop] = EndLoopToken.Token,
            [TokenType.Increment] = IncrementToken.Token,
            [TokenType.Decrement] = DecrementToken.Token,
            [TokenType.Input] = InputToken.Token,
            [TokenType.Output] = OutputToken.Token,
        };

        protected Token(Span position, int index, TokenType type)
            : this(position, index, Tokens[type])
        {
            Type = type;
        }

        protected Token(Span position, int index, string text)
        {
            Index = index;
            Type = TokenType.Trivia;
            Position = position;
            Text = text;
        }

        /// <summary>
        /// The type of token.
        /// </summary>
        public TokenType Type { get; }

        /// <summary>
        /// The position of the token in the source text.
        /// </summary>
        public Span Position { get; }

        /// <summary>
        /// The position of the token in the token stream.
        /// </summary>
        public int Index { get; }

        /// <summary>
        /// The text content of the token.
        /// </summary>
        public string Text { get; }

        public bool Equals(Token other)
        {
            return other != null
                && other.Type == Type
                && other.Position == Position
                && other.Text == Text;
        }

        public int CompareTo(Token other)
        {
            if (other == null)
            {
                return Position.CompareTo(Span.Empty);
            }

            return Position.CompareTo(other.Position);
        }

        public override string ToString()
        {
            return Text;
        }
    }
    /// <summary>
    /// A trivia token, representing any non-code content.
    /// </summary>
    public sealed class TriviaToken : Token
    {
        public TriviaToken(Span position, int index, string text)  : base(position, index, text) { }
    }

    /// <summary>
    /// A language token representing a "Move Left" instruction.
    /// </summary>
    public sealed class MoveLeftToken : Token
    {
        public static string Token => "<";
        public MoveLeftToken(Span position, int index) : base(position, index, TokenType.MoveLeft) { }
    }

    /// <summary>
    /// A language token representing a "Move Right" instruction.
    /// </summary>
    public sealed class MoveRightToken : Token
    {
        public static string Token => ">";
        public MoveRightToken(Span position, int index) : base(position, index, TokenType.MoveRight) { }
    }

    /// <summary>
    /// A language token representing a "Begin Loop" instruction.
    /// </summary>
    public sealed class BeginLoopToken : Token
    {
        public static string Token => "[";
        public BeginLoopToken(Span position, int index) : base(position, index, TokenType.BeginLoop) { }
    }

    /// <summary>
    /// A language token representing an "End Loop" instruction.
    /// </summary>
    public sealed class EndLoopToken : Token
    {
        public static string Token => "]";
        public EndLoopToken(Span position, int index) : base(position, index, TokenType.EndLoop) { }
    }

    /// <summary>
    /// A language token representing an "Increment" instruction.
    /// </summary>
    public sealed class IncrementToken : Token
    {
        public static string Token => "+";
        public IncrementToken(Span position, int index) : base(position, index, TokenType.Increment) { }
    }

    /// <summary>
    /// A language token representing a "Decrement" instruction.
    /// </summary>
    public sealed class DecrementToken : Token
    {
        public static string Token => "-";
        public DecrementToken(Span position, int index) : base(position, index, TokenType.Decrement) { }
    }

    /// <summary>
    /// A language token representing an "Input" instruction.
    /// </summary>
    public sealed class InputToken : Token
    {
        public static string Token => ",";
        public InputToken(Span position, int index) : base(position, index, TokenType.Input) { }
    }

    /// <summary>
    /// A language token representing an "Output" instruction.
    /// </summary>
    public sealed class OutputToken : Token
    {
        public static string Token => ".";
        public OutputToken(Span position, int index) : base(position, index, TokenType.Output) { }
    }
}

The position of a token in the source code input is stored in a Span value type which is really nothing more than a StartLine, StartColumn, EndLine and EndColumn values and a number of static utility methods:

using System;
using System.Linq;

namespace BrainFuck.Tokens
{
    /// <summary>
    /// A value representing a span of characters in a document.
    /// </summary>
    public struct Span : IEquatable<Span>, IComparable<Span>
    {
        /// <summary>
        /// Creates an empty span starting and ending at column 0 of line 0.
        /// </summary>
        public static Span Empty => new Span();

        /// <summary>
        /// Creates a single-character span at specified line and column.
        /// </summary>
        /// <param name="line">The start/end document line.</param>
        /// <param name="column">The start/end document column.</param>
        public Span(int line, int column) : this(line, column, line, column) { }

        /// <summary>
        /// Creates a span within the specified document coordinates.
        /// </summary>
        /// <param name="startLine">The starting document line.</param>
        /// <param name="startColumn">The starting document column.</param>
        /// <param name="endLine">The ending document line.</param>
        /// <param name="endColumn">The ending document column.</param>
        public Span(int startLine, int startColumn, int endLine, int endColumn)
        {
            StartLine = startLine;
            EndLine = endLine;
            StartColumn = startColumn;
            EndColumn = endColumn;
        }

        /// <summary>
        /// The starting line position.
        /// </summary>
        public int StartLine { get; }

        /// <summary>
        /// The ending line position.
        /// </summary>
        public int EndLine { get; }

        /// <summary>
        /// The starting column position.
        /// </summary>
        public int StartColumn { get; }

        /// <summary>
        /// The ending column position.
        /// </summary>
        public int EndColumn { get; }

        /// <summary>
        /// The number of lines in the document coordinates.
        /// </summary>
        public int Lines => EndLine - StartLine + 1;

        /// <summary>
        /// Extends the span to the next line. Returns a new Span with the same start position, ending on next line at column 0.
        /// </summary>
        public Span NextLine => new Span(StartLine, StartColumn, EndLine + 1, 0);

        /// <summary>
        /// Returns a new span starting on the next line, at column 0
        /// </summary>
        public Span NewLine => new Span(EndLine + 1, 0, EndLine + 1, 0);

        /// <summary>
        /// Extends the span to the next column. Returns a new Span with the same start position, ending on the same line at the next column.
        /// </summary>
        public Span NextColumn => new Span(StartLine, StartColumn, EndLine, EndColumn + 1);

        /// <summary>
        /// Returns a new span starting on the same line, at the next column.
        /// </summary>
        public Span Next => new Span(EndLine, EndColumn + 1);

        /// <summary>
        /// Returns a new span with the same start position, ending on the same line at the previous column.
        /// </summary>
        public Span PreviousColumn => new Span(StartLine, StartColumn, EndLine, EndColumn - 1);

        /// <summary>
        /// Returns a new span starting at the end of the current position.
        /// </summary>
        public Span End => new Span(EndLine, EndColumn);

        public Span OffSet(int columns, int lines = 0)
        {
            return new Span(StartLine + lines, StartColumn + columns, EndLine + lines, EndColumn + columns);
        }

        public Span Combine(Span other)
        {
            return Combine(this, other);
        }

        public static Span Combine(params Span[] a)
        {
            var min = a.Min();
            var max = a.Max();
            return new Span(min.StartLine, min.StartColumn, max.EndLine, max.EndColumn);
        }

        public static bool operator ==(Span x, Span y)
        {
            return x.Equals(y);
        }

        public static bool operator !=(Span x, Span y)
        {
            return !x.Equals(y);
        }

        public bool Equals(Span other)
        {
            return other.StartLine == StartLine
                   && other.EndLine == EndLine
                   && other.StartColumn == StartColumn
                   && other.EndColumn == EndColumn;
        }

        public int CompareTo(Span other)
        {
            if (Equals(other))
            {
                return 0;
            }

            if (other.StartLine < StartLine || (other.StartLine == StartLine && other.StartColumn < StartColumn))
            {
                return -1;
            }

            return 1;
        }

        public override bool Equals(object obj)
        {
            return obj != null && Equals((Span)obj);
        }

        public override int GetHashCode()
        {
            return HashCode.Compute(StartLine, EndLine, StartColumn, EndColumn);
        }

        public override string ToString()
        {
            return Lines == 1
                ? $"L{EndLine}C{EndColumn}"
                : $"L{StartLine}C{StartColumn}:L{EndLine}C{EndColumn}";
        }
    }
}

These utility methods are very useful for cleanly generating tokens when writing unit tests:

[TestMethod]
public void GivenConsecutiveInstructions_RegroupsSyntaxTreeByTokenType()
{
    var parser = new Parser();
    var tree = parser.Parse(new Token[]
    {
        new IncrementToken(Span.Empty.OffSet(0), 0),
        new IncrementToken(Span.Empty.OffSet(1), 1),
        new DecrementToken(Span.Empty.OffSet(2), 2),
        new DecrementToken(Span.Empty.OffSet(3), 3),
    });

    Assert.AreEqual(2, tree.Children.Count());
}

The Lexer class also makes good use of them. I tried to come up with a little naming scheme, but found that XML comments would be the most efficient way to convey exactly what a method is returning. Or would there be better names for them? Also, do Equals and CompareTo implementations look right? Any other feedback is welcome, too.

\$\endgroup\$
3
\$\begingroup\$

I was looking at your code thinking "it's so nice to see struct when it makes sense and one that implements all the equality and comparison stuff!". Then I saw this:

public override bool Equals(object obj)  
{
     return obj != null && Equals((Span)obj);
}

And I broke down and wept.

I give you the following test case:

Span.Empty.Equals(new object());
// InvalidCastException

You can fix it with the as dance:

public override bool Equals(object obj)  
{
    var otherSpan = obj as Span?;
    return otherSpan != null && Equals(otherSpan.Value);
}

Or with is which I actually prefer in this case from a readability point of view:

public override bool Equals(object obj)  
{
     return obj is Span && Equals((Span)obj);
}

Other than that, nothing is jumping out at me.

\$\endgroup\$
4
\$\begingroup\$

Let's take a look at three of your token classes:

/// <summary>
/// A language token representing a "Move Left" instruction.
/// </summary>
public sealed class MoveLeftToken : Token
{
    public static string Token => "<";
    public MoveLeftToken(Span position, int index) : base(position, index, TokenType.MoveLeft) { }
}

/// <summary>
/// A language token representing a "Move Right" instruction.
/// </summary>
public sealed class MoveRightToken : Token
{
    public static string Token => ">";
    public MoveRightToken(Span position, int index) : base(position, index, TokenType.MoveRight) { }
}

/// <summary>
/// A language token representing a "Begin Loop" instruction.
/// </summary>
public sealed class BeginLoopToken : Token
{
    public static string Token => "[";
    public BeginLoopToken(Span position, int index) : base(position, index, TokenType.BeginLoop) { }
}

Now let me ask you: Did you copy-paste any code while writing this? You did, didn't you?

I don't see a reason for why you need 8 (one for each BF instruction) different classes. How about 8 different objects instead? Or 8 different factory methods possibly. You are not using any OOP aspects for these token classes. So.... do they really deserve to be classes?

Forgive my Java, but may I suggest something like this instead?

public class Tokens {
    public static final String TOKEN_INCREMENT = "+";

    public static Token increment(Span position, int index) {
        return new Token(position, index, TOKEN_INCREMENT);
    }
}

As far as I can see, there is no functionality that you would lose out on if you would go this way instead.

\$\endgroup\$
  • \$\begingroup\$ Java forgiven =) \$\endgroup\$ – Mathieu Guindon Nov 22 '16 at 20:26
  • \$\begingroup\$ I like how this solves the very annoying problem I was having with these repeated public static string Token members. But no, I don't recall Copy+Pasting anything here. R# Alt+Enter to auto-implement a constructor doesn't count, does it? \$\endgroup\$ – Mathieu Guindon Nov 22 '16 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.