Challenge Lab: Language Interpretation

Grammar

A computer language is defined by a prescriptive grammar. Don't confuse this with the descriptive grammars that define natural languages (like English). A prescriptive grammar demands that its language follow the rules. A descriptive grammar changes its rules as the language changes.

For this lab we will work with a simple language, marmalade3000. Here is its grammar. [labbie: discuss grammar specification style/notation and also marmalade3000's weaknesses]

Tokenizing

When we deal with code that needs to be interpreted, the first thing that we are dealing with is a stream of characters. Here is some "code" in a language that you are familiar with, algebra:

        3 * [5+17]

We need to make sense of this stream of characters. The first step is to separate the code into "tokens". A tokenizer doesn't have (and doesn't want) extensive knowledge of the grammar of the language and only deals with chopping up the stream of characters into smaller chunks. The result of tokenizing the above expression might look something like this:

        (list '3 '* '[ '5 '+ '17 '] )

Note how the tokenizer knew that [ and 5 should be different tokens but that 1 and 7 should come together to make 17. Now that we have the code into tokens, it's time for...

PARSING

In different contexts people have varying definitions of where tokenizing ends and were parsing begins. In general, A parser definitely has full knowledge of the grammar, and the tokenizer has as much knowledge as you want it to have to create "ideal" input for the parser.

The parser takes the series of tokens and, using the rules of the grammar, generates structures which represent parts of the language. These structures are called...

Abstract Syntax

Abstract syntax is a nice, clean, and organized way to represent a program. It is the last thing we need before we start interpreting the meaning of the program. When we have code into abstract syntax, we know that it does not have errors and it is not ambiguous. The abstract syntax for our expression might look like this:

        (make-multiply (make-number '3) (make-add (make-number '5) (make-number '17)))

Notice that we no longer need to represent the square brackets from our original code, since their meaning is now represented by the structure of the abstract syntax.

Evaluation

It's time to actually evaluate the meaning of the code. Now that we have the abstract syntax, our work is cut out for us. Looking at our example, what does the program have to do? The data (and how the program runs) looks like this:

(*
   3
   (+
      5
      17
   )
)

As an exercise (below) you will write evaluation functions for marmalade3000.

Error Reporting

We won't go into it in depth, but something important to mention is that at each of these steps, a certain amount of error checking is happening. If the tokenizer comes across a character that is not part of the languages grammar, it will halt and report the error. If the parser see's that the code tries to multiply 3 numbers when the language only allows multiplying 2, it will halt and report the error.

Exercises

Exercise 1

group1:

(define (imperative_series_eval as) ...)

Desired behavior: whatever each line of code reduces to is printed on the screen, line by line. Use this if you want:

  (define (output value)
    (begin
      (display value)
      (display (list->string (list #\newline)))))

group2:

(define (expression_eval as) ...)

Assume that definition_eval and reference_eval are available to you.

group3:

(define (number_eval as) ...)
(define (boolean_eval as) ...)
(define (binary_operator_eval as) ...)

group4:

(define (application_as_eval as) ...)

Exercise 2

• How would you implement definition_eval and reference_eval?
• What do you need in order for those two functions to define and reference the same variables?
• How can you make reference_eval behave appropriately if the same name is used for two variables (we want the most recent one)?

Solution

Here is the final code.