What is a BNF BNF? How do we define a BNF metagram?

Question

I am trying to determine BNF BNF. In other words, I am trying to define a BNF metagram. That is, a BNF grammar, which is an instance of itself and can generate any other BNF grammar.

Any tips / hints / snippets would be much appreciated!

Thanks!

Answer 1

Here is 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 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 a selection (|), a few rules and a star wedge to make it BNF for EBNF; this answer obviously caresses the handling of spaces, but you can handle this by inserting the “spaces” of the non-terminal where spaces are allowed (not good, but it works). There are BNF specification systems in which you actually write the grammar essentially over characters, and an implicit non-terminal insert is made for you (for example, Stratego "Syntax Formalism Definition" .

If you want a fascinating lesson in BNF-about-BNF, you should read the document / make a tutorial for the BNF-processor system from honest to miracle of 1965 called "MetaII". This document describes how to make BNF in BNF, and how to build two compilers on all 10 pages.

(One big lesson here: read all the materials on computer science from the 60s and 70s. It's not so much, and you will be amazed at how good the material is there).

Answer 2

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