Building Parsers and Interpreters with BNF

Understanding Parsers and Abstract Syntax

A Parser is a program that translates terms in concrete syntax into abstract syntax.

• In our language (PLAI, not Racket), we use {braces} instead of (parentheses) to distinguish concrete syntax from Scheme by looking at the delimiters.
• The parser identifies the program structure and converts it to the appropriate abstract syntax. This requires a clear specification of the concrete syntax using Backus-Naur Form (BNF).

Arithmetic BNF Specification

<AE> ::= <num>
      | {+ <AE> <AE>}
      | {- <AE> <AE>}

• The <AE> in BNF is a non-terminal, meaning it can be rewritten as one of the items on the right-hand side.
• The ::= symbol means “can be rewritten as.”
• Each | presents an additional choice, called a production.
• Everything in a production not enclosed in <> is literal syntax.

Implementing a Simple Parser

(define (parse sexp)
  (cond
    [(number? sexp) (num sexp)]
    [(list? sexp)
     (case (first sexp)
       [(+) (add (parse (second sexp)) (parse (third sexp)))]
       [(-) (sub (parse (second sexp)) (parse (third sexp)))])]))

Building an Interpreter

The calc function consumes an AE and computes the corresponding number:

(define (calc an-ae)
  (type-case AE an-ae
    [num (n) n]
    [add (l r) (+ (calc l) (calc r))]
    [sub (l r) (- (calc l) (calc r))]))

Identifiers and WAE

Identifiers are variables. Since our language initially lacks a way to change associated values, we use the term “identifier.”

WAE stands for “with arithmetic expressions.” Its BNF is:

<WAE> ::= <num>
        | {+ <WAE> <WAE>}
        | {- <WAE> <WAE>}
        | {with {<id> <WAE>} <WAE>}

• We added rules for associating values with identifiers and using them. The <id> non-terminal represents a sequence of alphanumeric characters.

WAE Data Definition

(define-type WAE
  [num (n number?)]
  [add (lhs WAE?) (rhs WAE?)]
  [sub (lhs WAE?) (rhs WAE?)]
  [with (name symbol?) (named-expr WAE?) (body WAE?)]
  [id (name symbol?)])

The with construct functions like passing an argument into a function (e.g., f(x) = x+x, f(2) = 4):

{with {x 5} {+ x x}} becomes {with {x 5} {+ 5 5}} after substitution.