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

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

Я считаю правильным:

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

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

Например, С++ является двусмысленным языком, потому что 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

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

Ответы

Ответ 1

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

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

Ответ 2

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

Пример 1. XML-подобный язык, который позволяет использовать любое имя тега. Поскольку контекстно-свободная грамматика не может анализировать предложение ww, состоящее из двух повторяющихся слов w = {a, b} +, оно не может разобрать <ID></ID>, где идентификаторы равны. Таким образом, определяется контекстно-свободная грамматика, которая принимает надмножество:

start -> elem
elem  -> open elem* close
open  -> '<' ID '>'
close -> '</' ID '>'
ID    -> ('a' / 'b')+

Это явно анализирует даже предложения, которые не нужны, поэтому необходимо выполнить дополнительную проверку эквивалентных идентификаторов в open и close.

Пример 2: C-like 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: Надеюсь, что предыдущий пример ответил на это.

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

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

Ответ 3

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