WikiSort.ru - Программирование

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

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

Пример

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

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

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

N ::= 1 | N1

X ::= a | b | c

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

Start ::= ${\displaystyle \langle a^{N}\rangle \langle b^{N}\rangle \langle c^{N}\rangle }$

${\displaystyle \langle X^{N1}\rangle }$  ::= ${\displaystyle \langle X^{N}\rangle X}$

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

Ссылки