Skip to content

Symbol Tables

12 March 2008

Abstract Syntax Trees sunt folosiţi pentru reprezentarea intermediară a codului despre care vorbeam în postul trecut. Menţionez că există şi alte modele de reprezentare intermediară şi că tipul de AST pe care îl prezint este cel folosit de mine dar în nici un caz bătut în cuie.

În primul rând, există tabelele de simboluri. Tabelele de simboluri conţin declaraţii de clase, metode, variabile etc. din codul sursă, toate acestea fiind considerate simboluri. O tabelă de simboluri este sociată fiecărui scope. Un scope este o porţiune de program care poate conţine astfel de declaraţii. În C# de exemplu, un namespace are un scope care conţine declaraţii de clase, structuri, interfeţe etc. Clasele au de asemenea un scope care conţine declaraţii de metode, câmpuri etc. Metodele au la rândul lor un scope unde sunt declaraţi parametrii şi variabilele locale. Scope este şi zona cuprinsă între “{” şi “}”, deoarece o variabilă declarată acolo nu mai poate fi referită după “}”. În momentul construirii AST-ului (în timpul parsingului), de fiecare dată când se identifică un scope, se crează o nouă tabelă de simboluri apoi toate declaraţiile din scope-ul respectiv sunt introduse în tabelă. Tabelele conţin şi o referinţă la tabela imediat superioară (tabela asociată unei metode de exemplu are o referinţă spre tabela asociată clasei).

Cum sunt folosite tabelele de simboluri? Pentru a rezolva o referinţă, de exemplu

int a = 2;
Console.WriteLine(a);

atât pentru apelul Console.WriteLine cât şi pentru variabila a este cerută referinţa de la tabela de simboluri asociată scope-ului (şi metodele şi variabilele sunt simboluri). În exemplul de mai sus, a este rezolvat imediat deoarece există în tabela de simboluri asociată blocului de cod. Ce se întamplă cu apelul, din momente ce Console.WriteLine nu este declarat aici? În caz că tabela nu poate rezolva referinţa, se foloseşte de referinţa spre tabela superioară, cerându-i acesteia să o rezolve. Cererea se propagă în sus până este rezolvată sau se ajunge la un nod care nu are referinţă spre un nod superior (cel mai “de sus”). Dacă nici ultimul nod nu conţine simbolul, înseamnă că referinţa este invalidă.

Desigur, nu toate tabelele de simboluri pot conţine toate tipurile de declaraţii, de exemplu tabela de simboluri asociată unui bloc de cod cuprins între “{” şi “}” nu poate conţine declaraţii de clase dar expune metodele pentru a rezolva o referinţă la o clasă şi trimite pur şi simplu cererea la tabelul superior.

Nodul care stă la bază (care nu mai are referinţă spre o altă tabelă superioară), expune aceleaşi metode de rezolvare a referinţelor dar nu conţine declaraţii. În schimb, acest nod caută simbolurile în assembly-urile externe referite de program. În exemplul de mai sus, Console.WriteLine se află în namespace-ul System din assembly-ul mscorlib.dll. Desigur, compilatorul trebuie să ştie ce assembly-uri externe sunt folosite.

Practic, avem o clasă abstractă care reprezintă o tabelă de simboluri cu metodele pentru a rezolva referinţe:

abstract class Scope
{
  public Scope parent; 
  public abstract Symbol Solve(Reference reference);
}

şi clase derivate din ea care implementează metodele de rezolvare şi conţin declaraţii.

class GlobalScope : Scope
{
  private Assembly[] referencedAssemblies;
 

  public GlobalScope(Assembly[] referencedAssemblies)
  {
    parent = null;
    this.referencedAssemblies = referencedAssemblies;
  }
 

  public override Symbol Solve(Reference reference)
  {
    // Căutare în referinţe
    ...
  }
}

class SomeScope : Scope
{
  private List<Symbol> symbols;
  

  public SomeScope(Scope parentScope)
  {
    parent = parentScope;
  }
 

  public void AddSymbol(Symbol symbol)
  {
    // Adăugare simbol
    ...
  }

  public override Symbol Solve(Reference reference)
  {
    // Căutare în symbols
    ...
    if (result != null)
      return result;
    else
      return parent.Solve(reference);
  }
}

Desigur, codul este schematic, dar cam aşa ar trebui să arate tabelele de simboluri care stau, de fapt, la “rădăcina” AST-ului.

Aşa se explică şi vizibilitatea variabilelor, pentru întrebările de la cursul de C gen

int a;

void test(int a)
{
  printf("%d", a);
}

Care a e referit? E referit primul a mergând de jos în sus şi căutând în tabelele de simboluri – aici e argumentul, deoarece acesta aparţine scope-ului asociat funcţiei pe când variabila globală aparţine scope-ului asociat fişierului.

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: