El algoritmo de etiquetado es utilizado por el compilador durante la fase de generación de código. Básicamente, este algoritmo se utiliza para averiguar cuántos registros necesitará un programa para completar su ejecución. El algoritmo de etiquetado funciona de forma ascendente. Comenzaremos etiquetando primero los Nodes secundarios y luego los Nodes interiores. Las reglas del algoritmo de etiquetado son:
- Si ‘n’ es un Node hoja:
- una. Si ‘n’ es un hijo izquierdo entonces su valor es 1.
- b. Si ‘n’ es un hijo derecho entonces su valor es 0.
- Si ‘n’ es un Node interior:
supongamos que L1 y L2 son hijos izquierdo y derecho del Node interior, respectivamente.- una. Si L1 == L2 entonces el valor de ‘n’ es L1 + 1 o L2 + 1
- b. Si L1 != L2 entonces el valor de ‘n’ es MAX(L1, L2)
Ejemplo:
considere los siguientes tres códigos de dirección:
t1 = a + b t2 = c + d t3 = t1 + t2
El código de más de tres direcciones requerirá un máximo de 2 registros para completar su ejecución.
Hay una función llamada getregister() que el compilador usa para decidir dónde se almacenará el resultado. Hay 4 casos de esta función que son los siguientes:
- Si hay un registro R que no contiene valores múltiples, podemos usar este registro para almacenar el valor de nuestro resultado (en el ejemplo anterior, podemos almacenar t3 en R, siempre que el valor actual en R no se use en ninguna parte en el programa.).
- Si la primera condición no se cumple, el compilador buscará cualquier registro vacío para almacenar el valor de nuestro resultado (t3).
- Si no hay registros vacíos, intercambie el contenido de cualquier registro en la memoria y almacene el resultado (t3) en ese registro, siempre que ese contenido no tenga ningún uso posterior.
- Si las 3 condiciones no se cumplen, almacene el resultado en cualquier ubicación de memoria libre.
Publicación traducida automáticamente
Artículo escrito por natasha_mundada y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA