Контекстно-свободная грамматика

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

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

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.

Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.

Следует заметить, что по сути КС-грамматика — другая форма БНФ.

Содержание

Применение

КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т.д. (см. грамматический анализ)

Для разбора КС-грамматики достаточно автомата со стеком, для разбора не-КС-грамматик может потребоваться полная машина Тьюринга.

Типы КС грамматик

Примеры

Примеры КС-грамматик и соответствующих им КС-языков:

Вложенные скобки

  • Терминалы: '(' и ')';
  • нетерминал: S;
  • продукции: S→(S), S→ε;
  • начальный нетерминал — S.

Этой грамматикой задаётся язык вложенных скобок { (n)n | n≥0 }.

Язык Дика

Основная статья: Язык Дика

Целые числа

  • Терминалы: '+', '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9';
  • нетерминалы: <число>, <число без знака>, <последовательность цифр>, <ненулевая цифра>, <цифра>;
  • продукции:
<число> → 0
<число> → +<число без знака>
<число> → -<число без знака>
<число> → <число без знака>
<число без знака> → <ненулевая цифра>
<число без знака> → <ненулевая цифра><последовательность цифр>
<последовательность цифр> → <цифра><последовательность цифр>
<последовательность цифр> → <цифра>
<цифра> → 0
<цифра> → <ненулевая цифра>
<ненулевая цифра> → 1
<ненулевая цифра> → 2
<ненулевая цифра> → 3 
<ненулевая цифра> → 4 
<ненулевая цифра> → 5 
<ненулевая цифра> → 6 
<ненулевая цифра> → 7
<ненулевая цифра> → 8 
<ненулевая цифра> → 9 
  • начальный нетерминал: <число>.

Этой грамматикой задаётся язык целых чисел.

Арифметическое выражение

  • Терминалы: '+', '-', '*', '/', '(', ')', 'x'
  • нетерминалы: <выражение>, <слагаемое>, <множитель>
  • продукции:
<выражение> → <выражение> + <слагаемое>,
<выражение> → <выражение> - <слагаемое>,
<выражение> → <слагаемое>,
<слагаемое> → <слагаемое> * <множитель>,
<слагаемое> → <слагаемое> / <множитель>,
<слагаемое> → <множитель>,
<множитель> → ( <выражение> ),
<множитель> → x,
  • начальный нетерминал: <выражение>.

Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действие над переменной x. Если заменить терминал 'x' на нетерминал <число> из предыдущего примера, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножение и деления над целыми числами.

Ограничения возможностей КС грамматик

Не все языки могут быть заданы КС-грамматикой. Так, язык { anbncn | n≥1 } не является контекстно-свободным.

Литература

cs:Bezkontextová gramatika de:Kontextfreie Grammatik en:Context-free grammar es:Gramática libre de contexto fi:Yhteydetön kielioppi fr:Grammaire non contextuelle gl:Gramática libre de contexto hr:Kontekstno neovisna gramatika hu:Környezetfüggetlen nyelvtan it:Grammatica libera dal contesto ja:文脈自由文法 ko:문맥 자유 문법 mk:Контексно слободна граматика nl:Context-vrije grammatica pl:Gramatyka bezkontekstowa pt:Gramática livre de contexto sh:Kontekstno neovisna gramatika sk:Bezkontextová gramatika sr:Контекстно слободна граматика sv:Kontextfri grammatik ta:இடம் சாரா இலக்கணம் zh:上下文无关文法

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

Served in 0.096 secs.