# Formal grammar with variables for consistent substitutions

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?

• Your extended kind of grammar can generate the language $\{ ww : w \in \{a,b\}^* \}$, which isn’t context-free. – Yuval Filmus Aug 4 '18 at 13:08
• Possible duplicate: cs.stackexchange.com/questions/76186/… – rici Aug 4 '18 at 14:45
• @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. – Seninha Aug 4 '18 at 23:47
• @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). – Seninha Aug 5 '18 at 0:19
• Well, as far as I understand that question... – Seninha Aug 5 '18 at 0:23