Things are getting exciting. I will introduce control statements in this part of the ANTLR tutorial, like repetitions and conditionals. For that, we will need to do a small walk, visiting the comparison and boolean operators. Then, we will be able to implement the control operators and, in the end, test everything.
Comparisons
LOGO does not have exactly a boolean type. By default, a value of 0 is false, and a value of 1 is true. This is mostly like the C programming language. I will follow the C programming language convention, and consider that 0 is false, and everything else is true. Given that our numeric values are floats, and rounding errors might occur, I will consider that any value between \(\left]-0.5, 0.5\right[\) is a false value.
To make the conversion from floats to booleans, back and forth, I will create a new extension class to support some AST conversions. It will be created inside the Logo2SVG/AST folder:
namespace Logo2Svg.AST;
public static class AstUtils
{
public static bool AsBool(this float v) => v is >= 0.5f or <= -0.5f;
public static float AsFloat(this bool b) => b ? 1f : 0f;
}We create two auxiliary methods, one that will be able to be called on float values, to convert them to a boolean, and the other that will be able to be called on boolean values, to convert them to floats. By this time, I expect you already understand extension methods. If not, you will understand them better with the following code blocks.
Regarding the lexicon recognition, we need to define a couple of new tokens: the comparison operators (both as symbols and as a command):
LessSign : '<' ;
GreaterSign : '>' ;
LessEqualSign : '<=' ;
GreaterEqualSign : '>=' ;
Less : L E S S (P | '?');
Greater : G R E A T E R (P | '?');
LessEqual : L E S S E Q U A L (P | '?');
GreaterEqual : G R E A T E R E Q U A L (P | '?');Please take note that the less or equal and greater or equal signs are two characters, although the WordPress plugin shows a single one. Also, there are two variations for the command syntax, one ending with the character p and the other ending with the question mark. They are similar in meaning, just different syntaxes.
The next step is to handle the comparison syntaxes in the grammar. We already have rules for inline binary operators and Polish notation operators. This means we just need to add the new ones in the existing production, taking care to handle correctly the operator precedence:
expr : cmd=(Sum|Difference|Product|Quotient|Power|Remainder|Modulo
|Less|Greater|LessEqual|GreaterEqual) expr expr #prefixBinaryOp
| op=(Minus|MinusSign) expr #unaryMinus
| fun=(Abs|Int|Round|Sqrt|Exp|Log10|Ln|Arctan|Sin| Cos|Tan
|Radarctan|Radsin|Radcos|Radtan) expr #arithFuncs
| '(' fun=(Arctan|Radarctan) expr expr ')' #arithFuncs
| '(' Sum expr+ ')' #summation
| '(' Product expr+ ')' #product
| '(' Quotient expr ')' #quotient
| <assoc=right> expr op='^' expr #binaryOp
| <assoc=left> expr op=('*'|'/'|'%') expr #binaryOp
| <assoc=left> expr op=('+'|'-') expr #binaryOp
| <assoc=left> expr op=('<'|'>'|LessEqualSign|GreaterEqualSign) expr #binaryOp
| value #scalar
| '(' expr ')' #scalar
| VariableRef #variable
| Thing Variable #variable
; Line 13 is new because the comparison operators have less precedence than all other binary operators. Also, the two character symbols should not be written as literal strings!
And the process follows as usual. After adding lexer and parser rules we go on adding visitors:
public override INode VisitBinaryOp([NotNull] LogoParser.BinaryOpContext context)
{
var parcels = context.expr().Select(Visit<Parameter>);
var op = context.op.Type switch
{
LogoLexer.CircunflexSign => LogoLexer.Power,
LogoLexer.PlusSign => LogoLexer.Sum,
LogoLexer.MinusSign => LogoLexer.Difference,
LogoLexer.AsteriskSign => LogoLexer.Product,
LogoLexer.SlashSigh => LogoLexer.Quotient,
LogoLexer.PercentSign => LogoLexer.Remainder,
LogoLexer.LessSign => LogoLexer.Less,
LogoLexer.GreaterSign => LogoLexer.Greater,
LogoLexer.LessEqualSign => LogoLexer.LessEqual,
LogoLexer.GreaterEqualSign => LogoLexer.GreaterEqual,
_ => context.op.Type
};
return new ExprParam(op, parcels.ToArray());
}There is no need to make changes to the method VisitPrefixBinaryOp. We wrote it generic enough to deal with new similar commands. But, for the inline binary operator, we need new code, as we map different tokens to the same identifier (for example, the multiple ways to compare if a number is less than another will generate a similar node in the abstract syntax tree). To make this method more versatile for the future (as well as a little faster), I changed the switch statement to look at the type of the operator (its symbol as defined by the lexer, as an integer) instead of the strings, and the default case just keeps the operator value intact.
Now that the AST is constructed, the next step is to evaluate it:
public override float Value(Turtle turtle)
{
var values = _parameters.Select(p => p.Value(turtle)).ToArray();
return Op switch
{
LogoLexer.Less => (values[0] < values[1]).AsFloat(),
LogoLexer.Greater => (values[0] > values[1]).AsFloat(),
LogoLexer.LessEqual => (values[0] <= values[1]).AsFloat(),
LogoLexer.GreaterEqual => (values[0] >= values[1]).AsFloat(),
// [...]I just show context enough for you to understand where this code goes. The lines 6 to 9 are the new ones. For each of the operators, we just compare the result of the evaluated parameters directly and convert the boolean value that C# gives us to a float value.
For the stringification method, we perform a similar approach:
public override string ToString()
{
var values = _parameters.Select(p => p.ToString()).ToArray();
var @params = string.Join(" ", values.Select(v => $"({v})"));
var op = Op switch {
LogoLexer.Less => "less?",
LogoLexer.Greater => "greater?",
LogoLexer.LessEqual => "lessEqual?",
LogoLexer.GreaterEqual => "greaterEqual?",
// [...]Again, the new lines are 6 through 9.
Booleans and Boolean Operators
Just like any other programming language, LOGO has the and, or and xor operators. They can be used inline or as an aggregation (LISP style). It also includes two constants: true and false.
We need to perform the complete dance again: Lexer, Parser, AST construction and AST evaluation. Starting with the lexer, these are the new tokens:
And : A N D ;
Xor : X O R ;
Or : O R ;
True : T R U E ;
False : F A L S E ;In the grammar, the binary operators will be added in the usual Binary Operator branch of the expression production, taking care of the precedence of operators. For the LISP style, we will add a new branch:
expr : cmd=(Sum|Difference|Product|Quotient|Power|Remainder|Modulo
|Less|Greater|LessEqual|GreaterEqual) expr expr #prefixBinaryOp
| op=(Minus|MinusSign) expr #unaryMinus
| fun=(Abs|Int|Round|Sqrt|Exp|Log10|Ln|Arctan|Sin| Cos|Tan
|Radarctan|Radsin|Radcos|Radtan) expr #arithFuncs
| '(' fun=(Arctan|Radarctan) expr expr ')' #arithFuncs
| '(' Sum expr+ ')' #summation
| '(' Product expr+ ')' #product
| '(' Quotient expr ')' #quotient
| '(' cmd=(And|Or|Xor) expr+ ')' #boolean
| <assoc=right> expr op='^' expr #binaryOp
| <assoc=left> expr op=('*'|'/'|'%') expr #binaryOp
| <assoc=left> expr op=('+'|'-') expr #binaryOp
| <assoc=left> expr op=('<'|'>'|LessEqualSign|GreaterEqualSign) expr #binaryOp
| <assoc=left> expr op=(And|Or|Xor) expr #binaryOp
| value #scalar
| '(' expr ')' #scalar
| VariableRef #variable
| Thing Variable #variable
; Line 10 is new, with the LISP style syntax for the boolean operators, as well as line 15, which defines these operators as inline. With the change we performed earlier to the Binary Operator visitor, we do not need to change anything now. Thus, only the new visitor for the LISP syntax needs to be created.
public override INode VisitBoolean([NotNull] LogoParser.BooleanContext context)
{
var parcels = context.expr().Select(Visit<Parameter>);
return new ExprParam(context.cmd.Type, parcels.ToArray());
}This code is similar to the one we used before for the summation, for example. We could reuse it if we wish. I suggest that as a challenge for the eager reader.
But we are forgetting the grammar change for the true and false constants. They behave like literals, so we can add them to the value rule:
value : IntegerValue
| RealValue
| True
| False
;The visitor for the value rule needs a simple update:
public override INode VisitValue([NotNull] LogoParser.ValueContext context)
{
if (context.True() is not null) return new ExprParam(LogoLexer.True);
if (context.False() is not null) return new ExprParam(LogoLexer.False);
var valueStr = (context.IntegerValue() ?? context.RealValue()).Symbol.Text;
return new ValueParam(float.Parse(valueStr));
}The only new lines are lines 3 and 4, which check if we are handling a true or false constant. Considering each case we just create a new expression with the correct operator.
For the evaluation, we continue populating the switch statement:
public override float Value(Turtle turtle)
{
var values = _parameters.Select(p => p.Value(turtle)).ToArray();
return Op switch
{
LogoLexer.True => true.AsFloat(),
LogoLexer.False => false.AsFloat(),
LogoLexer.And => values.Select(x => x.AsBool())
.Aggregate(true, (a, b) => a && b).AsFloat(),
LogoLexer.Xor => values.Select(x => x.AsBool())
.Aggregate(false, (a, b) => a ^ b).AsFloat(),
LogoLexer.Or => values.Select(x => x.AsBool())
.Aggregate(false, (a, b) => a || b).AsFloat(),
// [...]The constants are easy: we just convert true and false to a float value. For the boolean operators, we perform a LINQ aggregation, that applies the same operator to the whole list of parameters. We just need to take care of converting the float values obtained by evaluating each parameter to a boolean, so that C# can apply them to the boolean operator. And, before returning, convert the boolean value back to a float.
For the stringification method, the code is the expected one:
public override string ToString()
{
var values = _parameters.Select(p => p.ToString()).ToArray();
var @params = string.Join(" ", values.Select(v => $"({v})"));
var op = Op switch {
LogoLexer.True => "true",
LogoLexer.False => "false",
LogoLexer.And => "and",
LogoLexer.Or => "or",
LogoLexer.Xor => "xor",
// [...]
};
return @params.Length > 0 ? $"({op} {@params})" : op;
}The true and false constants do not have any parameters. Thus, line 13 was changed to handle that case, not adding an extra space to the resulting string.
Control Statements and Code Blocks
We will start by implementing a small set of control statements:
- For repeating, the command
repeat n, that repeats a code block a fixed amount of times, and the commandforeverthat repeats a code block forever. To finish a forever cycle we can break it using the commandbye. - For conditional statements, we have the commands
ifandifelse.
Both situations have code blocks, a concept we have not handled yet. Namely, these blocks will be parameters to commands, and up to now commands can only have expressions as parameters. Of course, we can create a special kind of command, named statement, for this situation. Nevertheless, the needed changes are not large, so I will follow the first option.
Code Blocks
To support code blocks we will implement a new AST node, named CommandBlock:
namespace Logo2Svg.AST;
public class CommandBlock : List<Command>, INode
{
public CommandBlock(IEnumerable<Command> cmdLst) : base(cmdLst)
{ }
public void Execute(Turtle turtle)
{
foreach (var cmd in this)
{
cmd.Execute(turtle);
if (turtle.IsExiting) break;
}
}
public override string ToString() => $"[{string.Join("\n", this)}]";
}As you can see, it is very similar to what we had in the node of type Program. The main differences are:
- the stringification method adds brackets around the commands, as expected by the LOGO syntax;
- the execution method has a special condition, to check if the program is exiting. We will add the code to handle this in a moment. It will be used to break the execution when the command
byeis found. This way we prevent future commands from being executed.
Given the similarity of this code with the Program.cs contents, we will rewrite it:
namespace Logo2Svg.AST
{
public class Program : CommandBlock
{
public Program(IEnumerable<Command> cmdLst) : base(cmdLst)
{
}
public override string ToString() => string.Join("\n", this);
}
}Note how simple it is now. We just changed the stringification method, as the brackets are no longer needed. Do not be afraid to refactor code whenever you see there is some repetition. We will benefit from that change in the future.
We need to update the turtle to handle the field IsExiting we used above.
public bool IsExiting { get; private set; }
public void Exiting() => IsExiting = true;Our setter always sets the value to a true value. After starting to exit, a program can never recover. Also, we have a new field that stores the boolean value.
Finally, our commands now need to support any type of node as a parameter. Thus, we need to make some changes to the class Command.cs:
public readonly List<INode> Params;
public Command(int id, string command, params INode[] @params)
{
Id = id;
Name = command;
Params = @params is null ? null : new List<INode>(@params);
}
private Parameter Parameter(int i) => Parameter<Parameter>(i);Line 1 changes the list of parameters to a list of nodes. I took the opportunity to make this field read-only. The constructor now receives a list of nodes, instead of a list of parameters. The default parameter accessor makes a direct cast of the node to the Parameter type.
The visitor for the command arc, in the file AST/TreeVisitor.cs, also needs a little adaptation, replacing var parameters = context.expr().Select(Visit<Parameter>).ToArray(); with var parameters = context.expr().Select(Visit).ToArray();.
Conditional and Loops
Follows the changes needed in the lexer file:
IfElse : I F E L S E ;
If : I F ;
Bye : B Y E ;
Repeat : R E P E A T ;
Forever : F O R E V E R ;For the grammar, we need a new production to handle the block of commands, a new production for the control structures, and a new branch to handle the new command bye. In the snippet below notice that line 4 now handles two commands at the same time. I did this to make it simpler to add new commands that do not have any parameters. Line 9 adds the branch for the new control statements, that are defined in lines 15 to 18.
command : simpleCommand #basicCommand
| SetPos squarePoint #setPosition
| SetXY simplePoint #setPosition
| cmd=(Home|Bye) #atomicCmd
| Arc expr expr #arc
| Make Variable expr #setVariable
| Name expr Variable #setVariable
| Show expr #show
| controlStmt #controlStatement
;
cmdBlock : '[' command+ ']'
;
controlStmt : Repeat expr cmdBlock #repeatStmt
| Forever cmdBlock #foreverStmt
| If ('[' expr ']' | expr) cmdBlock #ifStmt
| IfElse ('[' expr ']' | expr) cmdBlock cmdBlock #ifElseStmt
; As usual, I will not explain the semantics and syntax for the LOGO commands. Please refer to the documentation. The conditionals can have the condition between brackets or directly, without any delimiter. To make it easier, we just add the two options in each of the production branches. The command block production is also quite simple, very similar to the program production, but adding the brackets around the list of commands.
Now, on to the visitors. First, delete the old VisitHome method. It will be replaced by this one:
public override INode VisitAtomicCmd([NotNull] LogoParser.AtomicCmdContext context)
=> new Command(context.cmd.Type, context.cmd.Text);We take advantage of the recognized symbol to get from there the text of the command as well as its identifier so that the visitor gets simpler and able to handle any command that does not have any parameter.
The visitor for the code block is shown below and is very simple. Given the new constructor we added, we can also rewrite the visitor for the program non-terminal symbol:
public override INode VisitCmdBlock(LogoParser.CmdBlockContext context)
=> new CommandBlock(context.command().Select(Visit<Command>));
public override INode VisitProgram([NotNull] LogoParser.ProgramContext context)
=> new Program(context.command().Select(Visit<Command>));The visitor for the four flow control structures is also simple:
public override INode VisitIfStmt(LogoParser.IfStmtContext context)
=> new Command(LogoLexer.If, "if", Visit(context.expr()), Visit(context.cmdBlock()));
public override INode VisitIfElseStmt(LogoParser.IfElseStmtContext context)
=> new Command(LogoLexer.IfElse, "ifElse",
Visit(context.expr()), Visit(context.cmdBlock(0)), Visit(context.cmdBlock(1)));
public override INode VisitRepeatStmt(LogoParser.RepeatStmtContext context)
=> new Command(LogoLexer.Repeat, "Repeat",
Visit(context.expr()), Visit(context.cmdBlock()));
public override INode VisitForeverStmt(LogoParser.ForeverStmtContext context)
=> new Command(LogoLexer.Forever, "Forever", Visit(context.cmdBlock()));These visitors are all very similar, they just create the command, with the proper ID and name as well as the parameters.
Finally, we need to implement the execution of the new five commands:
public void Execute(Turtle turtle)
{
switch (Id)
{
case LogoLexer.If:
{
var condition = Parameter(0).Value(turtle).AsBool();
if (condition) Parameter<CommandBlock>(1).Execute(turtle);
break;
}
case LogoLexer.IfElse:
{
var condition = Parameter(0).Value(turtle).AsBool();
if (condition) Parameter<CommandBlock>(1).Execute(turtle);
else Parameter<CommandBlock>(2).Execute(turtle);
break;
}
case LogoLexer.Forever:
while (!turtle.IsExiting) Parameter<CommandBlock>(0).Execute(turtle);
break;
case LogoLexer.Repeat:
{
var times = (int) Parameter(0).Value(turtle);
for (var i = 0; i < times && !turtle.IsExiting; i++)
Parameter<CommandBlock>(1).Execute(turtle);
break;
}
case LogoLexer.Bye:
turtle.Exiting();
break;
// [...]Both conditional evaluations start by looking at the condition expression, evaluating it as a boolean. If it holds a true value, the then branch is executed. If not, and if it exists, the else branch is executed.
Regarding the forever, we just execute the command block over and over again, until the turtle gets in existing mode. For the repeat, we start by evaluating the number of times the repetition needs to be performed (and cast to an integer value) and then repeat the command block that amount of times. Again, we need to take care and check if the turtle is in exit mode.
Finally, the Bye command just sets the turtle into exiting mode.
Tests
As usual, the tests I present here are not exhaustive. I just wrote some to validate my work. More is needed.
To test the AST construction of a conditional expression, add this code:
[TestMethod]
public void IfElse()
{
var tree = @"IfElse [ :b < 69 ] [ MAKE ""d 0 ] [ MAKE ""d 1 ]".ToAst() as Program;
Assert.IsNotNull(tree);
Assert.AreEqual(1, tree.Count);
var cmd = tree[0];
Assert.IsNotNull(cmd);
Assert.AreEqual(LogoLexer.IfElse, cmd.Id);
Assert.AreEqual(3, cmd.Params.Count);
var cmp = cmd.Parameter<ExprParam>(0);
Assert.IsNotNull(cmd);
Assert.AreEqual(LogoLexer.Less, cmp.Op);
var trueBranch = cmd.Parameter<CommandBlock>(1);
Assert.AreEqual(1, trueBranch.Count);
Assert.AreEqual(LogoLexer.Make, trueBranch[0].Id);
var falseBranch = cmd.Parameter<CommandBlock>(2);
Assert.AreEqual(1, falseBranch.Count);
Assert.AreEqual(LogoLexer.Make, falseBranch[0].Id);
}We start by parsing the LOGO code and getting the command that holds the information about the conditional (the variable cmd). Then we check it has the correct ID and the correct number of parameters. Follows tests to look into each parameter. For the comparison (variable cmp) we just check the operator type. For the branches, we check the number of commands they have and guarantee they hold a make command.
To test the conditional execution, add the following test:
[TestMethod]
public void IfTest()
{
var tree = @"MAKE ""a 10
If :a > 15 [ MAKE ""a 15 ]
If [ true ] [ MAKE ""b 69 ]
IfElse [ :b >= 69 ] [ MAKE ""c 0 ] [ MAKE ""c 1 ]
IfElse [ :b < 69 ] [ MAKE ""d 0 ] [ MAKE ""d 1 ]".ToAst();
var turtle = new Turtle();
tree.Execute(turtle);
Assert.IsTrue(turtle.RetrieveVariable("a", out var val1));
Assert.AreEqual(10, val1);
Assert.IsTrue(turtle.RetrieveVariable("b", out var val2));
Assert.AreEqual(69, val2);
Assert.IsTrue(turtle.RetrieveVariable("c", out var val3));
Assert.AreEqual(0, val3);
Assert.IsTrue(turtle.RetrieveVariable("d", out var val4));
Assert.AreEqual(1, val4);
}Here we set the value of a couple of variables accordingly with other variable values. At the end, we check if the variables are defined in the symbol table and if they hold the correct values.
Finally, we can add more test cases to some of our existing tests:
// [...]
[DataRow("1 < 2", 1f)]
[DataRow("2 < 1", 0f)]
[DataRow("lessp 1 2", 1f)]
[DataRow("less? 2 1", 0f)]
[DataRow("1 > 2", 0f)]
[DataRow("2 > 1", 1f)]
[DataRow("greaterp 1 2", 0f)]
[DataRow("greater? 2 1", 1f)]
[DataRow("1 >= 2", 0f)]
[DataRow("2 >= 1", 1f)]
[DataRow("2 >= 2", 1f)]
[DataRow("greaterequalp 1 2", 0f)]
[DataRow("greaterequal? 2 1", 1f)]
[DataRow("greaterequalp 2 2", 1f)]
[DataRow("1 <= 2", 1f)]
[DataRow("2 <= 1", 0f)]
[DataRow("2 <= 2", 1f)]
[DataRow("lessequalp 1 2", 1f)]
[DataRow("lessequal? 2 1", 0f)]
[DataRow("lessequalp 2 2", 1f)]
[DataRow("1 and 1", 1f)]
[DataRow("1 and 0", 0f)]
[DataRow("0 or 1", 1f)]
[DataRow("0 or 0", 0f)]
[DataRow("0 xor 1", 1f)]
[DataRow("1 xor 1", 0f)]
[DataRow("(and 1 2 > 1 3 > 1)", 1f)]
[DataRow("(or false true)", 1f)]
public void ParseBasicOperators(string expr, float value, float? delta = null)
{ // [...]The cases above guarantee that the comparison and boolean expressions evaluate to the right values. The cases below guarantee the priority of the comparison operators:
// [...]
[DataRow("2 + 2 >= 4", 1f)]
[DataRow("2 + 2 <= 2", 0f)]
public void Priorities(string expr, float value)
{ // [...]Finally, the code below validates the stringification of the new operators:
// [...]
[DataRow("1 < 2", "(less? (1) (2))")]
[DataRow("lessp 1 2", "(less? (1) (2))")]
[DataRow("less? 2 1", "(less? (2) (1))")]
[DataRow("1 > 2", "(greater? (1) (2))")]
[DataRow("greaterp 1 2", "(greater? (1) (2))")]
[DataRow("greater? 2 1", "(greater? (2) (1))")]
[DataRow("1 >= 2", "(greaterEqual? (1) (2))")]
[DataRow("greaterequalp 1 2", "(greaterEqual? (1) (2))")]
[DataRow("greaterequalp 2 2", "(greaterEqual? (2) (2))")]
[DataRow("1 <= 2", "(lessEqual? (1) (2))")]
[DataRow("lessequal? 2 1", "(lessEqual? (2) (1))")]
[DataRow("lessequalp 2 2", "(lessEqual? (2) (2))")]
[DataRow("1 and 1", "(and (1) (1))")]
[DataRow("0 or 1", "(or (0) (1))")]
[DataRow("1 xor 1", "(xor (1) (1))")]
[DataRow("(and 1 2 > 1 3 > 1)", "(and (1) ((greater? (2) (1))) ((greater? (3) (1))))")]
[DataRow("(or false true)", "(or (false) (true))")]
public void Stringification(string expr, string expected)
{ // [...]Wrap-up
During the next week, I will add to the repository some LOGO files that you can use to test your implementation. Along with these files, I will add a readme explaining what each file includes and what it tests, as well as the image it should produce.
Our code is currently limited to a canvas of \(200\times 200\). I will also add the code to make our canvas virtually infinite. Given it does not have anything with parsers, I will not waste space in this tutorial with that. Nevertheless, the code will be documented, so you can understand what is going on.
Request for Contribution:
Are you following this tutorial? Are you learning? Do you want to contribute? Some ideas of things that are missing and that I would welcome as a pull-request:
- Further tests, namely for loops
- Code to stringify commands and not just parameters
- Tests for the command stringification