¿Qué lenguajes de programación son libres de contexto?

¿Qué lenguajes de programación son libres de contexto? [...]

Mi instinto me dice que los lenguajes funcionales podrían ser 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 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 imperativo lenguaje Brainfuck :

Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

Y aquí está un CFG para el funcional Cálculo combinador de esquí :

Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'

Estos CFGs reconocen todos los programas válidos de los dos lenguajes porque son tan simples.

La versión más larga: Generalmente, las gramáticas libres de contexto (CFGs) solo se usan para aproximadamente especificar la sintaxis de un lenguaje. Uno debe distinguir entre sintácticamente correcta programas y programas que compilan. Más comúnmente, los compiladores dividen el análisis del lenguaje en análisis sintáctico que construye y verifica la estructura general de un fragmento de código, y análisis semántico que verifica el significado del programa.

Si por "lenguaje libre de contexto" quieres decir "... para lo cual todos los programas compilan", 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, sensibilidad a espacios en blanco, un sistema de tipos o cualquier otro contexto: Información definida en un lugar y en la que se confía en otro.

Si, por otro lado, "lenguaje libre de contexto" solo significa "... para lo que todos los programas pasan syntax analysis", 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. Algunos de estos son superar mediante la adición de estado adicional a los analizadores para realizar un seguimiento de los contadores, tablas de búsqueda, y así sucesivamente.

Ejemplos de características sintácticas que no son posibles de expresar con un CFG:

• Lenguajes sensibles a la sangría y los espacios en blanco como Python y Haskell. Realizar un 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 hay niveles.

  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 Tipo C dice que los programas 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 tipo typedef para un tipo existente.

  El ejemplo is:

    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 habrá lexeado 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 auto-modificable. Véase también " Es C++ ¿libre de contexto o sensible al contexto?"

• A menudo, la precedencia del operador y la asociatividad no se expresan directamente en CFGs a pesar de que *es posible. Por ejemplo, un CFG para una gramática de expresión pequeña donde ^ se une más apretado que×, y × se une más apretado que+, podría tener este aspecto:

  E → E ^ E
  E → E × E
  E → E + E
  E → (E)
  E → num
  

  Este CFG es ambiguo , sin embargo, y a menudo va acompañado de una tabla de precedencia / asociatividad que dice, por ejemplo, que ^ se une más apretado, × se une más apretado que + , que ^ es derecha-asociativa, y que × y + son izquierda-asociativa.

  La precedencia y la asociatividad pueden codificarse en un CFG de una manera mecánica de tal manera que sea inequívoca 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 de CFGs + precedencia / asociatividad ambiguas son comunes porque son más legibles y porque varios tipos de analizador LR bibliotecas generadoras pueden producir más analizadores eficientes mediante eliminando los conflictos shift/reduce en lugar de tratar con una gramática inequívoca 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 son libres de contexto. El argumento continúa,

, Mientras que se puede argumentar que sería aceptable limitación para que un lenguaje permita 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.
     - Torben Morgensen Basics of Compiler Design, ch. 2.10.2

Lo mismo ocurre con 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 los lenguajes de programación del mundo real se definen por sus implementaciones, y la mayoría de los analizadores para lenguajes de programación del mundo real están escritos a mano o utilizan un generador de analizadores que extiende 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 Backus-Naur (BNF), o una especificación de analizador sintáctico que probablemente no esté puramente libre de contexto.

Ejemplos de especificaciones gramaticales de la salvaje:

• BNF para ML estándar
• Tipo BNF para Haskell
• BNF for SQL
• Gramática Yacc para PHP

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 existe una gramática libre de contexto que acepte solo programas sintácticamente correctos en C. Las personas que apuntan a las gramáticas libres de contexto de yacc/bison para C están perdiendo el punto.

Para ir al ejemplo más dramático de una gramática sin contexto, la gramática de Perl es, según lo entiendo, turing-completa.

Si entiendo su pregunta, está buscando lenguajes de programación que puedan ser descritos por gramáticas libres de contexto (cfg) para que el cfg genere todos los programas válidos y solo programas válidos.

Creo que la mayoría (si no todos) los lenguajes de programación modernos no están libres de contexto. Por ejemplo, una vez que tiene los tipos definidos por el usuario (muy comunes en los lenguajes modernos), automáticamente es sensible al contexto.

Hay una diferencia entre la sintaxis de verificación y verificar la corrección semántica de un programa. Comprobar la sintaxis es libre de contexto, mientras que comprobar 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. Untyped lambda calculus, por ejemplo, se puede describir usando una gramática libre de contexto, y es, por supuesto, Turing completa.

Creo que Haskelly ML están soportando libre de contexto. Ver este enlace para Haskell.

VHDL es algo sensible al contexto.

(Google: parsing-vhdl-is-very-hard)

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 de máquina correspondiente no puede procesar coincidencias de cadenas como {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