EXPR =
  '<expr>' [ DEFUN | DEFMACRO | DEFVAR | TERM ] * '</expr>'

TERM = [ INT | STRING | SYMBOL | LIST | ERROR | VARREF | FUNCALL ]

DEFUN =
  '<defun fname="' FNAME '">'
  ARGS ?
  TERM *
  '</defun>'

DEFMACRO =
  '<defmacro fname="' FNAME '">'
  ARGS ?
  TERM *
  '</defmacro>'

ARGS =
  '<args>' FIXED * OPTIONAL * REST ? '</args>'

FIXED =
  '<fixed vname="' VNAME '">'

OPTIONAL =
  '<optional vname="' VNAME '">'

REST =
  '<rest vname="' VNAME '">'

DEFVAR = DEFVAR-INT | DEFVAR-STR | DEFVAR-SYM

DEFVAR-INT =
  '<defvar vname="' VNAME '">'
  DESCRIPTION ?
  [ INT POSSIBLE-INT-VALUE ? ] ?
  '</defvar>'

POSSIBLE-INT-VALUE =
  <possible-value> [ INT | '<range>' INT INT '</range>' ] + </possible-value>

DEFVAR-STR =
  '<defvar vname"' VNAME '">'
  DESCRIPTION ?
  [ STR DEFVAR-STR_VALUE ? ] ?
  '</defvar>'

DEFVAR-STR_VALUE =
  <possible-value> STR + </possible-value>

DEFVAR-SYM =
  '<defvar vname"' VNAME '">'
  DESCRIPTION ?
  [ SYMBOL POSSIBLE-SYM-VALUE ? ] ?
  '</defvar>'

POSSIBLE-SYM-VALUE =
  <possible-value> SYMBOL + </possible-value>

DESCRIPTION =
  '<description>' [ TEXT | GETTEXT ] '</description>'

GETTEXT =
  '<gettext>' TEXT '</gettext>'

INT =
  '<integer>' INTEGER '</integer>'
STR =
  '<string>' STRING '</string>'
SYMBOL =
  '<symbol>' NAME '</symbol>'
LIST =
  '<list>' TERM * '</list>'
ERROR =
  [ '<error>' | '<error ename="' ENAME '">"' ] STRING '</error>'

VARREF =
  '<varref vname="' VNAME '"/>'

FUNCALL =
  '<funcall fname="' FNAME '">' TERM * '</funcall>'
  | PREDEFINED

PREDEFINED =
  SET
  | AND | OR | NOT | EQ | NOTEQ | EQUAL | MATCH
  | LT | LE | GE | GT
  | ADD | SUB | MUL | DIV | MOD
  | LOGAND | LOGIOR | LOGXOR | LSH
  | APPEND | CONCAT | LENGTH | NTH  | COPY | INS | DEL
  | PROGN | IF | WHEN | COND
  | LOOP | WHILE | FOREACH | BREAK | RETURN | CATCH | THROW
  | QUOTE | EVAL | TYPE

;; TERM contains an object, and is evaluated to a TERM as below.
;; INT contains an integer, and is evaluated to itself .
;;   Two integers of the same value are regarded as the same object.
;; STRING contains a string, and is evaluated to itself.
;; SYMBOL contains a named symbol, and is evaluated to itself.
;;   Two symbols of the same name are reguarded as the same object.
;; LIST contains a list and, is evaluated to itself.
;; ERROR contains an error type symbol and an error message (optional).
;; VARREF contains a variable, and is evalued to the value of that variable.
;; FUNCALL contains a function and arguments to it, and is evalued to the
;; value of function called with those arguments.

INTTERM = INT | VAR (value is INT) | FUNCALL (return INT)
STRTERM = STR | VAR (value is STR) | FUNCALL (return STR)
SYMTERM = SYMBOL | VAR (value is SYMBOL) | FUNCALL (return SYMBOL)
LISTTERM = LIST | VAR (value is LIST) | FUNCALL (return LIST)
XXXTERM = TERM

;; Here after, when an argument is written as TERM, it is given to a
;; function without being evaluted.  Otherwise, an evaluated term is
;; given.  "the value is NUM" means "the value is
;; <integer>NUM</integer>".

SET = '<set vname="' VNAME '">' XXXTERM '</set>'

;; Set the value of the variable VNAME to XXXTERM, and the value is
;; XXXTERM.

ADD = '<add>' INTTERM + '</add>'
      | '<add vname="' VNAME '">' INTTERM + '</add>'
SUB = '<sub>' INTTERM + '</sub>'
      | '<sub vname="' VNAME '">' INTTERM + '</sub>'
MUL = '<mul>' INTTERM + '</mul>'
      | '<mul vname="' VNAME '">' INTTERM + '</mul>'
DIB = '<div>' INTTERM + '</div>'
      | '<div vname="' VNAME '">' INTTERM + '</div>'
MOD = '<mod>' INTTERM INTTERM '</mod>'
      | '<mod vname="' VNAME '">' INTTERM '</div>'
LOGAND = '<logand> INTTERM + '</logand>'
         | '<logand vname="' VNAME '">' INTTERM + '</logand>'
LOGIOR = '<logior> INTTERM + '</logior>'
         | '<logior vname="' VNAME '">' INTTERM + '</logior>'
LOGXOR = '<logxor> INTTERM + '</logxor>'
         | '<logxor vname="' VNAME '">' INTTERM + '</logxor>'
LSH = '<lsh>' INTTERM INTTERM '</lsh>'
      | '<lsh vname="' VNAME '">' INTTERM '</mul>'
LT = '<lt>' INTTERM INTTERM '</lt>'
LE = '<le>' INTTERM INTTERM '</le>'
GE = '<ge>' INTTERM INTTERM '</ge>'
GT ='<gt>' INTTERM INTTERM '</gt>'

EQ = '<eq>' XXXTERM + '</eq>'

;; If XXXTERMs have the same object, the value is 1.  Otherwise the
;; value is 0.

NOTEQ = '<noteq>' XXXTERM XXXTERM '</noteq>'

;; If XXXTERMs have the same object, the value is 0.  Othersise the
;; value is 1.

APPEND = '<append>' XXXTERM + '</append>'
         | '<append vname=" VNAME '">' XXXTERM + '</append>'

;; In the first form, the value is a LIST made by concatinating all
;; elements of XXXTERM (if it is a LIST) or XXXTERM itself (if it is
;; not a LIST) in the specified order.

;; In the second form, the value of the variable VNAME must be a LIST,
;; and that LIST is modified destructively by concatinating ANYterms
;; in the same manner as the previous case.  The value is the
;; resulting LIST.

CONCAT = '<concat>' [ STRTERM | INTTERM | LISTTERM ] + '</concat>'
         | '<concat vname=" VNAME '">' [ STRTERM | INTTERM | LISTTERM ] + '</concat>'

;; In the first form, the value is a STR made by concatinating all
;; the strings made from the arguments as below:
;;    STRTERM gives a string contained in it.
;;    INTTERM gives a string of a character whose code is INTTERM's integer.
;;    LISTTERM must contain only INTTERMs, and give a string containing
;;      characters whose codes are INTTERM's integer.

;; In the second form, the value of the variable VNAME must be a STR,
;; and that STR is modified destructively by concatinating the
;; arguments in the same manner as the previous case.  The value is
;; the resulting STR.

LENGTH = '<length>' [ STRTERM | LISTTERM ] '</length>'
NTH = '<nth>' INTTERM [ STRTERM | LISTTERM ] '</nth>'
COPY = '<copy>' [ STRTERM | LISTTERM ] '</nth>'
INS = '<ins vname="' VNAME '">' INTTERM [ STRTERM | LISTTERM ] '</ins>'
DEL = '<del vname="' VNAME '">' INTTERM INTTERM '</ins>'

AND = '<and>' TERM + '</and>'

;; Evaluates TERMs one by one until one is evaluated to 0.  If none is
;; evaluated to 0, the value is 1.  Othersise the value is 0.

OR = '<or>' TERM + '</or>'

;; Evaluates TERMs one by one until one is evaluated not to 0.  If
;; none is evaluated not to 0, the value is 0.  Othersise the value is
;; 1.

NOT = '<not>' XXXTERM '</not>'

;; If XXX is 0, the value is 1.  Othersise the value is 0.

EQUAL = '<equal>' XXXTERM1 XXXTERM2 '</equal>'

;; If XXX1 equals to XXX2, the value is 1.  Otherwise the value is 0.
;; The equality of terms is decided as below:
;;   INT: INT1 equals to INT2 iff they contain the same integer values.
;;   STR: STR1 equals to STR2 iff they contain strings of the same characters.
;;   SYM: SYM1 equals to SSYM2 iff they contain the same symbol.
;;   LIST: LIST1 equals to LIST2 iff they have the same length, and
;;     the Nth element of LIST1 equals to the Nth element of LIST2.

MATCH = '<match>' XXXTERM1 XXXTERM2 <'/match>'

;; If XXX1 matches with XXX2, the value is 1.  Otherwise the value is
;; 0.  Two terms match as below:
;;   INT: INT1 matches with INT2 iff they contain the same integer values.
;;   STR: STR1 matches with STR2 iff STR1's string is a valid regular
;;      expression matching with STR2's string
;;   SYM: SYM1 matches with SSYM2 iff they contain the same symbol.
;;   LIST: LIST1 matches with LIST2 iff LIST1 is not longer than
;;     LIST2, and Nth element of LIST1 equals to Nth element of LIST2.
;;   ERROR: ERROR1 matches with ERROR2 iff ERROR1's error type is
;;     <symbol/> or is the same as ERROR2's error type.

PROGN = '<progn>' TERM * '</progn>'
IF = '<if>' TERM TERM TERM ? '</if>'
WHEN = '<when>' TERM TERM * '</when>'
COND = '<cond>' LIST + '</cond>'
LOOP = '<loop>' TERM + '</loop>'
WHILE = '<while>' TERM + '</while>'
FOREACH = '<foreach vname="' VNAME '">' [STRTERM | LISTTERM] TERM + '</foreach>'
BREAK = '<break>' TERM ? '</break>'
RETURN = '<return>' TERM ? '</return>'
QUOTE = '<quote>' TERM '</quote>'

CATCH = '<catch>' [ SYMBOL | ERROR ] TERM + '</catch>'
        | '<catch vname="' VNAME '">' [ SYMBOL | ERROR ] TERM + '</catch>'

;; Evaluate TERMs one by one until a term matching with the specified
;; SYMBOL or ERROR is thrown by <throw/>.  If thrown, the value is 1,
;; otherwise the value is 0.  If VNAME is specified, its value is set
;; to the last evaluated term.  It is the value of <throw/> if thrown.

THROW = '<throw>' SYMBOL XXXTERM ? '</throw>'
        | '<throw>' ERROR '</throw>'

;; Throw to the catch for SYMBOL or ERROR.  The value is XXXTERM (if
;; any) or SYMBOL in the first form, and ERROR in the second form.

EVAL = '<eval>' TERM '</eval>'

TYPE = '<type>' XXXTERM '</type>'

;; The value is SYM representing the type of XXXTERM as below:
;;   INT: the type is <symbol>integer</symbol>
;;   STR: the type is <symbol>string</symbol>
;;   SYM: the type is <symbol>symbol</symbol>
;;   LIST: the type is <symbol>list</symbol>
;;   ERROR: the type is <symbol>error</symbol>