1.5 Syntactic Summary

^1.2

All parts of the LISP language have now been explained. That which follows is a complete syntactic definition of the LISP language, together with semantic comments. The definition is given in Backus notation with the addition of three dots (...) to avoid naming unneccessary syntactic types.

In Backus notation the symbols "::=" , " $<$" , " $>$" , and " $\vert$" are used. The rule $<$S-expression $>$::= $<$atomic symbol $>$ $\vert$ ( $<$S-expression $>$ . $<$S-expression $>$) means that an S-expression is either an atomic symbol, or it is a left parenthesis followed by an S-expression followed by a dot followed by an S-expression followed by a right parenthesis. The vertical bar means "or" , and the angular brackets always enclose elements of the syntax that is being defined.

The Data Language

$<$LETTER $>$ ::= A $\vert$ B $\vert$ C $\vert$ $\ldots$ $\vert$ Z 
$<$number $>$ ::= 0 $\vert$ 1 $\vert$ 2 $\vert$ $\ldots$ $\vert$ 9 
$<$atomic-symbol $>$ ::= $<$LETTER $>$ $<$atom part $>$  
$<$atom part $>$ ::= $<$empty $>$ $\vert$ $<$LETTER $>$ $<$atom part $>$ $\vert$ $<$number $>$ $<$atom part $>$

Atomic symbols are the smallest entities in LISP. Their decomposition into characters has no significance.

$<$S-expression $>$ ::= $<$atomic symbol $>$ $\vert$  
        ( $<$S-expression $>$ . $<$S-expression $>$) $\vert$  
        ( $<$S-expression $>$ $\ldots$ $<$S-expression $>$)

When three dots are used in this manner, they mean that any number of the given type of symbol may occur, including none at all. According to this rule, () is a valid S-expression. (It is equivalent to NIL.)

The dot notation is the fundamental notation of S-expressions, although the list notation is often more convenient. Any S-expression can be written in dot notation.

The Meta-Language

$<$letter $>$ ::= a $\vert$ b $\vert$ c $\vert$ $\ldots$ $\vert$ z 
$<$identifier $>$ ::= $<$letter $>$ $<$id part $>$  
$<$id part $>$ ::= $<$empty $>$ $\vert$ $<$letter $>$ $<$id part $>$ $\vert$ $<$number $>$ $<$id part $>$

The names of functions and variables are formed in the same manner as atomic symbols but with lower-case letters.

$<$form $>$ ::= $<$constant $>$ $\vert$ $<$variable $>$ $\vert$  
         $<$function $>$[ $<$argument $>$; $\ldots$ ; $<$argument $>$] $\vert$  
         ${[}$ $<$form $>$ $\rightarrow$ $<$form $>$; $\ldots$ ; $<$form $>$ $\rightarrow$ $<$form $>$]  
$<$constant $>$ ::= $<$S-expression $>$  
$<$variable $>$ ::= $<$identifier $>$  
$<$argument $>$ ::= $<$form $>$

A form is an expression that can be evaluated. A form that is merely a constant has that constant as its value. If a form is a variable, then the value of the form is the S-expression that is bound to that variable at the time when we evaluate the form.

The third part of this rule states that we may write a function followed by a list of arguments separated by semicolons and enclosed in square brackets. The expressions for the arguments are themselves forms; this indicates that compositions of functions are permitted.

The last part of this rule gives the format of the conditional expression. This is evaluated by evaluating the forms in the prepositional position in order until one is found whose value is T. Then the form after the arrow is evaluated and gives the value of the entire expression.

$<$function $>$ ::= $<$identifier $>$ $\vert$  
         $\lambda$[ $<$var list $>$; $<$form $>$] $\vert$  
        label[ $<$identifier $>$; $<$function $>$]  
$<$var list $>$ ::= [ $<$variable $>$; $\ldots$ ; $<$variable $>$]

A function can be simply a name. In this case its meaning must be previously understood. A function may be defined by using the lambda notation and establishing a correspondence between the arguments and the variables used in a form. If the function is recursive, it must be given a name by using a label.