91.204 Computing IV Wiki

Using Scribbler to Learn Compiler Basics

In 91.204 Computer IV, we will use Scribbler robot devices as the system target to learn compiler basics. To program the Scribbler robots, we have designed a new language: Chirp-Scribbler. Chirp-Scribbler has C-like syntax, and includes both common and specialized language features to program Scribbler. The full specificiation of Chirp-Scribbler is described in this PDF spec.

Chirp-Scribbler Lite (CSLite)

To make it possible to build a Chirp-Scribbler compiler project in a short time frame, we will implement a simplified subset of the Chirp-Scribbler language, called CSLite. The sample compiler demonstrates the basics of lexing, parsing, and code generation to compile CSLite to target Scribbler.

CSLite Features

CSLite is a subset of Chirp-Scribbler, you should first read the above Chirp-Scribbler language spec PDF. Comparing to the full language, CSLite provides only the following language features:

• Variable definitions.
• Assignment statement, if-else statement, function call (to call System and Scribbler system functions), and block statement - statement list wrapped around by {}, similar to C.
• Arithmetic expressions, including +,-,*,/, % (mod) operators. Variables, numbers, and string constants are atomic expressions.

What CSLite does NOT have:

• bit, nib, pin, rom datatypes and array variables.
• function definition.
• general function call and return.
• loop statements: loop, loop-while, loop-until, break, for.

Implementation of these features will be done in the student's project.

Using CSLite features, CSLite program can be written as a collection of variable definitions and statements. The following program demonstrates the use of CSLite: hello.csl sample program:

     int a;
     byte b;
     int c;

     int led1;
     int led2;
     int led3;

     a = 3;
     b = 4;
     c = a+b*5;

     System.print("hello, world");
     System.print("a=", a);
     System.print("b=", b);
     System.print("c=", c);

     if (a%2) {
       led1 = 1;
     } else {
       led1 = 0;
     }

     a = a/2;
     if (a%2) {
       led2 = 1;
     } else {
       led2 = 0;
     }


     a = a/2;
     if (a%2) {
       led3 = 1;
     } else {
       led3 = 0;
     }
     Scribbler.setLED(led3, led2, led1);

     System.print("Done demo.");

CSLite Sample Compiler: csc

To help you build the CSLite compiler, we will give you a working CSLite sample compiler csc. In the student's project, you will study the source code of csc and extended to implement the required language features.

You can download the csc source code using this link: download csc Eclipse project .zip file. The easiest way to run it is using Eclipse: select file menu Import->Existing Project->Choose archive file and select your downloaded .zip file, then Eclipse will import the CSLite project in your workspace and you should be able to run the Test classes.

The following are information and directions to use csc.

1. csc use ANTLR tool to build the front end lexer and parser. The ANTLR rule files are in the csc package directory. To generate the lexer and parser Java files, you need to run command:
   

     java antlr.Tool lexer.g and 
     java antlr.Tool parser.g
   

   
   This will run ANTLR on your rule file and create the lexer and parser. Make sure you have antlr.jar file in your CLASSPATH.
2. The csc is implemented using the standard front-end, back-end structure. You may want to review discussion on compiler front-end and back-end to understand the concepts. After you generate the lexer and parser .java files, you can build the Eclipse project which will compile all java files.
3. You can use TestLexer, TestParser, TestCodeGen to run the sample lexer, parser and csc compiler. You can either run these in Eclise by Project->Open Run dialog and create a run configuration->specify the input program file; or you can run at command line:
   

     java csc.TestLexer hello.csl
     java csc.TestParser hello.csl
     java csc.TestCodeGen hello.csl
   

   
   Running TestCodeGen will compile the above hello.csl example and generate the following PBASIC code:
   

        ' {$STAMP BS2}
        ' {$PBASIC 2.5}
   
        LED_left PIN   10
        LED_center PIN 9
        LED_right PIN 8
   
        a VAR WORD
        b VAR BYTE
        c VAR WORD
        led1 VAR WORD
        led2 VAR WORD
        led3 VAR WORD
        a = 3
        b = 4
        c = (a)+((b)*(5))
        DEBUG "hello, world", CR
        DEBUG "a=", DEC a, CR
        DEBUG "b=", DEC b, CR
        DEBUG "c=", DEC c, CR
        IF ((a)//(2)) THEN
        led1 = 1
        ELSE
        led1 = 0
        ENDIF
        a = (a)/(2)
        IF ((a)//(2)) THEN
        led2 = 1
        ELSE
        led2 = 0
        ENDIF
        a = (a)/(2)
        IF ((a)//(2)) THEN
        led3 = 1
        ELSE
        led3 = 0
        ENDIF
        OUTPUT LED_left
        OUTPUT LED_center
        OUTPUT LED_right
        LED_left = led3
        LED_center = led2
        LED_right = led1
        DEBUG "Done demo.", CR
   

   
   Run the above yourself, and observe the generated output: the lexer should print token stream, and display XML tree of the token stream; the parser will parse the input and generate the AST tree in XML; the codegen will print out the compiled PBASIC commands. Now write your own CSLite program and run through the test class and see what output will be.
4. JDOM. We will use open source JDOM XML package to represent the AST tree used by csc compiler. Check out the JDOM wiki. To run csc or JDOM classes directly, you need to download the jdom.jar, jdom-contrib.jar

References

• Chirp-Scribbler spec PDF
• ANTLR manual
• Scribbler PBASIC Manual

Download Files

• CSLite.zip
• antlr.jar
• jdom.jar
• jdom-contrib.jar
• csctool.jar

The csctool.jar has the XMLTreeView class which can be used to display the JDOM Document or Element tree.