**Cheat Sheet for the XBNF Metalanguage**

This page summarizes a practical version of the Backus Naur Form ( BNF) in the book. You will need it for the project, in the final,
and in class. It is called **XBNF**. This stands for eXtreme
BNF because it is an eXtremely eXtended BNF. The name was invented by a student of CS320 -- Bob Arter
who died in 2009.

Use XBNF whenever you need to define anything.

**. Example**

BNF <number>::=<digit>|<number> <digit>

XBNF number::= N(digit).

More examples are on the WWW:

http://cse.csusb.edu/dick/samples/algol60.syntax.html

http://cse.csusb.edu/dick/samples/

http://cse.csusb.edu/cs320/index.html#BNF

**. Meta Symbols**

The "::=" means "is defined to be". "|" separates alternatives. XBNF *defined term*s (BNF non-terminal symbols) have no <_>.
Instead the terminal symbols are written as C/C++/Java strings using double quotation marks. Parentheses "()" are used as they are
in algebra. XBNF uses "#" for `any number of, including zero`, "O(_)" for options, and "N(_)" for "one or more of". Three
dots("...") indicate that something is defined somewhere else.

**. Predefined XBNF Lexemes**

You can use any of the following terms in defining syntax:

char::=`any ASCII character`. digit::= "0".."9". capital_letter::="A".."Z". letter::=capital_letter | "a".."z". underscore="_". sign::= "+" | "-". comma::=",", semicolon::=";", left_bracket::="[", right_bracket::="]". quotes::="\'". space::=" ". non_quote::=char ~ quotes. l_paren::="(", r_paren::=")",...

**. Generalized Definitions**

XBNF lets you define terms using any kind of mathematical expression. This lets it be used for semantics, glossaries, and dictionaries as well as syntax.

*term *::=*expression*.

*term *::=`*informal description*`.

For *parameters *, *term *::=*expression*.

*term *::*type *=*expression*.

*term *::*type*, *properties_of_term.*

For *parameters *, *term *::*type *=*expression*.

**. Predefined XBNF Operations**

The expressions in XBNF definitions are constructed using mathematical operators and functions.

**Algebra **+ - * / ^ =(`equal to`) < > <= >= <>(`not equal to`) ...

**Logic** and or not iff if...then..., for all...(...), for some ....(....).

**Set Theory** A | B::=union, A B::=concatenation, #A ::=`zero or more A's concatenated`,

A & B::=intersection, A ~ B::= complement, @A::=`Power Set`,

A><B ::=`Cartesian product (set of pairs)`, %A ::= `Set of parenthesized Lists`,

A->B::=`The set of functions or mappings that given an A return a B`.

{ x : A || P(x) }::=`The set of x in A that make P(x) true`.

**. Predefined sets**

Boolean::={true, false}, Bit::={0,1}, Byte::=0..255, Natural::={1,2,3,...},

Unsigned::={0,1,2,3,...}, Integer::={..., -2,-1,0,1,2,...}

Rational::=`Ratios of two Integers`, Real::=`See mathematical texts`,

Float(s) ::=`Rational with a power of two as a denominator and *s* significant bits`.

For i, j, i..j ::= {k || i<=k<=j }, the set of k such that i <= k <= j,

(i..*)::={k || k>=i}, (*..j)::={k || k<=j}.