ANTLR Tutorial – Part III

Keeping up with the ANTLR tutorial, here goes a new issue. Part I and Part II are also available.

As discussed previously, we are writing a conversion tool from the LOGO programming language into SVG. Up to now, we wrote a lot of code but did accomplish the generation of any SVG. In this issue I promise to focus on the SVG generation, allowing for the next parts of this tutorial to add other features to the language.

In this issue we will focus on:

1. Creating the classes required to store the drawing information, namely a Line.cs and a Point.cs classes.
2. Creating the Turtle.cs class. It will take care of saving the state of the drawing, and the current position and orientation of the drawing turtle.
3. Making tweaks in the Abstract Syntax Tree representation, to store commands using integer identifiers instead of using strings.

Update 1: Added rotation normalization at the end of the article.

Update 2: The rotation normalization was using \(\pi\) instead of \(2\pi\).

Two-Paragraph Introduction to SVG

What we need to know to generate basic drawings in SVG is… mostly nothing. At the moment our language only allows us to draw lines (moving the turtle forward) and rotate the turtle. Thus, only lines are required at the moment.

SVG, as you should know, is an XML schema to draw scalable vector graphics. It is a W3C Specification and is currently supported by all modern browsers. The minimal SVG code required to draw a line is the following one:

<svg height="210" width="500">
  <line x1="0" y1="0" x2="200" y2="200" style="stroke:rgb(255,0,0);stroke-width:2" />
</svg> 

What we need to know from this example:

• SVG requires you to specify the size of the drawing. We will consider a \(200 \times 200\) canvas for this part of the tutorial.
• Each line is an XML element that has the cartesian coordinates of each point, represented by \((x_1, y_1)\) and \((x_2, y_2)\). Finally, there is some CSS information about the type of the line stroke, namely its width and colour (we will draw everything in red for now).

It is also relevant to let you know that the SVG canvas has its point \((0,0)\) at the top left of the screen. This will be relevant when we start drawing.

The SVG Canvas

We will represent the SVG Canvas by a class, Canvas.cs. It will be, at this point, mostly, a list of lines. Then, each line will be a class Line.cs that has two points (source and target) and a colour. Each point is a Point.cs which contains a pair of coordinates, and each colour is a Colour.cs with the red/green/blue component values.

We will put everything inside the Turtle folder that we created last time. For some of these classes, we will also override the ToString method to return the XML representation of it.

namespace Logo2Svg.SVG;

public class Colour
{
    public int Red, Green, Blue;

    public Colour(int r, int g, int b)
    {
        Red = r;
        Green = g;
        Blue = b;
    }

    public override string ToString() => $"rgb({Red},{Green},{Blue})";
}

The Colour class should be straightforward. Just notice we are creating a new namespace, and that some editors, like Rider, might complain it does not correspond with the folder the file is into. I will ignore that convention. Be free to change if you like.

namespace Logo2Svg.SVG;

public class Point
{
    public float X, Y;

    public Point(float x, float y)
    {
        X = x;
        Y = y;
    }
}

The point class is also simple. We will store points as floats as, as soon we start making trigonometric computations, values will get real. In this case, I did not override the ToString method, as it won’t be too useful.

namespace Logo2Svg.SVG;

public class Line
{
    public Point Pt1, Pt2;
    public Colour Colour;

    public Line(Point pt1, Point pt2, Colour c)
    {
        Pt1 = pt1;
        Pt2 = pt2;
        Colour = c;
    }

    public override string ToString()
    {
        var style = $"stroke:{Colour}; stroke-width:1";
        return $@"<line x1=""{Pt1.X}"" y1=""{Pt1.Y}"" x2=""{Pt2.X}"" y2=""{Pt2.Y}"" style=""{style}""/>";
    }
}

For the line, we store the two points (origin and target) as well as the colour. For now, the stroke width will be hardcoded. We can get there later.

namespace Logo2Svg.SVG;

public class Canvas : List<Line>
{
    public override string ToString()
    {
        var lines = string.Join("\n", this);
        return $@"<svg width=""200"" height=""200"">{lines}</svg>";
    }
}

For the canvas, we are specifying it as a list of lines (we are subclassing the List class from C#), and as stated above, the SVG output will be, at the moment, fixed to a \(200 \times 200\) canvas.

The Turtle

In the original LOGO language, the drawing is performed by a moving turtle. Consider it as our pen or pencil. As our output will be static, we will not draw the turtle. But we need to know where the turtle is on the canvas (its position) as well as where it is facing.

Follows the Turtle.cs class, to be saved inside the Turtle folder. We will keep editing it for the rest of this tutorial, so this is just the basic data we need to store.

using Logo2Svg.SVG;

namespace Logo2Svg;

public class Turtle
{
    private Canvas _canvas = new();
    public Point Position = new(100, 100);
    public Colour Colour = new(255, 0, 0);
    public float Rotation = 90f;
}

So, the canvas starts empty, the turtle is in position \((100, 100)\), it is drawing in red, and facing north (up in the screen).

To make things easier to visualize, we will consider the usual trigonometric circle, where 0 degrees is pointing right, and 90 degrees is pointing up. Also, as C# trigonometric functions deal with radians instead of degrees, we will store the rotation in radians, and declare a constant to easily convert degrees into radians:

    public const float ToRadians = MathF.PI / 180f; 
    public float Rotation = ToRadians * 90f;

Executing Commands

Now that we have everything set up, we need to update the App.cs code to execute the commands we are storing in the abstract syntax tree, and then output the generated SVG.

While this first step is not critical, it annoys me that we are storing the command name as a string. This means that every time we need to check which command is stored in a Command instance, we need to compare strings. And comparing strings is not something fast to perform. Thus, we are replacing them by integer codes, that represent each command.

To make things easier, and as each command will be a token in our Lexer, we can use the enumeration ANTLR creates when generating its Lexer code. To perform this change, first edit the Command.cs class:

namespace Logo2Svg.AST
{
    public class Command : INode
    {
        public string Name { get; }
        public int Id { get;  }
        public int Value { get; }

        public Command(int id, string command, string value)
        {
            Id = id;
            Name = command;
            if (int.TryParse(value, out var intVal))
            {
                Value = intVal;
            }
        }

        public override string ToString() => $"{Name}({Value})";
    }
}

Note that we did not get rid of the command name. It might get handy for debugging purposes (and for the ToString method).

Now the Tree Visitor needs some tweaking. The VisitCommand method gets the following update:

        public override INode VisitCommand([NotNull] LogoParser.CommandContext context)
        {
            string value = context.Value().GetText();
            string command = null;
            int id = 0;

            if (context.Forward() is { } forwardContext)
            {
                command = forwardContext.GetText();
                id = forwardContext.Symbol.Type;
            }
            if (context.Right() is { } rightContext)
            {
                command = rightContext.GetText();
                id = rightContext.Symbol.Type;
            }

            return command != null ? new Command(id, command, value) : null;
        }

Here we have something new. As the Forward and Right members of the grammar rule are terminal symbols, we can access the symbol itself, and get its type. This type is an integer computed by ANTLR and accessible through the Lexer class as we will see.

As for the execution of the LOGO code, we have two distinct options: either the Turtle receives the command, peeks inside it, and executes the code, or the command receives the Turtle, peeks and updates it executing the command. I would prefer the second as it will allow more code division, instead of having a big switch statement inside the turtle class.

So, each node of our abstract syntax tree needs to know how to execute it. For that, we can force every node that implements the INode interface to implement a custom execution method:

namespace Logo2Svg.AST
{
    public interface INode
    {
        public void Execute(Turtle turtle);
    }
}

After adding line 5 you will notice that you will get errors in Command.cs and Command.cs. That’s because they implement the INode interface, but the new method is missing from their implementation. Let’s fix this.

For the Command.cs class, the Execute implementation will be as follows:

public void Execute(Turtle turtle)
{
    switch (Id)
    {
        case LogoLexer.Forward:
            var pos = turtle.Position;
            var target = new Point(pos.X + MathF.Cos(turtle.Rotation) * Value, 
                                   pos.Y - MathF.Sin(turtle.Rotation) * Value);
            turtle.AddLine(pos, target);
            turtle.Position = target;
            break;
        case LogoLexer.Right:
            turtle.Rotation -= Value * Turtle.ToRadians; 
            break;
        default:
            throw new Exception($"Unknown command: {Id}-{Name}");
    }
}

So, we check the command identifier, and taking into account its value, we execute the command creating the required changes in the Turtle.

I will not explain the trigonometry, sorry. Just a note, that we use a negative value for the Y axis as our canvas is inverted (we have the origin in the top left corner of the screen).

You might notice the AddLine method is not yet implemented in the turtle class. We’ll get there soon.

For the Program node, our execution is just to run each command inside it:

namespace Logo2Svg.AST
{
    public class Program : List<Command>, INode
    {
        public void Execute(Turtle turtle)
        {
            ForEach(cmd => cmd.Execute(turtle));
        }

        public override string ToString() => string.Join("\n", this);
    }
}

Now, implementing the method AddLine in the turtle, as well as the code to save the SVG into a file:

   public void AddLine(Point from, Point to)
    {
        _canvas.Add(new Line(from, to, Colour));
    }

    public bool Save(string filename)
    {
        try {
            using var fs = new FileStream(filename, FileMode.Create);
            using var stream = new StreamWriter(fs);

            stream.Write(_canvas);
            return true;
        }
        catch (Exception e)
        {
            Console.WriteLine(e.Message);
            return false;
        }
    }

Nothing fancy here. Let us update the App.cs code, and we’ll get the first working version of our tool. Follows the last part of the try block inside the App.cs file.

  try
  {
      // [...]

      var programContext = parser.program();
      var visitor = new TreeVisitor();
      Program program = visitor.Visit(programContext) as Program;

      Turtle turtle = new Turtle();
      program.Execute(turtle);
      turtle.Save(output);
  }

We just create a new turtle, feed it to the program executor and, when it finishes, we save the turtle output to a file.

Compile the project, and try it with the following LOGO code:

FD 100
RT 90
FD 100
RT 135
FD 140

You should get the following SVG output.

Minor Enhancements

As discussed in Part II of this tutorial, the ANTLR visitors return elements that implement INode. This means that every time a visitor is invoked, the result needs to be cast to the proper type. To make this easier I like to have the following method implemented in the TreeVisitor:

    public T Visit<T>(IParseTree tree) => (T)Visit(tree);

After this change, you can reimplement the method VisitProgram as follows:

    public override INode VisitProgram([NotNull] LogoParser.ProgramContext context)
    {
        Program program = new();
        program.AddRange(context.command().Select(cmd => Visit<Command>(cmd)).ToList());
        return program;
    }

Note the difference in the lambda function. Instead of casting the result of the Visit call, we just pass the type we are expecting as a generic type parameter.

In the same way, App.cs can have the following line rewritten.

    Program program = visitor.Visit<Program>(programContext);

While at the moment the changes are only in these two lines, this will be handy in the next development.

As a second enhancement, suppose we keep rotating right. The rotation will increment over and over again. It might be useful to keep the rotation values inside the \([0, 2\pi]\) interval. For that, we can add a setter for the rotation field, in the Turtle.cs class.

    private float _rotation = ToRadians * 90f;
    public float Rotation
    {
        get => _rotation;
        set => _rotation = Norm(value);
    }
    
    private static float Norm(float a) {
        while(a > 2*MathF.PI) a -= 2 * MathF.PI;
        while(a < 0f) a += 2 * MathF.PI;
        return a;
    }