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

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

Контекстно-зависимый язык - это формальный язык, который можно анализировать с помощью контекстно-зависимой грамматики (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'

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

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

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

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

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