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

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

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

пример

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

${\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 X^{N1}\rangle }$ ::= ${\displaystyle \langle X^{N}\rangle X}$

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

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

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

использованная литература

1. Синцов, М. «Существование синтаксиса ван Вейнгаардена для каждого рекурсивно перечислимого множества», Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.

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

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