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