Back to BASICs

Adding Goto and If Statements

---

Now that we have a working interpreter that uses a lexer and a parser, let’s next add support for goto and if statements. Goto statements jump to a line in the program, while if statements conditionally jump to a line in the program.

Goto Statements

Goto statements in BASIC jump to a specific line in the program. For example, GOTO 30 jumps to line 30, so the output of the following program would be “Thank you for using BASIC!”.

10 GOTO 30
20 PRINT "This is skipped"
30 PRINT "Thank you for using BASIC!"

Lexing

Let’s first add a test to the lexer for the GOTO keyword. Add the following test to lexer_test.dart:

  test('Goto statement: 10 GOTO 20', () {
    var lexer = Lexer('10 GOTO 20');
    expect(lexer.tokenize(), [
      Token(Category.numberLiteral, '10'),
      Token(Category.goto, 'GOTO'),
      Token(Category.numberLiteral, '20'),
    ]);
  });

Then, add the goto category categories in tokens.dart:

enum Category {
  // ...
  goto,
  // ...
}

// ...

And modify lexer.dart to catch goto. We need to add just one to the switch expression in the else if branch that looks for keywords or identifiers.

  // ...
} else if (keywordOrIdentifierRegex.hasMatch(char)) {
  // ...
    final token = switch (keyword) {
      "GOTO" => Token(Category.goto, keyword),
      "LET" => Token(Category.let, keyword),
      "PRINT" => Token(Category.print, keyword),
      _ => Token(Category.identifier, keyword),
    };
  // ...
} else if (char == ',') {
  // ...

Now, when we run the tests for the lexer using dart test test/lexer_test.dart, we see that all tests pass.

00:00 +7: All tests passed!

Parsing

Next, let’s add the functionality for parsing the GOTO statement. Add a test to parser_test.dart:

  test("GOTO statement", () {
    final tokens = [
      Token(Category.numberLiteral, "10"),
      Token(Category.goto, "GOTO"),
      Token(Category.numberLiteral, "20"),
    ];

    final parser = Parser(tokens);
    final program = parser.parse();

    expect(program[10], isA<GotoStatement>());
  });

The tests do not even compile yet, as we have not added the GotoStatement class to statements.dart. Let’s add it. The execution of a goto statement returns a number that indicates the line number to jump to.

import "expressions.dart";

sealed class Statement<T> {
  T execute(Map<String, num> variables);
}

class GotoStatement extends Statement<int> {
  final int lineNumber;

  GotoStatement(this.lineNumber);

  @override
  int execute(Map<String, num> variables) {
    return lineNumber;
  }
}

class LetStatement extends Statement<void> {
  // ...
}

class PrintStatement extends Statement<String> {
  // ...
}

Then, add the GotoStatement to the parser. First, we need to add a line to the while loop in the parse method to parse a goto statement if the keyword category is goto.

Map<int, Statement> parse() {
  // ...
    final statement = switch (keywordToken.category) {
      Category.goto = parseGotoStatement(),
      Category.let => parseLetStatement(),
      Category.print => parsePrintStatement(),
      _ => throw Exception("Unexpected token: ${tokens[position]}"),
    };
  // ...
}

And then, we need to add the parseGotoStatement method to the parser. The method cheks that the next token is a number literal and then returns a new GotoStatement with the line number.

Statement parseGotoStatement() {
  expectToken(Category.numberLiteral);
  final lineNumber = int.parse(tokens[position].value);
  return GotoStatement(lineNumber);
}

Now, the parsing tests pass and the output of dart test test/parser_test.dart has the following line.

00:00 +7: All tests passed!

Interpreting

Finally, we need to modify the interpreter to handle GotoStatement. Let’s first add a test to the interpreter for the GotoStatement, which checks that the interpreter jumps to the correct line number.

Add the following test to basic_interpreter_test.dart:

  test("Goto statement", () {
    expect(interpreter.interpret('10 GOTO 30\n20 PRINT "SKIP"\n30 PRINT "END"'),
        ["END"]);
  });

Then, modify the interpreter to handle GotoStatement — unlike earlier, we no longer can just iterate over the lines. We need to keep track of the line numbers and jump to the correct line number when we encounter a GotoStatement.

import "lexer.dart";
import "parser.dart";
import "statements.dart";

class Interpreter {
  Map<int, Statement> programLines = {};
  Map<String, num> variables = {};

  List<String> interpret(String code) {
    final lexer = Lexer(code);
    final parser = Parser(lexer.tokenize());

    programLines = parser.parse();

    List<int> lineNumbers = programLines.keys.toList()..sort();
    int currentLine = lineNumbers.first;

    List<String> outputLines = [];

    for (var lineNumber in lineNumbers) {
      Statement statement = programLines[lineNumber]!;
      if (statement is PrintStatement) {
        String output = statement.execute(variables);
        outputLines.add(output);
      } else {
        statement.execute(variables);
      }
    }

    return outputLines;
  }
}

And, finally modify interpreter to handle GotoStatement — unlike earlier, we no longer can just iterate over the lines. We need to keep track of the line numbers and jump to the correct line number when we encounter a GotoStatement.

This requires changing the way got the lines are handled — now, if we encounter a GotoStatement, we need to jump to the correct line number, while otherwise, we need to continue from the next line number. A good choice for continuing from the next line number is the firstWhere method, which can be used to conditionally find the next line number in the list of line numbers.

The following code shows the revised interpreter.

import "lexer.dart";
import "parser.dart";
import "statements.dart";

class Interpreter {
  Map<int, Statement> programLines = {};
  Map<String, num> variables = {};

  List<String> interpret(String code) {
    final lexer = Lexer(code);
    final parser = Parser(lexer.tokenize());

    programLines = parser.parse();

    List<int> lineNumbers = programLines.keys.toList()..sort();
    int currentLine = lineNumbers.first;

    List<String> outputLines = [];

    while (currentLine > 0) {
      Statement statement = programLines[currentLine]!;

      if (statement is GotoStatement) {
        currentLine = statement.execute(variables);
        continue;
      }

      if (statement is PrintStatement) {
        String output = statement.execute(variables);
        outputLines.add(output);
      } else {
        statement.execute(variables);
      }

      currentLine = lineNumbers.firstWhere((lineNumber) {
        return lineNumber > currentLine;
      }, orElse: () => -1);
    }

    return outputLines;
  }
}

When we run the tests using dart test test/basic_interpreter_test.dart, we see that all tests pass.

00:00 +7: All tests passed!

If statements

If statements in BASIC conditionally jump to a specific line in the program. For example, the following program skips the line 30 as the variable A evalutes to 5.

10 LET A = 5
20 IF A = 5 THEN 40
30 PRINT "This is skipped"
40 PRINT "Thank you for using BASIC!"

Adding if statements works similarly to adding goto statements. We need to add support for lexing, parsing, and interpreting if statements.

Lexing

Let’s first add a test to the lexer for the IF and THEN keywords. Add the following test to lexer_test.dart:

  test('If statement: 20 IF A = 5 THEN 40', () {
    var lexer = Lexer('20 IF A = 5 THEN 40');
    expect(lexer.tokenize(), [
      Token(Category.numberLiteral, '20'),
      Token(Category.ifToken, 'IF'),
      Token(Category.identifier, 'A'),
      Token(Category.equals, '='),
      Token(Category.numberLiteral, '5'),
      Token(Category.then, 'THEN'),
      Token(Category.numberLiteral, '40'),
    ]);
  });

As already indicated in the above code, we cannot use if as a token category, as if is a reserved keyword in Dart. Instead, we use ifToken.

Add ifToken and then to tokens.dart.

enum Category {
  // ...
  ifToken,
  // ...
  then,
}

// ...

Then, modify lexer.dart to catch if and then keywords. Like before, we need to just modify the switch expression in the else if branch that looks for keywords or identifiers.

// ...
} else if (keywordOrIdentifierRegex.hasMatch(char)) {
  final match = keywordOrIdentifierRegex.matchAsPrefix(source, position);
  if (match != null) {
    final keyword = match.group(0)!;
    final token = switch (keyword) {
      "GOTO" => Token(Category.goto, keyword),
      "IF" => Token(Category.ifToken, keyword),
      "LET" => Token(Category.let, keyword),
      "PRINT" => Token(Category.print, keyword),
      "THEN" => Token(Category.then, keyword),
      _ => Token(Category.identifier, keyword),
    };

    tokens.add(token);
    position = match.end;
    continue;
  }
} else if (char == ',') {
// ...

Now, when we run the tests for the lexer using dart test test/lexer_test.dart, we see that all tests pass.

00:00 +8: All tests passed!

Parser

If statements consist of a comparison expression, which is evaluated to determine whether to jump to a specific line in the program. Let’s first define the comparison expression and the if statement, and then add the if statement to the parser.

Comparison operator and comparison expression

To do comparisons, we need to have comparison operators, e.g., =, >, <, etc. Let’s add a new enum for comparison operators for clarity. Create a file called operators.dart, and add the following to the file — for now, we just have the comparison operator equals.

enum ComparisonOperator {
  equals,
}

Then, let’s add a comparison expression to expressions.dart. A comparison expression takes a left and right expression, and a comparison operator, and evaluates to a boolean value based on the comparison operator.

import "operators.dart";

sealed class Expression<T> {
  T evaluate(Map<String, num> variables);
}

class ComparisonExpression extends Expression<bool> {
  final Expression<num> left;
  final Expression<num> right;
  final ComparisonOperator operator;

  ComparisonExpression(this.left, this.right, this.operator);

  @override
  bool evaluate(Map<String, num> variables) {
    num leftValue = left.evaluate(variables);
    num rightValue = right.evaluate(variables);

    return switch (operator) {
      ComparisonOperator.equals => leftValue == rightValue,
    };
  }
}

class NumberLiteralExpression extends Expression<num> {
  // ...
}

class StringLiteralExpression extends Expression<String> {
  // ...
}

class IdentifierExpression extends Expression<num> {
  // ....
}

If statement

Then, modify the statements.dart to include the IfStatement class. The IfStatement class takes a comparison expression and a line number to jump to. If the comparison expression evaluates to true, the IfStatement returns the line number to jump to, otherwise it returns null.

import "expressions.dart";

sealed class Statement<T> {
  T execute(Map<String, num> variables);
}

class GotoStatement extends Statement<int> {
  // ...
}

class IfStatement extends Statement<int?> {
  final ComparisonExpression condition;
  final int lineNumber;

  IfStatement(this.condition, this.lineNumber);

  @override
  int? execute(Map<String, num> variables) {
    return condition.evaluate(variables) ? lineNumber : null;
  }
}

class LetStatement extends Statement<void> {
  // ...
}

class PrintStatement extends Statement<String> {
  // ...
}

Test for parser

We should have added this already earlier, but it’s not too late! Add a test to parser_test.dart to check that the parser returns an if statement based on a set of tokens.

  test("If statement", () {
    final tokens = [
      Token(Category.numberLiteral, "20"),
      Token(Category.ifToken, "IF"),
      Token(Category.identifier, "A"),
      Token(Category.equals, "="),
      Token(Category.numberLiteral, "5"),
      Token(Category.then, "THEN"),
      Token(Category.numberLiteral, "40"),
    ];

    final parser = Parser(tokens);
    final program = parser.parse();

    expect(program[20], isA<IfStatement>());
  });

When we run the tests with dart test test/parser_test.dart, we see that the tests fail.

00:00 +7 -1: Some tests failed.

Parsing functionality

With the if statement and the comparison expression in place, we can add the if statement to the parser. The parser should parse the comparison expression and the line number to jump to. We again first start with the switch expression in the loop, adding a case for parsing an if statement if we encounter an if token.

import "expressions.dart";
import "statements.dart";
import "tokens.dart";

class Parser {
  final List<Token> tokens;
  int position = -1;

  Parser(this.tokens);

  Map<int, Statement> parse() {
      // ...

      final statement = switch (keywordToken.category) {
        Category.goto => parseGotoStatement(),
        Category.ifToken => parseIfStatement(),
        Category.let => parseLetStatement(),
        Category.print => parsePrintStatement(),
        _ => throw Exception("Unexpected token: ${tokens[position]}"),
      };

      // ...
  }

  // ...

  Statement parseIfStatement() {
    throw UnimplementedError();
  }

  // ...
}

Then, we need to implement the parseIfStatement method. The method should parse the comparison expression and the line number to jump to, and then return a new IfStatement with the comparison expression and the line number. One possible implementation is as follows.

Statement parseIfStatement() {
  position++;
  Expression<num> left = switch (tokens[position].category) {
    Category.numberLiteral =>
      NumberLiteralExpression(num.parse(tokens[position].value)),
    Category.identifier => IdentifierExpression(tokens[position].value),
    _ => throw Exception("Invalid expression: ${tokens[position]}")
  };

  expectToken(Category.equals);

  ComparisonOperator operator = switch (tokens[position].category) {
    Category.equals => ComparisonOperator.equals,
    _ => throw Exception("Invalid operator: ${tokens[position]}")
  };

  position++;
  Expression<num> right = switch (tokens[position].category) {
    Category.numberLiteral =>
      NumberLiteralExpression(num.parse(tokens[position].value)),
    Category.identifier => IdentifierExpression(tokens[position].value),
    _ => throw Exception("Invalid expression: ${tokens[position]}")
  };

  expectToken(Category.then);
  expectToken(Category.numberLiteral);

  final lineNumber = int.parse(tokens[position].value);
  final expression = ComparisonExpression(left, right, operator);

  return IfStatement(expression, lineNumber);
}

Now, when we run the tests for the parser, we see that the tests pass.

00:00 +8: All tests passed!

Interpreting

Finally, we need to modify the interpreter to handle IfStatement. If the condition of the if statement evaluates to true, the interpreter should jump to the line number specified in the if statement. Let’s first add a test to test/basic_interpreter_test.dart to check that the interpreter jumps to the correct line number when encountering an if statement.

  test("If statement", () {
    expect(interpreter.interpret('''10 LET A = 5
20 IF A = 5 THEN 40
30 PRINT "This is skipped"
40 PRINT "Thanks, BASIC!"'''), ["Thanks, BASIC!"]);
  });

When we run the tests for the interpreter, we see that there’s a failing test.

00:00 +7 -1: Some tests failed.

This is expected, as we have not yet added the IfStatement to the interpreter. We can add it as another if-statement in the loop that iterates over the program lines — when an if statement is encountered, we evaluate the condition and jump to the correct line number if the condition is true.

Modify the loop in the basic_interpreter.dart to include the if statement; the jump should only occur when the if statement returns a line number to jump to.

while (currentLine > 0) {
  Statement statement = programLines[currentLine]!;

  // ...

  if (statement is IfStatement) {
    int? nextLine = statement.execute(variables);
    if (nextLine != null) {
      currentLine = nextLine;
      continue;
    }
  } else if (statement is PrintStatement) {
    String output = statement.execute(variables);
    outputLines.add(output);
  } else {
    statement.execute(variables);
  }

  // ...
}

Now, when we run the tests with dart test test/basic_interpreter_test.dart, we see that the interpreter tests pass.

00:00 +8: All tests passed!

Loading Exercise...