H4: Meta Grammars

Due Monday, Sept 23th, 12noon

Extended Backus-Naur (Normal) Form of Grammars

BNF was created by John Backus to describe the syntax and semantics of what is now known as ALGOL in 1959.  Peter Naur simplified Backus's notation in 1963.  Further generalizations brought us Extended BNF. A brief overview can be found here.

The basic idea is that a grammar is a set of productions: the production name is listed on the right hand side of := (aka production rule) and one or more patterns are listed to the right of :=

Grammar := Production1 | Production2 | Production3 | ... | Productionn ; 
// Producti can also be Patterns, like the rules below
Production1 := Pattern11 | Pattern12 | ... ;
Production2 := Pattern21 | Pattern22 | ... ;

Above: a Grammar is a sentence or instance of Production1, Production2, Production3 , ... , Productionn

Production1 is a sentence or instance of Pattern21, Pattern22, ...; the same for Production2.

A Pattern is a sequence of production names or tokens (these are primitive strings or regular expressions); these names or tokens may be repeated any number of times (*), one or more times (+), or at most once [also called optional]:

Pattern11 := token1 [token2] Production1* [token3] Production2+ ;

Above: an instance of Pattern11 is token1, followed by the optional appearance of token2, followed by zero or more instances any pattern of Production1, followed by the optional appearance of token3, followed by one or more instances of any pattern of Production2.

Note: for this assignment [+2] (that is, the optional token sequence "+" followed by "2") is illegal in BNF; you should write it as [plus2]  where plus2 :=+ 2; (that is, plus2 is a production with a single pattern).

Note: for this assignment, specific tokens will be in quotes; generic tokens will be labeled as such.  See example below.

An example is the BNF for the grammar that defines the multiplication and addition of integers, where INT denotes a token (representing any integer), "x" and "+" representing times and plus, and "(" and ")" tokens for parenthesis pairs.

IntExp : INT
| INT "+" IntExp
| INT "x" IntExp
| "(" IntExp ")"
;

Your assignment is to write a BNF of BNF -- that is, what is the BNF grammar of all BNF grammars?  Note that your meta-grammar must be an instance of itselfYou should show this. You are NOT to create an UML model for your answer.