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:

. Meta Symbols

The "::=" means "is defined to be". "|" separates alternatives. XBNF defined terms (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}.

. More