Skip to content

Abstract Syntax Trees

23 March 2008

După ce am scris despre tabelele de simboluri, am să scriu şi despre restul arborelui şi tipurile de noduri care apar. În primă instanţă, nodurile se împart în două categorii: noduri declarative şi non-declarative. În momentul generării codului, pe baza nodurilor declarative se generează metadata iar pe baza nodurilor non-declarative se generează instrucţiuni IL.

Tabelele de simboluri conţin doar noduri declarative. Nodurile declarative sunt noduri care descriu, de exemplu, o clasă (nume, părinte, interfeţe implementate, vizibilitate etc.) sau o metodă (nume, parametri, tip întors, modificatori gen virtual, static etc.). Dacă pentru generarea codului se foloseşte Reflection.Emit, acestor noduri le corespund obiecte de tipul TypeBuilder, MethodBuilder şi aşa mai departe. Nodurile declarative pot conţine atât alte noduri declarative (un nod care descrie o clasă conţine noduri care descriu membrii clasei) cât şi noduri non-declarative (un nod care descrie o metodă conţine noduri care descriu instrucţiunile din corpul metodei). Tabelele de simboluri rezolvă referinţele căutând în nodurile declarative pe care le conţin.

Nodurile non-declarative reprezintă instrucţiunile din corpurile metodelor. Folosind Reflection.Emit, aceste noduri folosesc un ILGenerator pentru a emite instrucţiuni. Nodurile se împart la rândul lor în două categorii: noduri statement şi noduri expression. Nodurile statement nu întorc valori, cele expression întorc întotdeauna o valoare. De exemplu, dacă în codul pe care vrem să-l compilăm avem

x = 100 + 5;

partea din AST corespondentă expresiei 100 + 5 este formată din trei noduri de tip expresie. Un nod expresie este de tipul BinaryExpression (expresie cu 2 termeni), care descrie operaţia (adunare) şi conţine două noduri expresie, câte unul pentru fiecare operand. În cazul nostru, operanzii sunt de tip IntLiteral, adică o expresie constantă care întoarce o valoare de tip întreg. La nivelul expresiilor se face type-checking şi se construiesc conversiile implicite. De exemplu, pentru

x = 100 + 0.5;

Avem o constantă de tip int şi una de tip double. Atunci adăugăm în AST un nod, între nodul BinaryExpression şi nodul IntLiteral, care se ocupă de conversia din int în double. Apare întrebarea de ce să folosim trei noduri pentru o expresie atât de simplă? Păi expresia a fost doar un exemplu pe când tipurile de noduri rămân aceleaşi. Pentru expresia

100 + 5 + 10

avem nodul BinaryExpression care descrie prima adunare şi cei doi operanzi: IntLiteral (100) şi BinaryExpression (+) care conţine la rândul lui două noduri IntLiteral (5 şi 10). După cum vedem, astfel se pot reprezenta expresii oricât de complexe. Parserul se asigură că arborele va fi construit ţinând cont de prioritatea operatorilor (înmulţiri înainte de adunări, etc.). Exemplu de tip de expresii sunt: literale (constante literale), expresii unare (expresii care au doar un operand: negarea logică, minus unar), expresii binare (expresii cu doi operanzi: adunări, scăderi, comparaţii, şi logic, sau logic etc.), apeluri de metode (metodele care întorc void sunt excepţii, în rest toate metodele întorc o valoare deci sunt considerate expresii), indexeri aplicaţi matricilor şamd.

Pornind de la o clasă abstractă Expression, derivăm toate tipurile de noduri ce descriu expresii.

abstract class Expression
{
    public Type returnType;
    public abstract void Evaluate();
    public abstract void Emit(ILGenerator ilGen);
}

Avantajul acestei reprezentări este că fiecare expresie conţine noduri Expression, deci nu este nici o problemă dacă un parametru al unei metode este o constantă, o împărţire sau un apel la o altă metodă, cât timp moşteneşte clasa Expression. Arborele este parcurs de două ori: prima oară se face o evaluare, apelând recursiv metoda Evaluate (aici se verifică referinţele şi compatibilitatea tipurilor), apoi se emite codul, apelând recursiv metoda Emit. Parametrul ilGen este dat de nodul declarativ al metodei, folosind MethodBuilder.GetILGenerator(). Dacă avem de exemplu un tip de nod care descrie o adunare (simplific aici, de obicei acest tip de nod descrie toate operaţiile binare), AddExpression:

class AddExpression : Expression
{
    public Expression leftOperand;
    public Expression rightOperand;

    public override void Evaluate()
    {
        leftOperand.Evaluate();
        rightOperand.Evaluate();

        if (leftOperand.returnType != rightOperand.returnType)
            ...
    }

    public override void Emit(ILGenerator ilGen)
    {
        leftOperand.Emit(ilGen);
        rightOperand.Emit(ilGen);
        ilGen.Emit(OpCodes.Add);
    }
}

După cum se vede, operanzii pot fi orice fel de expresie, atât timp cât tipurile returnate sunt compatibile. După cum scriam şi într-un post mai vechi, .NET foloseşte o stivă pentru a evalua expresiile, şi astfel ne asigurăm că stiva este echilibrată. leftOperand.Emit lasă o valoare de tip leftOperand.returnType pe stivă. rightOperand.Emit lasă la rândul lui o valoare de tip rightOperand.returnType. Instrucţiunea add consumă cele două valori şi pune pe stivă rezultatul adunării. Astfel AST-ul poate fi construit incremental, adaugându-se diferite tipuri de noduri pentru diferite tipuri de expresii rând pe rând până când putem evalua orice expresie ce poate să apară în limbajul nostru.

Celălalt tip de noduri, statement, se deosebeşte de expresii prin faptul că nu întoarce o valoare. Statement sunt toate construcţiile limbajului diferite de expresii. De exemplu construcţia condiţională if-else este reprezentată ca

if (expression) statement else statement

Practic, nodul conţine un nod de tip expresie şi două noduri de tip statement. La fel şi construcţia while:

while (expression) statement

De fapt şi blocurile de cod sunt tot statements: un nod de tip statement care conţine o listă de noduri de tip statement. Avân ca părinte comun clasa abstractă Statement, avem din nou avantajul de a putea trata în acelaşi fel o construcţie de tip

if (expression)
{
    statement;
    statement;
    statement;
}

şi una de tip

if (expression) statement;

Practic, orice construcţie a unui limbaj poate fi considerată fie expresie, fie propoziţie. Există câteva excepţii, construcţii ce pot fi atât expresie, cât şi propoziţie. Un apel de funcţie, de exemplu

Console.ReadLine();

lasă pe stivă o valoare doar că, în unele cazuri, valoarea nu se consumă. Dat fiind tipul de nod CallExpression care apelează o funcţie şi îi întoarce valoarea, soluţia este construirea unui tip de nod CallStatement care conţine un nod CallExpression. În momentul generării codului, CallStatement apelează metoda de generare a codului ce corespunde nodului CallExpression şi mai adaugă instrucţiunea pop, pentru a goli stiva.

Un alt exemplu sunt atribuirle care, la unele limbaje pot fi considerate expresii. În Pascal avem

x := 10;

statement, care nu poate fi folosit ca expresie. În alte limbaje, precum C sau C#, avem, pe lângă

x = 10;

ca statement, expresii ca

if ((x = Console.ReadLine()) == "")

Aceste expresii se tratează în mod diferit deoarece .NET, la nivelul IL, nu se lasă nimic pe stivă după o atribuire. În acest caz, dat fiind tipul de nod AssignementStatement, construim nodul de tip AssignementExpression care adaugă instrucţiunea dup după evaluarea expresiei din dreapta semnului “=”. Dup duplică valoarea din vârful stivei astfel încât, după ce este consumată odată de atribuire, valoarea rămâne pe vârful stivei pentru următoarea expresie.

Cam aşa ar trebui să arate un AST. Evaluarea şi generarea codului se fac recursiv, pornind de la tabela de simboluri, evaluând şi generând nodurile declarative, apoi nodurile non-declarative.

Happy compiling!

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: