Чувствительность к контексту против неоднозначности
Я запутался в том, как контекстная чувствительность и неоднозначность влияют друг на друга.
То, что я считаю правильным:
Неоднозначность:
Неоднозначная грамматика приводит к построению более одного дерева синтаксического анализа с использованием левого или правого вывода. Язык, где все возможные грамматики неоднозначны, является неоднозначным языком.
Например, C++ является неоднозначным языком, потому что x * y всегда может означать две разные вещи, как обсуждалось в: Почему C++ не может быть проанализирован с помощью парсера LR(1)?,
Контекст чувствительности:
У контекстно-зависимой грамматики есть правила, в которых левая часть этих правил может содержать (не) терминальные символы в дополнение к одному нетерминальному, необходимому в пределах lhs всех правил различных видов грамматик. Это означает, что вы не можете просто заменить нетерминал при спуске. Вместо этого вы должны смотреть на окружающие нетерминалы в первую очередь.
Теперь меня беспокоят утверждения, которые более или менее говорят о том, что контекстно-зависимые парсеры могут анализировать неоднозначности, такие как x * y. Например, в приведенном выше связанном вопросе утверждается, что "... синтаксический анализатор, который [украшает синтаксическое дерево при его создании], не является контекстно-свободным, а синтаксические анализаторы LR (чистые) - контекстно-свободными". По моему мнению, это означает, что контекстно-зависимые парсеры (противоположность контекстно-свободным парсерам?) Могут это делать. Другой пример: чувствительна ли какая-либо часть контекста синтаксиса C++? где на этот вопрос отвечает "Да...". То же самое здесь: что такое неоднозначная контекстно-свободная грамматика?
Я не понимаю, как эта неопределенность в C++ связана с контекстно-зависимой. Я не думаю, что есть какая-либо контекстно-зависимая грамматика, которая может справиться с этой неоднозначностью. Например, если вы берете вымышленное правило, такое как Typedef,
тогда вы все равно не сможете определить (с помощью чистого синтаксического анализа), использовался ли конкретный первый идентификатор (например, "x") во время Typedef (например, typedef double x;).
Поэтому возможно, что термин "чувствительность к контексту" используется в связанных вопросах, хотя он подразумевает нечто простое, например зависимость от контекста (например, требуется больше информации, чем предоставлено простым анализатором). Или есть какая-то связь между "реальной" контекстной чувствительностью и неясностями.
Изменить более конкретный вопрос: есть ли какие-либо двусмысленности внутри контекстно-свободных грамматик, с которыми можно справиться, используя контекстно-зависимые грамматики. Этот вопрос возникает у меня, потому что в связанных вопросах это звучит так, как будто неоднозначность C++ иногда упоминается как проблема, связанная с контекстом.
Edit2 Дополнительная информация: в книге " Компьютерные системы" на странице 346 говорится, что такие требования, как наличие одинакового количества фактических и формальных параметров, могут быть выражены контекстно-зависимыми грамматиками. Но это очень громоздко, потому что вам нужно много сложных правил. Но, возможно, это также может относиться к неоднозначности C++, упомянутой ранее. Так что у нас есть такие правила, как
"Typedef double x",
Конечно, такие правила будут очень ограничены, и вам понадобится огромное количество, чтобы выразить каждую возможность. По крайней мере, это может быть подходом к ответу на вопрос, можно ли (теоретически) безконтекстные неопределенности, не зависящие от контекста, заменить контекстно-зависимыми правилами
3 ответа
Чувствительность к контексту и неоднозначность полностью ортогональны. Существуют неоднозначные контекстно-свободные языки и однозначные контекстно-зависимые языки.
Контекстно-зависимый язык - это формальный язык, который может быть проанализирован с помощью контекстно-зависимой грамматики (CSG). Каждый контекстно-свободный язык также является контекстно-зависимым языком, поскольку контекстно-свободные грамматики являются упрощенными контекстно-зависимыми языками. Хотя не каждый формальный язык является контекстно-зависимым; Есть языки, которые даже CSG не может описать.
Если вы хотите проанализировать контекстно-зависимый язык с помощью контекстно-независимого синтаксического анализатора, вы определяете контекстно-свободную грамматику, которая принимает расширенный набор контекстно-зависимого языка (потому что они менее мощные). Поскольку вы принимаете надмножество, вы можете получить двусмысленности или ложноположительные результаты, которые должны быть устранены после анализа.
Пример первый: XML-подобный язык, который допускает любое имя тега. Поскольку не зависящая от контекста грамматика не может разобрать предложение ww, состоящее из двух повторяющихся слов w = {a, b} +, оно не может разобрать <ID></ID> где идентификаторы одинаковы. Таким образом, определяется контекстно-свободная грамматика, которая принимает надмножество:
start -> elem
elem -> open elem* close
open -> '<' ID '>'
close -> '</' ID '>'
ID -> ('a' / 'b')+
Это, очевидно, анализирует даже предложения, которые не нужны, поэтому дополнительная проверка эквивалентных идентификаторов в open а также close должно быть сделано.
Пример второй: C-подобный Typedef на очень простом языке. Представьте себе язык, который содержит только typedef, указатели и умножения. У него только два идентификатора, a а также b, Пример такого языка:
typedef a;
b * a; // multiplication
a * b; // b is pointer to type a
Контекстно-свободная грамматика будет выглядеть так:
start -> typedef multiplication-or-pointer+
typedef -> 'typedef' ID ';'
multiplication-or-pointer -> ID '*' ID ';'
ID -> 'a'
ID -> 'b'
Грамматика не принимает суперсет, но она не знает, видит ли она умножение или указатель, поэтому она неоднозначна. И поэтому нужно просмотреть результат и решить, является ли он умножением или указателем, в зависимости от того, какой тип определен в typedef.
С контекстно-зависимой грамматикой можно сделать гораздо больше. Очень грубо (и неточно)
start -> typedef multiplication-or-pointer+
typedef -> 'typedef' ID ';'
multiplication-or-pointer -> pointer / multiplication
'typedef' 'a' ';' WHATEVER pointer -> 'a' '*' ID
'typedef' 'b' ';' WHATEVER pointer -> 'b' '*' ID
'typedef' 'b' ';' WHATEVER multiplication -> 'a' '*' ID
'typedef' 'a' ';' WHATEVER multiplication -> 'b' '*' ID
ID -> 'a'
ID -> 'b'
Обратите внимание, что то, что я показываю здесь, не является точным, потому что я ограничил количество идентификаторов. В общем, может быть бесконечное количество идентификаторов. Вы можете написать контекстно-зависимую грамматику для общего случая (даже если она должна быть абсолютно неинтуитивной), но вы не можете написать контекстно-свободную грамматику.
Что касается вашего Edit 1: я надеюсь, что предыдущий пример отвечает на это.
Относительно вашего Правки 2: Есть еще одна хитрость, как выразить это так, чтобы правила не были так ограничены, но они, как правило, ошеломляют, и именно по этой причине никто не использует формализм CSG.
NB: контекстно-зависимая грамматика эквивалентна линейному ограниченному автомату, контекстно-свободная грамматика эквивалентна автомату выталкивания. Неверно утверждать, что контекстно-свободный анализатор является противоположностью контекстно-зависимого анализатора.
Компиляторы не используют "чистые" (что бы это ни значило) грамматики для их анализа - это программы реального мира, которые делают то же, что и все программы реального мира, - применяют эвристику в определенных ситуациях. Вот почему компиляторы C++ (и компиляторы для большинства других языков, кроме упражнений для студентов) не создаются с использованием генераторов компиляторов.