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

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

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

• 1 Пример
• 2 См. Также
• 3 ссылки
• 4 Внешние ссылки

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

${\ displaystyle \ {a ^ {n} b ^ {n} a ^ {n} | n \ geq 1 \}.}$

Двухуровневая грамматика для этого языка - метаграмматика.

N:: = 1 | N1

X:: = a | б

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

Начало:: = ${\ displaystyle \ langle a ^ {N} \ rangle \ langle b ^ {N} \ rangle \ langle a ^ {N} \ rangle}$

${\ Displaystyle \ langle Х ^ {N1} \ rangle}$ знак равно ${\ Displaystyle \ langle X ^ {N} \ rangle X}$

${\ displaystyle \ langle X ^ {1} \ rangle}$ :: = X

• Аффикс грамматики
• Грамматика атрибутов
• Грамматика Ван Вейнгаардена

1. ^ Синцов, М. "Существование синтаксиса ван Вейнгаардена для каждого рекурсивно перечислимого множества", Анналы де ла Сосьете научного де Брюсселя 2 (1967), 115-118.

• Петерссон, Кент (1990), «Синтаксис и семантика языков программирования», черновые конспекты лекций, текст в формате PDF.