Este team especializado despúes de algunos días de investigación y recopilación de de información, dieron con la respuesta, queremos que todo este artículo sea de gran utilidad en tu trabajo.
Solución:
¿Qué lenguajes de programación están libres de contexto? […]
Mi instinto me dice que los lenguajes funcionales pueden estar libres de contexto […]
La versión corta: Casi no hay lenguajes de programación del mundo real que estén libres de contexto en cualquier significado de la palabra. Si un idioma está libre de contexto o no, no tiene nada que ver con que sea funcional. Es simplemente una cuestión de cuán complejas son las reglas y características del lenguaje para analizar.
Aquí hay un CFG para el imperativo lenguaje Brainfuck:
Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'
Y aquí hay un CFG para el funcional Cálculo del combinador de SKI:
Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'
Estos CFG reconocen todos programas válidos de los dos lenguajes porque son muy simples.
La versión más larga: Por lo general, las gramáticas libres de contexto (CFG) solo se utilizan para aproximadamente especificar la sintaxis de un idioma. Hay que distinguir entre programas sintácticamente correctos y programas que compilan / evalúan correctamente. Por lo general, los compiladores dividen el análisis del lenguaje en análisis de sintaxis que construye y verifica la estructura general de un fragmento de código, y análisis semántico que verifica el sentido Del programa.
Si por "lenguaje sin contexto" te refieres a "... para el que se compilan todos los programas", entonces la respuesta es: casi ninguno. Los lenguajes que se ajustan a este proyecto de ley apenas tienen reglas o características complicadas, como la existencia de variables, la sensibilidad a los espacios en blanco, un sistema de tipos, o cualquier otro contexto: Información definida en un lugar y basada en otro.
Si, por otro lado, "lenguaje libre de contexto" solo significa "... para lo cual todos los programas pasan el análisis de sintaxis", la respuesta es una cuestión de cuán compleja es la sintaxis por sí sola. Hay muchas características sintácticas que son difíciles o imposibles de describir con un CFG solo. Algunas de ellas se superan agregando estados adicionales a los analizadores para realizar un seguimiento de los contadores, búsqueda tablas, etc.
Ejemplos de características sintácticas que no se pueden expresar con un CFG:
-
Lenguajes sensibles a la sangría y los espacios en blanco como Python y Haskell. El seguimiento de los niveles de sangría anidados arbitrariamente es esencialmente sensible al contexto y requiere contadores separados para el nivel de sangría; tanto cuántos espacios se utilizan para cada nivel como cuántos niveles hay.
Permitir solo un nivel fijo de sangría usando una cantidad fija de espacios funcionaría duplicando la gramática para cada nivel de sangría, pero en la práctica esto es un inconveniente.
-
El problema de análisis de typedef de C dice que los programas de C son ambiguos durante el análisis léxico porque no pueden saber solo por la gramática si algo es un identificador regular o un alias de typedef para un tipo existente.
El ejemplo es:
typedef int my_int; my_int x;En el punto y coma, el entorno de tipos debe actualizarse con una entrada para my_int. Pero si el lexer ya ha mirado hacia adelante a my_int, lo habrá lexado como un identificador en lugar de un nombre de tipo.
-
Lenguajes basados en macros y plantillas como Lisp, C ++, Template Haskell, Nim, etc. Dado que la sintaxis cambia a medida que se analiza, una solución es convertir el analizador en un programa que se modifica automáticamente. Consulte también ¿C ++ es libre de contexto o sensible al contexto?
-
A menudo, la precedencia y la asociatividad de los operadores no se expresan directamente en los CFG a pesar de que es posible. Por ejemplo, un CFG para una gramática de expresión pequeña donde ^ enlaza más fuerte que × y × enlaza más fuerte que +, podría verse así:
E → E ^ E E → E × E E → E + E E → (E) E → numSin embargo, este CFG es ambiguo y suele ir acompañado de una tabla de precedencia / asociatividad que dice, por ejemplo, que ^ enlaza más estrechamente, × enlaza más estrechamente que +, que ^ es asociativo por la derecha y que × y + son asociativos por la izquierda.
La precedencia y la asociatividad se pueden codificar en un CFG de forma mecánica, de modo que no sea ambiguo y solo produzca árboles de sintaxis donde los operadores se comporten correctamente. Un ejemplo de esto para la gramática anterior:
E₀ → EA E₁ EA → E₁ + EA EA → ε E₁ → EM E₂ EM → E₂ × EM EM → ε E₂ → E₃ EP EP → ^ E₃ EP E₃ → num E₃ → (E₀)Pero las tablas CFG ambiguas + precedencia / asociatividad son comunes porque son más legibles y porque varios tipos de bibliotecas generadoras de analizadores sintácticos LR pueden producir analizadores sintácticos más eficientes al eliminar los conflictos de cambio / reducción en lugar de lidiar con una gramática transformada inequívoca de mayor tamaño.
En teoría, todos los conjuntos finitos de cadenas son lenguajes regulares, por lo que todos los programas legales de tamaño limitado son regulares. Dado que los lenguajes regulares son un subconjunto de los lenguajes libres de contexto, todos los programas de tamaño limitado son libres de contexto. El argumento continúa,
Si bien se puede argumentar que sería una limitación aceptable para un lenguaje permitir solo programas de menos de un millón de líneas, no es práctico describir un lenguaje de programación como un lenguaje regular: la descripción sería demasiado grande.
- Conceptos básicos del diseño de compiladores de Torben Morgensen, cap. 2.10.2
Lo mismo ocurre con los CFG. Para abordar su subpregunta de manera un poco diferente,
Qué lenguajes de programación son definido por una gramática libre de contexto?
La mayoría de los lenguajes de programación del mundo real se definen por sus implementaciones, y la mayoría de los analizadores de los lenguajes de programación del mundo real están escritos a mano o utilizan un generador de analizadores que amplía el análisis sin contexto. Desafortunadamente, no es tan común encontrar un CFG exacto para su idioma favorito. Cuando lo hace, suele estar en formato Backus-Naur (BNF) o en una especificación de analizador que probablemente no sea puramente libre de contexto.
Ejemplos de especificaciones gramaticales de la naturaleza:
- BNF para ML estándar
- Tipo BNF para Haskell
- BNF para SQL
- Gramática yacc para PHP
El conjunto de programas que son sintácticamente correctos no tiene contexto para casi todos los idiomas.
El conjunto de programas que se compilan no está libre de contexto para casi todos los lenguajes. Por ejemplo, si el conjunto de todos los programas de compilación de C estuviera libre de contexto, entonces al cruzarse con un lenguaje regular (también conocido como regex), el conjunto de todos los programas de compilación de C que coinciden
^int main(void) int a+; a+ = a+; return 0; $
sería libre de contexto, pero esto es claramente isomorfo al lenguaje a ^ kba ^ kba ^ k, que es bien conocido no estar libre de contexto.
Dependiendo de cómo entienda la pregunta, la respuesta cambia. Pero en mi humilde opinión, la respuesta adecuada es que todos los lenguajes de programación modernos son de hecho sensibles al contexto. Por ejemplo, no existe una gramática libre de contexto que acepte solo programas en C sintácticamente correctos. Las personas que apuntan a las gramáticas libres de contexto yacc / bison para C se pierden el punto.
Si entiendes que ha sido de utilidad nuestro artículo, te agradeceríamos que lo compartas con otros programadores de esta forma contrubuyes a difundir este contenido.