c++ - pila - ¿La gramática de D''s es realmente libre de contexto?

gramatica libre de contexto java (7)

Lo publiqué en el grupo de noticias D hace algunos meses, pero por alguna razón, la respuesta nunca me convenció realmente, así que pensé que podría preguntarlo aquí.

La gramática de D aparentemente no tiene ningún contexto .

La gramática de C ++, sin embargo, no lo es (incluso sin macros). (¡ Por favor, lea esto con cuidado! )

Ahora bien, no sé nada (oficialmente) sobre compiladores, lexers y analizadores sintácticos. Todo lo que sé es por lo que aprendí en la web.
Y esto es lo que (creo) he entendido con respecto al contexto, en una jerga no tan técnica:

La gramática de un idioma está libre de contexto si y solo si siempre se puede entender el significado (aunque no necesariamente el comportamiento exacto) de una pieza determinada de su código sin necesidad de "buscar" en otro lugar.

O, incluso con menos rigor:

La gramática no puede estar libre de contexto si lo necesito. No puedo decir el tipo de expresión simplemente mirándola.

Entonces, por ejemplo, C ++ falla la prueba sin contexto porque el significado de confusing<sizeof(x)>::q < 3 > (2) depende del valor de q .

Hasta aquí todo bien.

Ahora mi pregunta es: ¿se puede decir lo mismo de D?

En D, las tablas hash se pueden crear a través de una declaración Value[Key] , por ejemplo

int[string] peoplesAges; // Maps names to ages

Las matrices estáticas se pueden definir en una sintaxis similar:

int[3] ages; // Array of 3 elements

Y las plantillas se pueden usar para hacerlas confusas:

template Test1(T...) { alias int[T[0]] Test; } template Test2(U...) { alias int[U] Test2; // LGTM } Test1!(5) foo; Test1!(int) bar; Test2!(int) baz; // Guess what? It''s invalid code.

Esto significa que no puedo decir el significado de T[0] o U simplemente mirándolo (es decir, podría ser un número, podría ser un tipo de datos, o podría ser una tupla de Dios sabe qué). Ni siquiera puedo decir si la expresión es gramaticalmente válida (ya que int[U] ciertamente no lo es; no se puede tener una tabla hash con tuplas como claves o valores).

Cualquier árbol de análisis que intente hacer para Test no tendría ningún sentido (ya que necesitaría saber si el nodo contiene un tipo de datos versus un literal o un identificador) a menos que retrase el resultado hasta que se conozca el valor de T ( haciéndolo dependiente del contexto).

Teniendo esto en cuenta, ¿D realmente no tiene contexto, o estoy malinterpretando el concepto?

¿Por qué por qué no?

Actualizar:

Solo pensé en comentar: es realmente interesante ver las respuestas, ya que:

Algunas respuestas afirman que C ++ y D no pueden estar libres de contexto
Algunas respuestas afirman que C ++ y D son ambos sin contexto
Algunas respuestas apoyan la afirmación de que C ++ es sensible al contexto, mientras que D no es
Nadie ha afirmado aún que C ++ no tiene contexto, mientras que D es sensible al contexto :-)

No puedo decir si estoy aprendiendo o estoy más confundido, pero de cualquier manera, estoy feliz de haber preguntado esto ... ¡gracias por tomarse el tiempo para responder, todos!

La gramática no puede estar libre de contexto si lo necesito. No puedo decir el tipo de expresión simplemente mirándola.

No, eso está completamente mal. La gramática no puede estar libre de contexto si no puede decir si es una expresión simplemente mirándola y el estado actual del analizador (¿estoy en una función, en un espacio de nombres, etc.)?

Sin embargo, el tipo de una expresión es un significado semántico, no sintáctico, y el analizador sintáctico y la gramática no dan ni un centavo sobre los tipos o la validez semántica o si puede tener tuplas como valores o claves en hashmaps, o si definió ese identificador antes de usarlo.

A la gramática no le importa lo que significa, o si tiene sentido. Solo se preocupa por lo que es .

Estar libre de contexto es primero una propiedad de gramáticas generativas. Significa que lo que un no terminal puede generar no dependerá del contexto en el que aparece el no terminal (en la gramática generativa sin contexto, la noción de "cadena generada por un no terminal dado" es en general difícil definir). Esto no impide que dos cadenas no terminales generen la misma cadena de símbolos (por lo que las mismas cadenas de símbolos aparecen en dos contextos diferentes con un significado diferente) y no tiene nada que ver con la verificación de tipos.

Es común ampliar la definición libre de contexto de las gramáticas al lenguaje al afirmar que un idioma no tiene contexto si hay al menos una gramática libre de contexto que lo describa.

En la práctica, ningún lenguaje de programación es libre de contexto porque las cosas como "una variable debe declararse antes de ser utilizada" no pueden ser verificadas por una gramática libre de contexto (pueden ser verificadas por otros tipos de gramáticas). Esto no está mal, en la práctica las reglas que deben verificarse se dividen en dos: las que desea verificar con la gramática y las que verifica en un pase semántico (y esta división también permite un mejor informe de errores y recuperación, por lo que a veces desea aceptar más en la gramática de lo que sería posible para dar a sus usuarios mejores diagnósticos).

Lo que las personas quieren decir al afirmar que C ++ no está libre de contexto es que hacer esta división no es posible de manera conveniente (con criterios convenientes que incluyen "casi la descripción oficial del lenguaje" y "mi herramienta generadora del analizador admite ese tipo de división ", lo que permite que la gramática sea ambigua y que la ambigüedad se resuelva con la comprobación semántica es una forma relativamente fácil de hacer el corte para C ++ y seguir el estándar de C ++, pero es inconveniente cuando se depende de herramientas que no no permita gramáticas ambiguas, cuando tenga tales herramientas, es conveniente).

No sé lo suficiente sobre D para saber si hay o no un corte conveniente de las reglas del lenguaje en una gramática libre de contexto con verificaciones semánticas, pero lo que se muestra está lejos de demostrar que no lo es.

Estas respuestas me hacen doler la cabeza.

En primer lugar, las complicaciones con los lenguajes de bajo nivel y la determinación de si están libres de contexto o no, es que el idioma que escribe a menudo se procesa en varios pasos.

En C ++ (el orden puede estar desactivado, pero eso no debería invalidar mi punto):

tiene que procesar macros y otros materiales preprocesadores
tiene que interpretar plantillas
finalmente interpreta tu código.

Como el primer paso puede cambiar el contexto del segundo paso y el segundo puede cambiar el contexto del tercer paso, el idioma en el que escribe (incluidos todos estos pasos) es sensible al contexto.

La razón por la que las personas intentarán y defenderán un idioma (declarando que no tiene ningún contexto) es porque las únicas excepciones que agregan contexto son las declaraciones de preprocesador trazables y las llamadas de plantilla. Solo tiene que seguir dos excepciones restringidas a las reglas para pretender que el idioma no tiene contexto.

La mayoría de los lenguajes son sensibles al contexto en general, pero la mayoría de los idiomas solo tienen estas pequeñas excepciones para estar libres de contexto.

Hay una construcción en el lexer de D''s:

string ::= q" Delim1 Chars newline Delim2 "

donde Delim1 y Delim2 son identificadores coincidentes, y Chars no contiene nueva línea Delim2.

Este constructo es sensible al contexto, por lo tanto, la gramática lexer de D''es sensible al contexto.

Han pasado algunos años desde que trabajé con la gramática de D''mucho, así que no puedo recordar todos los puntos problemáticos de la cabeza, o incluso si alguno de ellos hace que la gramática del analizador de D sea sensible al contexto, pero creo que sí no. Por recuerdo, yo diría que la gramática de D''es libre de contexto, no LL (k) para cualquier k, y tiene una cantidad desagradable de ambigüedad.

La propiedad de estar libre de contexto es un concepto muy formal; puedes encontrar una definición here . Tenga en cuenta que se aplica a las gramáticas : se dice que un lenguaje está libre de contexto si hay al menos una gramática libre de contexto que lo reconoce. Tenga en cuenta que puede haber otras gramáticas, posiblemente sin contexto, que reconocen el mismo idioma.

Básicamente, lo que significa es que la definición de un elemento de lenguaje no puede cambiar según los elementos que lo rodean. Por elementos de lenguaje me refiero a conceptos como expresiones e identificadores y no a instancias específicas de estos conceptos dentro de los programas, como a + b o count .

Probemos y construyamos un ejemplo concreto. Considere esta simple declaración COBOL:

01 my-field PICTURE 9.9 VALUE 9.9.

Aquí estoy definiendo un campo, es decir, una variable, que está dimensionada para contener un dígito integral, el punto decimal y un dígito decimal, con un valor inicial de 9.9. Una gramática muy incompleta para esto podría ser:

field-declaration ::= level-number identifier ''PICTURE'' expression ''VALUE'' expression ''.'' expression ::= digit+ ( ''.'' digit+ )

Desafortunadamente, las expresiones válidas que pueden seguir PICTURE no son las mismas expresiones válidas que pueden seguir a VALUE . Podría reescribir la segunda producción en mi gramática de la siguiente manera:

''PICTURE'' expression ::= digit+ ( ''.'' digit+ ) | ''A''+ | ''X''+ ''VALUE'' expression ::= digit+ ( ''.'' digit+ )

Esto haría que mi gramática fuera sensible al contexto, ya que la expression sería diferente según si se encontró después de ''PICTURE'' o después de ''VALUE'' . Sin embargo, como se ha señalado, esto no dice nada sobre el lenguaje subyacente. Una mejor alternativa sería:

field-declaration ::= level-number identifier ''PICTURE'' format ''VALUE'' expression ''.'' format ::= digit+ ( ''.'' digit+ ) | ''A''+ | ''X''+ expression ::= digit+ ( ''.'' digit+ )

que está libre de contexto.

Como puede ver, esto es muy diferente de su comprensión. Considerar:

a = b + c;

Es muy poco lo que se puede decir sobre esta afirmación sin consultar las declaraciones de a, byc, en ninguno de los idiomas para los que esta es una declaración válida, sin embargo, esto por sí solo no implica que ninguno de esos idiomas no sea contexto libre. Probablemente lo que te confunde es el hecho de que la libertad de contexto es diferente de la ambigüedad. Esta es una versión simplificada de tu ejemplo de C ++:

a < b > (c)

Esto es ambiguo ya que al observarlo solo no puede decir si se trata de una llamada a una plantilla de función o una expresión booleana. El ejemplo anterior, por otro lado, no es ambiguo; Desde el punto de vista de las gramáticas solo se puede interpretar como:

identifier assignment identifier binary-operator identifier semi-colon

En algunos casos, puede resolver ambigüedades introduciendo sensibilidad contextual en el nivel de la gramática. No creo que este sea el caso con el ejemplo ambiguo anterior: en este caso no se puede eliminar la ambigüedad sin saber si a es una plantilla o no. Tenga en cuenta que cuando dicha información no está disponible, por ejemplo, cuando depende de una especialización de plantilla específica, el lenguaje proporciona formas de resolver ambigüedades: es por eso que a veces tiene que usar typename para referirse a ciertos tipos dentro de las plantillas o para usar la template cuando llamar a plantillas de funciones de miembros.

Para responder a la pregunta de si un lenguaje de programación está libre de contexto, primero debe decidir dónde trazar la línea entre la sintaxis y la semántica. Como ejemplo extremo, es ilegal en C que un programa use el valor de algunos tipos de enteros después de que se ha permitido que se desborden. Claramente, esto no se puede verificar en tiempo de compilación, y mucho menos analizar el tiempo:

void Fn() { int i = INT_MAX; FnThatMightNotReturn(); // halting problem? i++; if(Test(i)) printf("Weeee!/n"); }

Como un ejemplo menos extremo que otros han señalado, las reglas de desaceleración antes de usar no se pueden aplicar en una sintaxis de contexto libre, por lo que si desea mantener su sintaxis sin contexto, debe postergarse para la siguiente pasada.

Como definición práctica, comenzaría con la pregunta: ¿Puede determinar correcta y inequívocamente el árbol de análisis sintáctico de todos los programas correctos utilizando una gramática libre de contexto y, para todos los programas incorrectos (que el lenguaje requiere ser rechazado), rechazarlos como sintácticamente inválido o produce un árbol de análisis sintáctico que los pases posteriores pueden identificar como no válido y rechazar?

Dado que la especificación más correcta para la sintaxis D es un analizador sintáctico (analizador IIRC y LL), creo firmemente que, de hecho, la definición que sugerí

Nota: lo anterior no dice nada sobre qué gramática utiliza la documentación del lenguaje o un analizador dado, solo si existe una gramática libre de contexto. Además, la única documentación completa sobre el lenguaje D es el código fuente del compilador DMD.

Ya hay muchas respuestas buenas, pero como no estás informado sobre gramáticas, analizadores sintácticos y compiladores, etc., déjame demostrar esto con un ejemplo.

Primero, el concepto de gramáticas es bastante intuitivo. Imagina un conjunto de reglas:

S -> a T T -> b G t T -> Y d b G -> a Y b Y -> c Y -> lambda (nothing)

E imagina que comienzas con S Las letras mayúsculas no son terminales y las letras minúsculas son terminales. Esto significa que si obtiene una oración de todas las terminales, puede decir que la gramática generó esa oración como una "palabra" en el idioma. Imagine tales sustituciones con la gramática anterior (la frase entre * frase * es la que se reemplaza):

*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t

Entonces, podría crear aabt con esta gramática.

Ok, de vuelta a la línea principal.

Supongamos un lenguaje simple. Tienes números, dos tipos (int y cadena) y variables. Puedes hacer multiplicaciones en enteros y suma en cadenas pero no al revés.

Lo primero que necesitas es un Lexer. Por lo general, es una gramática regular (o igual a ella, un DFA o una expresión regular) que coincide con los tokens del programa. Es común expresarlos en expresiones regulares. En nuestro ejemplo:

(Estoy creando estas sintaxis)

number: [1-9][0-9]* // One digit from 1 to 9, followed by any number // of digits from 0-9 variable: [a-zA-Z_][a-zA-Z_0-9]* // You get the idea. First a-z or A-Z or _ // then as many a-z or A-Z or _ or 0-9 // this is similar to C int: ''i'' ''n'' ''t'' string: ''s'' ''t'' ''r'' ''i'' ''n'' ''g'' equal: ''='' plus: ''+'' multiply: ''*'' whitespace: ('' '' or ''/n'' or ''/t'' or ''/r'')* // to ignore this type of token

Entonces, ahora tienes una gramática regular, tokenizando tu entrada, pero no comprende nada de la estructura.

Entonces necesitas un analizador. El analizador es generalmente una gramática libre de contexto. Una gramática libre de contexto significa que en la gramática solo tiene terminales individuales en el lado izquierdo de las reglas gramaticales. En el ejemplo al principio de esta respuesta, la regla

b G -> a Y b

hace que la gramática sea sensible al contexto porque a la izquierda tienes b G y no solo G ¿Qué significa esto?

Bueno, cuando escribes una gramática, cada uno de los no terminales tiene un significado. Escribamos una gramática libre de contexto para nuestro ejemplo (| means o. Como si estuviéramos escribiendo muchas reglas en la misma línea):

program -> statement program | lambda statement -> declaration | executable declaration -> int variable | string variable executable -> variable equal expression expression -> integer_type | string_type integer_type -> variable multiply variable | variable multiply number | number multiply variable | number multiply number string_type -> variable plus variable

Ahora esta gramática puede aceptar este código:

x = 1*y int x string y z = x+y

Gramáticamente, este código es correcto. Entonces, volvamos a lo que significa libre de contexto. Como puede ver en el ejemplo anterior, cuando expande el executable , genera una declaración de la variable = operand operator operand forma variable = operand operator operand sin ninguna consideración en qué parte del código se encuentra. Ya sea al principio o al medio, si las variables están definidas o no, o si los tipos coinciden, usted no sabe y no le importa.

Luego, necesitas semántica. Estas son las gramáticas sensibles al contexto que entran en juego. Primero, déjeme decirle que, en realidad, nadie escribe realmente una gramática sensible al contexto (porque analizarla es demasiado difícil), sino más bien bits de código que el analizador llama al analizar la entrada (llamados rutinas de acción. Aunque esto no es la única forma). Formalmente, sin embargo, puede definir todo lo que necesita. Por ejemplo, para asegurarse de definir una variable antes de usarla, en lugar de esto

executable -> variable equal expression

tienes que tener algo como:

declaration some_code executable -> declaration some_code variable equal expression

más complejo, para asegurarse de que la variable en la declaración coincida con la que se está calculando.

De todos modos, solo quería darte la idea. Entonces, todas estas cosas son sensibles al contexto:

Tipo de comprobación
Número de argumentos para funcionar
valor predeterminado para funcionar
si el member existe en obj en el código: obj.member
Casi cualquier cosa que no sea como: faltante ; o }

Espero que tengas una idea de cuáles son las diferencias (si no lo hiciste, estaría más que feliz de explicarlo).

Entonces en resumen:

Lexer usa una gramática regular para tokenizar la entrada
Parser usa una gramática libre de contexto para asegurarse de que el programa esté en la estructura correcta
El analizador semántico utiliza una gramática sensible al contexto para realizar la verificación de tipos, la coincidencia de parámetros, etc.

Sin embargo, no necesariamente siempre es así. Esto solo muestra cómo cada nivel necesita ser más poderoso para poder hacer más cosas. Sin embargo, cada uno de los niveles de compilador mencionados podría, de hecho, ser más poderoso.

Por ejemplo, un idioma que no recuerdo, usé la suscripción de matriz y la función invoque ambas con paréntesis y, por lo tanto, requirió que el analizador busque el tipo (elementos relacionados con el contexto) de la variable y determine qué regla (función_llamada o array_substitution) para tomar.

Si diseña un lenguaje con lexer que tiene expresiones regulares que se superponen, entonces también deberá buscar el contexto para determinar qué tipo de token está haciendo coincidir.

Para llegar a tu pregunta! Con el ejemplo que mencionaste, está claro que la gramática c ++ no está libre de contexto. El idioma D, no tengo ni idea, pero deberías poder razonar sobre eso ahora. Piénselo de esta manera: en una gramática libre de contexto, un no terminal puede expandirse sin tener en cuenta nada, PERO la estructura del lenguaje. Similar a lo que dijiste, se expande, sin "mirar" en ningún otro lado.

Un ejemplo familiar serían los lenguajes naturales. Por ejemplo, en inglés, dices:

sentence -> subject verb object clause clause -> .... | lambda

Bueno, la sentence y la clause son no terminales aquí. Con esta gramática puedes crear estas oraciones:

I go there because I want to

I jump you that I is air

Como puede ver, el segundo tiene la estructura correcta, pero no tiene sentido. Siempre que se trate de una gramática libre de contexto, el significado no importa. Simplemente expande el verb a cualquier verbo sin "mirar" el resto de la oración.

Entonces, si crees que D tiene que verificar en algún momento cómo se definió algo en otra parte, solo para decir que el programa es estructuralmente correcto, entonces su gramática no está libre de contexto. Si aísla cualquier parte del código y todavía puede decir que es estructuralmente correcto, entonces está libre de contexto.