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

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

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

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

Примеры

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

  • Терминалы: '(' и ')';

нетерминал: S; продукции: S→(S), S→ε; начальный нетерминал — S. Этой грамматикой задаётся язык вложенных скобок { (n)n | n≥0 }.

  • Терминалы: '+', '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9';

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

ε обозначает пустое слово.

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

Применение

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home