syn.tex

\chapter{Formal syntax and semantics}
\label{formalchapter}

This chapter provides formal descriptions of what has already been
described informally in previous chapters of this report.

\section{Formal syntax}
\label{BNF}

This section provides a formal syntax for Scheme written in an extended
BNF.

All spaces in the grammar are for legibility.  Case is significant
in the definition of \meta{letter}; for example,  {\cf foo} and {\cf Foo}
are distinct.
\meta{empty} stands for the empty string.

The following extensions to BNF are used to make the description more
concise:  \arbno{\meta{thing}} means zero or more occurrences of
\meta{thing}; and \atleastone{\meta{thing}} means at least one
\meta{thing}.

\subsection{Lexical structure}

This section describes how individual tokens\index{token} (identifiers,
numbers, etc.) are formed from sequences of characters.  The following
sections describe how expressions and programs are formed from sequences
of tokens.

\vest Identifiers are
terminated by a \meta{delimiter} or by the end of the input.
So are numbers and booleans.

The following ten characters from the ASCII repertoire
are reserved for future extensions to the
language or are used in \rsevenrs:
{\tt \verb"[" \verb"]" \verb"{" \verb"}" \verb',' \verb'@'
\verb'"' \verb'|' \verb'\'} \verb"`"

In addition to the identifier characters of the ASCII repertoire specified
below, Scheme implementations may permit any additional repertoire of
Unicode characters to be employed in identifiers,
provided that each such character has a Unicode general category of Lu,
Ll, Lt, Lm, Lo, Mn, Mc, Me, Nd, Nl, No, Pd, Pc, Po, Sc, Sm, Sk, So,
or Co, or is U+200C or U+200D (the zero-width non-joiner and joiner,
respectively, which are needed for correct spelling in Persian, Hindi,
and other languages).
However, it is an error for the first character to have a general category
of Nd, Mc, or Me.  It is also an error to use a non-Unicode character
in symbols or identifiers.

\label{identifiersyntax}

\begin{grammar}%
\meta{token} \: \meta{identifier} \| \meta{boolean} \| \meta{number}\mainindex{identifier}
\>  \| ( \| ) \| \singlequote{}
\meta{delimiter} \: \meta{whitespace} \| ( \| ) \| ;
\meta{intraline whitespace} \: \meta{space or tab}
\meta{whitespace} \: \meta{intraline whitespace} \| \meta{line ending}
\meta{line ending} \: \meta{newline} \| \meta{return} \meta{newline}
\> \| \meta{return}
\meta{comment} \: ; \= $\langle$\rm all subsequent characters up to a
		    \>\ \rm line ending$\rangle$\mainindex{comment}
\end{grammar}

%start with \meta{identifier}
\begin{grammar}%
\meta{identifier} \: \meta{initial} \arbno{\meta{subsequent}}
 \>  \| \meta{peculiar identifier}
\meta{initial} \: \meta{letter} \| \meta{special initial}
\meta{letter} \: a \| b \| c \| ... \| z
\> \| A \| B \| C \| ... \| Z
\meta{special initial} \: ! \| \$ \| \% \| \verb"&" \| * \| / \| : \| < \| =
 \>  \| > \| ? \| \verb"^" \| \verb"_" \| \verb"~"
\meta{subsequent} \: \meta{initial} \| \meta{digit}
 \>  \| \meta{special subsequent}
\meta{digit} \: 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9
\meta{explicit sign} \: + \| -
\meta{special subsequent} \: \meta{explicit sign} \| . 
\meta{peculiar identifier} \: \meta{explicit sign}
 \> \| \meta{explicit sign} \meta{sign subsequent} \arbno{\meta{subsequent}}
 \> \| \meta{explicit sign} . \meta{dot subsequent} \arbno{\meta{subsequent}}
 \> \| . \meta{dot subsequent} \arbno{\meta{subsequent}}
 %\| 1+ \| -1+
\meta{dot subsequent} \: \meta{sign subsequent} \| .
\meta{sign subsequent} \: \meta{initial} \| \meta{explicit sign}

\meta{boolean} \: \schtrue{} \| \schfalse{}
\end{grammar}

\label{numbersyntax}
\begin{grammar}%
  \meta{number} \: \meta{sign} \atleastone{\meta{digit}}

  \meta{sign} \: \meta{empty}  \| + \|  -
\end{grammar}

\subsection{External representations}
\label{datumsyntax}

\meta{Datum} is what Pico Scheme
successfully parses.  Note that any string that parses as an
\meta{ex\-pres\-sion} will also parse as a \meta{datum}.  \label{datum}

\begin{grammar}%
\meta{datum} \: \meta{simple datum} \| \meta{compound datum}
\meta{simple datum} \: \meta{boolean} \| \meta{number}
\>  \|  \meta{symbol}
\meta{symbol} \: \meta{identifier}
\meta{compound datum} \: \meta{list} \| \meta{abbreviation}
\meta{list} \: (\arbno{\meta{datum}}) \| (\atleastone{\meta{datum}} .\ \meta{datum})
\meta{abbreviation} \: ' \meta{datum}
\end{grammar}

\subsection{Expressions}

The definitions in this and the following subsections assume that all
the syntax keywords defined in this report have not been redefined or shadowed.

\begin{grammar}%
\meta{expression} \: \meta{identifier}
\>  \| \meta{literal}
\>  \| \meta{procedure call}
\>  \| \meta{lambda expression}
\>  \| \meta{conditional}
\>  \| \meta{derived expression}

\meta{literal} \: \meta{quotation} \| \meta{self-evaluating}
\meta{self-evaluating} \: \meta{boolean} \| \meta{number}
\meta{quotation} \: '\meta{datum} \| (quote \meta{datum})
\meta{procedure call} \: (\meta{operator} \arbno{\meta{operand}})
\meta{operator} \: \meta{expression}
\meta{operand} \: \meta{expression}

\meta{lambda expression} \: (lambda \meta{formals} \meta{body})
\meta{formals} \: (\arbno{\meta{identifier}}) \| \meta{identifier}
\meta{body} \:  \arbno{\meta{definition}} \meta{expression}

\meta{conditional} \: (if \meta{test} \meta{consequent} \meta{alternate})
\meta{test} \: \meta{expression}
\meta{consequent} \: \meta{expression}
\meta{alternate} \: \meta{expression} \| \meta{empty}

\meta{derived expression} \:
\>  \> (cond \atleastone{\meta{cond clause}})
\>  \| (cond \arbno{\meta{cond clause}} (else \meta{expression}))
\>  \| (and \arbno{\meta{test}})
\>  \| (or \arbno{\meta{test}})
\>  \| (let (\arbno{\meta{binding spec}}) \meta{body})

\meta{cond clause} \: (\meta{test} \meta{expression})
\meta{binding spec} \: (\meta{identifier} \meta{expression})
\end{grammar}

\subsection{Programs and definitions}

\begin{grammar}%
\meta{program} \:
\> \atleastone{\meta{expression or definition or io}}
\meta{expression or definition or io} \: \meta{expression}
\> \| \meta{definition} \| \meta{io}
\meta{definition} \: (define \meta{identifier} \meta{expression})
\meta{io} \: (display \meta{expression}) \| (newline)
\end{grammar}