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 a
se 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 1
o '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?
fuente
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 resultadoa = 3.5
. El ascendente realizaría la división de enteros y convertiría solo en el último paso (asignación), entoncesa = 3.0
.int a = 1 + 2 - 3 * 4 - 5
, pero aint a = 5 - ((4*3) - (1+2))
int + int
convierteint
.Respuestas:
La recursión es la respuesta, pero desciende a cada subárbol antes de manejar la operación:
a la forma del árbol:
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:
-> descender a lhs
-> inferir
a
.a
se sabe que esint
. Estamos de vuelta en elassign
nodo ahora:-> descender a rhs, luego a las lhs de los operadores internos hasta que encontremos algo interesante
-> inferir el tipo de
1
, que esint
, y volver al padre-> ir a la derecha
-> inferir el tipo de
2
, que esint
, y volver al padre-> inferir el tipo de
add(int, int)
, que esint
, y volver al padre-> descender a la derecha
etc., hasta que termines con
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.
fuente
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:
a
se 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 tipoauto
.1
,2
o'c'
tienen un tipo inherente: un literal int siempre tiene tipoint
, un carácter literal siempre tiene tipochar
, ...+
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 entradaa: int
a la tabla.La tipificación de las hojas es el caso básico de la recursividad trivial: el tipo de literales como
1
ya se conoce, y el tipo de variables comoa
se 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 * 3
y1 + 2
se escribenint
porque4
&3
y1
&2
se han escrito previamenteint
y sus reglas de escritura dicen que la suma o producto de dosint
-s es anint
, 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 .
fuente
auto
no 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. Conauto
usted simplemente descubra el tipo del lado derecho y listo.auto
, C #var
y 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 ejemploint i = f(&i)
. Sii
se infiere el tipo de , el algoritmo anterior fallará: necesita saber el tipo dei
para inferir el tipo dei
. En cambio, necesitaría una inferencia de tipo de estilo HM completa con variables de tipo.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:
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 == 0
porque1/2
se evalúa como una expresión int.fuente
+
no se maneja como llamadas de función (ya que tiene un tipeo diferente paradouble
y paraint
operandos)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.f(a,b)
es bastante más fácil que averiguar el tipo dea+b
.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.
fuente
En realidad, es bastante fácil, siempre que piense
+
que es una variedad de funciones en lugar de un solo concepto.Durante la etapa de análisis del lado derecho, el analizador recupera
1
, sabe que es unint
, luego analiza+
y almacena eso como un "nombre de función no resuelto", luego analiza el2
, sabe que es unint
, y luego lo devuelve a la pila. El+
nodo de función ahora conoce ambos tipos de parámetros, por lo que puede resolver+
enint 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.
Aquí, el árbol es:
fuente
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:
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.
fuente