Что означает «контекстно-свободный» в термине «контекстно-свободная грамматика»?

Учитывая количество материала, который пытается объяснить, что такое не зависящая от контекста грамматика (CFG), я нахожу удивительным, что очень немногие (в моем примере менее 1 из 20) дают объяснение тому, почему такие грамматики называются «context- свободно". И, на мой взгляд, никому не удается это сделать.

Мой вопрос: почему контекстно-свободные грамматики называются контекстно-свободными? Что такое "контекст"? У меня была интуиция, что контекстом могут быть другие языковые конструкции, окружающие анализируемую в настоящее время конструкцию, но, похоже, это не так. Может ли кто-нибудь дать точное объяснение?

Это означает, что все его производственные правила имеют один нетерминал с левой стороны.

Например, эта грамматика, которая распознает строки совпадающих скобок ("()", "() ()", "(()) ()", ...), не зависит от контекста:

S → SS
S → (S)
S → ()

Левая часть каждого правила состоит из одного нетерминала (в этом случае это всегда S, но может быть и больше).

Теперь рассмотрим следующую грамматику, которая распознает строки вида {a ^ nb ^ nc ^ n: n> = 1} (например, «abc», «aabbcc», «aaabbbccc»):

S  → abc
S  → aSBc
cB → WB
WB → WX
WX → BX
BX → Bc
bB → bb

Если нетерминалу Bпредшествует конечный / буквальный символ c, вы переписываете этот термин на, WBно если ему предшествует b, bbвместо этого вы расширяете его . Это, по-видимому, то, на что намекает контекстно-зависимая грамматика.

Не зависящий от контекста язык можно распознать как автомат . В то время как конечный автомат не использует вспомогательное хранилище, т. Е. Его решение основывается только на его текущем состоянии и входных данных, автомат с опрокидыванием также имеет в своем распоряжении стек и может смотреть на вершину стека для принятия решений.

Чтобы увидеть это в действии, вы можете разобрать вложенные скобки, перемещаясь слева направо и помещая левые скобки в стек каждый раз, когда вы сталкиваетесь с ними, и выталкивая каждый раз, когда вы сталкиваетесь с правильными скобками. Если вы никогда не пытаетесь выскочить из пустого стека, а стек в конце строки пуст, строка действительна.

Для контекстно-зависимого языка КПК недостаточно. Вам понадобится линейно-ограниченный автомат, похожий на машину Тьюринга, чья лента не безгранична (хотя количество доступной ленты пропорционально входу). Обратите внимание, что это описывает компьютеры довольно хорошо - нам нравится думать о них как о машинах Тьюринга, но в реальном мире вы не можете произвольно получить больше оперативной памяти в середине программы. Если вам не очевидно, насколько LBA более мощная, чем КПК, LBA может эмулировать КПК, используя часть своей ленты в качестве стека, но она также может использовать свою ленту другими способами.

(Если вам интересно, что может распознавать конечный автомат, ответ - это регулярные выражения. Но не те регулярные выражения для стероидов с группами захвата и опережающими / смотрящими вперед, которые вы видите в языках программирования; я имею в виду те, которые вы можете построить с операторами нравится [abc], |, *, +, и ?. Вы можете видеть , что abbbzсоответствует регулярному выражению , ab*zпросто сохраняя текущую позицию в строке и регулярное выражение, не стек требуется.)

Другие ответы довольно длинные, даже если они точные и правильные. Это короткая версия.

Если у вас есть строка символов (терминалы и нетерминалы), и вы хотите заменить нетерминал в строке, контекстно-свободная грамматика позволяет вам делать это независимо от символов, окружающих нетерминал.

Рассмотрим следующие правила (строчные буквы являются терминалами, прописные - нетерминалами):

A -> a
AB -> a

В первом правиле вы можете заменить A независимо от того, что появляется вокруг него (контекст). Во втором правиле вы не можете заменить, Aесли оно не сопровождается B. Хотя оба нетерминала будут заменены в этом случае, важным моментом является то, что нетерминалы, окружающие Aматерию. Никто не может заменить BAс a, или Bс a: только Aсопровождаемым , Bпотому что порядок, контекст из нетерминалов имеет важное значение. Это означает, что контекст нетерминала имеет значение во втором правиле, делая его контекстно-зависимым, в то время как первое правило не зависит от контекста.

Чтобы лучше понять различие и терминологию, неплохо бы сравнить контекстно-свободный язык, такой как a ⁿ b ^n, с контекстно-зависимым языком, таким как a ⁿ b ⁿ c ⁿ . (Обозначения: a, b и c здесь являются литералами, а показатель степени n означает повторение литерала n раз , скажем , n > 0.) Например, aabbcили aabbbccне на последнем языке, тогда как aabbccесть.

Акцептор для языка без контекста a ⁿ b ⁿ может заключить пару aи bнезависимо от того, что вокруг него (т.е. независимо от контекста, в котором появляется ab), и он будет функционировать правильно, принимая только строки в языке и отвергая что-либо еще, т.е. грамматика есть S -> aSb | ab. Обратите внимание, что на левой стороне продукции нет терминалов . (Есть два правила производства, но мы просто пишем их компактно.) Акцептор может в основном принимать локальное решение без контекста.

Напротив, вы не можете сделать что-то подобное для контекстно-зависимого языка a ⁿ b ⁿ c ⁿ , потому что для последнего вы должны как-то вспомнить контекст, в котором вы были, т.е. сколько сокращений ab вы делаете, чтобы сопоставить их с сокращениями до н. э. Грамматика для последнего языка

S -> abc | aBSc
Ba -> aB
Bb -> bb

Обратите внимание, что у вас есть оба терминала и нетерминалы слева в последних двух правилах. Терминалы слева - это контекст, в котором нетерминалы могут быть расширены.

Bootnote относительно терминов «контракт» или «расширить» и т. Д .: хотя формальные грамматики являются [формально, ха] генеративными, способ, которым они фактически реализуются в синтаксических анализаторах, на самом деле является редукционистским, то есть вы связываете все с нетерминалом, в основном применение правил «в обратном порядке», поэтому даже первая приведенная выше грамматика непрактична в программе (она даст вам известный конфликт сдвига-уменьшения, поскольку вы не можете решить, какое правило применять), но приведенные выше два грамматик достаточно для иллюстрации различия между контекстно-независимым и контекстно-зависимым. Проблема неоднозначности в контекстно-свободных грамматиках довольно сложна, и на самом деле не является темой этого вопроса, поэтому я не буду здесь говорить больше, тем более что оказывается, что в Википедии есть достойная статья на эту тему., Напротив, его статьи по контекстно-свободным и особенно по контекстно-зависимому языку являются! @ # $ @! # $, Особенно если вы новичок в этой теме ... Я думаю, это больше в моем списке TODO.

Ответы выше дают довольно хорошее определение того, что это такое. Давайте посмотрим, смогу ли я выразить это своими словами, чтобы у вас было 23 объяснения вместо 20. Вся цель грамматики, любой грамматики, состоит в том, чтобы выяснить, является ли конкретное предложение предложением на данном языке. Однако, что мы действительно используем для грамматики и синтаксического анализа, так это для того, чтобы выяснить, что означает это предложение. Это как старая схема предложения, которое вы могли или не могли сделать еще на уроке английского в школе. Предложение состоит из предметной части и предикатной части, предметная часть имеет существительное и, возможно, некоторые прилагательные, предикатная часть имеет глагол и, возможно, объектное существительное, с некоторыми прилагательными и т. Д.

Если бы существовала грамматика для английского языка (и я не думаю, что она есть, не в смысле информатики), то в ней были бы правила следующей формы, называемые продукцией.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun

и т.д...

Затем вы могли бы написать программу и передать ей любое предложение, и программа могла бы использовать грамматику, чтобы выяснить, какой частью предложения является каждое слово и какое отношение они имеют друг к другу.

Если в каждом производстве есть только одна вещь с левой стороны, то это означает, что всякий раз, когда вы видите правую сторону в предложении, вам разрешается заменить на левой стороне. Например, всякий раз, когда вы видели прилагательное существительное, вы можете сказать «Это предметная часть», не обращая внимания ни на что, кроме этой фразы.

Тем не менее, английский (даже упрощенное описание английского, которое я дал выше) является контекстно-зависимым. «Прилагательное существительное» не всегда является SubjectPart, это может быть NounPhrase в PredicatePart. Это зависит от контекста. Давайте немного расширим нашу псевдоанглийскую грамматику:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

Вы можете сделать «прилагательное существительное» только в ObjectNounPhrase, если оно идет сразу после VerbPhrase.

По сути, если у вас есть производство, и вы можете применить его в любое время, независимо от того, что его окружает, оно не зависит от контекста.

Вы всегда можете легко определить, является ли грамматика контекстно-свободной. Просто проверьте, есть ли более одного символа на левой стороне стрелок.

Любой язык может быть описан несколькими грамматиками. Если некоторая грамматика для языка не зависит от контекста, язык не зависит от контекста. Для некоторых языков может быть доказано, что грамматика без контекста невозможна. Я полагаю, что для упрощенного псевдоанглийского подмножества, которое я описываю выше, может существовать контекстно-свободная грамматика.

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

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

Этот вид анализа языка был изобретен для автоматического анализа естественного языка (такого как английский), но оказывается, что это наиболее полезно для анализа компьютерных языков. Разработчик языка может написать грамматику, которая фиксирует его новый язык, а затем запустить ее через генератор синтаксического анализатора, чтобы получить программу, которая анализирует его язык и переводит, интерпретирует, компилирует, выполняет и т.д., если он хочет.

На самом деле, в большинстве случаев вы не можете этого сделать. Например, сбалансированные скобки являются контекстно-свободным языком, но язык, в котором требуется объявить все переменные перед их использованием, является контекстно-зависимым. Парсер является частью компилятора, но для реализации этих требований требуется дополнительная логика. Затем вам нужно написать грамматику, которая захватывает как можно больше вашего языка, выполнить ее через генератор синтаксического анализатора, а затем написать код, который обеспечивает выполнение остальных требований (обработчик таблицы символов и т. Д.).

Обычно мы не используем контекстно-зависимые грамматики, потому что они гораздо хуже поддерживаются. Я не знаю, существует ли эквивалент синтаксического анализатора LR (k) для контекстно-зависимых языков. Да, машина Тьюринга (или машина с линейной привязкой) может ее проанализировать, но я не знаю, существует ли общий алгоритм для преобразования контекстно-зависимой грамматики в программу для машины Тьюринга, в том смысле, что LR (1 ) Генератор создает таблицы разбора для машины. Я предполагаю, что таблицы, лежащие в основе парсера, будут экспоненциально больше. В любом случае, студенты CS (как и я, в свое время) обычно преподают грамматику без контекста и генераторы парсеров LR (1), такие как YACC.

Контекстные грамматики не учитывают никакого контекста для правил производства. Контекстом являются либо терминалы, либо нетерминалы.

Итак: у контекстно-свободных грамматик есть только один нетерминал в левой части правил разработки.