A menudo escucho afirmaciones de que C ++ es un lenguaje sensible al contexto. Tome el siguiente ejemplo:
a b(c);
¿Es esta una definición variable o una declaración de función? Eso depende del significado del símbolo c
. Si c
es una variable , a b(c);
define una variable llamada b
de tipo a
. Se inicializa directamente con c
. Pero si c
es un tipo , a b(c);
declara una función llamada b
que toma un c
y devuelve un a
.
Si busca la definición de lenguajes sin contexto, básicamente le dirá que todas las reglas gramaticales deben tener lados izquierdos que consisten en exactamente un símbolo no terminal. Las gramáticas sensibles al contexto, por otro lado, permiten cadenas arbitrarias de símbolos terminales y no terminales en el lado izquierdo.
Navegando por el Apéndice A de "El lenguaje de programación C ++", no pude encontrar una sola regla gramatical que tuviera algo más que un solo símbolo no terminal en su lado izquierdo. Eso implicaría que C ++ no tiene contexto. (Por supuesto, cada lenguaje libre de contexto también es sensible al contexto en el sentido de que los lenguajes libres de contexto forman un subconjunto de los lenguajes sensibles al contexto, pero ese no es el punto).
Entonces, ¿C ++ no tiene contexto o es sensible al contexto?
fuente
Respuestas:
A continuación está mi demostración favorita (actual) de por qué analizar C ++ es (probablemente) Turing completo , ya que muestra un programa que es sintácticamente correcto si y solo si un entero dado es primo.
Por lo tanto, afirmo que C ++ no es libre de contexto ni sensible al contexto .
Si permite secuencias de símbolos arbitrarias en ambos lados de cualquier producción, produce una gramática de tipo 0 ("sin restricciones") en la jerarquía de Chomsky , que es más poderosa que una gramática sensible al contexto; las gramáticas sin restricciones son completas de Turing. Una gramática sensible al contexto (Tipo-1) permite múltiples símbolos de contexto en el lado izquierdo de una producción, pero el mismo contexto debe aparecer en el lado derecho de la producción (de ahí el nombre "sensible al contexto"). [1] Las gramáticas sensibles al contexto son equivalentes a las máquinas de Turing con límites lineales .
En el programa de ejemplo, el cálculo principal podría ser realizado por una máquina de Turing con límites lineales, por lo que no prueba la equivalencia de Turing, pero la parte importante es que el analizador debe realizar el cálculo para realizar un análisis sintáctico. Podría haber sido cualquier cálculo expresable como una creación de instancias de plantilla y hay muchas razones para creer que la creación de instancias de plantilla C ++ es completa de Turing. Ver, por ejemplo, el artículo de 2003 de Todd L. Veldhuizen .
De todos modos, C ++ puede ser analizado por una computadora, por lo que ciertamente podría ser analizado por una máquina Turing. En consecuencia, una gramática sin restricciones podría reconocerlo. En realidad, escribir tal gramática no sería práctico, por lo que el estándar no intenta hacerlo. (Vea abajo.)
El problema con la "ambigüedad" de ciertas expresiones es principalmente una pista falsa. Para empezar, la ambigüedad es una característica de una gramática particular, no un lenguaje. Incluso si se puede demostrar que un idioma no tiene gramáticas inequívocas, si puede ser reconocido por una gramática libre de contexto, es libre de contexto. Del mismo modo, si no puede ser reconocido por una gramática libre de contexto pero puede ser reconocido por una gramática sensible al contexto, es sensible al contexto. La ambigüedad no es relevante.
Pero en cualquier caso, como la línea 21 (es decir
auto b = foo<IsPrime<234799>>::typen<1>();
) en el programa a continuación, las expresiones no son ambiguas en absoluto; simplemente se analizan de manera diferente según el contexto. En la expresión más simple del problema, la categoría sintáctica de ciertos identificadores depende de cómo se hayan declarado (tipos y funciones, por ejemplo), lo que significa que el lenguaje formal debería reconocer el hecho de que dos cadenas de longitud arbitraria en Los mismos programas son idénticos (declaración y uso). Esto puede ser modelado por la gramática de "copia", que es la gramática que reconoce dos copias exactas consecutivas de la misma palabra. Es fácil de probar con el lema de bombeoque este lenguaje no está libre de contexto. Es posible una gramática sensible al contexto para este idioma, y se proporciona una gramática de tipo 0 en la respuesta a esta pregunta: /math/163830/context-sensitive-grammar-for-the- lenguaje de copia .Si uno intentara escribir una gramática sensible al contexto (o sin restricciones) para analizar C ++, posiblemente llenaría el universo con garabatos. Escribir una máquina de Turing para analizar C ++ sería una tarea igualmente imposible. Incluso escribir un programa en C ++ es difícil, y que yo sepa, ninguno ha demostrado ser correcto. Esta es la razón por la cual el estándar no intenta proporcionar una gramática formal completa, y por qué elige escribir algunas de las reglas de análisis en inglés técnico.
Lo que parece una gramática formal en el estándar C ++ no es la definición formal completa de la sintaxis del lenguaje C ++. Ni siquiera es la definición formal completa del lenguaje después del preprocesamiento, lo que podría ser más fácil de formalizar. (Sin embargo, ese no sería el lenguaje: el lenguaje C ++ definido por el estándar incluye el preprocesador, y la operación del preprocesador se describe algorítmicamente, ya que sería extremadamente difícil de describir en cualquier formalismo gramatical. Está en esa sección del estándar donde se describe la descomposición léxica, incluidas las reglas en las que debe aplicarse más de una vez).
Las diversas gramáticas (dos gramáticas superpuestas para el análisis léxico, una que tiene lugar antes del preprocesamiento y la otra, si es necesario, después, más la gramática "sintáctica") se recogen en el Apéndice A, con esta nota importante (énfasis agregado):
Finalmente, aquí está el programa prometido. La línea 21 es sintácticamente correcta si y solo si la N
IsPrime<N>
es primo. De lo contrario,typen
es un entero, no una plantilla, por lo quetypen<1>()
se analiza como(typen<1)>()
sintácticamente incorrecto porque()
no es una expresión sintácticamente válida.[1] Para decirlo más técnicamente, cada producción en una gramática sensible al contexto debe tener la forma:
αAβ → αγβ
donde
A
es un no terminal yα
,β
posiblemente son secuencias vacías de símbolos gramaticales, yγ
es una secuencia no vacía. (Los símbolos gramaticales pueden ser terminales o no terminales).Esto se puede leer
A → γ
solo en el contexto[α, β]
. En una gramática libre de contexto (Tipo 2),α
yβ
debe estar vacía.Resulta que también puede restringir las gramáticas con la restricción "monotónica", donde cada producción debe tener la forma:
α → β
donde|α| ≥ |β| > 0
(|α|
significa "la longitud deα
")Es posible demostrar que el conjunto de idiomas reconocidos por las gramáticas monotónicas es exactamente el mismo que el conjunto de idiomas reconocidos por las gramáticas sensibles al contexto, y a menudo es más fácil basar las pruebas en las gramáticas monotónicas. En consecuencia, es bastante común ver "sensible al contexto" usado como si significara "monótono".
fuente
0
dentro()
, por uno simple), pero creo que es más interesante de esta manera, porque demuestra que necesitas la creación de instancias de plantilla incluso para reconocer si una cadena es un programa C ++ sintácticamente correcto. Si ambas ramas se compilan, entonces tendría que trabajar más para refutar el argumento de que la diferencia es "semántica". Curiosamente, aunque a menudo me desafían a definir "sintáctico", nadie ha ofrecido una definición de "semántico" que no sea "cosas que no creo que sean sintácticas" :)Primero, usted observó correctamente que no hay reglas sensibles al contexto en la gramática al final del estándar C ++, por lo que la gramática está libre de contexto.
Sin embargo, esa gramática no describe con precisión el lenguaje C ++, porque produce programas que no son C ++ como
o
El lenguaje C ++ definido como "el conjunto de programas C ++ bien formados" no está libre de contexto (es posible demostrar que las variables simplemente exigentes que se declaran lo hacen así). Dado que teóricamente puedes escribir programas completos de Turing en plantillas y hacer que un programa esté mal formado en función de su resultado, ni siquiera es sensible al contexto.
Ahora, las personas (ignorantes) (generalmente no teóricos del lenguaje, sino diseñadores de analizadores sintácticos) generalmente usan "no sin contexto" en algunos de los siguientes significados
La gramática en la parte posterior del estándar no satisface estas categorías (es decir, es ambigua, no LL (k) ...) por lo que la gramática de C ++ "no está libre de contexto" para ellos. Y en cierto sentido, tienen razón, es muy difícil producir un analizador de C ++ que funcione.
Tenga en cuenta que las propiedades aquí utilizadas solo están débilmente conectadas a lenguajes libres de contexto: la ambigüedad no tiene nada que ver con la sensibilidad al contexto (de hecho, las reglas sensibles al contexto generalmente ayudan a desambiguar las producciones), los otros dos son simplemente subconjuntos de contexto -Los idiomas libres. Y analizar lenguajes libres de contexto no es un proceso lineal (aunque sí lo es).
fuente
ambiguity doesn't have anything to do with context-sensitivity
Esta también era mi intuición, así que me alegra ver que alguien (a) está de acuerdo y (b) lo explica donde no pude. Creo que descalifica todos los argumentos en los que se basaa b(c);
y satisface parcialmente la pregunta original cuya premisa eran afirmaciones "a menudo escuchadas" de que la sensibilidad al contexto se debe a la ambigüedad ... especialmente cuando para la gramática en realidad no hay ambigüedad incluso en el MVPSi. La siguiente expresión tiene un orden diferente de operaciones según el tipo de contexto resuelto :
Editar: cuando el orden real de operación varía, hace que sea increíblemente difícil usar un compilador "normal" que analiza un AST sin decorar antes de decorarlo (propagar información de tipo). Otras cosas sensibles al contexto mencionadas son "bastante fáciles" en comparación con esto (no es que la evaluación de la plantilla sea fácil).
Seguido por:
fuente
Para responder a su pregunta, necesita distinguir dos preguntas diferentes.
La mera sintaxis de casi todos los lenguajes de programación no tiene contexto. Por lo general, se da como una forma extendida de Backus-Naur o gramática libre de contexto.
Sin embargo, incluso si un programa se ajusta a la gramática libre de contexto definida por el lenguaje de programación, no es necesariamente un programa válido . Hay muchas propiedades no libres de contexto que un programa tiene que satisfacer para ser un programa válido. Por ejemplo, la propiedad más simple es el alcance de las variables.
Para concluir, si C ++ está libre de contexto depende de la pregunta que haga.
fuente
VARDECL : TYPENAME IDENTIFIER
, pero no puede tener eso, porque no puede distinguir los nombres de tipo de otros identificadores a nivel de CF. Otro ejemplo: a nivel CF, no puede decidir si analizara*b
como una declaración variable (b
de tipo puntero aa
) o como una multiplicación.Es posible que desee echar un vistazo a The Design & Evolution of C ++ , de Bjarne Stroustrup. En él, describe sus problemas al tratar de usar yacc (o similar) para analizar una versión anterior de C ++, y deseando haber usado el descenso recursivo en su lugar.
fuente
Sí, C ++ es sensible al contexto, muy sensible al contexto. No puede construir el árbol de sintaxis simplemente analizando el archivo usando un analizador de contexto libre porque en algunos casos necesita conocer el símbolo de conocimiento previo para decidir (es decir, construir una tabla de símbolos mientras analiza).
Primer ejemplo:
¿Es esta una expresión de multiplicación?
O
¿Es esta una declaración de
B
variable para ser un puntero de tipoA
?Si A es una variable, entonces es una expresión, si A es tipo, es una declaración de puntero.
Segundo ejemplo
¿Es este un prototipo de función que toma un argumento de
bar
tipo?O
¿Esto declara una variable
B
de tipoA
y llama al constructor de A conbar
constante como inicializador?Necesita saber nuevamente si
bar
es una variable o un tipo de la tabla de símbolos.Tercer ejemplo:
Este es el caso cuando construir una tabla de símbolos mientras se analiza no ayuda porque la declaración de xey viene después de la definición de la función. Por lo tanto, primero debe explorar la definición de clase y observar las definiciones de método en una segunda pasada, para decir que x * y es una expresión, y no una declaración de puntero o lo que sea.
fuente
A B();
es una declaración de función incluso en una definición de función. Busque el análisis más irritante ...C ++ se analiza con el analizador GLR. Eso significa que durante el análisis del código fuente, el analizador puede encontrar ambigüedad, pero debe continuar y decidir qué regla gramatical usar más adelante .
mira también
¿Por qué C ++ no se puede analizar con un analizador LR (1)?
Recuerde que la gramática libre de contexto no puede describir TODAS las reglas de una sintaxis de lenguaje de programación. Por ejemplo, la gramática de atributos se usa para verificar la validez de un tipo de expresión.
No puede describir la siguiente regla con una gramática libre de contexto: El lado derecho de la tarea debe ser del mismo tipo que el lado izquierdo.
fuente
Tengo la sensación de que existe cierta confusión entre la definición formal de "sensible al contexto" y el uso informal de "sensible al contexto". El primero tiene un significado bien definido. Este último se usa para decir "necesita contexto para analizar la entrada".
Esto también se pregunta aquí: sensibilidad al contexto frente a ambigüedad .
Aquí hay una gramática libre de contexto:
Es ambiguo, por lo que para analizar la entrada "x" necesita algo de contexto (o vivir con la ambigüedad, o emitir "Advertencia: E8271 - La entrada es ambigua en la línea 115"). Pero ciertamente no es una gramática sensible al contexto.
fuente
Ningún lenguaje similar a Algol está libre de contexto, porque tienen reglas que restringen las expresiones y declaraciones en las que pueden aparecer identificadores en función de su tipo, y porque no hay límite en el número de declaraciones que pueden ocurrir entre la declaración y el uso.
La solución habitual es escribir un analizador sin contexto que realmente acepte un superconjunto de programas válidos y coloque las porciones sensibles al contexto en un código "semántico" ad hoc adjunto a las reglas.
C ++ va mucho más allá de esto, gracias a su sistema de plantillas Turing-complete. Consulte la Pregunta de desbordamiento de pila 794015 .
fuente
Cierto :)
J. Stanley Warford. Sistemas informáticos . Páginas 341-346.
fuente
A veces es peor: ¿qué quieren decir las personas cuando dicen que C ++ tiene una "gramática indecidible"?
fuente
Es sensible al contexto, ya que
a b(c);
tiene dos parámetros válidos: declaración y variable. Cuando dices "Sic
es un tipo", ese es el contexto, allí mismo, y has descrito exactamente cómo C ++ es sensible a él. Si no tuviera ese contexto de "¿Qué esc
?" no podrías analizar esto sin ambigüedades.Aquí, el contexto se expresa en la elección de tokens: el analizador lee un identificador como un token de tipo de nombre si nombra un tipo. Esta es la resolución más simple y evita gran parte de la complejidad de ser sensible al contexto (en este caso).
Editar: Hay, por supuesto, más problemas de sensibilidad al contexto, simplemente me he centrado en el que has mostrado. Las plantillas son especialmente desagradables para esto.
fuente
a<b<c>>d
, ¿verdad? (Su ejemplo es en realidad un clásico de C , donde es la única obstrucción para estar libre de contexto.)Las producciones en el estándar C ++ están escritas sin contexto, pero, como todos sabemos, en realidad no definen el lenguaje con precisión. Algo de lo que la mayoría de la gente ve como ambigüedad en el idioma actual podría (creo) resolverse sin ambigüedades con una gramática sensible al contexto.
Para el ejemplo más obvio, consideremos el más irritante de análisis:
int f(X);
. SiX
es un valor, esto se definef
como una variable que se inicializará conX
. SiX
es un tipo, se definef
como una función que toma un único parámetro de tipoX
.Mirando eso desde un punto de vista gramatical, podríamos verlo así:
Por supuesto, para ser completamente correctos, necesitaríamos agregar algunas "cosas" adicionales para tener en cuenta la posibilidad de intervenir declaraciones de otros tipos (es decir, A y B deberían ser realmente "declaraciones que incluyan la declaración de X como ..." , o algo en ese orden).
Sin embargo, esto es bastante diferente de un CSG típico (o al menos lo que recuerdo de ellos). Esto depende de la construcción de una tabla de símbolos: la parte que reconoce específicamente
X
como un tipo o valor, no solo algún tipo de declaración que lo precede, sino el tipo correcto de declaración para el símbolo / identificador correcto.Como tal, tendría que investigar un poco para estar seguro, pero mi suposición inmediata es que esto realmente no califica como un CSG, al menos como el término se usa normalmente.
fuente
El caso más simple de gramática no libre de contexto implica analizar expresiones que involucran plantillas.
Esto puede analizar como
O
Las dos AST solo pueden ser desambiguadas examinando la declaración de 'a': la primera AST si 'a' es una plantilla, o la segunda si no.
fuente
<
deben ser un paréntesis si pudieran serlo (por ejemplo, sigue un identificador que nombra una plantilla). C ++ 11 agregó el requisito>
y el primer carácter de>>
ser interpretado como corchetes si ese uso es plausible. Esto afecta el análisis dea<b>c>
dóndea
hay una plantilla pero no tiene ningún efectoa<b<c>
.a();
(que esexpr.call
oexpr.type.conv
)?Se ha demostrado que las plantillas de C ++ son Turing Powerful. Aunque no es una referencia formal, aquí hay un lugar para buscar en ese sentido:
http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html
Me aventuraré a adivinar (tan antiguo como una prueba de CACM folkorica y concisa que muestra que ALGOL en los años 60 no podía ser repetido por un CFG) y decir que C ++ no puede ser analizado correctamente solo por un CFG. CFG, junto con varios mecanismos de TP en un pase de árbol o durante eventos de reducción: esta es otra historia. En un sentido general, debido al problema de detención, existe algún programa de C ++ que no se puede demostrar que sea correcto / incorrecto pero que, sin embargo, es correcto / incorrecto.
{PD- Como autor de Meta-S (mencionado por varias personas arriba), puedo decir con toda seguridad que Thothic no está extinto ni el software está disponible de forma gratuita. Tal vez he redactado esta versión de mi respuesta de tal manera que no me eliminen ni voten por -3.}
fuente
C ++ no está libre de contexto. Lo aprendí hace algún tiempo en la conferencia de compiladores. Una búsqueda rápida le dio este enlace, donde la sección "Sintaxis o semántica" explica por qué C y C ++ no están libres de contexto:
Wikipedia Talk: gramática libre de contexto
Un saludo,
Ovanes
fuente
Obviamente, si toma la pregunta al pie de la letra, casi todos los idiomas con identificadores son sensibles al contexto.
Es necesario saber si un identificador es un nombre de tipo (un nombre de clase, un nombre introducido por typedef, un parámetro de plantilla de nombre de tipo), un nombre de plantilla o algún otro nombre para poder utilizar correctamente parte del identificador. Por ejemplo:
es una conversión si
name
es un nombre de tipo y una llamada a función siname
es un nombre de función. Otro caso es el llamado "análisis más irritante" donde no es posible diferenciar la definición de variable y la declaración de función (hay una regla que dice que es una declaración de función).Esa dificultad ha introducido la necesidad de
typename
ytemplate
con nombres dependientes. El resto de C ++ no es sensible al contexto hasta donde yo sé (es decir, es posible escribir una gramática libre de contexto para él).fuente
El enlace correcto está analizando enigines
Meta-S era propiedad de una empresa extinta llamada Thothic. Puedo enviar una copia gratuita del Meta-S a cualquier persona interesada y la he usado en la investigación de análisis. Tenga en cuenta que la "gramática de pseudoknot" incluida en las carpetas de ejemplos fue escrita por un programador aficionado no bioinformático y básicamente no funciona. Mis gramáticas toman un enfoque diferente y funcionan bastante bien.
fuente
Un gran problema aquí es que los términos "libre de contexto" y "sensible al contexto" son poco intuitivos dentro de la informática. Para C ++, la sensibilidad al contexto se parece mucho a la ambigüedad, pero eso no es necesariamente cierto en el caso general.
En C / ++, una instrucción if solo se permite dentro de un cuerpo de función. Eso parecería hacerlo sensible al contexto, ¿verdad? Bueno no. Las gramáticas sin contexto en realidad no necesitan la propiedad donde puede extraer alguna línea de código y determinar si es válida. Eso no es realmente lo que significa sin contexto. Realmente es solo una etiqueta que implica vagamente algo relacionado con lo que parece.
Ahora, si una declaración dentro del cuerpo de una función se analiza de manera diferente dependiendo de algo definido fuera de los antepasados gramaticales inmediatos (por ejemplo, si un identificador describe un tipo o variable), como en el
a * b;
caso, entonces es, de hecho, sensible al contexto. No hay ambigüedad real aquí; se analizará como una declaración de un puntero sia
es un tipo y una multiplicación de lo contrario.Ser sensible al contexto no significa necesariamente "difícil de analizar". C en realidad no es tan difícil porque la infame
a * b;
"ambigüedad" se puede resolver con una tabla de símbolos que contiene lostypedef
mensajes encontrados anteriormente. No requiere ninguna instancia de plantilla arbitraria (que se haya comprobado que es Turing Complete) para resolver ese caso como lo hace C ++ en ocasiones. En realidad, no es posible escribir un programa en C que no se compile en un tiempo finito aunque tenga la misma sensibilidad al contexto que C ++.Python (y otros lenguajes sensibles al espacio en blanco) también depende del contexto, ya que requiere un estado en el léxico para generar tokens de sangría y sangría, pero eso no hace que sea más difícil de analizar que una gramática LL-1 típica. En realidad, utiliza un generador de analizadores, que es parte de por qué Python tiene mensajes de error de sintaxis tan poco informativos. También es importante tener en cuenta aquí que no hay "ambigüedad" como el
a * b;
problema en Python, dando un buen ejemplo concreto de un lenguaje sensible al contexto sin gramática "ambigua" (como se menciona en el primer párrafo).fuente
Esta respuesta dice que C ++ no está libre de contexto ... hay una implicación (no por el respondedor) de que no se puede analizar, y la respuesta ofrece un ejemplo de código difícil que produce un programa C ++ no válido si una constante constante no es un número primo.
Como otros han observado, la pregunta sobre si el lenguaje es sensible al contexto / libre es diferente de la misma pregunta sobre una gramática específica.
Para dejar en reposo la pregunta sobre la capacidad de análisis, ofrezco evidencia empírica de que existen gramáticas libres de contexto para C ++, que se pueden usar para producir un AST para un análisis libre de contexto del texto fuente al analizarlo de hecho con un GLR existente herramienta basada en analizadores que se basa en una gramática explícita.
Sí, tiene éxito al "aceptar demasiado"; no todo lo que acepta es un programa válido de C ++, por lo que se sigue con verificaciones adicionales (verificaciones de tipo). Y sí, el verificador de tipos puede encontrarse con problemas de computabilidad. En la práctica, las herramientas no tienen este problema; si la gente escribiera programas como ese, ninguno de ellos compilaría. (Creo que el estándar realmente pone un límite a la cantidad de cómputo que puede hacer desplegando una plantilla, por lo que, de hecho, el cómputo es en realidad finito pero probablemente bastante grande).
Si lo que quiere decir es determinar si el programa fuente es miembro del conjunto de programas fuente C ++ válidos , entonces estaré de acuerdo en que el problema es mucho más difícil. Pero el problema no es el análisis .
La herramienta resuelve este problema al aislar el análisis de la verificación de tipo del programa analizado. (Cuando hay múltiples interpretaciones en ausencia de contexto, registra un nodo de ambigüedad en el árbol de análisis con varios análisis posibles; la verificación de tipo decide cuál es la correcta y elimina los subárboles no válidos). Puede ver un árbol de análisis (parcial) en el siguiente ejemplo; todo el árbol es demasiado grande para caber en una respuesta SO. Tenga en cuenta que obtiene un árbol de análisis si se usa el valor 234797 o 234799.
Ejecutar el resolutor de tipo / nombre de la herramienta sobre el AST con el valor original 234799 tiene éxito. Con el valor 234797, el solucionador de nombres falla (como se esperaba) con el mensaje de error, "typen no es un tipo". y, por lo tanto, esa versión no es un programa válido de C ++.
fuente