¿Qué quiere decir la gente cuando dice que C++ tiene "gramática indecidible"?

Question

¿Qué quiere decir la gente cuando dice esto? ¿Cuáles son las implicaciones para los programadores y compiladores?

Answer 1

Esto se relaciona con el hecho de que el sistema de plantillas de C++ es Turing complete. Esto significa (teóricamente) que puede calcular cualquier cosa en tiempo de compilación con plantillas que podría usar con cualquier otro lenguaje o sistema completo de Turing.

Esto tiene el efecto secundario de que algunos programas C++ aparentemente válidos no se pueden compilar; el compilador nunca podrá decidir si el programa es válido o no. Si el compilador pudiera decidir la validez de todos los programas, podría resolver el Halting problem.

Tenga en cuenta que esto no tiene nada que ver con la ambigüedad de la gramática C++.

---

Editar: Josh Haberman señaló en los comentarios a continuación y en una blog post con un excelente ejemplo de que la construcción de un árbol de análisis sintáctico para C++ realidad es acotable. Debido a la ambigüedad de la gramática, es imposible separar el análisis de sintaxis del análisis semántico, y dado que el análisis semántico es indecidible, también lo es el análisis de sintaxis.

Ver también (enlaces de entrada de Josh):

• C++ grammar: the type name vs object name issue
• C++ grammar: type vs object and template specializations

Answer 2

Lo que probablemente significa es que la gramática de C++ es sintácticamente ambigua, que puede escribir un código que podría significar cosas diferentes, según el contexto. (La gramática es una descripción de la sintaxis de un lenguaje. Es lo que determina que a + b es una operación de suma, que involucra variables a y b.)

Por ejemplo, foo bar(int(x));, como está escrito, podría ser una declaración de una variable llamada bar, de tipo foo, con int (x) siendo un inicializador. También podría ser una declaración de una función llamada bar, tomando un int y devolviendo un foo. Esto se define dentro del lenguaje, pero no como parte de la gramática.

La gramática de un lenguaje de programación es importante. En primer lugar, es una forma de entender el idioma y, en segundo lugar, es parte de la compilación lo que puede hacerse rápidamente. Por lo tanto, los compiladores C++ son más difíciles de escribir y más lentos de usar que si C++ tuviera una gramática no ambigua. Además, es más fácil crear ciertas clases de errores, aunque un buen compilador proporcionará suficientes pistas.

Answer 3

La implicación para quienes usamos el lenguaje es que los mensajes de error pueden ser muy extraños, muy rápidos (en la práctica, esto no es un problema. Los errores de la biblioteca STL suelen ser peores que las cosas con las que termina debido a la gramática del lenguaje).

La implicación para quienes escriben los compiladores es que tienen que gastar mucho tiempo y esfuerzo en compilar el idioma.

Answer 4

Si "algunas personas" incluye Yossi Kreinin, a continuación, basado en lo que escribe here ...

Considere este ejemplo:

x * y(z); 

en dos contextos diferentes:

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

y

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

... que significa "Usted no puede decidir por mirar en x * y (z) ya sea t es una expresión o una declaración ". En el primer caso, significa "llamar a la función y con el argumento z, luego invocar operador * (int, int) con xy el valor de retorno de la llamada de función, y finalmente descartar el resultado". En el segundo caso, significa que "y es un puntero a una estructura x, inicializado para apuntar a la misma dirección (bomba de tiempo & basura) como lo hace z".

Supongamos que ha tenido un ataque de COBOLmania y ha agregado DECLARAR al idioma. Entonces el segundo se convertiría en

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

y la decidability aparecería. Tenga en cuenta que ser decidible no hace desaparecer el problema del puntero a la basura.

Answer 5

'Gramática indecidible' es una elección muy pobre de palabras. Una gramática verdaderamente indecidible es tal que no existe un analizador para la gramática que terminará en todas las entradas posibles. Lo que probablemente quieren decir es que la gramática de C++ no está libre de contexto, pero incluso esto es una cuestión de gusto: ¿dónde trazar la línea entre la sintaxis y la semántica? Cualquier compilador admitirá solo un subconjunto adecuado de aquellos programas que pasen la etapa del analizador sin errores de sintaxis y solo un subconjunto adecuado de esos programas realmente se ejecute sin errores, por lo tanto, ningún idioma es verdaderamente libre de contexto o incluso decidable (salvo tal vez algunos lenguajes esotéricos) .