miniSL parte 7 - Las cadenas internas

El intérprete que estamos desarrollando es un intérprete basado en entornos. Esto quiere decir que cuando encontremos una variable y queramos saber su valor, vamos a buscar el nombre de la variable en el entorno actual. El entorno será un diccionario (std::map) de forma que habrá que comparar las cadenas del nombre de la variable y las claves almacenadas en el diccionario.

Comparar cadenas es un algoritmo de complejidad O(n) lo que significa que va a ralentizar todo el proceso. Para solucionar esto la estrategia más común es usar lo que se llaman cadenas internas (interned string). De cada cadena interna sólo va a haber una única copia de forma que podamos usar su dirección para comparar cadenas. Así que la comparación de cadenas se reduce a una comparación de punteros.

Para convertir una cadena a su cadena interna bastará buscar la copia única o, si no existe aún, crearla.
STRING_MAP es el diccionario que a cada cadena le asigna una única copia. Esta copia será una celda del tipo NAME_CODE. De hecho, la única diferencia entre NAME_CODE y STRING_VAL es que en el primer caso la cadena es interna y en el segundo no (puede haber copias).

ENVIR_TABLE es ahora la tabla de símbolos que relaciona un NAME_CODE (el nombre de la variable) con un valor. Cada entorno tendrá un ENVIR_TABLE y un puntero opcional al entorno padre.


La clase Script, que contendrá todo el estado del intérprete del lenguaje que estamos creando, también tendrá que guardar el diccionario de cadenas internas. Lo haremos con la siguiente declaración de variable miembro privada.

STRING_MAP m_InternedStrings;

Los casos de uso serán buscar o crear una cadena interna y borrarla. El valor de la cadena es accesible mediante CELL::string_val.

La creación es algo más compleja que la destrucción ya que hemos de comprobar si ya está la cadena en nuestro diccionario.

CELL& Script::CreateName(STRING const& val)
{
 STRING_MAP::const_iterator i=m_InternedStrings.find(val);
 if(i==m_InternedStrings.end())
 {
  CELL& c=CreateCell(NAME_CODE);
  i=m_InternedStrings.insert(std::make_pair(val, &c)).first;
  c.string_val=&i->first;
 }
 return *i->second;
}

Aprovechamos que la implementación de std::map es un árbol (y no mueve los nodos por memoria una vez creados) para usar la propia cadena que hace de clave como la única copia de la cadena. Por esa razón hacemos c.string_val=&i->first. Esto no podría hacerse si la implementación fuera una tabla hash ya que estas tablas cambian de tamaño y requieren cambiar de posición de memoria las claves.

La destrucción, por otro lado, es sencilla.

m_InternedStrings.erase(*i->string_val);

Aunque hay que ver esta línea en el contexto del recolector de basura. Dedicaremos la siguiente entrada a implementar el recolector de basura.