¿Cuál es el procedimiento común utilizado cuando los compiladores escriben estáticamente las expresiones "complejas" de verificación?

23

Nota: Cuando utilicé "complejo" en el título, quiero decir que la expresión tiene muchos operadores y operandos. No es que la expresión en sí misma sea compleja.


Recientemente he estado trabajando en un compilador simple para ensamblar x86-64. Terminé el front-end principal del compilador, el lexer y el analizador, y ahora puedo generar una representación de árbol de sintaxis abstracta de mi programa. Y dado que mi idioma se escribirá de forma estática, ahora estoy haciendo la siguiente fase: escribir comprobando el código fuente. Sin embargo, me he encontrado con un problema y no he podido resolverlo razonablemente.

Considere el siguiente ejemplo:

El analizador de mi compilador ha leído esta línea de código:

int a = 1 + 2 - 3 * 4 - 5

Y lo convirtió al siguiente AST:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Ahora debe escribir check the AST. comienza por el primer tipo que verifica el =operador. Primero verifica el lado izquierdo del operador. Ve que la variable ase declara como un entero. Por lo tanto, ahora debe verificar que la expresión del lado derecho se evalúe como un número entero.

Entiendo cómo se podría hacer esto si la expresión fuera solo un valor único, como 1o 'a'. Pero, ¿cómo se haría esto para expresiones con múltiples valores y operandos, una expresión compleja , como la anterior? Para determinar correctamente el valor de la expresión, parece que el verificador de tipo realmente tendría que ejecutar la expresión en sí misma y registrar el resultado. Pero esto obviamente parece anular el propósito de separar las fases de compilación y ejecución.

La única otra forma en que imagino que esto podría hacerse es verificar de forma recursiva la hoja de cada subexpresión en el AST y verificar que todos los tipos de la hoja coincidan con el tipo de operador esperado. Entonces, comenzando con el =operador, el verificador de tipos escanearía todo el AST del lado izquierdo y verificaría que todas las hojas sean enteras. Luego repetiría esto para cada operador en la subexpresión.

He intentado investigar el tema en mi copia de "El libro del dragón" , pero no parece entrar en muchos detalles, y simplemente reitera lo que ya sé.

¿Cuál es el método habitual que se utiliza cuando un compilador es tipo de comprobación de expresiones con muchos operadores y operandos? ¿Se utiliza alguno de los métodos que mencioné anteriormente? Si no, ¿cuáles son los métodos y cómo funcionarían exactamente?

Christian Dean
fuente
8
Hay una manera obvia y simple de verificar el tipo de una expresión. Será mejor que nos diga qué lo hace llamarlo "desagradable".
gnasher729
12
El método habitual es el "segundo método": el compilador infiere el tipo de expresión compleja de los tipos de sus subexpresiones. Ese fue el punto principal de la semántica denotacional, y la mayoría de los sistemas de tipos creados hasta el día de hoy.
Joker_vD
55
Los dos enfoques pueden producir un comportamiento diferente: el enfoque de arriba hacia abajo double a = 7/2 trataría de interpretar el lado derecho como doble, por lo tanto, trataría de interpretar el numerador y el denominador como doble y convertirlos si fuera necesario; como resultado a = 3.5. El ascendente realizaría la división de enteros y convertiría solo en el último paso (asignación), entonces a = 3.0.
Hagen von Eitzen
3
Tenga en cuenta que la imagen de su AST no se corresponde con su expresión int a = 1 + 2 - 3 * 4 - 5, pero aint a = 5 - ((4*3) - (1+2))
Basile Starynkevitch
22
Puede "ejecutar" la expresión en los tipos en lugar de los valores; por ejemplo se int + intconvierte int.

Respuestas:

14

La recursión es la respuesta, pero desciende a cada subárbol antes de manejar la operación:

int a = 1 + 2 - 3 * 4 - 5

a la forma del árbol:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Inferir el tipo ocurre primero caminando el lado izquierdo, luego el lado derecho, y luego manejando el operador tan pronto como se infieren los tipos de operandos:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descender a lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> inferir a. ase sabe que es int. Estamos de vuelta en el assignnodo ahora:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descender a rhs, luego a las lhs de los operadores internos hasta que encontremos algo interesante

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> inferir el tipo de 1, que es int, y volver al padre

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> ir a la derecha

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> inferir el tipo de 2, que es int, y volver al padre

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> inferir el tipo de add(int, int), que es int, y volver al padre

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> descender a la derecha

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

etc., hasta que termines con

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Si la asignación en sí misma es también una expresión con un tipo depende de su idioma.

La conclusión importante: para determinar el tipo de cualquier nodo de operador en el árbol, solo tiene que mirar a sus hijos inmediatos, que ya deben tener un tipo asignado.

Simon Richter
fuente
43

¿Cuál es el método generalmente utilizado cuando un compilador es la comprobación de tipos de expresiones con muchos operadores y operandos?

Lea wikipages en el sistema de tipos y la inferencia de tipos y en el sistema de tipos Hindley-Milner , que utiliza la unificación . Lea también sobre semántica denotacional y semántica operativa .

La verificación de tipos puede ser más simple si:

  • Todas sus variables como ase declaran explícitamente con un tipo. Esto es como C o Pascal o C ++ 98, pero no como C ++ 11 que tiene alguna inferencia de tipo auto.
  • todos los valores literales como 1, 2o 'c'tienen un tipo inherente: un literal int siempre tiene tipo int, un carácter literal siempre tiene tipo char, ...
  • las funciones y los operadores no están sobrecargados, por ejemplo, el +operador siempre tiene tipo (int, int) -> int. C tiene sobrecarga para operadores ( +funciona para tipos enteros con y sin signo y para dobles) pero no sobrecarga de funciones.

Bajo estas restricciones, un algoritmo de decoración de tipo AST recursivo ascendente podría ser suficiente (esto solo se preocupa por los tipos , no por los valores concretos, por lo que es un enfoque de tiempo de compilación):

  • Para cada ámbito, mantiene una tabla para los tipos de todas las variables visibles (denominado entorno). Después de una declaración int a, agregaría la entrada a: inta la tabla.

  • La tipificación de las hojas es el caso básico de la recursividad trivial: el tipo de literales como 1ya se conoce, y el tipo de variables como ase puede buscar en el entorno.

  • Para escribir una expresión con algún operador y operandos de acuerdo con los tipos previamente calculados de los operandos (subexpresiones anidadas), usamos recursividad en los operandos (por lo que escribimos primero estas subexpresiones) y seguimos las reglas de escritura relacionadas con el operador .

Entonces, en su ejemplo, 4 * 3y 1 + 2se escriben intporque 4& 3y 1& 2se han escrito previamente inty sus reglas de escritura dicen que la suma o producto de dos int-s es an int, y así sucesivamente para(4 * 3) - (1 + 2) .

Luego, lea el libro Tipos y lenguajes de programación de Pierce . Recomiendo aprender un poco de Ocaml y cálculo λ

Para lenguajes más dinámicamente escritos (como Lisp), lea también Lisin de Queinnec en piezas pequeñas

Lea también los lenguajes de programación de Scott Pragmática libro de

Por cierto, no puede tener un código de escritura agnóstico de idioma, porque el sistema de tipos es una parte esencial de la semántica del idioma .

Basile Starynkevitch
fuente
2
¿Cómo es que C ++ 11 autono es más simple? Sin él, tiene que averiguar el tipo en el lado derecho, luego ver si hay una coincidencia o conversión con el tipo en el lado izquierdo. Con autousted simplemente descubra el tipo del lado derecho y listo.
nwp
3
@nwp La idea general de las definiciones de variables de C ++ auto, C # vary Go :=es muy simple: ingrese el lado derecho de la definición. El tipo resultante es el tipo de la variable en el lado izquierdo. Pero el diablo está en los detalles. Por ejemplo, las definiciones de C ++ pueden ser autorreferenciales, por lo que puede hacer referencia a la variable que se declara en los rhs, por ejemplo int i = f(&i). Si ise infiere el tipo de , el algoritmo anterior fallará: necesita saber el tipo de ipara inferir el tipo de i. En cambio, necesitaría una inferencia de tipo de estilo HM completa con variables de tipo.
amon
13

En C (y, francamente, la mayoría de los lenguajes estáticamente tipados basados ​​en C) cada operador puede verse como un azúcar sintáctico para una llamada a función.

Entonces su expresión puede reescribirse como:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Luego, la resolución de sobrecarga se activará y decidirá que cada función es del tipo (int, int)o (const int&, const int&).

De esta forma, la resolución de tipo es fácil de entender y seguir y (lo que es más importante) fácil de implementar. La información sobre los tipos solo fluye de 1 manera (desde las expresiones internas hacia afuera).

Esa es la razón por la double x = 1/2;cual resultará x == 0porque 1/2se evalúa como una expresión int.

monstruo de trinquete
fuente
66
Casi cierto para C, donde +no se maneja como llamadas de función (ya que tiene un tipeo diferente para doubley para intoperandos)
Basile Starynkevitch
2
@BasileStarynkevitch: Está implementado como una serie de funciones sobrecargadas: operator+(int,int), operator+(double,double), operator+(char*,size_t), etc. El analizador sólo tiene que seguir la pista de los cuales uno se selecciona.
Mooing Duck
3
@aschepler Nadie estaba sugiriendo que en el nivel de fuente y especificación, C en realidad tiene funciones sobrecargadas o funciones de operador
cat
1
Por supuesto no. Simplemente señalando que en el caso de un analizador C, una "llamada de función" es algo más con lo que tendrá que lidiar, que en realidad no tiene mucho en común con los "operadores como llamadas de función" como se describe aquí. De hecho, en C averiguar el tipo de f(a,b)es bastante más fácil que averiguar el tipo de a+b.
aschepler
2
Cualquier compilador de C razonable tiene múltiples fases. Cerca del frente (después del preprocesador) encontrará el analizador, que genera un AST. Aquí está bastante claro que los operadores no son llamadas a funciones. Pero en la generación de código, ya no le importa qué construcción de lenguaje creó un nodo AST. Las propiedades del nodo en sí determinan cómo se trata el nodo. En particular, + puede muy bien ser una llamada de función; esto ocurre comúnmente en plataformas con matemática de punto flotante emulada. La decisión de usar matemática FP emulada ocurre en la generación de código; no se necesita diferencia previa de AST.
MSalters
6

Centrándose en su algoritmo, intente cambiarlo de abajo hacia arriba. Conoces las variables y constantes de tipo pf; etiquete el nodo que lleva al operador con el tipo de resultado. Deje que la hoja determine el tipo de operador, también lo contrario de su idea.

JDługosz
fuente
6

En realidad, es bastante fácil, siempre que piense +que es una variedad de funciones en lugar de un solo concepto.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

Durante la etapa de análisis del lado derecho, el analizador recupera 1, sabe que es un int, luego analiza +y almacena eso como un "nombre de función no resuelto", luego analiza el 2, sabe que es un int, y luego lo devuelve a la pila. El +nodo de función ahora conoce ambos tipos de parámetros, por lo que puede resolver +en int operator+(int, int), por lo que ahora conoce el tipo de esta subexpresión y el analizador continúa de manera alegre.

Como puede ver, una vez que el árbol está completamente construido, cada nodo, incluidas las llamadas a funciones, conoce sus tipos. Esto es clave porque permite funciones que devuelven diferentes tipos que sus parámetros.

char* ptr = itoa(3);

Aquí, el árbol es:

    char* itoa(int)
     /           \
  ptr(char*)      3
Pato mugido
fuente
4

La base para la verificación de tipos no es lo que hace el compilador, es lo que define el lenguaje.

En el lenguaje C, cada operando tiene un tipo. "abc" tiene el tipo "array of const char". 1 tiene el tipo "int". 1L tiene el tipo "largo". Si x e y son expresiones, entonces hay reglas para el tipo de x + y así sucesivamente. Entonces el compilador obviamente tiene que seguir las reglas del lenguaje.

En lenguajes modernos como Swift, las reglas son mucho más complicadas. Algunos casos son simples como en C. Otros casos, el compilador ve una expresión, se le ha dicho de antemano qué tipo debe tener la expresión y determina los tipos de subexpresiones basadas en eso. Si x e y son variables de diferentes tipos, y se asigna una expresión idéntica, esa expresión podría evaluarse de una manera diferente. Por ejemplo, asignar 12 * (2/3) asignará 8.0 a un Doble y 0 a un Int. Y tiene casos en los que el compilador sabe que dos tipos están relacionados y se da cuenta de qué tipos se basan en eso.

Ejemplo rápido:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

imprime "8.0, 0".

En la asignación x = 12 * (2/3): el lado izquierdo tiene un tipo conocido Double, por lo tanto, el lado derecho debe tener el tipo Double. Solo hay una sobrecarga para el operador "*" que devuelve Doble, y es Doble * Doble -> Doble. Por lo tanto, 12 debe tener el tipo Double, así como 2/3. 12 admite el protocolo "IntegerLiteralConvertible". Double tiene un inicializador que toma un argumento de tipo "IntegerLiteralConvertible", por lo que 12 se convierte en Double. 2/3 deben tener el tipo Doble. Solo hay una sobrecarga para el operador "/" que devuelve Double, y es Double / Double -> Double. 2 y 3 se convierten a Doble. El resultado de 2/3 es 0.6666666. El resultado de 12 * (2/3) es 8.0. 8.0 se asigna a x.

En la asignación y = 12 * (2/3), y en el lado izquierdo tiene el tipo Int, por lo que el lado derecho debe tener el tipo Int, por lo que 12, 2, 3 se convierten en Int con el resultado 2/3 = 0, 12 * (2/3) = 0.

gnasher729
fuente