В теории формального языка - контекстно-свободный язык (CFL ) - это язык, созданный с помощью контекстно-свободной грамматики (CFG).
Контекстно-свободные языки имеют множество приложений в языках программирования, в частности, большинство арифметических выражений генерируются с помощью контекстно-свободных грамматик.
Различные контекстно-свободные грамматики могут генерировать один и тот же контекстно-свободный язык. Внутренние свойства языка можно отличить от внешних свойств конкретной грамматики путем сравнения нескольких грамматик, описывающих язык.
Набор всех контекстно-свободных языков идентичен набору языков, принимаемых автоматами раскрытия, что делает эти языки доступными для синтаксического анализа. Кроме того, для данного CFG существует прямой способ создания автомата выталкивания для грамматики (и, следовательно, соответствующего языка), хотя пойти другим путем (создание грамматики для данного автомата) не так просто.
Модельный контекстно-свободный язык: , язык всех непустых строк четной длины, все первые половины которых являются буквами a, а все вторые половины - буквами b. L порождается грамматикой . Этот язык не обычный. Это принимается автоматом выталкивания где определяется следующим образом:
Однозначные CFL являются правильным подмножеством всех CFL: есть по своей сути неоднозначные CFL. Примером неоднозначного по своей сути CFL является объединение с . Этот набор контекстно-свободный, так как объединение двух контекстно-свободных языков всегда контекстно-независимое. Но нет способа однозначно проанализировать строки в (неконтекстно-независимом) подмножестве , который является пересечением этих двух языков.
Язык всех правильно подобранных скобок генерируется грамматикой .
Контекстно-свободный характер языка упрощает синтаксический анализ с помощью выталкивающего автомата.
Определение экземпляра, т. Е. Для строки , определить, где - язык, созданный данной грамматикой ; также известен как Бесконтекстное распознавание грамматик нормальной формы Хомского было показано Лесли Г. Валиантом. сводится к логическому умножению матриц, таким образом наследуя верхнюю границу сложности O (n). И наоборот, Лиллиан Ли показала, что умножение логических матриц O (n) сводится к разбору O (n) CFG, тем самым устанавливая некую нижнюю границу для последнего.
Практическое использование Контекстно-свободные языки требуют также создания производного дерева, которое демонстрирует структуру, которую грамматика связывает с данной строкой. Процесс создания этого дерева называется синтаксическим анализом. Известные парсеры имеют временную сложность, кубическую по размеру анализируемой строки.
Формально набор всех контекстно-свободных языков идентичен набору языков, принимаемых автоматами выталкивания (КПК). Алгоритмы синтаксического анализатора для контекстно-свободных языков включают алгоритм CYK и алгоритм Эрли.
. Особым подклассом контекстно-свободных языков являются детерминированные контекстно-свободные языки, которые определены как набор языков, принимаемых детерминированным автоматом выталкивания и может быть проанализирован парсером LR (k).
См. также синтаксический анализ грамматики выражений как альтернативный подход к грамматика и парсер.
Класс контекстно-свободных языков закрыт при следующих операциях. То есть, если L и P являются контекстно-независимыми языками, следующие языки также являются контекстно-независимыми:
Контекстно-свободный язык участки не закрываются при пересечении. Это можно увидеть, взяв языки и , которые не зависят от контекста. Их пересечение: , который может быть показан как неконтекстный с помощью леммы о перекачке для контекстно-свободных языков. Как следствие, контекстно-свободные языки не могут быть закрыты при дополнении, поскольку для любых языков A и B их пересечение может быть выражено объединением и дополнением: . В частности, контекстно-свободный язык нельзя замкнуть под разницей, поскольку дополнение может быть выражено разницей: .
Однако, если L - контекстно-свободный язык, а D - обычный язык, то их пересечение и их различие - это контекстно-свободные языки.
В теории формального языка вопросы о регулярных языках обычно разрешимы, но о контекстно-свободных языках часто нет. Решаемо, является ли такой язык конечным, но не содержит ли он всех возможных строк, является ли он правильным, однозначным или эквивалентным языку с другой грамматикой.
Следующие проблемы неразрешимы. для произвольно заданных контекстно-свободных грамматик A и B:
Для произвольных контекстно-свободных языков разрешимы следующие проблемы:
. Согласно Хопкрофту, Мотвани, Ульману (2003), многие фундаментальные свойства замыкания и (не) разрешимости контекстно-свободных языков были показаны в статье 1961 года Бар-Хиллель, Перлес и Шамир
Набор - это контекстно-зависимый язык, но не существует контекстно-независимой грамматики, генерирующей этот язык. Таким образом, существуют контекстно-зависимые языки, которые не являются контекстно-независимыми. Чтобы доказать, что данный язык не является контекстно-независимым, можно использовать лемму перекачки контекста -свободные языки или ряд других методов, таких как лемма Огдена или теорема Париха.