tuto - ¿Qué quiere decir la gente cuando dice que C++ tiene "gramática indecidible"?
program c++ (5)
Esto está relacionado con el hecho de que el sistema de plantillas de C ++ está completo . 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 problema de Detención .
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 publicación de blog con un excelente ejemplo que la construcción de un árbol de análisis sintáctico para C ++ en realidad es indescifrable. 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 la publicación de Josh):
¿Qué quiere decir la gente cuando dice esto? ¿Cuáles son las implicaciones para los programadores y compiladores?
La "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) .
La implicación para aquellos de nosotros que usamos el lenguaje es que los mensajes de error pueden ser muy extraños, muy rápidos (en la práctica, esto no es tan importante. Los errores de la biblioteca STL son generalmente peores que las cosas que terminan debido al lenguaje gramática).
La implicación para quienes escriben los compiladores es que tienen que gastar mucho tiempo y esfuerzo para compilar el lenguaje.
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 idioma. Es lo que determina que a + b sea una operación de suma, que involucre las 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.
Si "algunas personas" incluye a Yossi Kreinin, basado en lo que escribe aquí ...
Considera 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); }
... él quiere decir "No puedes decidir mirando x * y (z) si 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 (basura y bomba de tiempo) que hace z".
Digamos que tuvo un ataque de COBOLmania y agregó DECLARAR al idioma. Entonces el segundo se convertiría
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.