Now, to code! The first thing we have to do is translate the BNF terms into Scheme data types, so we can actually manipulate them in scheme. We'll choose a Scheme representation for each BNF term, and we'll make a predicate function for each term that tells us whether a given scheme data object is an instance of that term type.
You will notice that the code used in each predicate is basically the BNF syntax. A direct translation.
We will include the pattern matching module in PLT mzscheme because it makes writing the operator predicates very straightforward:
(require (lib "match.ss"))
We will represent terminals of type K (numerical constants) using Scheme's number types: so any number Scheme recognizes is a valid K terminal. So the built-in predicate number? is all we need to tell if a term is a constant in our grammar:
(define constant? number?)
We will represent terminals of type V (variable identifiers) as symbols belonging to a set of predefined variable symbols. We'll store this set in the global variable *variable-names*:
(define *variable-names* '(x y z s t q r))(define (variable? var) (if (member var *variable-names*) #t #f))
Now, the meat of the issue are the nonterminals of type mul-expr, sum-expr, etc. Just as the BNF definition of a given operator expression is recursive (operator expressions are defined in terms of expressions) the predicate for identifying them will be recursive. Let's make predicates for the *, /, + and - cases.
We represent these cases as lists of the form
( )
This common structure for these binary operators means we can abstract a function that makes predicates for a given binary operator. The function make-binary-operator-pred is a function that returns functions. We use that predicate-generating function to make predicates for the operators we'll use. This is the only nontrivial code written so far; the third link in my previous post is the documentation for the mzscheme pattern matcher, but check the fourth link for a simpler explanation:
(define (make-binary-operator-pred op-symbol) (lambda (expr) (match expr ((operator subexpr1 subexpr2) (and (eq? operator op-symbol) (expression? subexpr1) (expression? subexpr2))) (anything-else #f))))(define mul-expr? (make-binary-operator-pred '*))(define div-expr? (make-binary-operator-pred '/))(define sum-expr? (make-binary-operator-pred '+))(define sub-expr? (make-binary-operator-pred '-))
The predicate returned by make-binary-operator-pred is a function that tries to match its argument expr to the (operator subexpr1 subexpr2) pattern. If it matches, it ensures that operator is indeed the symbol that represents the operator the predicate recognizes (stored in op-symbol), and also ensures that subexpr1 and subexpr2 are valid subexpressions, by executing
(and (eq? operator op-symbol) (expression? subexpr1) (expression? subexpr2)).
anything-else is guaranteed to match anything at all. It works kind of like the else clause in a cond; in this case, I use it to mean that any pattern that is not matched by (operator subexpr1 subexpr2) is not a binary operation so the predicate should return false.
Now we can trivially define the expression? predicate, which looks exactly like the BNF definition for :
(define (expression? expr) (or (constant? expr) (variable? expr) (mul-expr? expr) (div-expr? expr) (sum-expr? expr) (sub-expr? expr)))
Notice that, given the BNF definition, we directly translated each nonterminal into scheme code.
These predicates allow us to validate an expressions' syntactical correctness. They also will allow us to dispatch control on expression type, which is what we need in order to manipulate symbolic expressions.
Let's test it:
> (expression? '(+ 3 (- 4 5)))#t> (expression? 5)#t> (expression? '(y))#f> (expression? '(+ y (- 4 5)))#t> (expression? '(+ e (- 4 5)))#f> (expression? '(b y (- 4 5)))#f
