Двухуровневая грамматика - Two-level grammar

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

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

пример

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

${\ 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

Смотрите также

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

Ссылки

внешние ссылки

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

Это язык программирования о связанной статье заглушка . Вы можете помочь Википедии, расширив ее . v т е