A semana pasada non vos quixen falar das árbores de sintaxe abstracta (AST), pero esta semana tampouco o vou facer. No seu lugar, vouvos falar do que ocorre antes da análise sintáctica.
Para poder facer a análise sintáctica dun programa, primeiro hai que extraer os símbolos e palabras clave do código fonte. É dicir: o código fonte é un ficheiro de texto composto de bytes e querémolo converter nunha secuencia de elementos “program”, “record”, “:=”, “[”, nomes de variables, números, etc.
Este proceso chámase “tokenization” en inglés e négome rotundamente a pseudo-traducilo como “tokenización”, “toquenización” ou ningunha barbaridade polo estilo, así que (por chamalo dalgunha maneira) heino chamar “peneirar”.
Pois ben: para poder peneirar todos eses elementos sintácticos, é preciso ter unha lista cos nomes de todos eles (como pode un programa recoñecer a palabra clave “array” se esta palabra non está gardada en ningún sitio?). Esta lista tamén é necesaria para poder presentar mensaxes de erro e todas esas cousas bonitas.
A maneira obvia de facer isto sería cun array (esta palabra non a traduzo) de cadeas de texto que conteña todos eses nomes.
const Keywords : array[KwArray..KwWith] of string =
('array', 'downto', 'else', 'for',
'if', 'then', 'to', 'while', 'with');
(Este é un exemplo abreviado; na realidade o array é máis longo.)
O malo é que isto non me serve, e o motivo é que, no meu compilador, unha cadea de texto ocupa 256 bytes (255 caracteres máis 1 byte para a lonxitude). Como o meu compilador ten 71 símbolos, o array ocuparía 18 kilobytes. Isto, no ano 2024, non é nada pero eu aprendín a programar nos 90 e tal desperdicio atenta contra a miña sensibilidade.
Para calmar sensibilidades dos anos 90 podemos usar trucos dos anos 80. Os microordenadores domésticos daquela época viñan todos cun intérprete de BASIC na súa ROM. Como a memoria ROM era moi cara, eses intérpretes tiñan que caber nun espazo pequeno (case sempre menos de 16 kB) e tamén precisaban dunha lista de palabras clave, así que os autores deses intérpretes poñíanas todas xuntas e usaban índices para acceder e buscar entre elas.
En Pascal, isto sería algo como isto:
const Keywords : string =
'arraydowntoelseforifthentowhilewith';
const KeywordPos : array[1..9] of 1..255 =
(1, 6, 12, 16, 19, 21, 25, 27, 32);
const KeywordLen : array[1..9] of 1..10 =
(5, 6, 4, 3, 2, 4, 2, 5, 4);
Dado isto, se queremos saber o nome da palabra número 3 só temos que ollar a súa posición (12) e lonxitude (4) e extraela da cadea para saber que é “else”.
Hai a posibilidade de aforrar máis espazo. Por exemplo, fixádevos en que a palabra “downto” contén “to”, así que non é necesario gardar esta segunda palabra separadamente: abonda con gardar a primeira e axustar os índices.
const Keywords : string =
'arraydowntoelseforifthenwhilewith';
const KeywordPos : array[1..9] of 1..255 =
(1, 6, 12, 16, 19, 21, 10, 25, 30);
const KeywordLen : array[1..9] of 1..10 =
(5, 6, 4, 3, 2, 4, 2, 5, 4);
A palabra número 7 comeza na posición 10 e ten lonxitude 2: ese é o noso “to”.
Aínda hai máis posibilidades de aforrar espazo. Por exemplo, “with” remata con “th”, que é o comezo de “then”, así que tamén os podemos combinar, igual que podemos combinar “while” con “else” e “if” con “for”.
const Keywords : string =
'arraydowntoiforwhilelsewithen';
const KeywordPos : array[1..9] of 1..255 =
(1, 6, 20, 13, 12, 26, 10, 16, 24);
const KeywordLen : array[1..9] of 1..10 =
(5, 6, 4, 3, 2, 4, 2, 5, 4);
E con isto pasamos de 36 bytes a 30: un aforro do 17%! Case nada!
Os lectores máis atentos xa se decatarían de que esta optimización, tal como a describín, non me aforraba ningún espazo porque, como dixen enriba, no meu compilador todas as cadeas de texto ocupan 256 bytes.
Na práctica, a cadea orixinal con todas as palabras claves do meu compilador ocupaba máis dese espazo, así que as optimizacións permitíronme facela caber.
E vós, cal foi a optimización máis innecesaria que fixestes?
1 comentario