Контекстно-свободная грамматика
-
Определение и свойства контекстно-свободных грамматик
- Контекстно-свободная грамматика (CFG) – это формальная грамматика, которая не зависит от контекста.
- CFG состоит из набора правил, которые определяют, как создавать строки из начальных символов и нетерминалов.
- Нетерминалы могут быть заменены на другие нетерминалы или терминальные символы.
-
Примеры контекстно-свободных грамматик
- Примеры включают грамматики для арифметических выражений, регулярных выражений и языков программирования.
- Грамматика для языка {a
- n
- b
- :
- ≥
- 0
- }
- {\displaystyle \{a^{n}b^{n}:n\geq 0\}}
- является контекстно-свободной, но содержит пустую строку.
- Грамматика для языка {b
- a
- m
- 2n
-
Обычные грамматики и их связь с контекстно-свободными
- Обычная грамматика также не зависит от контекста, но не все контекстно-свободные грамматики являются обычными.
- Примеры обычных грамматик включают грамматики для строк из a и b, заканчивающихся на a.
- Регулярные грамматики соответствуют недетерминированным конечным автоматам и являются обычными.
-
Производные и синтаксические деревья
- Вывод строки для грамматики представляет собой последовательность применений правил, которые преобразуют начальный символ в строку.
- Вывод определяет, принадлежит ли строка языку грамматики.
- Существуют стратегии для детерминистического выбора следующего нетерминала для перезаписи.
- Различие между крайним левым и крайним правым выводом важно для анализаторов.
-
Нормальные формы и свойства закрытия
- Контекстно-свободные языки могут быть представлены в нормальной форме Хомского или Грейбаха.
- Нормальные формы имеют теоретическое и практическое значение, например, для построения алгоритмов синтаксического анализа.
- Контекстно-свободные языки замкнуты при определенных операциях, но не при общем пересечении.
-
Разрешимые проблемы с контекстно-свободными грамматиками
- Разбор слова для контекстно-свободной грамматики является разрешимой задачей с использованием различных алгоритмов синтаксического анализа.
- Достижимость, продуктивность и возможность обнуления для нетерминалов являются важными свойствами грамматики.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.
Полный текст статьи: