[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / comp.text.Meta
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Tue Sep 18 15:25:24 PDT 2007

Opening the PDF files on this page may require you to download Adobe Reader or an equivalent viewer (GhostScript).

Contents


    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 to the Algol 60 committee and Pete Naur worked with him to define a tool for defining Algol 60: [ algol60.syntax.html ]

      Since then various extensions to BNF have appeared in every programming languages reference manual.

    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 }.

        Here [ 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 [ 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::=";".
            PrioritySymbol
            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 comment_symbol end_comment_symbol, -- this definition does not 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,
            OpenCloseContains
            ''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

        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 most Unix platforms and generates HTML pages from XBNF documents. For examples

       		mth2html ebnf.mth
      generates ebnf.html and ebnf.txt ready to be published on the web.

      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 all discrete mathematics 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, see [ rjb99g.xbnf.html ] in an unpublished paper.

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

    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>>

End