Чувствительность к контексту против неоднозначности

Question

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

То, что я считаю правильным, это:

Неоднозначность:

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

Например, C ++ является неоднозначным языком, потому что x * y всегда может означать две разные вещи, как обсуждено в: Почему C ++ не может быть проанализирован с анализатором LR (1)? .

Контекст чувствительности:

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

---

Теперь меня беспокоят утверждения, которые более или менее говорят о том, что контекстно-зависимые парсеры могут анализировать неоднозначности, такие как x * y. Например, в приведенном выше связанном вопросе утверждается, что «... синтаксический анализатор, который [украшает синтаксическое дерево при его создании], не является контекстно-свободным, а синтаксические анализаторы LR (чистые) - контекстно-свободными». По моему мнению, это подразумевает, что контекстно-зависимые парсеры (противоположность контекстно-свободным парсерам?) Могут это делать. Другим примером будет Является ли какая-либо часть синтаксиса C ++ чувствительной к контексту? , где на этот вопрос отвечает «Да ...». То же самое здесь: Что такое неоднозначная контекстно-свободная грамматика?

Я не вижу, как эта неоднозначность в C ++ связана с контекстно-зависимой. Я не думаю, что есть какая-либо контекстно-зависимая грамматика, которая может справиться с этой неоднозначностью. Например, если вы берете вымышленное правило вроде Typedef, *, PointerDeclaration -> Ident "*" Ident

тогда вы все равно не сможете определить (с помощью чистого анализа), использовался ли конкретный первый Ident (например, «x») во время Typedef (например, typedef double x;).

---

Таким образом, возможно, что термин "чувствительность к контексту" используется в связанных вопросах, хотя он означает нечто простое, например, зависимость от контекста (например, требуется больше информации, чем предоставлено простым анализатором). Или есть какая-то связь между "реальной" чувствительностью к контексту "и неясностями.

Редактировать Более конкретный вопрос: есть ли какие-либо двусмысленности внутри контекстно-свободных грамматик, с которыми можно справиться, используя контекстно-зависимые грамматики. Этот вопрос возникает у меня, потому что в связанных вопросах это звучит так, как будто неоднозначность C ++ иногда упоминается как проблема, связанная с контекстом.

Edit2 Дополнительная информация: В книге Компьютерные системы на странице 346 говорится, что такие требования, как наличие одинакового количества фактических и формальных параметров, могут быть выражены контекстно-зависимыми грамматиками. Но это очень громоздко, потому что вам нужно много сложных правил. Но, возможно, это также может относиться к неоднозначности C ++, упомянутой ранее. Так что у нас есть правила вроде

"Typedef double x", *, PointerDeclaration -> "x" "*" Ident

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

Answer 1

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

A контекстно-зависимый язык - это формальный язык, который можно проанализировать с помощью контекстно-зависимой грамматики (CSG). Каждый контекстно-свободный язык также является контекстно-зависимым языком, поскольку контекстно-свободные грамматики являются упрощенными контекстно-зависимыми языками. Хотя не каждый формальный язык является контекстно-зависимым; Есть языки, которые даже CSG не может описать.

Answer 2

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

Пример первый: 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'

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

Относительно вашего редактирования 1: Я надеюсь, что предыдущий пример отвечает этому.

Относительно вашего Правки 2: Есть и другие уловки, как выразить это, чтобы правила не были столь ограничены, но они обычно являются сногсшибательными, и IMO - причина, почему никто не использует формализм CSG.

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

Answer 3

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