Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet.

Grammars themselves can be seen as languages, e.g. the set of REs over $\{0, 1\}$. In that sense we can specify a grammars by means of a meta-grammar. For example the language of all REs over a fixed alphabet can be specified as a context-free grammar (CFG), e.g. like so

$$ R \quad::=\quad 0 \ |\ a \ |\ RR \ |\ R+R \ |\ (R) \ |\ R^* $$

where $a$ ranges over the ambient alphabet. One advantage of thinking of grammars in terms of their meta-grammar is that we can parse REs and check them for syntactic correctness.

What kind of meta-grammar (context-free or otherwise) allows us to specify the language of CFGs over a given alphabet? What about subsets of CFGs like LL(k) or LR(k)? I'm sure this has been investigated before as there are many tools that take grammars as input, e.g. parser generators.

  • 2
    $\begingroup$ Backus–Naur Form's syntax can be represented with a BNF itself. See this wikipedia article $\endgroup$ Commented Apr 21, 2016 at 12:19
  • 1
    $\begingroup$ @AntonTrunov Given that BNF-form is equivalent to CFGs, that means CFGs, unlike REs can represent their own formalism. Interesting. Thanks. If you post your comment as an answer, I can accept it. $\endgroup$ Commented Apr 21, 2016 at 13:08
  • 1
    $\begingroup$ Indeed this has long been investigated. Other folks here have identified the answer to your question as "BNF". You might enjoy this paper on compilers driven by BNF from, yes, 1963: en.wikipedia.org/wiki/META_II. Here an augmented BNF is used to define a compiler, and a metacompiler is defined that can self-compile and thus be extended. All in 10 pages. $\endgroup$
    – Ira Baxter
    Commented Sep 11, 2016 at 9:40

2 Answers 2


Backus–Naur Form's syntax can be represented with a BNF itself. Here is an example taken from this Wikipedia article:

<syntax>         ::= <rule> | <rule> <syntax>
<rule>           ::= <opt-whitespace> "<" <rule-name> ">"
                     <opt-whitespace> "::=" <opt-whitespace> 
                     <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression>     ::= <list> |
                     <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list>           ::= <term> | <term> <opt-whitespace> <list>
<term>           ::= <literal> | "<" <rule-name> ">"
<literal>        ::= '"' <text> '"' | "'" <text> "'"

"" denotes the empty string. The article provides some more details on undefined here rules for <rule-name>, etc.

  • $\begingroup$ How do we specify the initial production in this way? $\endgroup$ Commented Apr 21, 2016 at 13:29
  • $\begingroup$ With the "First rule is the initial production" rule. $\endgroup$ Commented Apr 21, 2016 at 13:30
  • $\begingroup$ Yes. Sorry I removed the context. $\endgroup$ Commented Apr 21, 2016 at 13:59

The typical notation I've seen can be described as a regex: (S -> (S|a)*\n)+ where S is a non-terminal symbol and a is the range of the alphabet. Informally it's a list of production rules where a non-terminal maps to a string of terminals (a character in the alphabet) and non-terminals.

However this grammar doesn't have the constraints on how proper the grammar is For example non-terminals can have no production rule. For that you can use a variant of whether a string contains every character of an alphabet at least once in any order which is a regular language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.