Что люди имеют в виду, когда говорят, что C ++ имеет «неразрешимую грамматику»?

Question

Что люди имеют в виду, когда говорят это? Каковы последствия для программистов и компиляторов?

Answer 1

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

У этого есть побочный эффект, что некоторые очевидно действительные программы на C ++ не могут быть скомпилированы; компилятор никогда не сможет решить, является ли программа действительной или нет. Если бы компилятор мог определить допустимость всех программ, он смог бы решить проблему Halting .

Обратите внимание, что это не имеет ничего общего с неоднозначностью грамматики C ++.

---

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

Смотрите также (ссылки из поста Джоша):

• C ++ грамматика: имя типа и проблема имени объекта
• C ++ грамматика: тип и специализация объекта и шаблона

Answer 2

Возможно, это означает, что грамматика C ++ синтаксически неоднозначна, что вы можете записать некоторый код, который может означать разные вещи, в зависимости от контекста. (Грамматика - это описание синтаксиса языка. Это то, что определяет, что a + b является операцией сложения, включающей переменные a и b.)

Например, foo bar(int(x));, как написано, может быть объявлением переменной с именем bar типа foo, где int (x) является инициализатором. Это также может быть объявление функции с именем bar, принимающей int и возвращающей foo. Это определяется внутри языка, но не как часть грамматики.

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

Answer 3

Если в число «некоторых людей» входит Йосси Крейнин, то исходя из того, что он пишет здесь ...

Рассмотрим этот пример:

x * y(z);

в двух разных контекстах:

int main() {
    int x, y(int), z;
    x * y(z);
}

и

int main() {
    struct x { x(int) {} } *z;
    x * y(z);
}

... он означает «Вы не можете решить, глядя на x * y (z), является ли это выражением или объявлением». В первом случае это означает «вызвать функцию y с аргументом z, затем вызвать оператор * (int, int) с x и возвращаемым значением вызова функции и, наконец, отбросить результат». Во втором случае это означает, что «y является указателем на структуру x, инициализированную для указания на тот же адрес (мусор и бомба замедленного действия), что и z.»

Скажем, у вас был приступ COBOLmania и вы добавили DECLARE в язык. Тогда второй станет

int main() {
    DECLARE struct x { x(int) {} } *z;
    DECLARE x * y(z);
}

и появится разрешение. Обратите внимание, что возможность разрешения не устраняет проблему указателя на мусор.

Answer 4

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

Answer 5

Для тех из нас, кто использует язык, это означает, что сообщения об ошибках могут становиться очень странными, очень быстрыми (на практике это не так уж и много. Ошибки библиотеки STL обычно хуже, чем те, которые вы в итоге получаете к грамматике языка).

Для тех, кто пишет компиляторы, подразумевается, что им приходится тратить много дополнительного времени и усилий на компиляцию языка.