In a rewriting system, suppose the production rule S→xAyAz (or <S>:=x<A>y<A>z, in BNF), where S and A are nonterminal symbols and x, y, z are any string.

This rule produces the string xa1ya2z, where a1 and a2 are strings substituted by the nonterminal symbol A. The substitutions a1 and a2 may be equal or different strings.

But what if I want to a1 and a2 to be the same string; that is, if the nonterminal A be substituted by the same instance in both its occurrences in that production rule?

I used a kind of BNF I created informally for such purpose, with <v:A> instead of <A>: a kind of "typed variable", whose type is a nonterminal symbol and the variable is the same substitution for all its occurrences. Thus, <S>:=x<v:A>y<v:A>z, and <v:A> is substituted for the same string in its both occurrences.

What is the name of such a grammar that uses variables for consistent substitution of a nonterminal? And there is a grammar formalism for it?

  • 1
    $\begingroup$ Your extended kind of grammar can generate the language $\{ ww : w \in \{a,b\}^* \}$, which isn’t context-free. $\endgroup$ Aug 4 '18 at 13:08
  • $\begingroup$ Possible duplicate: cs.stackexchange.com/questions/76186/… $\endgroup$
    – rici
    Aug 4 '18 at 14:45
  • $\begingroup$ @YuvalFilmus Yeah, I searched about it and I discovered that it is context-sensitive, but the formalisms for context-sensitive grammar that I found do not use variables as I did. I edited the question for asking for the name and formalism of such a variable-based context-sensitive grammar. $\endgroup$
    – Seninha
    Aug 4 '18 at 23:47
  • $\begingroup$ @rici I think they are different question. Mine asks for naming a nonterminal occurrence (as in S ::= x:A x:A, for the language {ww:w∈{a,b}*} ), this one you commented asks for parameterizing a nonterminal occurrence (as in NounPhrase(number) ::= Adjective(number) Noun(number) for a grammar with agreement). $\endgroup$
    – Seninha
    Aug 5 '18 at 0:19
  • $\begingroup$ Well, as far as I understand that question... $\endgroup$
    – Seninha
    Aug 5 '18 at 0:23

You've created an affix grammar, so named because they were created to deal with affixes (prefixes and suffixes) in natural languages.

Specifically, this is a type of affix grammar where the "affixes" (what you call typed variables) are defined by the same type of grammar rather than coming from a simpler (finite) grammar. This creates a two-level grammar, specifically a type known as a Van Wijngaarden grammar after its creator.

It turns out that this type of grammar is in fact Turing-complete, so non-trivial semantic properties of such grammars are undecidable by Rice's theorem. On the one hand this makes them extremely powerful; on the other hand, it makes them not as useful in practice, since you could use some other Turing-complete system instead.


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.