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: [ bnf in abcbnf ] and [ 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 and developed by Pete Naur as a tool for defining Algol 60: [ algol60.syntax.html ]
1. BNF::acronym=Backus Naur Form.
2. BNF::=
   Net{

   1. non_terminal::="<"phrase">",
   2. production::=non_terminal "::=" BNF_alternatives,
   3. BNF_alternatives::=BNF_sequence#("|"BNF_sequence),
   4. BNF_sequence::=#(terminal|nonterminal|whitespace),
   5. terminal::=character~meta
   6. meta::="<" | "|" | ">".
   7. phrase::=a descriptive phrase in some natural language.

   
   }=::BNF.

   EBNF -- Extended BNF

   1. 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:

   2. <identifier>::= <letter> | <identifier> <letter> | <identifier> <digit>

      one would write in most EBNF's:

   3. identifier = letter { letter | digit }.

      ISO-EBNF -- Standard Extended BNF

      There is now an international standard EBNF, see [ 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
   4. identifier = letter, { letter | digit };

      Notice the use of "," and ";" above.

      The following notes (in XBNF) come from a 1996 draft.

   5. ISO_IEC_14977::=following,
      Net

      Normal Standard EBNF metasymbols

      1. repetition_symbol::="*".
      2. except_symbol::="-".
      3. concatenate_symbol::=",".
      4. definition_separator_symbol::="|".
      5. defining_symbol::="=".
      6. terminator_symbol::=";".

         Priority	Symbol
         Do first	*
         2nd	-
         3rd	,
         4th	|
         5th	=
         Last	;

      7. first_quote_symbol::="'".
      8. second_quote_symbol::="\"".

      9. start_comment_symbol::= "(*".
      10. end_comment_symbol::= "*)".

      11. comment::=start_comment_symbol commnet_symbol end_comment_symbol, -- this definition does treat comments fairly.

          Comments are also used to indicate certain symbols such as white space.

      12. start_group_symbol::= "(".
      13. end_group_symbol::= ")".
      14. start_option_symbol::= "[".
      15. end_option_symbol::= "]".

      16. start_repeat_symbol::= "{".
      17. end_repeat_symbol::= "}".

      18. special_sequence_symbol::="?".

      19. other_symbol::=" " | "." | ":" | "!" | "+" | "_" | "%" | "@" | " &" | "#" | "$" | "<" | ">" | "/" | "\" | "^" | "`" | "~" .

      20. bracket_pairs::=following,

          Open	Close	Contains
          '	'	no '
          "	"	no "
          ?	?	no ?
          (*	*)	comment characters
          (	)	definitions_list
          [	]	definitions_list
          {	}	definitions_list

      . . . . . . . . . ( end of section Normal Standard EBNF metasymbols) <<Contents | End>>

      1. Alternative_representations::=following,
         Net
         1. definition_separator_symbol::="/" | "!".
         2. terminator_symbol::=".".
         3. start_option_symbol::= "(/".
         4. end_option_symbol::= "/)".
         5. start_repeat_symbol::= "(:".
         6. end_repeat_symbol::= ":)".
         7. invalid_sequence::= "(*)" | "(:)" | "(/)".

         
         (End of Net Alternative_representations)
         
         

      2. syntax::= N(syntax_rule).

      3. syntax_rule::=meta_identifier "=" definitions_list.

      4. meta_identifier::= letter #( letter | digit), -- spaces are ignored(?) inside identifiers and used to improve readability?

      5. definitions_list::=L( single_definition, definition_separator_symbol).

      6. single_definition::=L( term, concatenate_symbol).

      7. term::= factor O( except_symbol exception).

      8. exception::= factor.

      9. factor::= O( integer repetition_symbol ) primary.

      10. primary::= optional_sequence | repeated_sequence | special_sequence | grouped_sequence | meta_identifier | terminal_string | empty.

      11. optional_sequence::= start_option_symbol definitions_list end_option_symbol.
      12. repeated_sequence::= start_repeated_symbol definitions_list end_repeated_symbol.
      13. grouped_sequence::= start_group_symbol definitions_list end_group_symbol.

      14. special_sequence::= special_sequence_symbol #(char ~ special_quote_symbol) special_sequence_symbol.
      15. terminal_string::= first_quote_symbol #(char ~ first_quote_symbol) first_quote_symbol | second_quote_symbol #(char ~ second_quote_symbol) second_quote_symbol.

      
      (End of Net ISO_IEC_14977)
      
      

   . . . . . . . . . ( end of section EBNF -- Extended BNF) <<Contents | End>>

   British Standard Syntactic Metalanguage

3. BS6154::=
   Net{

   Scowen R 83. Roger Scowen, An Introduction and Handbook for the Standard Syntactic Meta-language, National Physical Laboratory Report DITC 19/8, 1983
   1. BS_definition::= nonterminal "=" alternatives ";",
   2. BS_alternatives::= sequence #("|" sequence),
   3. sequence::= item #("," item),
   4. item::= group | string | nonterminal,
   5. string::=single_quoted_string | double_quoted_sting,
   6. group::= optional_group | selective_group | iterated_group,
   7. optional_group::="["BS_alternatives"]",
   8. selective_group::="("BS_alternatives")",
   9. 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 [ http://csci.csusb.edu/dick/samples/ ] are written using XBNF. It uses brackets and braces as in mathematics and has special operators for repetitions(#) and option(O).
4. identifier::=letter #(letter | digit).

   There is a tool [ mth2html ] which runs on Unix platforms and generates HTML pages from XBNF documents.

   For more see [ intro_ebnf.html ] and [ XBNF in BS Syntactic Meta Language ] below.

   XBNF is itself a subset of a powerful formal language (MATHS) designed for expressing any discrete mathematical idea in ASCII [ 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 into the semantic and formal domains see [ rjb99g.xbnf.html ]

   XBNF in BS Syntactic Meta Language

5. XBNF::=
   Net{

   .Use BS6154
   1. dictionary= {definition|comment};
   2. definition= defined_term, ':',':', =', set_expression;
   3. set_expression= item, {'&', item };
   4. item = (element | defined_term | '('selection ')' | meta_function '(' selection ')' );
   5. selection= (alternative, { '|', alternative };
   6. alternative= (complementary_form | sequence);
   7. sequence = {phase };
   8. phase = ['#'], item;
   9. complementary_form= item , '~', item;
   10. element=quote, {ordinary_char|backslash, char}, quote;
   11. quote='"';
   12. backslash='\';
   13. comment={char};
   14. ordinary_char=char;
   15. meta_function=identifier;

   
   }=::XBNF.

   Some special definitions used to simplify XBNF:

6. char::=the ASCII characters.
7. empty::= .
8. O(x)::= empty|x, -- opitonal x.
9. N(x)::= x |x N(x), -- number of xs.
10. #(x)::=O(N(x)), -- zero or more xs.
11. L(x,y)::= x #( y x), -- list of xs separated by ys.

. . . . . . . . . ( end of section Syntactic meta-languages: BNF, BS6154, XBNF, ISO-EBNF) <<Contents | End>>