compiler theory - regular - ¿Qué lenguajes de programación son libres de contexto?
lenguaje regular (8)
¿Qué lenguajes de programación son libres de contexto? [...]
Mi instinto me dice que los lenguajes funcionales podrían 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 ningún significado de la palabra. Si un lenguaje es libre de contexto o 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 lenguaje imperativo Brainfuck :
Program → Instr Program | ε
Instr → ''+'' | ''-'' | ''>'' | ''<'' | '','' | ''.'' | ''['' Program '']''
Y aquí hay un CFG para el cálculo funcional del combinador SKI :
Program → E
E → ''S'' E E E
E → ''K'' E E
E → ''I''
E → ''('' E '')''
Estos CFG reconocen todos los programas válidos de los dos idiomas porque son muy simples.
La versión más larga: por lo general, las gramáticas sin contexto (CFG) solo se usan para especificar aproximadamente la sintaxis de un idioma. Uno debe distinguir entre los programas sintácticamente correctos y los programas que se compilan . Más comúnmente, los compiladores dividen el análisis de lenguaje en un análisis de sintaxis que construye y verifica la estructura general de una pieza de código, y el análisis semántico que verifica el significado del programa.
Si por "lenguaje libre de contexto" quiere decir " ... para lo que compilan todos los programas ", entonces la respuesta es: casi ninguno. Los idiomas que se ajustan a este proyecto de ley apenas tienen reglas o características complicadas, como la existencia de variables, la sensibilidad a espacios en blanco, un sistema de tipos o cualquier otro contexto : la información se define en un lugar y se confía en otro.
Si, por otro lado, "lenguaje libre de contexto" solo significa " ... para el cual todos los programas pasan el análisis de sintaxis ", la respuesta es una cuestión de cuán compleja es la sintaxis. Hay muchas características sintácticas que son difíciles o imposibles de describir con un CFG solo. Algunos de estos se superan mediante la adición de un estado adicional a los analizadores para realizar un seguimiento de los contadores, las tablas de búsqueda, etc.
Ejemplos de características sintácticas que no se pueden expresar con un CFG:
Lenguajes sensibles a la sangría y al espacio 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; ¿Cuántos espacios se utilizan para cada nivel y 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 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 puede saber solo por la gramática si algo es un identificador regular o un alias typedef para un tipo existente.
El ejemplo es:
typedef int my_int; my_int x;En el punto y coma, el entorno de tipo debe actualizarse con una entrada para my_int. Pero si el lexer ya ha mirado hacia adelante a my_int, lo tendrá 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 modifique a sí mismo. Consulte también " ¿Es C ++ libre de contexto o sensible al contexto? "
A menudo, la precedencia y la asociatividad del operador no se expresan directamente en los CFG, aunque es posible. Por ejemplo, un CFG para una gramática de expresión pequeña donde ^ se une más que X, y × se une más que +, podría verse así:
E → E ^ E E → E × E E → E + E E → (E) E → numSin embargo, este CFG es ambiguous y suele ir acompañado de una tabla de precedencia / asociatividad que dice, por ejemplo, que ^ se enlaza más fuerte, x se enlaza más fuerte que +, que ^ es asociativo a la derecha, y que x y + son asociativos a la izquierda.
La precedencia y la asociatividad se pueden codificar en un CFG de forma mecánica, de manera que no sea ambigua y solo produzca árboles de sintaxis en los que los operadores se comportan 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 ambiguas de CFGs + precedencia / asociatividad son comunes porque son más legibles y porque varios tipos de bibliotecas de generadores de analizadores LR pueden generar analizadores más eficientes al eliminar los conflictos de cambio / reducción en lugar de tratar con una gramática no ambigua y transformada 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 lenguajes libres de contexto, todos los programas de tamaño limitado están 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.
- Fundamentos de Torben Morgensen del diseño del compilador, cap. 2.10.2
Lo mismo ocurre con los CFGs. Para abordar su sub-pregunta un poco diferente,
¿Qué lenguajes de programación están definidos por una gramática libre de contexto?
La mayoría de los lenguajes de programación del mundo real están definidos por sus implementaciones, y la mayoría de los analizadores para los lenguajes de programación del mundo real están escritos a mano o utilizan un generador de analizador que amplía el análisis sin contexto. Desafortunadamente, no es tan común encontrar un CFG exacto para su idioma favorito. Cuando lo haces, generalmente está en forma de Backus-Naur (BNF), o una especificación de analizador que probablemente no sea puramente libre de contexto.
Ejemplos de especificaciones gramaticales de la naturaleza:
O, para ser un poco más preciso: ¿qué lenguajes de programación están definidos por una gramática libre de contexto?
De lo que recojo, C ++ no está libre de contexto debido a cosas como macros y plantillas. Mi instinto me dice que los lenguajes funcionales pueden estar libres de contexto, pero no tengo ningún dato con el que respaldar eso.
Representación extra para ejemplos concisos :-)
Dependiendo de cómo entiendas la pregunta, la respuesta cambia. Pero IMNSHO, la respuesta correcta es que todos los lenguajes de programación modernos son, de hecho, sensibles al contexto. Por ejemplo, no hay una gramática libre de contexto que acepte solo programas C sintácticamente correctos. A las personas que apuntan a las gramáticas libres de contexto yacc / bison para C les falta el punto.
El conjunto de programas que son sintácticamente correctos está libre de contexto para casi todos los idiomas.
El conjunto de programas que se compilan no está libre de contexto para casi todos los idiomas. Por ejemplo, si el conjunto de todos los programas de compilación en C no tenía contexto, entonces al cruzarse con un idioma regular (también conocido como regex), el conjunto de todos los programas de compilación en C que coincidan
^int main/(void/) { int a+; a+ = a+; return 0; }$
estaría libre de contexto, pero esto es claramente isomorfo para el lenguaje a ^ kba ^ kba ^ k, que se sabe que no está libre de contexto.
La mayoría de los lenguajes de programación modernos no son lenguajes libres de contexto. Como prueba, si profundizo en la raíz de CFL, su PDA correspondiente a la máquina no puede procesar coincidencias de cadenas como {ww | w is a string} {ww | w is a string} . Así que la mayoría de los lenguajes de programación requieren eso.
Ejemplo:
int fa; // w
fa=1; // ww as parser treat it like this
Para ir al ejemplo más dramático de una gramática no libre de contexto, la gramática de Perl es, según tengo entendido, muy turing-complete .
Si entiendo su pregunta, está buscando lenguajes de programación que puedan describirse mediante gramáticas sin contexto (cfg) para que cfg genere todos los programas válidos y solo los programas válidos.
Creo que la mayoría (si no todos) los lenguajes de programación modernos no son, por lo tanto, libres de contexto. Por ejemplo, una vez que tiene tipos definidos por el usuario (muy comunes en los idiomas modernos), es automáticamente sensible al contexto.
Hay una diferencia entre verificar la sintaxis y verificar la corrección semántica de un programa. La verificación de la sintaxis es libre de contexto, mientras que la verificación de la corrección semántica no lo es (de nuevo, en la mayoría de los idiomas).
Esto, sin embargo, no significa que tal lenguaje no pueda existir. El cálculo lambda no tipificado , por ejemplo, se puede describir utilizando una gramática libre de contexto y, por supuesto, se completa con Turing.
VHDL es algo sensible al contexto.
(Google: parsing-vhdl-is-very-hard)