Arithmetic expressions

Goal

This note describes how to implement a BNF for arithmetic expressions and how to implement a syntax checker, i.e., a procedure that checks whether a given value conforms to this BNF.

BNF of arithmetic expressions

An arithmetic expression is either a literal (any Scheme number), the addition of two arithmetic expressions, or the multiplication of two arithmetic expressions. Its abstract syntax is defined inductively with the following BNF, in the same fashion as the regular expressions presented in Week 02, i.e., with tagged proper lists:

<arithmetic-expression> ::= (literal <literal>)
                          | (plus <arithmetic-expression> <arithmetic-expression>)
                          | (times <arithmetic-expression> <arithmetic-expression>)

<literal>               ::= ...any Scheme number...

Implementation of the BNF

The BNF is implemented with constructors, predicates, and accessors.

• Here are the constructors:

  (define make-literal
    (lambda (n)
      (list 'literal n)))
  
  (define make-plus
    (lambda (e1 e2)
      (list 'plus e1 e2)))
  
  (define make-times
    (lambda (e1 e2)
      (list 'times e1 e2)))
  

• Here are the predicates, using the same auxiliary procedure proper-list-of-given-length? as above:

  (define is-literal?
    (lambda (v)
      (and (pair? v)
           (equal? (car v) 'literal)
           (proper-list-of-given-length? (cdr v) 1))))
  
  (define is-plus?
    (lambda (v)
      (and (pair? v)
           (equal? (car v) 'plus)
           (proper-list-of-given-length? (cdr v) 2))))
  
  (define is-times?
    (lambda (v)
      (and (pair? v)
           (equal? (car v) 'times)
           (proper-list-of-given-length? (cdr v) 2))))
  

• And here are the accessors:

  (define literal-1
    (lambda (v)
      (list-ref v 1)))
  
  (define plus-1
    (lambda (v)
      (list-ref v 1)))
  
  (define plus-2
    (lambda (v)
      (list-ref v 2)))
  
  (define times-1
    (lambda (v)
      (list-ref v 1)))
  
  (define times-2
    (lambda (v)
      (list-ref v 2)))
  

Sample of well-formed arithmetic expressions

(define ae0
  (make-literal 32))

(define ae1
  (make-plus (make-literal 1)
             (make-literal 10)))

(define ae2
  (make-plus ae1
             (make-plus (make-literal 100)
                        (make-literal 1000))))

(define ae3
  (make-times
    (make-times
      (make-times
        (make-literal 1)
        (make-literal 2))
      (make-literal 3))
    (make-times
      (make-literal 4)
      (make-literal 5))))

• ae0 is meant to be evaluated to 32.
• ae1 represents 1 + 10 and is meant to be evaluated to 11.
• ae2 represents (1 + 10) + (100 + 1000) and is meant to be evaluated to 1111.
• ae3 represents ((1 * 2) * 3) * (4 * 5) and is meant to be evaluated to the factorial of 5, i.e., 120.

Positive unit-test procedure

Given a procedure implementing a syntax checker, the following testing procedure successively applies it to each of the four well-formed arithmetic expressions to verify that they syntax-check:

(define test-check_well-formed-arithmetic-expressions
  (lambda (candidate)
    (and (candidate ae0)
         (candidate ae1)
         (candidate ae2)
         (candidate ae3)
         ;;; add more tests here
         )))

Negative unit tests

A syntax checker should not only accept well-formed expressions – otherwise (lambda (v) #t) would do fine and be very quick, thank you very much – it should also reject ill-formed expressions. So far, the goal of all our unit tests has been to verify that the syntax checkers accept well-formed expressions. But we also need to devise unit tests to verify that the syntax checkers reject ill-formed expressions. In other words, we do not only need positive unit tests to verify something: we also need negative unit tests to verify its converse.

Sample of ill-formed arithmetic expressions

(define ea0
  32)

(define ea1
  '(literal))

(define ea2
  '(literal . whatever))

(define ea3
  '(literal 10 . whatever))

(define ea4
  '(literal 10 20))

(define ea5
  '(plus))

(define ea6
  '(plus . whatever))

(define ea7
  '(plus (literal 10) . whatever))

(define ea8
  '(plus (literal 10) (literal 20) . whatever))

(define ea9
  '(plus (literal 10) (literal 20) (literal 30)))

Negative unit-test procedure

(define test-check_ill-formed-arithmetic-expressions
  (lambda (candidate)
    (not (or (candidate ea0)
             (candidate ea1)
             (candidate ea2)
             (candidate ea3)
             (candidate ea4)
             (candidate ea5)
             (candidate ea6)
             (candidate ea7)
             (candidate ea8)
             (candidate ea9)
             ;;; add more tests here
             ))))

Given a procedure implementing a syntax checker, this testing procedure successively applies it to each of the ill-formed arithmetic expressions to verify that they fail to syntax-check.

The syntax checker for arithmetic expressions

Here is an implementation of the syntax checker as a Scheme procedure. Given a value, it decides whether this value conforms to the BNF of arithmetic expressions. This procedure attempts to traverse its input recursively as per the inductive definition of arithmetic expressions (i.e., the BNF). If it can, the input is syntactically correct and the result is #t. If it cannot, the input is not syntactically correct and the result is #f:

(define check-arithmetic-expression
  (lambda (e)
    (cond
      [(is-literal? e)
       (number? (literal-1 e))]
      [(is-plus? e)
       (and (check-arithmetic-expression (plus-1 e))
            (check-arithmetic-expression (plus-2 e)))]
      [(is-times? e)
       (and (check-arithmetic-expression (times-1 e))
            (check-arithmetic-expression (times-2 e)))]
      [else
       #f])))

Let us positively test this syntax checker:

> (test-check_well-formed-arithmetic-expressions check-arithmetic-expression)
#t
>

Success. Let us negatively test it as well:

> (test-check_ill-formed-arithmetic-expressions check-arithmetic-expression)
#t
>

Success as well.

Exercise 01

Extend the BNF of arithmetic expressions with subtractions (minus), quotients (quotient), and remainders (remainder). To this end, you will need to define new constructors, new predicates, and new accessors, as well as new positive tests, new negative tests, and new clauses in the syntax checker.

Version

Created [09 Oct 2025]