Являются ли грамматики современных языков программирования контекстно-зависимыми или контекстно-зависимыми?

Question

Являются ли языки C++, C# или Java контекстно-зависимыми или контекстно-зависимыми?

Answer 1

C++ не является ни контекстно-зависимым, ни контекстно-зависимым, поскольку система шаблонов полна по Тьюрингу, и определить, является ли фрагмент кода C++ допустимым C++, неразрешимо сложно. Например, я мог бы определить класс шаблона, который имитирует TM для строки, а затем создает константу со значением 1, если машина принимает, и 0, если нет. Если бы я сделал это, то следующий код был бы законным, если бы ТМ остановился на данном входе:

int myArray[TMTemplate</* ... args ... */>::value];

Поскольку, если TM отклоняет, это создает массив размером 0, что недопустимо.

Ни C#, ни Java не являются контекстно-свободными, поскольку известно, что проверка правильности и согласованности использования переменной во всей конкретной области видимости не является контекстно-свободной (доказательство является сложным и опирается на лемму Огдена). Однако я не уверен, являются ли они контекстно-зависимыми.

Надеюсь, что это дает частичный ответ на ваши вопросы!