Контекстно-свободные грамматики против контекстно-зависимых грамматик?

Ответ 1

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

A контекстная грамматика (CFG) - это грамматика, где (как вы отметили) каждое произведение имеет форму A → w, где A - нетерминал, а w - строка терминалов и нетерминалов. Неофициально, CFG - это грамматика, где любой нетерминал может быть раскрыт в любом из своих постановок в любой момент. Язык грамматики - это набор строк терминалов, которые могут быть получены из символа начала.

A контекстно-зависимая грамматика (CSG) - это грамматика, где каждое произведение имеет вид wAx → wyx, где w и x - строки терминалов и нетерминалов, а y также является строкой терминалов. Другими словами, в постановках приводятся правила, говорящие "если вы видите A в данном контексте, вы можете заменить A на строку y". К сожалению, эти грамматики называются "контекстно-зависимыми грамматиками", потому что это означает, что "контекстно-зависимые" и "контекстно-зависимые" не являются противоположностями, а это означает, что существуют определенные классы грамматик, которые, возможно, занимают много контекстуальных информации, но формально не рассматриваются как контекстно-зависимые.

Чтобы определить, содержится ли строка в CFG или CSG, существует множество подходов. Во-первых, вы можете создать распознаватель для данной грамматики. Для CFG, pushdown automaton (PDA) - это тип автомата, который принимает именно контекстно-свободные языки, и существует простая конструкция для превращая CFG в КПК. Для контекстно-зависимых грамматик автомат, который вы используете, называется линейным ограниченным автоматом (LBA).

Однако эти вышеприведенные подходы, если их рассматривать наивно, не очень эффективны. Чтобы определить, содержится ли строка в языке CFG, существуют гораздо более эффективные алгоритмы. Например, многие грамматики могут иметь LL (k) или LR ( k), которые позволяют вам (в линейном времени) определять, содержится ли строка в грамматике. Все грамматики могут быть проанализированы с помощью анализатора Эрли, который в O (n ³) может определить, длина n содержится в грамматике (интересно, что она может анализировать любой однозначный CFG в O (n ²), а с помощью lookgheads можно анализировать любую грамматику LR (k) в O (n) времени!). Если вас просто интересовал вопрос "строка x, содержащаяся в языке, порожденном грамматикой G?", То один из этих подходов был бы превосходным. Если вы хотите узнать, как была создана строка x (путем поиска дерева анализа ), вы можете адаптировать эти подходы, чтобы также предоставить эту информацию. Однако разбор CSG является, вообще говоря, PSPACE-полным, поэтому для них не существует известных алгоритмов синтаксического анализа, которые работают в худшем случае полиномиального времени. Есть некоторые алгоритмы, которые на практике, как правило, работают быстро. Авторы" Parsing Techniques: Практическое руководство "(см. Ниже) собрали фантастическую страницу, содержащую всевозможные алгоритмы синтаксического анализа, включая те, которые анализируют контекстно-зависимые языки.

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

Надеюсь, это поможет!

Ответ 2

Как было сказано ранее, грамматика не принимает строку, но это просто способ генерации определенных слов языка, который вы анализируете. На самом деле грамматика как порождающее правило в Теории формального языка вместо автомата конечного состояния делает то, что вы говорите, распознавание определенных строк. В частности, вам нужен рекурсивный перечислимый автомат, чтобы распознавать языки 1-го типа (контекстно-чувствительные языки в иерархии Хомского). Грамматика для определенного языка предоставляет только вам указание свойства всех строк, которые собираются в набор строк языка CS. Надеюсь, что мое объяснение было ясным.

Ответ 3

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