SBI: The Small Basic Interpreter

Steve works at Boeing North American and teaches object-oriented programming at California State University, Fullerton. He can be reached at [email protected]. Tom, who owns Polar Engineering and Consulting, can be contacted at http://www.kenai.com or at 907-776-5509.

With the Internet's increasing ability to provide a complete interactive experience, scripting languages such as JavaScript and VBScript (along with their corresponding interpreter engines) have received lots of attention. But the Web isn't the only place to find scripting -- it's also a core part of desktop applications like Microsoft Word, Excel, and Access. In fact, the VBA (Visual Basic for Applications) engine lies at the heart of almost all of Microsoft's software.

Although interpreted code typically runs slower than compiled code, it can give your applications several advantages. First, you can promote key functionality to the run-time domain. Run-time programmability gives you the latest possible binding, which results in the ultimate flexibility. Users instantly gain the capability to modify a program's functionality. Scripts also bridge the gap between code and data. When you put scripts into databases, plain files, or remote sites, programs suddenly take on different characteristics, and changes to your application can take place without having to recompile. If your program was written in Visual Basic, having a Visual Basic scripting language also makes it easier to design and maintain your code -- you can selectively choose which code to put into the run-time domain. Microsoft thought of all these things when it developed its Office applications with the underlying COM (Component Object Model) mechanism.

In this article, we'll share the capabilities of COM that make it easier to write a scripting language. We'll present the Small Basic Interpreter (SBI) -- an engine that interprets a significant subset of Visual Basic. The complete SBI system, which you can immediately use and extend, is available electronically (see "Availability," page 3) and at http://www.kenai.com/.

Scripting Options

If you want to provide scripting in an application, you have several options, including JavaScript, VBA, and the like. However, you'll have to talk with the vendors about licenses, which usually have usage limitations, involve royalties, and cost money.

You can also use a VBA-compatible library such as the Sax Basic Engine, an OCX control you drop onto a Visual Basic form or MFC window. It gives you VBA with minimal limitations and no royalties -- for only a few hundred dollars. Its user interface includes a source-code editor with an integrated, step-mode debugger.

Polar Engineering designed both the Sax Basic Engine and SBI. SBI serves two primary purposes. First, it demonstrates the power of VB's general polymorphism mechanism, which makes it easy to implement the Interpreter design pattern (see Design Patterns, by Erich Gamma and others, Addison-Wesley, 1994). It also demonstrates a DLL called the InvokeMethod Library that makes it easy for VB applications to tap into COM. You can download the InvokeMethod library, register it in the Registry, and add the library to a VB project using the Tools|References dialog in VB. It gives your VB app the ability to manipulate an object's methods using strings.

SBI Characteristics

SBI, which implements a simple version of the VB syntax, consists of language control structures, expressions, and built-in functions/instructions.

SBI implements a useful subset of VB's language control structures. Code passed to SbiEngine's RunThis method must contain a Sub Main; see Listing One (SbiEngine is the public interface exposed by the SbiDll32.DLL. SbiEngine has two methods and three properties; see Table 1.) No other procedure definitions are allowed. Variables are declared automatically and arrays are not supported.

As Table 2 shows, SBI's expressions include nearly all of the normal VB capabilities. Complex expressions are allowed. SBI also provides most of the power that VB's built-in functions and instructions provide; see Table 3.

A set of VB class modules implements SBI. Figure 1 illustrates the Interpreter design pattern used in the SBI. Before using the interpreter, you can optionally create some VB classes to use as extension objects. All of the public members (methods, properties) of your extension objects become global variables and methods to the script code. Next, create an instance of SbiEngine and call its AddExtension method to add each extension. The first parameter to AddExtension is an empty string in SBI. However, you could improve it so that it works like the Sax Basic Engine's AddExtension method, which lets you pass a name such as "MyClass" to make your extensions behave like objects. Now you're ready to load the script from a database or wherever, and pass it to the engine by calling RunThis. Internally, the engine goes through two main steps.

It first creates a parser that translates the entire script, including extensions, into a hierarchical collection of SbiObjects. Each SbiObject subclass represents a grammar rule. To implement the parser's recursive descent mechanism, a parsing subroutine also exists for each grammar rule. These subroutines further contain a Select statement for each token fetched from the code stream. Whenever the parser detects a call to a method on an extension object, the parser checks that such a method exists, then generates an SbiFunctionFactorOp object. (It checks for the method's existence by calling VirtualGetIDsOfNames in the InvokeMethod library and checking for an error.) Each SbiFunctionFactorOp object stores a reference to the language extension, the method ID, type of method invocation (Function, Sub, Property) and other SbiObjects representing the arguments of the call. The parse method returns an SbiBlock that contains a collection of SbiObjects corresponding to the statements in the block. To execute the code, the engine calls Execute on the block, which in turn calls Execute on all of the statements, which also call Execute as necessary. The Execute method takes as a parameter an SbiController, which maintains the execution state (the run-time stack). The controller also has methods used by SbiObjects for invoking methods on extensions.

Looking Under SBI's Hood

Even though VB does not support inheritance, it can still be used in the design of a VB class library. Since all VB classes are descended from Object, you can use an inheritance tree. There are 18 classes used to implement the SBI; see Figure 2. There are 5 abstract classes. The abstract classes are not implemented, but are used to classify the classes.

All descendants of the SbiObject abstract class implement Example 1(a). These classes implement the executable objects in the SBI class library. All descendants of the SbiAdicOp abstract class implement Example 1(b). These classes implement the monadic and dyadic operators in expressions. Operator precedence affects the order in which operators are evaluated in expressions. All descendants of the SbiFactorOp abstract class implement Example 1(c). These classes implement the factors in expressions. All descendants of the SbiStmt class implement Example 1(d). The classes in Table 4 implement the executable statements.

Converting Code to Executable Objects

Parsing the code is done in two steps: As the text is tokenized, the tokens are recognized and the appropriate executable objects are generated. Tokenizing extracts the VB identifiers and operators from the code string. This simplifies the parsing logic since tokens (words) can be examined one at a time. SBI's tokenizing is sped up by using a number of tables (arrays) that can be indexed by number. VB's collections are used for symbol lookup.

As the code is being parsed, executable objects are emitted from the parser. These objects are created to represent the appropriate action that the controller should take.

Once the entire code string has been parsed, it is packaged up as a single SbiBlock object that contains the list of statements. SbiBlock's Execute method is then called to execute the code.

Polymorphic Execution

The SbiController object implements a stack machine. Most interpreters are implemented as stack machines, because that is an easy way to manage partial expressions and nested execution. The Execute method of every executable object is passed a reference to the SbiController. This allows the executable object to push or pop values from the controller's stack.

SbiMonadicOp implements the monadic operators +, -, and Not. It is a good example of how the Execute method is implemented. The definition of a monadic operator determines what the Execute method needs to do. As Listing Two illustrates, monadic operators replace the top value on the stack with the appropriate result.

Virtual Invocation

One weakness of VB is its inability to call methods/properties of an object by providing a string expression for the name. Normal VB syntax requires that the name be an identifier (like the name of a variable) and it can't be adjusted at run time. One solution is to make a Select Case statement and call each method explicitly. This assumes, however, that the names of all the methods are known at compile time.

Without a solution to this problem, SBI could not add extensions to the language. Fortunately, the InvokeMethod Library from Polar Engineering and Consulting (http://www.kenai.com/polar/) comes to the rescue. It is an OLE DLL written in C++ that adds some very useful capabilities to VB. Most importantly, it allows SBI to call methods/properties by name. SbiController's InvokeName method provides the necessary glue to call an object's method/property with a string value as its name (Listing Three), which in turn makes implementing SbiMethOp's Execute method straightforward (see Listing Four).

Conclusion

SBI does not execute code as fast as VB. The simple timing test in Example 2 was run on a Pentium 120 in three different environments: VB, Sax Basic/WinWrap Basic, and SBI. Table 5 presents its results. Even at 1/15th the speed of VB, having the ability to execute strings of code at run time can be very useful.

Executing code at run time has two potential pitfalls: First, the code may not be syntactically valid; second, the code may cause a run-time error. In both cases, SBI returns the errors to the calling application via its Error properties. It is the application's responsibility to decide what action, if any, needs to be taken.

Additional control structures could be added to the SBI. This is not as easy as adding new keywords by using AddExtension. To add a new control structure, new classes must be added to the SBI that implement its execution. Also, SbiParser's ParseStmt method would need to be modified to parse the new control structure.

DDJ

Listing One

Sub Main    ...
End Sub
[Let] var = expr
[Let] obj.prop[(args]) = expr
[Let] obj!index = expr
Set var = expr
Set obj.prop[(args]) = expr
Set obj!index = expr
func [args]
obj.method [args]
Call func[(args)]
Call obj.method[(args)]
If expr Then
    ...
[Else
    ...]
End If
While expr
    ...
Wend
For var = expr To expr _
          [Step expr]
    ...
Next [var]

Back to Article

Listing Two

' push (monadicop pop)Sub Execute _
  (Controller As SbiController)
  Dim Value As Variant
  Controller.PopValue Value
  Select Case m_OpNum
  Case SbiPosOpNum ' +
    Value = Value + 0
  Case SbiNegOpNum ' -
    Value = -Value
  Case SbiNotOpNum ' Not
    Value = Not Value
  End Select
  Controller.PushValue Value
End Sub

Back to Article

Listing Three

Sub InvokeName(_    ByVal Obj As Object, _
    Name As String, _
    InvokeType As Integer, _
    Exprs As Collection, _
    Optional Result As Variant)
  Dim N As Integer
  Dim Args() As Variant
  If Not Exprs Is Nothing Then
    ' evaluate all of the exprs
    ' place results in Args
     ReDim Args(1 To _
       Exprs.Count) As Variant
     Dim Expr As SbiExpr
     For Each Expr In Exprs
       Expr.Execute Me
       N = N + 1
       PopValue Args(N)
     Next Expr
   End If
  ' call method/prop by name
   VirtualInvokeByName
     Obj, _
     Name, _
     InvokeType, _
     Args, _
     Result
End Sub

Back to Article

Listing Four

Sub Execute _  (Controller As SbiController)
  m_FactorOp.Execute Controller
  Dim Value As Variant
  Controller.PopValue Value
  Dim Obj As Object
  Set Obj = Value
  Select Case m_InvokeType
  Case imcInvokeMethod + _
       imcInvokePropertyGet
    Controller.InvokeName _
      Obj, _
      m_Method, _
      m_InvokeType, _
      m_Exprs, _
      Value
    Controller.PushValue Value
  Case Else
    Controller.InvokeName _
      Obj, _
      m_Method, _
      m_InvokeType, _
      m_Exprs
  End Select
End Sub



Back to Article


Copyright © 1997, Dr. Dobb's Journal