3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Backus–Naur Form's syntax can be represented with a BNF itself. See this wikipedia article $\endgroup$ – Anton Trunov Apr 21 '16 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$ – Martin Berger Apr 21 '16 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 Sep 11 '16 at 9:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do we specify the initial production in this way? $\endgroup$ – Martin Berger Apr 21 '16 at 13:29
  • $\begingroup$ With the "First rule is the initial production" rule. $\endgroup$ – Anton Trunov Apr 21 '16 at 13:30
  • $\begingroup$ Yes. Sorry I removed the context. $\endgroup$ – Martin Berger Apr 21 '16 at 13:59
1
$\begingroup$

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 need something a little more advanced than even a CFG.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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