Я смущен тем, как контекстная чувствительность и двусмысленность влияют друг на друга.
Я считаю правильным:
неоднозначность:
Неоднозначная грамматика приводит к построению более одного дерева синтаксического анализа, используя либо левый, либо правый вывод. Язык, где все возможные грамматики неоднозначны, является неоднозначным языком.
Например, С++ является двусмысленным языком, потому что x * y всегда может означать две разные вещи, как описано в: Почему С++ не может быть проанализирован парсером LR (1)?.
Контекст-чувствительность:
Контекстно-зависимая грамматика имеет правила, в которых левая часть этих правил может содержать (не) терминальные символы, дополнительные к одному нетерминалу, требуемому в пределах всех правил разных видов грамматик. Это означает, что вы не можете просто заменить нетерминал при спуске. Вместо этого вы должны сначала посмотреть на окружающих нетерминалов.
Теперь меня беспокоят утверждения, которые более или менее говорят, что контекстно-зависимые парсеры могут анализировать двусмысленности, такие как x * y. Например, в вышеупомянутом связанном вопросе говорится, что "... парсер, который [украшает дерево синтаксиса при его создании], не свободен от контекста, а парсеры LR (чистые) не содержат контекста". На мой взгляд, это означает, что контекстно-зависимые парсеры (противоположные контекстуальным синтаксическим анализаторам?) Могут это сделать. Другим примером может быть Является ли какая-либо часть синтаксиса синтаксиса С++?, на который на этот вопрос отвечает "Да...". То же самое: что такое двусмысленная контекстная свободная грамматика?
Я не вижу, что эта двусмысленность С++ связана с контекстной чувствительностью. Я не думаю, что есть какая-то контекстно-зависимая грамматика, которая может справиться с этой двусмысленностью. Например, если вы принимаете вымышленное правило, подобное Typedef, <other> *, PointerDeclaration → Ident "*" Ident
то вы все равно не сможете определить (с чистым разбором), был ли конкретный первый идентификатор (например, "x" ) использован во время Typedef (например, typedef double x;).
Таким образом, возможно, что термин "контекстная чувствительность" используется в связанных вопросах, хотя это означает что-то простое, как контекстная зависимость (например, больше информации, необходимой, чем предоставленный простым парсером). Или существует какая-либо связь между "реальной" контекстно-чувствительной "и двусмысленностью.
Изменить. Более заданный вопрос: есть ли какие-либо двусмысленности в контекстно-свободных грамматиках, с которыми можно справиться с помощью контекстно-зависимых грамматик. Этот вопрос возникает у меня, потому что в связанных вопросах это звучит так, как двусмысленность С++ иногда упоминается как проблема контекстной чувствительности.
Edit2 Дополнительная информация: книга Компьютерные системы заявляет на стр. 346, что требования такие как наличие того же количества фактических и формальных параметров, могут быть выражены контекстно-зависимыми грамматиками. Но это очень громоздко, потому что вам нужно много сложных правил. Но, возможно, это может также относиться к неоднозначности С++, упомянутой ранее. Итак, у нас есть такие правила, как
"Typedef double x", <other> *, PointerDeclaration → "x" "*" Ident
Конечно, такие правила были бы очень ограниченными, и вам понадобилось бы огромное количество, чтобы выразить все возможности. По крайней мере, это может быть подход к ответу на вопрос, если (теоретически) свободные от контекста бесполезности могут быть заменены использованием контекстно-зависимых правил