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

Question

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

Answer 1

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

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

Обратите внимание, что это не имеет ничего общего с неоднозначностью грамматики 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 обычно хуже, чем те, с которыми вы сталкиваетесь из-за языка грамматика).

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