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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

Пример

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

<math>\{a^n b^n a^n | n \ge 1\}.</math>

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

N ::= 1 | N1
X ::= a | b

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

Start ::= <math> \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle </math>
<math> \langle X^{N1} \rangle</math> ::= <math>\langle X^N \rangle X </math>
<math> \langle X^1 \rangle</math> ::= X

Ссылки

  1. Sintoff, M. "Existence of Van Wijngaarden's Syntax for Every Recursively Enumerable Set." Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.

en:Two-level grammar hr:Dvorazinska gramatika zh:两级文法

Личные инструменты

Served in 0.048 secs.