;;;;;; Pseudo-BNF description of Scheme's syntax           -*- Text -*-

;;; Taylor Campbell wrote this text; he places it in the public domain.

;;; [TRC 2009-10-19: Updated for the first time since 2005-09-09 to
;;; omit a duplicate "~" in the <symbol initial> production rule.]

;;; This file describes the syntax of Scheme at two different levels,
;;; and it partitions the core of Scheme's syntax from standard macros
;;; such as COND or LET.  The first level of the syntax is the level of
;;; S-expression representations of Scheme objects.  Note that, since
;;; this is only BNF, it does _not_ provide a useful mapping from text
;;; to the Scheme objects represented by that text; it only describes
;;; the syntax of S-expressions.  The second level described here is
;;; Scheme's syntax itself; note that the description is in terms of
;;; Scheme objects, _not_ text.  This applies similarly to the section
;;; on standard macros.  (Note that there is, again, no mapping from
;;; the syntax of standard macros to the transformed expressions in a
;;; more primitive Scheme.)

;;; --------------------
;;; S-expression syntax

<S-expression> ---> <whitespace>* <quotation prefix> <whitespace>*
  <raw S-expression>

;;; <Whitespace character> is left unspecified.  It is expected to at
;;; least contain the ASCII characters space, carriage return, form
;;; feed/page, line feed, & tab.

<whitespace> --->
    <whitespace character>
  | ";" <any character that does not constitute a newline>* <newline>

<quotation prefix> ---> <empty> | "'" | "`" | "," | ",@"

<raw S-expression> --->
    <symbol>
  | <number 10>
  | <list>
  | <string>
  | <octothorpical>

;;; <Symbol> must be terminated by a delimiter as listed here.  The
;;; <delimiter> nonterminal is not actually used, however, since it
;;; would consume.

<delimiter> ---> <whitespace> | "(" | ")" | <string delimiter> | ";"

<symbol> --->
    <symbol initial> <symbol constituent>*
  | <peculiar symbol>
<symbol initial> ---> <letter> | "!" | "$" | "%" | "&" | "*" | "/"
  | ":" | "<" | "=" | ">" | "?" | "^" | "_" | "~"
<symbol constituent> ---> <symbol initial> | <digit> | "+" | "-" | "."
  | "@"
<peculiar symbol> ---> "+" | "-" | "..."

;;; The number-related rules should all be replicated for each R in {2,
;;; 8, 10, 16}.  <Decimal 10> is the only decimal rule; decimal points
;;; may not be written with other radices.  <Digit R> is a digit valid
;;; with a radix of R.  Radix 2 has 0 & 1; radix 8, 0-7; radix 10, 0-9;
;;; & radix 16, 0-9 & A-F.

<number with exactness prefix R> --->
    "#i" <number R>
  | "#e" <number R>
  | <number R>

<number with radix prefix> --->
    "#x" <number 16>
  | "#d" <number 10>
  | "#o" <number 8>
  | "#b" <number 2>
  | <number 10>

<number R> --->
    <real R>
  | <real R> "@" <real R>
  | <real R> "+" <real R> "i"
  | <real R> "-" <real R> "i"
  | <real R> "+i"
  | <real R> "-i"
  | "+" <real R> "i"
  | "-" <real R> "i"
  | "+i"
  | "-i"

<real R> ---> <optional sign> <unsigned real R>
<unsigned real R> --->
    <unsigned integer R>
  | <unsigned integer R> "/" <unsigned integer R>
  | <decimal R>

<unsigned integer R> ---> <digit R>+ "#"*

<decimal 10> --->
    <unsigned integer 10> <exponent suffix>
  | <raw decimal 10> "#"* <exponent suffix>
<raw decimal 10> --->
    "." <digit 10>+
  | <digit 10>+ "." <digit 10>*
  | <digit 10>+ "#"+ "."

<optional sign> ---> <empty> | "+" | "-"
<exponent suffix> --->
    <empty>
  | <exponent width> <optional sign> <digit 10>+
<exponent width> ---> "e" | "s" | "f" | "d" | "l"

<list> ---> "(" <S-expression>* <optional dot> <list terminator>
<optional dot> ---> <empty> | <S-expression> <dot> <S-expression>
<list terminator> ---> <list delimiter prefix> ")"
<dot> ---> <list delimiter prefix> "." <whitespace>*
<list delimiter prefix> --->
    <whitespace>*
  | <whitespace>* "#;" <S-expression> <whitespace>*

<string> ---> <string delimiter> <string element>* <string delimiter>
<string element> --->
    <any character other than " or \>
  | "\\"
  | "\" <string delimiter>
<string delimiter> ---> <the literal character ">

<octothorpical> ---> "#" <octothorpe dispatch>

<octothorpe dispatch> --->
    "t" | "f"                                   ; Boolean
  | "\" <character specifier>                   ; Character
  | "(" <S-expression>* <list terminator>       ; Vector
  | "x" <number with exactness prefix 16>       ; Hexadecimal
  | "d" <number with exactness prefix 10>       ; Decimal
  | "o" <number with exactness prefix 8>        ; Octal
  | "b" <number with exactness prefix 2>        ; Binary
  | "i" <number with radix prefix>              ; Inexact
  | "e" <number with radix prefix>              ; Exact
  | ";" <S-expression> <S-expression>           ; S-expression comment

<character specifier> ---> <character name> | <any character>
<character name> ---> "space" | "newline"       ; Case-insensitive here



;;; --------------------
;;; Scheme's syntax

;;; <Datum> is used in this section to denote any Scheme object,
;;; usually only those that can be read with READ (i.e. those that have
;;; external representations that could be accepted by the above
;;; grammar for S-expressions).

;;; At the top level, a Scheme program consists of a sequence of
;;; <command or definition> terms.

<command or definition> ---> <command> | <top-level sequence>
  | <definition> | <syntax definition>

<top-level sequence> ---> (BEGIN <command or definition>*)

<definition> --->
    (DEFINE <symbol> <expression>)
  | (DEFINE (<symbol> . <bvl>) . <lambda body>)

<syntax definition> --->
    (DEFINE-SYNTAX <symbol> <transformer specifier>)

;;; Syntax transformers

<transformer specifier> ---> (SYNTAX-RULES (<symbol>*) <syntax rule>*)

<syntax rule> ---> (<pattern> <template>)

<pattern> --->
    <simple pattern>
  | (<pattern> . <pattern>)
  | (<pattern>* <pattern> <ellipsis>)
  | #(<pattern>*)
  | #(<pattern>* <pattern> <ellipsis>)

<template> --->
    <simple pattern>
  | (<template> . <template>)
  | (<template> <ellipsis> . <template>)

<simple pattern> ---> <any symbol except ...> | <self-evaluating>
<ellipsis> ---> <the symbol ...>

;;; Expressions, commands, & bodies

<expression> --->
    <symbol>
  | <literal>
  | <combination>
  | <lambda>
  | <expression sequence>
  | <recursive binding>
  | <conditional>
  | <assignment>
  | <macro use>
  | <macro block>

<command> ---> <expression>

<literal> ---> <quotation> | <self-evaluating>
<quotation> ---> (QUOTE <datum>)
<self-evaluating> ---> <boolean> | <number> | <character> | <string>

<combination> ---> (<expression>+)

<lambda> ---> (LAMBDA <bvl> . <lambda body>)
<bvl> ---> <symbol> | () | (<symbol> . <bvl>)

<expression sequence> ---> (BEGIN . <body>)

<recursive binding> --->
  (LETREC ((<symbol> <expression>)*) . <lambda body>)

<lambda body> ---> (<internal definition>* . <body>)
<body> ---> (<command>* <expression>)

<internal definition> --->
    <definition>
  | (BEGIN <internal definition>*)

<conditional> --->
    (IF <expression> <expression> <expression>)
  | (IF <expression> <command>)

<assignment> ---> (SET! <symbol> <expression>)

<macro use> ---> (<keyword> . <datum>)
<macro block> --->
       (LET-SYNTAX ((<keyword> <transformer specifier>)*)
         . <lambda body>)
  | (LETREC-SYNTAX ((<keyword> <transformer specifier>)*)
      . <lambda body>)



;;; --------------------
;;; Miscellaneous macro syntax

<COND> --->
    (COND <COND clause>* <ELSE clause>)
  | (COND <COND clause>+)
<COND clause> --->
    (<expression>)
  | (<expression> => <expression>)
  | (<expression> . <body>)

<CASE> --->
    (CASE <CASE clause>* <ELSE clause>)
  | (CASE <CASE clause>+)
<CASE clause> ---> ((<datum>*) . <body>)

<ELSE clause> ---> (ELSE . <body>)

<conjunction> ---> (AND <expression>*)
<disjunction> ---> (OR  <expression>*)

<LET> --->
    (LET ((<symbol> <expression>)*) . <lambda body>)
  | (LET <symbol> ((<symbol> <expression>)*) . <lambda body>)

<sequential LET> ---> (LET* ((<symbol> <expression>)*) . <lambda body>)

<DO> ---> (DO (<DO binding>*)
              <DO test & result>
            <command>*)
<DO binding> --->
    (<symbol> <expression>)
  | (<symbol> <expression> <expression>)
<DO test & result> ---> (<expression>) | (<expression> <expression>)

<lazy evaluation> ---> (DELAY <expression>)

;;; Quasiquotations are not context-free.  Their syntax is determined
;;; by their nesting depth D.  A rule <name D> can be considered to be
;;; replicated infinitely for integers D > 0.

<quasiquotation> ---> <quasiquotation 1>
<quasiquotation D> ---> (QUASIQUOTE <qq template D>)

<simple qq> ---> <self-evaluating> | <symbol>

<qq template 0> ---> <expression>
<qq template D> --->
    <simple qq>
  | <unquotation D>
  | <quasiquotation D + 1>
  | <list qq template D>
  | <vector qq template D>

<unquotation D> ---> (UNQUOTE <qq template D - 1>)
<splicing unquotation D> ---> (UNQUOTE-SPLICING <qq template D - 1>)

<list qq template D> --->
    (<splicing unquotation D> . <qq template>)
  | (<qq template> . <qq template>)

<vector qq template D> --->
    #(<qq template or splice D>*)
<qq template or splice D> --->
    <qq template D>
  | <splicing unquotation D>