Синтаксис — Является ли C ++ контекстно-зависимым или контекстно-зависимым?

a b(c);

Ниже моя (текущая) любимая демонстрация того, почему синтаксический анализ C ++ (вероятно) Тьюринг, поскольку он показывает программу, синтаксически правильную тогда и только тогда, когда заданное целое число является простым.

Так что я утверждаю, что C ++ не является ни контекстно-зависимым, ни контекстно-зависимым.

Если вы разрешаете произвольные последовательности символов на обеих сторонах любого производства, вы создаете грамматику Типа-0 («неограниченную») в Хомская иерархия, которая является более мощной, чем контекстно-зависимая грамматика; неограниченные грамматики полны по Тьюрингу. Контекстно-зависимая (Тип-1) грамматика допускает наличие нескольких символов контекста в левой части продукции, но тот же контекст должен появляться в правой части продукции (отсюда и название «контекстно-зависимая»). [1] Контекстно-зависимые грамматики эквивалентны линейные машины Тьюринга.

В примере программы простое вычисление может быть выполнено с помощью машины Тьюринга с линейными ограничениями, поэтому она не вполне доказывает эквивалентность Тьюринга, но важная часть заключается в том, что синтаксическому анализатору необходимо выполнить вычисления для выполнения синтаксического анализа. Это могли быть любые вычисления, выражаемые как создание экземпляра шаблона, и есть все основания полагать, что создание экземпляра шаблона C ++ является тьюрингово полным. Смотрите, например, Статья Тодда Л. Вельдхуйзена за 2003 год.

Несмотря на это, C ++ может быть проанализирован компьютером, поэтому он может быть проанализирован машиной Тьюринга. Следовательно, неограниченная грамматика может распознать это. На самом деле написание такой грамматики было бы непрактичным, поэтому стандарт не пытается это сделать. (Увидеть ниже.)

Проблема с «неоднозначностью» некоторых выражений — это в основном красная сельдь. Начнем с того, что двусмысленность — это особенность определенной грамматики, а не языка. Даже если можно доказать, что в языке нет однозначных грамматик, если он может быть распознан с помощью контекстно-свободной грамматики, он не зависит от контекста. Точно так же, если он не может быть распознан с помощью контекстно-свободной грамматики, но он может быть распознан с помощью контекстно-зависимой грамматики, он является контекстно-зависимым. Неоднозначность не актуальна.

Но в любом случае, как строка 21 (т.е. auto b = foo<IsPrime<234799>>::typen<1>();в приведенных ниже программах выражения вовсе не являются двусмысленными; они просто разбираются по-разному в зависимости от контекста. В самом простом выражении проблемы синтаксическая категория определенных идентификаторов зависит от того, как они были объявлены (например, типы и функции), что означает, что формальному языку придется признать тот факт, что две строки произвольной длины в одна и та же программа идентична (декларация и использование). Это может быть смоделировано грамматикой «копирования», которая является грамматикой, которая распознает две последовательные точные копии одного и того же слова. Это легко доказать с насосная лемма что этот язык не является контекстно-свободным. Для этого языка возможна контекстно-зависимая грамматика, а в ответе на этот вопрос приведена грамматика типа 0: https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .

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

То, что выглядит как формальная грамматика в стандарте C ++, не является полным формальным определением синтаксиса языка C ++. Это даже не полное формальное определение языка после предварительной обработки, которое может быть легче формализовать. (Однако это не был бы язык: язык C ++, как определено стандартом, включает в себя препроцессор, и операция препроцессора описывается алгоритмически, так как это было бы чрезвычайно трудно описать в любом грамматическом формализме. Это в этом разделе стандарта, где описывается лексическое разложение, включая правила, в которых оно должно применяться более одного раза.)

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

Это краткое изложение синтаксиса C ++ предназначено для помощи в понимании. Это не точное утверждение языка. В частности, грамматика, описанная здесь, принимает расширенный набор допустимых конструкций C ++. Правила устранения неоднозначности (6.8, 7.1, 10.2) должны применяться, чтобы отличать выражения от объявлений. Кроме того, для исключения синтаксически допустимых, но бессмысленных конструкций необходимо использовать правила контроля доступа, неоднозначности и типа.

Наконец, вот обещанная программа. Строка 21 синтаксически правильна тогда и только тогда, когда N в IsPrime<N> прост. Иначе, typen целое число, а не шаблон, так typen<1>() анализируется как (typen<1)>() что синтаксически неверно, потому что () не является синтаксически допустимым выражением.

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
: IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; };

template<typename A> struct foo;
template<>struct foo<answer<true>>{
template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
static const int typen = 0;
};

int main() {
auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
return 0;
}

---

[1] Чтобы выразить это более технически, каждое производство в контекстно-зависимой грамматике должно иметь форму:

αAβ → αγβ

где A нетерминальный и α, β возможно пустые последовательности грамматических символов, и γ непустая последовательность (Символы грамматики могут быть терминалами или нетерминалами).

Это можно прочитать как A → γ только в контексте [α, β], В контекстно-свободной (тип 2) грамматике α а также β должен быть пустым.

Оказывается, вы также можете ограничить грамматику с помощью «монотонного» ограничения, где каждое произведение должно иметь форму:

α → β где |α| ≥ |β| > 0  (|α| означает «длина α«)

Можно доказать, что набор языков, распознаваемых монотонными грамматиками, точно такой же, как набор языков, распознаваемых контекстно-зависимыми грамматиками, и часто бывает проще основывать доказательства на монотонных грамматиках. Следовательно, довольно часто можно увидеть, что «контекстно-зависимый» используется так, как будто он означает «монотонный».

int m() { m++; }

typedef static int int;

#if FIRST_MEANING
template<bool B>
class foo
{ };
#else
static const int foo = 0;
static const int bar = 15;
#endif

static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );

int x;
x = 9 + 1.0;

A*B;

A B(bar);

class Foo
{
public:
void fn(){x*y;}
int x, y;
};

<a> ::= <b> | <c>
<b> ::= "x"<c> ::= "x"