Para que un lenguaje sea programable, ¿es obligatorio que se base en una gramática libre de contexto?

23

Prácticamente, para un lenguaje que eventualmente puede compilarse / transformarse en instrucciones de nivel de sistema, ¿es necesario que sea una gramática libre de contexto?

Ej: ¿Todos los lenguajes de programación / scripting son gramáticas libres de contexto? Java se basa en CFG, pero ¿es realmente el caso de que todos los lenguajes de programación se basen en CFG?

No parece obligatorio, pero hay lagunas en mi entendimiento.

Algún contexto para la pregunta: estaba mirando la especificación del lenguaje Java, que también proporciona las reglas gramaticales . Esto me hizo pensar en esta pregunta.

pl.programming-languages context-free sandeepkunkunuru
fuente
1
En general, creo que es solo que desea que el problema de compilación sea computable, y analizar los CFG es agradable y fácil. Aunque he escuchado algunas afirmaciones de que, por ejemplo, reconocer programas perl válidos es, de hecho, un problema no computable.
Janne H. Korhonen
2
en realidad, todo lo que realmente necesita es una sintaxis decidible de Turing (que son todos los CFG) También podría crear un lenguaje de programación cuya sintaxis no sea decidible durante el tiempo, pero cuando crea un error tipográfico, el compilador nunca se detiene mientras intenta decidir si es una sintaxis válida. esto no es realmente útil
monstruo de trinquete
@ratchet, ¿estás asumiendo que la sintaxis debe ser recursivamente enumerable?
David Harris
44
@ JananKorhonen: Específicamente, Perl no se puede analizar estáticamente , es decir, no se puede analizar sin que también se ejecute; Dado que dicha ejecución podría no terminar, analizar Perl estáticamente implicaría resolver el problema de detención.
Jon Purdy
@janne quiero decir, el preprocesamiento posterior que puede implicar problemas que pueden ser o no computables, es generalmente el caso de que la gramática final contra la cual se valida el programa no tiene contexto. Para ser más específicos, después del preprocesamiento, para identificar una regla que se ajuste a una secuencia de tokens, necesitamos observar otros tokens que rodean la secuencia. No sé si tengo sentido, lo siento. Estoy un poco confundido en realidad.
sandeepkunkunuru

Respuestas:

20

Dos veces no.

Primero, la mayoría de los HPL no están libres de contexto. Si bien generalmente tienen una sintaxis basada en un CFG, también tienen lo que las personas llaman semántica estática (que a menudo también se incluye en el término sintaxis). Esto puede incluir nombres y tipos que deben verificar para obtener un programa correcto. Por ejemplo,

class A {
  String a = "a";
  int b = a + d;
}

es un programa Java sintácticamente correcto pero no se compilará porque dno está definido y ano tiene un tipo de ajuste.

En segundo lugar, puede analizar lenguajes que no están libres de contexto (como es evidente por la existencia de compiladores). Es solo que los CFG pueden analizarse de manera eficiente, mientras que los CSG no pueden, en general. Sin embargo, puede agregar ciertas características que no están libres de contexto sin dejar de ser eficientes.

Los compiladores a menudo se ejecutan en fases: primero la tokenización (regular), luego el análisis sin contexto, luego el análisis de nombres y tipos (sensible al contexto, a veces incluso más difícil). Puede observar ese comportamiento por el tipo de mensajes de error que recibe.

Rafael
fuente
3
No olvides que public class Program { public static void main(String[] args) { ... } }... Java no te permitirá salir así de fácil. :-)
Roy Tinker
Técnicamente, class A { ... }es completamente suficiente ya que javaccompila cosas que realmente no puede ejecutar (por falta de un punto de entrada), también. Pero si.
Raphael
20

Analizar perl no se puede decidir.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Niall Murphy
fuente
66
Siento que esto debería ser el punto de partida de una broma de Perl :)
Suresh Venkat
55
Suresh: Ya hice esa broma, aunque no resultó ser una muy buena broma, en el documento "Sobre lenguajes de programación no flexibles" en SIGBOVIK 2011 ( sigbovik.org/2011/proceedings.pdf - página 79- 82)
Rob Simmons el
1
Nota: el intérprete de Perl aún no es no determinista, si eso es un consuelo para alguien :)
Roy Tinker
15

No creo que la gramática de Python esté libre de contexto. El requisito de que las líneas en el mismo bloque de código tengan la misma cantidad de sangría no es el tipo de cosa que las gramáticas libres de contexto manejan bien.

Más precisamente, parece haber un homomorfismo del lenguaje de los bloques de Python de la forma

si condición:
     línea 1
     línea 2
     línea 3
más:
     line4

0n10n10n

David Eppstein
fuente
44
Estrictamente tiene razón, pero en el contexto de los lenguajes de programación, tratamos de liberar el contexto del lenguaje resultante después de un paso de preprocesamiento llamado tokenización . Creo que la sangría se verifica antes de eso.
Diego de Estrada
77
Sí, el Python lexer (tokenizer) tiene una pila de profundidades de sangría; la secuencia de tokens tiene un símbolo INDENT al principio de cada bloque y un símbolo DEDENT al final que se puede analizar de forma libre de contexto (INDENT y DEDENT actúan de manera muy similar a las llaves en C). C tiene el problema de "no puedo decir si la declaración o expresión": ¿es foo * bar;una declaración foocomo un puntero baro una multiplicación de footiempos bar?
Max
8
Ok, claro, pero entonces solo estás ocultando la misma complejidad en el lexer, en lugar de convertirlo en un transductor de estado finito como lo son a menudo.
David Eppstein
1
@DavidEppstein: Para ser justos, dicha complejidad no es excelente de ninguna manera.
Jon Purdy
1
Además del manejo de INDENT / DEDENT en el lexer, Python tiene una gramática LL (1) muy simple.
rmmh
13

Bodo Manthey y Martin Böhme muestran que cada compilador de C ++ está necesariamente completo, es decir, puede calcular cualquier función recursiva parcial en tiempo de compilación . Por lo tanto, es mucho peor que solo sensible al contexto.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Markus Bläser
fuente
Sí, pero el compilador nunca son solo gramáticas libres de contexto. Debes discutir la gramática en sí, no el compilador.
Jeff Burdges
@Jeff: "Tiempo de compilación" en mi respuesta significa "verificar si un código fuente de C + es correcto". Mediante una ligera modificación de la construcción en el documento, se deduce que puede reducir cada lenguaje decidible al conjunto de todos los programas C ++ correctos.
Markus Bläser
7

Creo que la declaración antes del uso de variables y la función polimorfismo de los lenguajes OOP son otros ejemplos de especificaciones de lenguajes de programación que no pueden ser manejadas por gramáticas libres de contexto:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

Hice una pequeña búsqueda en Google y encontré este artículo: " Una gramática booleana para un lenguaje booleano simple " por A.Okhotin (2004); Según él, el verdadero problema es encontrar un lenguaje de programación que esté completamente descrito por una gramática formal:

Se define un lenguaje de programación procesal de juguete y se construye una gramática booleana para el conjunto de programas bien formados en este lenguaje. Aparentemente, esta es la primera especificación de un lenguaje de programación enteramente por una gramática formal.

La sección de Introducción del artículo es breve pero muy clarificadora.

Marzio De Biasi
fuente
6

Creo que la gramática de C solo es técnicamente libre de contexto, ya que los analizadores siempre usan técnicas no libres de contexto para admitir el dispositivo de Duff .

Los lenguajes basados ​​en sangría no están naturalmente libres de contexto, como dijo David, pero se vuelven libres de contexto en relación con un token de sangría parametrizado.

Haskell le permite cambiar la precedencia del operador con infix e infixl. El estricto módulo pragma de Perl se implementa utilizando las configuraciones léxicas $ ^ H y% ^ H, que lo hacen no contextual, probablemente también otras configuraciones.

Hay lenguajes de expansión de macros como TeX en los que el análisis afaik no tiene sentido sin ejecutarse.

Probablemente haya incluso dos gramáticas libres de contexto cuya intersección no esté libre de contexto, pero aún así describe una máquina de Turing.

Java y el ensamblador probablemente estén naturalmente libres de contexto.

Jeff Burdges
fuente
2
¿No es la ambigüedad de (a)-bhacer C sensible al contexto? ( apodría ser una variable o un typedef; algunos otros idiomas no permiten emitir expresiones menos unarias por este motivo)
Random832
Pido disculpas por el comentario muy retrasado, pero el dispositivo de Duff no implica desviaciones sintácticas. Los frenos se equilibran correctamente. La característica C que se ignora con mayor frecuencia en las discusiones sobre si C está libre de contexto es el preprocesador. Soy escéptico de que haya alguna interpretación, por informal que sea, de "contexto libre" que permita usarlo para describir un lenguaje con un procesador macro, incluso uno que se porte bien. Y el preprocesador C es cualquier cosa menos bueno.
rici
4

No, y muchos lenguajes prácticos no están libres de contexto. Por ejemplo, la gramática de C ++ no lo es, porque en algunos contextos la resolución de la gramática depende de escribir información que no esté libre de contexto.

antti.huima
fuente
4

Primero permítanme hacer una distinción entre la sintaxis de un lenguaje de programación y el lenguaje en sí.

La sintaxis de muchos idiomas es (al menos basada en) una Gramática libre de contexto (CFG) porque están bien estudiados y existen algoritmos que pueden analizar eficientemente un CFG y el caso límite que no puede ser resuelto por el CFG puede manejarse especialmente

Sin embargo, de hecho, muchos lenguajes no están libres de contexto (cuando se usan símbolos de declarar antes de usar, por ejemplo, en java, C (++), D).

Dato curioso: D tiene una evaluación de función de tiempo de compilación completa de Turing y una expansión de plantilla que hace que el lenguaje en sí no sea decidible para Turing. Sin embargo, el creador del lenguaje hizo todo lo posible para convertir la sintaxis en un CFG.

monstruo de trinquete
fuente
El análisis de nombres y tipos generalmente realiza tareas inherentemente libres de contexto.
Raphael el
La metaprogramación de plantillas en C ++ está completa.
Jeff Burdges
3

En cuanto a "¿Todos los lenguajes de programación / scripting son gramáticas libres de contexto?" parte se refiere, la respuesta es un No. definitivo

Re: la pregunta principal de "para un lenguaje que eventualmente puede compilarse / transformarse en instrucciones de nivel de sistema", no sé por qué necesariamente tiene que ser un CFG. Sin embargo, podrían surgir mejores explicaciones.

Kris
fuente
1
Kris, ¿puedes dar algunos ejemplos de lenguajes de programación basados ​​en gramática libre de contexto. Quiero decir, el preprocesamiento posterior que puede implicar problemas que pueden ser o no computables, la gramática final contra la cual se valida el programa.
sandeepkunkunuru
3

Un lenguaje de programación debe basarse en algún tipo de formalismo gramatical, de los cuales los CFG son un ejemplo. Si bien los CFG son los más comunes (y son lo habitual que se enseña en los cursos de compilación en las universidades), hay otros formalismos como Parsing Expression Grammars, que puede leer más aquí (pdf) o en Wikipedia para una lectura más pequeña.

evilcandybag
fuente