Developer's Guide

Abstract Syntax Tree Classes for Small Basic

• MySmallBasic supports all features of Small Basic with 12 keywords
• Stmt and Expr are two base classes for the other statement and expression classes inherit. Value is another base class for representing values such as string, number, boolean, and array.
• These AST classes are in src/com/coducation/smallbasic/ directory.
  • 

An Overview of the Internal Process of MySmallBasic

• Every Small Basic program in MySmallBasic goes through the following steps:

• Lexical analysis and Syntax analysis

  • The lexical analyzer implements a finite state automaton for a set of SmallBasic tokens.
    • src/com/coducation/smallbasic/LexerAnalyzer.java
  • The syntax analyzer basically implements an LALR(1) grammar of SmallBasic programs.
    • src/com/coducation/smallbasic/Parser.java
    • This parser starts taking the following three files in runtime, the grammar, the goto-table, and the shift-table, respectively, to perform the parsing of SmallBasic programs.
      • sb_grammar_rule.txt
      • sb_parsing_table.txt
      • sb_state_trans.txt
    • Be careful not to change the three text files.
    • We extend the basic grammar of SmallBasic to allow programmers to have (recursive) functions by writing a new extended grammar in here (sb_ext_grammar_rule.txt, sb_ext_parsing_table.txt, sb_ext_state_trans.txt)

• Basic Block Transformation

  • This step transforms an AST from the previous parsing step into a forest of ASTs each with a label. A basic block is a simple sequence of more than zero statements where no statement can go out of this block in the middle and there is no way to come in the middle of this block.

  • SmallBasic allows a very free form of Goto statements, which cannot be easily supported by block-structured programming languages such as Java. So, we divide a SmallBasic program into a list of basic blocks where only the end of each basic block is allowed for a Goto statement to be placed. The end of each block can be a Goto statement, and the other statements than that cannot be Goto statements.

  • For example,

     $main:
        Goto $L0
     $L0:
        I = 1
        Goto $L1
     $L1:
        If 1.0 <= 0.0 And I < 20 Or 1.0 > 0.0 And I >= 20 Then
           pic = Flickr.GetRandomPicture("mountains, river")
           GraphicsWindow.DrawResizedImage(pic, 0, 0, 640, 480) 
           I = I + 1.0
           Goto $L1
        EndIf

• Evaluation
  • The evaluator starts executing a block named $main, and it is based on so called the trampoline style.
    • sr/com/coducation/smallbasic/Eval.java
  • After the basic block transformation, a SmallBasic program is converted into a forest of basic block ASTs named with labels. When a block is executed, the evaluator will either meet a Goto statement with a label to jump into or not. The next basic block to execute has the label of the Goto statement. When no Goto statement is at the end of the basic block, it means that it is time to finish the evaluation.
  • The evaluator executes a train of blocks in the trampoline style as follows.

     public void eval() {
      env = new Env();
      env.label("$main"); // set the label of a staring block to execute

      while (env.label() != null) { // this evaluation will end when the label is null.
       Stmt stmt = bbEnv.get(env.label()); // get the label of a block to execute
       env.label(null); // reset the label
       eval(bbEnv, env, stmt);  // The Goto statement at the end of the block will set
                               //  the label of the next block to jump
       }
     }

How to Add a New Small Basic Library Written in Java to MySmallBasic

• To implement a new Small Basic library in Java, there are a few things that one needs to follow.

  • Every Small Basic library written in Java belongs to com.coducation.smallbasic.lib. A Small Basic library provides functions and fields.
  • Reading and writing fields of a Small Basic library requires library developers to keep some protocols.
  • Functions have also some protocols for library developers to follow.

• Fields are used either as in read mode or as in write mode. Graphic.Width and Graphics.Height are usually referred to resize Windows, and so they are use in write mode. Clock.Day is usually read to know which day is today, and so it is used in read mode.

  • For a field in write mode, after writing the field, some action associated with the field should be taken. For example, when one sets GraphicsWindows.Width to be 640, the window width should be changed accordingly. So, our evaluator calls GraphicWindow.notifyFieldAssign("Width") just after setting a field of a library.
  • On the other hand, for a field in read mode, one should take an action before reading an associated field of a Small Basic library. For example, Clock.Day should be set with today just before a Small Basic program reads it. So, our evaluator calls Clock.notifyFieldRead("Day") just before the Small Basic program reads it.
  • Note that the Java class has the same name as Small Basic library. For example, Small Basic GraphicsWindow library is implemented by GraphicsWindow class written in Java.

// Graphics.java
package com.coducation.smallbasic.lib;

public class Graphics {
  public final static Value Width; // a value to set

  public static void notifyFieldAssign(String fieldName) {
    if (“Width”.equalsIgnoreCase(fieldName)) {
       ... change the width of a window with the Width value set before this call ...;
    }
  }
  ...
}

// Clock.java
package com.coducation.smallbasic.lib;

public class Clock {
  public final static Value Day; // a value to read

  public static void notifyFieldRead(String fieldName) {
    if (“Day”.equalsIgnoreCase(fieldName)) {
       Day = ... set a value for Small Basic program to read after this call ...;
    }
  }
  ...
}

• Every Small Basic library function is implemented by the same named Java method. A Small Basic function can have the variable number of arguments.
  • Let us consider an example of Math.Sin function below.
  • The Java method Math.Sin implements the Small Basic Math.Sin function. It takes a single argument of class ArrayList<Value>, whose object can hold a list of values of class Value. Note Value is a class representing arbitrary Small Basic values in our evaluator.
  • The first thing inside the implementing method is to check the number of arguments, e.g., one in the example. When the number of arguments does not match with what is expected, it is implemented to throw an exception with InterpreteException.
  • Once the number of arguments is satisfied, the types of arguments should be examined. Small Basic is a dynamically typed programming language with only one type string internally. Number and boolean are convertible to string, and even an array can be converted to a string in some form. So the arguments should be properly converted to what the function expects before the function operation is performed.

// Math.java
package com.coducation.smallbasic.lib;

public class Math {
  ...
  public static void Value Sin(ArrayList<Value> args) {
    if (args.size() == 1) {
     Value sin_arg = args.get(0);
     ...
     double dbl_arg = ...;
     return new DoubleV(java.lang.Math.sin(dbl_arg);
    }
    else {
     throw InterpretException(“Sin : Unexpected # of args: ” + args.size());
    }
  }
}

The Architecture of Small Basic Debugger in Java

• The Small Basic debugger allows programmers to debug their Small Basic programs directly.
  • It provides a set of debugging functions as: start/stop debugging, set/unset breakpoints, step/continue, and watching variables and arrays.
  • The debugger is implemented with Java Debug Interface (JDI), Java Debug Wire Protocol (JDWP) and Java Tool Interface (lib/tools.jar), as shown in the following architecture diagram.

The Directory Structure of the MySmallBasic Project

• MySmallBasic

  • The top-level directory of the project
  • The parser relevant text files
    • sb_grammar_rule.txt (Small Basic LALR(1) Grammar)
    • sb_parsing_table.txt
    • sb_state_trans.txt
  • run.bat (for a quick start on Windows)

• MySmallBasic/src

  • The source directory

• MySmallBasic/src/com/coducation/smallbasic

  • MySmallBasic evaluator, abstract syntax tree classes (Stmt, Expr, etc), lexer, parser, AST transformation, and so on

• MySmallBasic/src/com/coducation/smallbasic/gui

  • MySmallBasic GUI and debugger

• MySmallBasic/src/com/coducation/smallbasic/lib

  • MySmallBasic library implementation of the standard Small Basic libraries and the extended libraries.

• MySmallBasic/docs

  • the document directory

• MySmallBasic/lib

  • Java libraries used for implementing Small Basic libraries and debugger

• MySmallBasic/Sample

  • Small Basic tutorial example programs

• MySmallBasic/regressiontest

  • Small Basic programs for testing the language features of MySmallBasic and the libraries

• MySmallBasic/resource/

  • Pictures, sounds, and the other resource files used for MySmallBasic GUI and libraries.