GRAIL Grammar for Lisp in Lisp

The following grammar shows how Small Lisp programs can be represented as Lisp data objects. This uses the GRAIL (Grammars in Lisp) formalism, which is essentially an augmented BNF. Each nonterminal on the RHS has two parts: a name which is used to name a data access function for selecting the component, as well as the grammatical type (syntactic category). Plus marks in the nonterminals indicate lists of one or more elements.

<expression> 	::=	<identifier> | <numeric-atom-expr> | 
                        <symbolic-atom-expr> | <list-expr> | 
                        <fn-call> | <cond-expr> | <let-expr>
<identifier> 	::=	<id-name:symbolic atom>
<numeric-atom-expr> 	::=	<numeric-val:numeric atom>
<symbolic-atom-expr> 	::=	( quote <symbolic-val:symbolic-atom> )
<list-expr> 	::=	( quote <list-val:list> )
<fn-call> 	::=	( <callee:identifier> <arguments:expression+> )
<cond-expr> 	::=	( cond <clauses:clause+> )
<clause> 	::=	( <predicate:expression> <result:expression> )
<let-expr> 	::=	( let ( <local-defs:local-def+> ) <final-expr:expression> )
<local-def> 	::=	( <local-var:variable> <local-val:expression> )

Data Accesss Functions in Small Lisp

The functions required by the GRAIL grammar above can be implemented as follows.

Recognizers

;;; The recognizers for Small Lisp expressions.
;;;
identifier-p[expr] = symbolp[expr]

numeric-atom-expr-p[expr] = numberp[expr]

symbolic-atom-expr-p[expr] =
  [listp[expr] -->
     [eq[first[expr]; "quote"] --> symbolp[second[expr]];
      otherwise --> F];
   otherwise --> F]

list-expr-p[expr] =
  [listp[expr] -->
     [eq[first[expr]; "quote"] --> listp[second[expr]];
      otherwise --> F];
   otherwise --> F]

fn-call-p[expr] =
  [listp[expr] -->
     [eq[first[expr]; "quote"] --> F;
      eq[first[expr]; "cond"] --> F;
      eq[first[expr]; "let"] --> F;
      otherwise --> T];
   otherwise --> F]

cond-expr-p[expr] =
  [listp[expr] --> eq[first[expr]; "cond"];
   otherwise --> F]

let-expr-p[expr] =
  [listp[expr] --> eq[first[expr]; "let"];
   otherwise --> F]

Converters

These trivial functions convert identifiers and numeric atoms to appropriate Lisp representations. We use functions in case we decide to change the representation later.

id-name[ident] = ident

make-identifier[id-name] = id-name

numeric-val[num-atom] = num-atom

make-numeric-atom-expr[val] = val

Symbolic atoms and List exprs

The access and constructor functions for symbolic-atom-exprs and list-exprs are nontrivial.

symbolic-val[sym-atom-expr] = second[sym-atom-expr]

make-symbolic-atom-expr[sym] = list2["quote"; sym]

list-val[list-expr] = second[list-expr]

make-list-expr[list] = list2["quote"; list]

Function Calls

make-fn-call[func; args] = cons[func; args]

callee[fn-call] = first[fn-call]

arguments[fn-call] = rest[fn-call]

Conditional Expressions and Clauses

make-cond-expr[clauses] = cons["cond"; clauses]

clauses[cond-expr] = rest[cond-expr]

make-clause[pred; result] = list2[pred; result]

predicate[clause] = first[clause]

result[clause] = second[clause]

Let-expressions

local-defs[let-expr] = second[let-expr]

final-expr[let-expr] = third[let-expr]

make-let-expr[defs; expr] = list3["let"; defs; expr]

local-var[local-def] = first[local-def]

local-val[local-def] = second[local-def]

make-local-def[var; val] = list2[var; val]

Definitions

;;;
;;; The recognizers for Small Lisp definitions (i.e., function
;;; and constant definitions).
;;;
fn-def-p[def] = eq[first[def]; "defun"]

const-def-p[def] = eq[first[def]; "setc"]

;;;
;;; The access functions for function definitions.
;;;
fn-name[fndef] = second[fndef]

parameters[fndef] = third[fndef]

body[fndef] = fourth[fndef]

make-fn-def[name; parms; body] = list4["defun"; name; parms; body]

;;;
;;; The access functions for constant definitions.
;;;
const-name[constdef] = second[constdef]

const-val[constdef] = third[constdef]

make-const-def[name; value] = list3["setc"; name; value]