Talk:S-expressions

Slightly restricted versions of both syntaxes

Note that the definition for the internal syntax of S-expressions differs slightly from a more traditional definition where an S-expression is simply an ordered pair, the terms of which may be atomic symbols or simpler S-expressions:

${\begin{array}{rll}{\textit {S-expression}}&\rightarrow &{\mathit {ATOM}}~~\vert ~~({\textit {S-expression}}~.~{\textit {S-expression}})\end{array}}$

Remember $\scriptstyle {\mathit {ATOM}}\,$ may stand also for an empty list $\scriptstyle \mathbf {(~)}$ (which is called NIL in Lisp parlance).

In contrast, our definition doesn't allow other atoms than an empty list, i.e. ( ) (NIL in Lisp-parlance) on the right side of a pair. However, this restricted syntax then guarantees that in the external, "nested list"-syntax, only well-formed lists occur, with no trailing dotted pairs, thus compensating the added complexity of the internal syntax with the simpler grammar for the external syntax.