Контекстно-свободная грамматика
Материал из Википедии — свободной энциклопедии
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.
Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.
Следует заметить, что по сути КС-грамматика — другая форма БНФ.
Содержание |
[править] Применение
КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т.д. (см. грамматический анализ)
[править] Типы КС грамматик
- LL-грамматика
- LALR-грамматика
- LR-грамматика
- SLR-грамматика
[править] Примеры
Примеры КС-грамматик и соответствующих им КС-языков:
[править] Вложенные скобки
- Терминалы: '(' и ')';
- нетерминал: 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 } не является контекстно-свободным.