Что имеют в виду люди, когда они говорят, что C++ имеет “неразрешимую грамматику”?
Вы можете сделать это за один проход, используя sideEffect():
gremlin> g.V().has('person','name','marko').as('m').
......1> outE('knows').
......2> filter(inV().has('person','name','vadas')).
......3> sideEffect(drop()).
......4> V().has('person','name','peter').
......5> addE('knows').from('m')
==>e[13][1-knows->6]
В строке 1 мы в основном идентифицируем ребро, от которого мы хотим избавиться (т.е. ребро «знает» от «marko»). на «vadas»), и мы drop(), что в строке 3. В строке 4 мы ищем вершину, с которой мы хотим соединить «marko» сейчас, а затем добавляем ребро в строке 5.
5 ответов
Это связано с тем, что система шаблонов C ++ завершена по Тьюрингу . Это означает (теоретически), что вы можете вычислить все что угодно во время компиляции с помощью шаблонов, которые вы могли бы использовать с любым другим полным языком или системой Тьюринга.
Это имеет побочный эффект, заключающийся в том, что некоторые явно допустимые программы C ++ не могут быть скомпилированы; компилятор никогда не сможет решить, является ли программа действительной или нет. Если бы компилятор мог определить допустимость всех программ, он мог бы решить проблему остановки .
Обратите внимание, что это не имеет никакого отношения к неоднозначности грамматики C ++.
Редактировать: Джош Хаберман указал в комментариях ниже и в блоге с отличным примером того, что построение дерева разбора для C ++ на самом деле неразрешимо. Из-за неоднозначности грамматики невозможно отделить синтаксический анализ от семантического анализа, и поскольку семантический анализ неразрешим, как и синтаксический анализ.
См. Также (ссылки из поста Джоша):
что грамматика C ++ синтаксически неоднозначна, что вы можете записать некоторый код, который может означать разные вещи, в зависимости от контекста. (Грамматика - это описание синтаксиса языка. Это то, что определяет, что a + b является операцией сложения, включающей переменные a и b.)
Например, foo bar ( int (x)); , как написано, может быть объявлением переменной с именем bar типа foo, где int (x) является инициализатором. Это также может быть объявление функции с именем bar, принимающей int и возвращающей foo. Это определяется внутри языка, но не как часть грамматики.
Грамматика языка программирования важна. Во-первых, это способ понять язык, а во-вторых, это часть компиляции, которая может быть выполнена быстро. Поэтому компиляторы C ++ сложнее писать и использовать медленнее, чем если бы C ++ имел однозначную грамматику. Кроме того, легче создавать определенные классы ошибок, хотя хороший компилятор предоставит достаточно подсказок.
Если "некоторые «люди» включает в себя Йосси Крейнина, затем на основе того, что он пишет здесь ...
Рассмотрим этот пример:
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);
}
и появится разрешимость. Обратите внимание, что возможность разрешения не устраняет проблему указателя на мусор.
'Undecidable grammar' is a very poor choice of words. A truly undecidable grammar is such that there exists no parser for the grammar that will terminate on all possible inputs. What they likely mean is that C++ grammar is not context-free, but even this is somewhat a matter of taste: Where to draw the line between syntax and semantics? Any compiler will admit only a proper subset of those programs that pass the parser stage without syntax errors and only a proper subset of those programs actually run without errors, thus no language is truly context-free or even decidable (barring perhaps some esoteric languages).
The implication for those of us using the language is that the error messages can get very weird, very fast (in practice this isn't such a big deal. STL library errors are usually worse than the stuff you end up with due to the language grammar).
The implication for those who write the compilers is that they have to spend a lot of extra time and effort compiling the language.