A finais do ano 2022 comecei a traballar nun compilador de Pascal, principalmente para ver se eu ía ser quen de facelo.
A xente sempre me pregunta: “por que Pascal?”. A resposta é que eu quería facer un compilador: busquei unha linguaxe de estilo Algol antiga dabondo para que o compilador non fose excesivamente complicado pero tamén moderna dabondo para soportar cadeas de texto compostas por bytes, e Pascal resultou ser a mellor opción.
O caso é que, por unha cousa e outra, en maio do 2023 parei de traballar nel; non parei de pensar nel, porén, e hai unhas semanas volvín collelo para facerlle un novo analizador sintáctico. O analizador vello é bastante servizal, pero está deseñado para un compilador que produce código compilado mentres le o código fonte, e eu quero un que produza unha árbore de sintaxe abstracta (AST) para despois poder facer outras ferramentas que manipulen o código fonte.
Pero non vos quero falar de ASTs senón do que fixen coas listas ligadas.
Cada elemento dunha lista ligada apunta ao seguinte elemento, ata que o derradeiro queda no aire.
Como imaxinades, mentres fago unha análise sintáctica, moitas veces teño que gardar listas de cousas: listas de variables, listas de tipos, listas de nodos irmáns (para a árbore), etc. Nunha linguaxe moderna podemos poñer esas listas nun vector ou nun ArrayList ou nun array extensible, pero eu estou a facer o meu compilador nun dialecto de Pascal propio dos anos 80, con arrays estáticos e procedementos para reservar memoria na morea e máis nada.
A solución consiste en retrotraerme ás aulas de programación da universidade (hai xa máis anos dos que eu quero contar) e facer a miña propia implementación das listas ligadas usando estruturas e punteiros e todas esas cousas bonitas, pero coa vantaxe de ter máis experiencia, de ter máis picardía, e de ser o autor do meu propio compilador.
type TListaInteger = ^TListaIntegerNodo;
type TListaIntegerNodo = record
Valor : integer;
Seguinte : TListaInteger;
end;
procedure EngadirListaInteger(var Lista : TListaInteger; Elem : integer);
var Nodo, Ptr : TListaInteger;
begin
new(Nodo);
Nodo^.Valor := Elem;
Nodo^.Seguinte := nil;
if Lista = nil then Lista := Nodo
else
begin
Ptr := Lista;
while Ptr^.Seguinte <> nil do Ptr := Ptr^.Seguinte;
Ptr^.Seguinte := Nodo
end
end;
{ Máis subrutinas para consultar, borrar, etc. }
Esta de enriba é a definición “clásica” dunha lista ligada: unha estrutura de datos que contén un valor e un punteiro ao seguinte elemento da lista, acompañada por subrutinas para engadir e extraer elementos desta lista.
Ata aquí todo ben se non temos en conta os inconvenientes:
- é necesario facer unha implementación distinta da estrutura e das súas subrutinas por cada tipo de datos que queremos gardar nunha lista e
- engadir un elemento a esta lista é unha operación O(n) respecto do seu tamaño porque é necesario percorrer todos os punteiros “
Seguinte” para atopar o derradeiro elemento e despois engadirlle o novo.
O primeiro problema pódese aliviar usando a maxia dos punteiros, a organización das estruturas na memoria e unha cousa que lle copiei sen miramentos a Turbo Pascal 3: os parámetros sen tipo.
Listas ligando.
Pascal normalmente usa paso por valor (cando chamo a unha subrutina e lle paso parámetros, a subrutina recibe copias deles), pero tamén é posible marcar algúns parámetros para que usen paso por referencia usando a palabra “var” (coma no primeiro parámetro do procedemento “EngadirListaInteger”). No meu compilador tamén é posible omitir o tipo dun parámetro pasado por referencia e así pode recibir obxectos de calquera tipo.
type TLista = ^TListaNodo;
type TListaNodo = record
Seguinte : TLista;
end;
procedure EngadirLista(var Lista; var Nodo);
var
ALista : TLista absolute Lista;
ONodo : TLista absolute Nodo;
Ptr : TLista;
begin
ONodo^.Seguinte := nil;
if ALista = nil then ALista := ONodo
else
begin
Ptr := ALista;
while Ptr^.Seguinte <> nil do Ptr := Ptr^.Seguinte;
Ptr^.Seguinte := ONodo
end
end;
Esta é a miña “lista xenérica”: unha estrutura de datos que só contén un punteiro ao seguinte elemento e unha función “EngadirLista” que recibe dous parámetros sen tipo: o primeiro elemento da lista e o elemento que hai que engadir.
(Os parámetros chegan sen tipo, pero para usalos hai que asignarlles un. Iso é o que fan as liñas que din “absolute”: crean variables que apuntan á mesma memoria que os parámetros sen tipo e despois o procedemento usa esas variables.)
Con esta lista xenérica é doado dabondo crear unha lista de enteiros:
type TListaInteger= ^TListaIntegerNodo;
type TListaIntegerNodo = record
_ : TLista;
Valor : integer;
end;
procedure EngadirListaInteger(var Lista : TListaInteger; Elem : integer);
var Nodo : TListaInteger;
begin
new(Nodo);
Nodo^.Valor := Elem;
EngadirLista(Lista, Nodo)
end;
Isto funciona porque o enderezo na memoria do primeiro campo dun “record” é o enderezo do propio “record”; poñendo unha TLista como primeiro campo de TListaInteger, a función “EngadirLista” funciona correctamente ao lle pasar obxectos deste tipo.
Visto así non parece que aforremos moito traballo, pero imaxinade que hai dez tipos de lista e non un só: cada función “EngadirListaXxxx” só ten que crear un obxecto do tipo axeitado e chamar a “EngadirLista” e non ten que duplicar todo o código desa función.
Para o segundo problema (a operación de adición é O(n)) existen moitas solucións posibles. A máis simple consiste en gardar dous punteiros na lista: un que apunta ao seguinte elemento e outro que apunta ao derradeiro. O inconveniente disto, claro está, é que fai que a lista ocupe máis memoria.
Outra cousa que probei para evitar o problema foi converter as listas en rimas: facer que o punteiro non leve ao seguinte elemento senón ao anterior, e despois manter sempre o enderezo do derradeiro elemento. Isto funciona ben se a orde dos elementos non importa, pero non tanto no caso contrario.
A solución coa que eu dei foi converter a lista ligada nunha lista circular na que o punteiro “Seguinte” do derradeiro elemento apunta ao primeiro elemento.
Lista circular.
Facendo que a variable da lista apunte ao derradeiro elemento (non ao primeiro), podo engadir máis elementos inseríndoos xusto despois dese elemento e tamén podo percorrer a lista en orde de inserción parando ao chegar outra vez ao primeiro elemento.
procedure EngadirLista(var Lista; var Nodo);
var
ALista : TLista absolute Lista;
ONodo : TLista absolute Nodo;
begin
if ALista <> nil then
begin
ONodo^.Seguinte := ALista^.Seguinte;
ALista^.Seguinte := ONodo
end;
ALista := ONodo
end;
procedure IterarPrimeiro(var Lista; var Elem);
var
ALista : TLista absolute Lista;
OElem : TLista absolute Elem;
begin
if ALista = nil then OElem := nil
else OElem := ALista^.Seguinte
end;
procedure IterarSeguinte(var Lista; var Elem);
var
ALista : TLista absolute Lista;
OElem : TLista absolute Elem;
begin
if OElem = ALista then OElem := nil
else OElem := OElem^.Seguinte
end;
Cando dei con esta solución, fiquei sorprendido do simple que era e de que non oíra eu falar dela antes. Podía ser que eu inventara algo novo? Por suposto que non: Knuth xa escribira sobre iso, pero xa podedes estar seguros de que, se no futuro teño que implementar unha lista ligada outra vez, vai ser así.
1 comentario