What is the BNF of BNF? i.e. How do we define a BNF meta-grammar?

Question

I am trying to define the BNF of BNF. In other words, I am trying to define the meta-grammar of BNF. That is, a BNF grammar that is an instance of itself and can generate any other BNF grammar.

Any tips/hints/snippets would be highly appreciated!

Thank you!

Answer 1

Here's one:

bnf = rules ;
rules = rule ;
rules = rules rule ;
rule = lefthandside EQUAL righthandside SEMICOLON  ;
lefthandside = IDENTIFIER ;
righthandside = ;
righthandside = righthandside token ;
token = IDENTIFIER ;
token = QUOTEDLITERAL ;

This leaves IDENTIFIER, QUOTEDLITERAL, EQUAL and SEMICOLON undefined, under the assumption that the BNF is defined over langauge tokens.

You can define BNF over characters. Just add:

EQUAL = '=' ;
SEMICOLON = ';' ;
IDENTIFIER = letter ;
IDENTIFIER = IDENTIFIER letterordigit ;
letterordigit = letter ;
letterordigit = digit ;
letter = 'A' ;
...
letter = 'Z' ;
digit = '0' ;
...
digit = '9' ;

Left as an exercise for the reader: add choice (|), multiple rules, and kleene star to make this a BNF for EBNF; this answer obviously weasels on handling of blanks, but you can handle that by inserting a "blanks" nonterminal wherever blanks are allowed (icky but works). There are BNF specification systems in which you actually do write the grammar essentially over characters, and that kind of implicit blank nonterminal insertion is done for you (e.g., Stratego's "Syntax Definition Formalism" ).

If you want an mind-blowing lesson in BNF-about-BNF, you should read the paper/do the tutorial for a BNF-processing system from honest-to-gosh 1965 called "MetaII". This paper describes how to do BNF in BNF, and how to build two compilers, in all of 10 pages.

(One big lesson here: read all the computer science stuff from the 60s and 70s. There isn't that much of it, and you'll be astonished by how much good material there is).