.Open Syntactic meta-languages: BNF, BS6154, XBNF, ISO-EBNF $BNF was the first syntactic metalanguage to be used Once loose it rapidly became used, in a dozen different forms (Extended BNFs, EBNFs) to define many languages and file formats: .See http://home1.swipnet.se/~w-11382/abcbnf.htm#bnf and .See http://ds.internic.net/rfc/rfc822.txt for examples. These notes use $XBNF(eXtreme BNF). This is an extended BNF. In Britain there was a British Standard syntax language $BS6154. This is probably overridden by the International Standard Organization $EBNF. . BNF -- Backus Naur Form $BNF was introduced by John Backus to the Algol 60 committee and Pete Naur worked with him to define a tool for defining Algol 60: .See http://www/dick/samples/algol60.syntax.html Since then various extensions to BNF have appeared in every programming languages reference manual. BNF::acronym=`Backus Naur Form`. BNF::=Net{ non_terminal::="<"$phrase">", production::=$non_terminal "::=" $BNF_alternatives, BNF_alternatives::=$BNF_sequence#("|"$BNF_sequence), BNF_sequence::=#($terminal|$nonterminal|$whitespace), terminal::=$character~$meta meta::="<" | "|" | ">". phrase::=`a descriptive phrase in some natural language`. }=::BNF. .Open EBNF -- Extended BNF EBNF ::= `Extended $BNF`. Most post-Algol-60 languages have used a form of $BNF which is simpler to use. They typically remove the diamond brackets from non-terminal symbols and use either quotes or typography to indicate terminal symbols. The "double-colon-equals" is often reduced to an equals sign or a colon. Braces and square brackets are added to indicate repetitive and optional structures. For example, instead of the $BNF definition of an Algol 60 identifier: ::= | | one would write in most EBNF's: identifier = letter { letter | digit }. Here .See http://www.cs.cmu.edu/~pattis/misc/ebnf.pdf is a 23 page chapter on one form of EBNF. . ISO-EBNF -- Standard Extended BNF There is now an international standard $EBNF, see .See http://www.cl.cam.ac.uk/~mgk25/iso-ebnf.html for the draft (like all standards you have to pay for the final version). It seems to have inherited (via Roger Scowen?) many notations from $BS6154. here is $identifier identifier = letter, { letter | digit }; Notice the use of "," and ";" above. The following notes (in $XBNF) come from a 1996 draft. ISO_IEC_14977::=following, .Net .Open Normal Standard EBNF metasymbols repetition_symbol::="*". except_symbol::="-". concatenate_symbol::=",". definition_separator_symbol::="|". defining_symbol::="=". terminator_symbol::=";". .Table Priority Symbol .Row Do first * .Row 2nd - .Row 3rd , .Row 4th | .Row 5th = .Row Last ; .Close.Table first_quote_symbol::="'". second_quote_symbol::="\"". start_comment_symbol::= "(*". end_comment_symbol::= "*)". comment::=start_comment_symbol $comment_symbol $end_comment_symbol, -- this definition does not treat comments fairly. Comments are also used to indicate certain symbols such as white space. start_group_symbol::= "(". end_group_symbol::= ")". start_option_symbol::= "[". end_option_symbol::= "]". start_repeat_symbol::= "{". end_repeat_symbol::= "}". special_sequence_symbol::="?". other_symbol::=" " | "." | ":" | "!" | "+" | "_" | "%" | "@" | " &" | "#" | "$" | "<" | ">" | "/" | "\" | "^" | "`" | "~" . bracket_pairs::=following, .Table Open Close Contains .Row ' ' no ' .Row " " no " .Row ? ? no ? .Row (* *) comment characters .Row ( ) $definitions_list .Row [ ] $definitions_list .Row { } $definitions_list .Close.Table .Close Normal Standard EBNF metasymbols Alternative_representations::=following, .Net definition_separator_symbol::="/" | "!". terminator_symbol::=".". start_option_symbol::= "(/". end_option_symbol::= "/)". start_repeat_symbol::= "(:". end_repeat_symbol::= ":)". invalid_sequence::= "(*)" | "(:)" | "(/)". .Close.Net Alternative_representations syntax::= $N(syntax_rule). syntax_rule::=meta_identifier "=" definitions_list. meta_identifier::= letter #( letter | digit), -- spaces are ignored(?) inside identifiers and used to improve readability? definitions_list::=$L( $single_definition, $definition_separator_symbol). single_definition::=$L( $term, $concatenate_symbol). term::= $factor $O( $except_symbol $exception). exception::= $factor. factor::= $O( integer $repetition_symbol ) $primary. primary::= $optional_sequence | $repeated_sequence | $special_sequence | $grouped_sequence | $meta_identifier | $terminal_string | $empty. optional_sequence::= $start_option_symbol $definitions_list $end_option_symbol. repeated_sequence::= $start_repeated_symbol $definitions_list $end_repeated_symbol. grouped_sequence::= $start_group_symbol $definitions_list $end_group_symbol. special_sequence::= $special_sequence_symbol #($char ~ $special_quote_symbol) $special_sequence_symbol. terminal_string::= $first_quote_symbol #($char ~ $first_quote_symbol) $first_quote_symbol | $second_quote_symbol #($char ~ $second_quote_symbol) $second_quote_symbol. .Close.Net ISO_IEC_14977 .Close EBNF -- Extended BNF . British Standard Syntactic Metalanguage BS6154::=Net{ .Source Scowen R 83. Roger Scowen, An Introduction and Handbook for the Standard Syntactic Meta-language, National Physical Laboratory Report DITC 19/8, 1983 BS_definition::= $nonterminal "=" $alternatives ";", BS_alternatives::= $sequence #("|" $sequence), sequence::= $item #("," $item), item::= $group | $string | $nonterminal, string::=$single_quoted_string | $double_quoted_sting, group::= $optional_group | $selective_group | $iterated_group, optional_group::="["$BS_alternatives"]", selective_group::="("$BS_alternatives")", iterated_group::="{"$BS_alternatives"}". }=::BS6154. . eXtreme BNF XBNF is my own eXtreme BNF that tries to extend BNF to the maximum possible. Most of my sample documents .See http://www/dick/samples/ are written using $XBNF. It uses brackets and braces as in mathematics and has special operators for repetitions(#) and option(O). identifier::=letter #(letter | digit). There is a tool .See http://www/dick/tools/mth2html which runs on most Unix platforms and generates HTML pages from $XBNF documents. For examples .As_is mth2html ebnf.mth generates `ebnf.html` and `ebnf.txt` ready to be published on the web. For more see .See http://www.csci.csusb.edu/dick/maths/intro_ebnf.html and .See XBNF in BS Syntactic Meta Language below. XBNF is itself a subset of a powerful formal language (MATHS) designed for expressing all discrete mathematics in ASCII .See http://www.csci.csusb.edu/dick/samples/math.syntax.html that I created back in the late 1980's. For a discussion of how far you can extend $BNF before it breaks, see .See http://www/dick/papers/rjb99g.xbnf.html in an unpublished paper. . XBNF in BS Syntactic Meta Language XBNF::=Net{ .Use BS6154 dictionary= {definition|comment}; definition= defined_term, ':',':', '=', set_expression; set_expression= item, {'&', item }; item = (element | defined_term | '('selection ')' | meta_function '(' selection ')' ); selection= (alternative, { '|', alternative }; alternative= (complementary_form | sequence); sequence = {phase }; phase = ['#'], item; complementary_form= item , '~', item; element=quote, {ordinary_char|backslash, char}, quote; quote='"'; backslash='\'; comment={char}; ordinary_char=char; meta_function=identifier; }=::XBNF. With thanks to Skip Geel who, on Mar 22nd 2005, emailed me about a missing quotation/blip symbol in the XBNF.definition above. Some special definitions used to simplify XBNF: char::=`the ASCII characters`. empty::= . O(x)::= empty|x, -- opitonal x. N(x)::= x |x N(x), -- number of `x`s. #(x)::=$O(N(x)), -- zero or more `x`s. L(x,y)::= x #( y x), -- list of `x`s separated by `y`s. .Close Syntactic meta-languages: BNF, BS6154, XBNF, ISO-EBNF