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!

Polymorphonuclear

Your question seems to be answered by the wikipedia article on BNF. – Arboreous

@GregHewgill Interesting. I was taught by Frank de Remer that BNF can't describe itself. – Walczak

@EJP: De Remer was (is?) pretty spectacular with parser generators and grammars I don't believe he would have taught that. I suspect you some mis-remembered what you learned. – Hydrophilous

@IraBaxter That is exactly what he taught me. – Walczak

@EJP: So, presumably that fact is backed up by some impossibility proof. Do you recall that? – Hydrophilous

@IraBaxter The issue Frank stated was lexical rather than grammatical: the variables are quoted rather than the literals, e.g. <primary> is a variable and + is not, rather than the other way around, so you end up with a vicious regress when trying to describe a variable. – Walczak

@EJP: So, you can't describe the lexical structure of a variable name because the "<" character serves as an introduction to a variable name? OK, I can see the problem if you insist that variable names are spelled "<var>" and the grammar doesn't go down to the character. If you do go down to the character, quoting character literals, defining a variable to have a spelling that involves "<", then this isn't a problem. – Hydrophilous

@IraBaxter I'm just telling you what Frank told me ;-) He pulled another trick which I'm sure is a standard lecturer's stunt, but I had never seen it before. We went around the class of about 30, standing up, saying our names and a bit of background, then he went around again pointing and giving everybody's names. Flawless. – Walczak

@EJP: If you wanted a BNF-of-BNF using "<...>" for identifier names, just modify the self-BNF I supplied in the obvious way. – Hydrophilous

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

Hydrophilous

Answer 2

<line> ::= '<' <word> '>' '::=' <definition>
<definition> ::= <word> '|' | '' <definition> | ''

Bufflehead

Answer 3

SELF-DEFINITION OF PROGRAMMING LANGUAGES

An example of an operational self-definition of a programming language is given by the use of a metacircular interpreter.

Tymoczko, Thomas. “Gödel and the Concept of Meaning in Mathematics.” Synthese, vol. 114, no. 1, 1998, pp. 25–40

Wang (1980) reports that Kurt Godel said all of logic could be defined by starting with the Concept of a Concept (CoC). CoC is self-defined. CoC is an object defined by itself.

A Logical Journey. From Gödel to Philosophy Hao Wang takes us into Gödel’s thoughts. Gödel described the concept of a concept as the foundation of logic. (chapter 8, page 247) “From 1953 to the beginning of 1959 he spent a great deal of his effort on the Carnap paper, in which he tries to prove that mathematics is not syntax of language and argues in favor of some form of Platonism.”

Grammars for programming languages (Programming languages series) Jan 1, 1977 Contains the BNF of BNF on page 33.

Rescissory