Двухуровневая грамматика

Двухуровневая грамматика — это формальная грамматика, которая используется для порождения другой формальной грамматики, например с бесконечным множеством правил. Именно так грамматика ван Вейнгаардена была использована для определения языка Алгол-68. Контекстно-свободная грамматика, которая определяет правила для другой грамматики может породить в сущности бесконечное множество правил производной грамматики. Это делает двухуровневые грамматики более мощными, чем одноуровневые контекстно-свободные грамматики, так как было доказано, что двухуровневые порождающие грамматики являются полными по Тьюрингу.

Двухуровневой грамматикой может также называться формальная грамматика для двухуровневого формального языка, то есть языка, заданного на двух уровнях, например уровень слов и уровень предложений.

Пример

Хорошо известным не контекстно-свободным языком является

<math>\{a^n b^n a^n | n \ge 1\}.</math>

Двухуровневой грамматикой для него может быть метаграмматика

N ::= 1 | N1

X ::= a | b

вместе с грамматической схемой

Start ::= <math> \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle </math>

<math> \langle X^{N1} \rangle</math> ::= <math>\langle X^N \rangle X </math>

<math> \langle X^1 \rangle</math> ::= X