La dificultad es que, si bien la mayoría de los lenguajes de programación tienen una estructura subyacente que se describe fácilmente por una gramática libre de contexto (Tcl ser una excepción interesante), muchas frases que se describen por la gramática libre de contexto no son en realidad "en el idioma" donde por "en el idioma" me refiero a "un programa válido en el idioma en cuestión". Estas oraciones adicionales generalmente se descartan mediante alguna forma de semántica estática . Por ejemplo, la siguiente expresión es una frase en la gramática independiente del contexto de los programas en C, pero ella misma no está en el conjunto de los programas de C válidas:
int f(void) { return n + 1; }
El problema aquí es que no es n en su alcance. C requiere "declaración antes del uso", y esa propiedad no se puede expresar utilizando una gramática libre de contexto.
un procedimiento de decisión típica de un lenguaje de programación real es parte de la parte delantera de un compilador o intérprete, y que tiene al menos dos partes: una, la analizador, es equivalente en poder de decisión a un desplazamiento descendente autómata; pero el segundo hace verificaciones adicionales que descartan muchas expresiones como inválidas. Si estas comprobaciones requieren algún tipo de propiedad de definición antes de usar, no pueden hacerse mediante un autómata pushdown o una gramática libre de contexto.
Si es cierto, entonces, ¿cómo podría un CFG mantener una gramática no restringida (UG), que se está completando?
Un CFG no "contiene" nada — simplemente describe un idioma.
... incluso si los lenguajes de programación se describen con CFG, en realidad se usan para describir máquinas de turing, y así a través de un UG.
Aquí omite algunos niveles importantes de indirección.
Creo que es debido al menos dos niveles diferentes de la computación, el primero, que es el análisis de un CFG se centra en la sintaxis relacionada con la estructura (la representación?) De la lengua, mientras que la otra se centra en la semántica (sentido, interpretación de los datos en sí?) relacionada con las capacidades del lenguaje de programación que está completando. Nuevamente, ¿son estas suposiciones correctas?
Parecen un poco confusos para mí, pero estás en el camino correcto. Una pregunta clave es "¿cuál es la diferencia entre un idioma y un programación idioma?" La respuesta es que un lenguaje de programación tiene una interpretación computacional . Las interpretaciones computacionales vienen en muchas variedades finas, y no todas son Turing-completas. Pero la magia está en la interpretación, no en la sintaxis, por lo que la jerarquía de Chomsky no es muy relevante aquí.
para probar mi punto, un ejemplo extremo: el lenguaje ordinario [1-9][0-9]* es Turing completo bajo la siguiente interpretación:
- El lenguaje SK-combinador es Turing completo.
- Existen solo numerosos programas SK.
- Se pueden enumerar fácilmente de manera única y determinista.
- Por lo tanto, podemos asociar cada entero positivo con un programa SK.
- Si interpretamos una secuencia de dígitos como un entero positivo de la manera estándar, también podemos interpretar la misma secuencia de dígitos como un programa SK, y además, cualquier programa SK se puede expresar usando una secuencia finita de dígitos
Por lo tanto, el lenguaje de los literales enteros es Turing-completo.
Si su cabeza no duele ahora, debería.
¡Demasiadas abreviaturas! Si no puede comunicarse sin codificar inútilmente, nunca será realmente eficaz. –
@DonalFellows, hay dos (2) abreviaturas, y si aún no está familiarizado con CFG, no podrá responder la pregunta de todos modos. –