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


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

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