Writing Recursive Code from a BNF

Where do I start?

It is easy to think that converting a BNF into scheme code will be very difficult.  But if you follow just a few simple steps, you will find how easy it can be to write a scheme function that solves the problem.

First, analyze the BNF

The BNF is the key to the structure of the function.  Let's write code for this sample BNF:

<exp>   ::= <number>
          | (+ <exp> <exp>)
          | (- <exp>)

Forget for a minute that all this grammar does is add and negate numbers.  Sometimes it's easier to write the code without knowing what the BNF means!  The easiest way to address all of the cases in a BNF is with a cond expression.  So I know from the start that my code is going to look something like this:

(define function
  (lambda (exp)
    (cond (..case 1..  ..expression 1..)
          (..case 2..  ..expression 2..)
          (..case 3..  ..expression 3..))
    ))

Another good thing to do is check to see where I am going to recurse, and how many times I am going to do it.  The first production only contains terminating symbols, so there will be no recursion for case 1.  Case 2 refers to the non-terminal exp twice, so this case will recurse exactly two times. Case 3 refers to the non-terminal exp once, so it will recurse once.  Since I know this about the BNF, I know that my code will have to look something like this:

(define function
  (lambda (exp)
    (cond (..case 1..  ..do not recurse..)
          (..case 2..  ...(function param)        

Notice:  Uninitialized string offset:  227 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 210

;; Note that there are three dots- meaning that some
                          (function param)...)    ;;  code is omitted.  We haven't written that part yet.
          (..case 3..  ...(function param)...))
    ))

Second, start with the easy cases

It makes sense to do the easy ones first, so let's write the code for the cases that don't involve recursion.

You should always ask yourself these questions for each case:

So our function will now look like this:

(define function
  (lambda (exp)
    (cond ((number? exp) exp)                    

Notice:  Uninitialized string offset:  206 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 210

;; According to the BNF, <exp> ::= <number>
          (..case 2..    ...(function param)
                            (function param)...)
          (..case 3..    ...(function param)...))
    ))

That does it for the easy cases, so let's move on.

Third, do the recursive cases in order of increasing complexity

In this example, case 3 has less recursive calls than case 2, so we'll do it first.  In general, I like to do them in order of how many times they recurse- starting with the one with the least amount of recursion.

So we need to negate whatever (cadr exp) is.  We don't really have to care what that evaluates to right now because we can assume that function will evaluate it correctly when we do the recursive call.  That's what makes induction so cool!  Anyway, our code will now look like this:

(define function
  (lambda (exp)
    (cond ((number? exp)      exp)
          (..case 2..         ...(function param)
                                 (function param)...)
          ((eq? (car exp) '-) (- 0 (function (cadr exp))))) 

Notice:  Uninitialized string offset:  42 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 210

;; cadr == Get element two from exp
    ))

With similar logic, we can deduce the last case:

(define function
  (lambda (exp)
    (cond ((number? exp)       exp)
          ((eq? (car exp) '+)  (+ (function (cadr exp))     

Notice:  Uninitialized string offset:  209 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 210

;; cadr == Get element two from exp
                                  (function (caddr exp))))  ;; caddr == Get element three from exp
          ((eq? (car exp) '-)  (- 0 (function (cadr exp)))))
    ))

We have now successfully translated a BNF into Scheme code.

Other things to consider

Multiple non-terminals

You may see a BNF with more than one non-terminal (hint. hint. Exam 1).  For each non-terminal on the left side of the BNF productions you will need a scheme function.  For example:

<num>   ::= <number>
          | ...
<sym>   ::= <symbol>
          | ...

Would require two functions:

(define func1
  (lambda (num)
    ...
  ))
  
(define func2
  (lambda (sym)
    ...
  ))

Environments and Counters

Sometimes we need to keep track of a few things during the recursion.  The free-vars program for Homework 11 is a good example of this.  With this problem, we have to keep track of a list of bound variables.  All we have to do to handle this is create an auxiliary function that accepts the extra parameter(s), then write the function as explained in the above steps.  My version of free-vars looks much like the one on the help page:

(define free-vars
  (lambda (exp)
    (free-vars-aux exp '())))

(define free-vars-aux
  (lambda (exp potentially-bound-vars)
    ...))

Just enumerate the cases as shown in the example above and TRUST THE RECURSION!

Debugging

The best way to debug these types of functions is to make sure the base case works first, then make sure the other cases work too.  For the example above, I would test case 1 first by calling (function 2). Once I was sure that the correct answer was returned for every simple case, I would move to the next one.  For the recursive cases, I would test something that would terminate on the next call.  For example, to test case 2, I would call (function '(+ 2 2)) since I know that exp will terminate on the next step due to case 1, and I know that case 1 works.  I would do the same thing for case 3.  The cool thing about these functions is that if each of the cases works for the simplest tests, they will work for ALL of them.

Good Luck!

Last updated at 9:53 am on Friday, August 27, 2004.