Синтаксна стабла

Увод и подсећање

Присетимо се да компилацију угрубо можемо да поделимо на следеће фазе¹:

лексичка анализа
синтаксичка анализа
семантичка анализа
генерисање кода
оптимизације

До сада смо се сусрели са прве две фазе – лексичком и синтаксичком анализом. Лексичка анализа проверава исправност најмањих јединица изворног кода програма, односно речи (које називамо лексеме), и додељује им категорије којима припадају (које називамо токени). Дакле, улаз лексичке анализе је иворни код програма, а излаз табела симбола (мапирање лексема у токене уз потенцијално неке додатне информације, попут линије на којој се лексема налази и слично). На пример, за изворни код int x = 3;, табела симбола може да изгледа овако

лексема	токен
`int`	`KLJUCNA_REC`
`x`	`IDENTIFIKATOR`
`=`	`SIMBOL_JEDNAKO`
`3`	`KONSTANTA`
`;`	`SEPARATOR`

То препознавање се врши коришћењем коначних аутомата, који користе математички формализам регуларних језика. Видели смо до сада да регуларне језике можемо да опишемо регуларним изразима, а коначне аутомате на основу регуларних израза можемо да генеришемо алатима као што су Lex/Flex.

Са друге стране, синтаксичка анализа узима већ лексички исправан изворни код (који можемо да посматрамо да се сада састоји од токена, а не лексема) и проверава његову синтаксичку исправност (на пример, код int = x 3; је лексички потпуно исправан, али није синтаксички иправан). То се остварује помоћу потисних аутомата, а математички формализам су контексно слободни језици (КСЈ). КСЈ описујемо контексно слободним граматикама (КСГ), а генерисање потисног аутомата смо радили помоћу алата Yacc/GNU Bison.

Претходно можемо да сумирамо наредном табелом:

	лексичка анализа	синтаксичка анализа
формализам	регуларни језици	КСЈ
механизам	коначни аутомати	потисни аутомати
oписивање	регуларни изрази	КСГ
алати	Lex/Flex	Yacc/GNU Bison
улаз	изворни код	токенизовани изворни код
излаз	табела симбола	*синтаксно стабло*

Улаз за целокупну процедуру превођења је изворни фајл, а излаз ивршиви програм. На овом курсу је идеја да обрадимо само прве две фазе и, да бисмо то урадили, остало је да пређемо детаљније излаз друге фазе превођења, односно, синтаксна стабла.

Дефиниција и структура

Синтаксно стабло, или апстрактно синтаксно стабло (енг. Abstract Syntax Tree, скраћено AST), је дрволика структура података којом се представља структура изворног кода програма. Узимимо за пример следећи код:

int x = log(y) + 2 * z;

Његово синтаксно стабло може да изгледа на следећи начин:

ast_example_01

Идеја је да се помоћу њега у потпуности опише синтакса. У овом примеру имамо само операцију доделе и она је представљена кореним чвором у стаблу. Операција доделе има леву (оно чему додељујемо) и десну (оно шта додељујемо) страну. Они су приказани левим и десним дететом тог чвора.

Оно што је важно је да приметимо да сваки чвор синтаксног стабла има свој тип, и у зависности од њега чува одговарајуће вредности. На пример, чвор доделе има тип Dodela и чува податке на лево и на десно дете. Са друге стране, чвор Log има само једно дете. Чворови Konstanta и Promenljiva немају даље потомке, али чувају један цео број, односно једну ниску, и то је оно што им је важно од података.

Покушајмо да се уверимо да заиста на овај начин можемо да опишемо целокупну синтаксу једног језика. На пример, ако имамо петљу:

while (x < 5) {
    x++;
}

Можемо је претворити у стабло на следећи начин:

ast_example_02

Петља whileима свој услов, који је представљен левим чвором, и има своје тело, које је десни чвор. Слично се може обрадити и случај if наредбе као и for петље (која би имала још један чвор који би био иницијализација).

Међутим, шта се дешава уколико имамо више наредби?

int i = 0;
i++;
while (i < 10) {
    printf("%d\n", i);
    i++;
}

То решавамо тако што додајемо нови тип чвора NizNaredbi који може имати произвољан број деце од којих је свако представља чвор неке наредбе. Редослед наредби је важан и на слици ће прва наредба бити прва слева, а последња, прва здесна.

ast_niz_naredbi

Онда синтаксно стабло за претходни пример може да изгледа овако.

ast_example_03

Сличним поступком можемо да обрадимо и остале случајеве синтаксе који су нам до сада познати и можемо да наслутимо да заиста можемо да опишемо један програм на овај начин. Дакле, синтаксно стабло је једна структура података (попут бинарног стабла у C-у) која нам служи за чување програма.

Мађутим, остаје питање, чему ово?

Мотивација

Главни разлог увођења овакве структуре је да омогућимо интерну репрезентацију програма у рачунару која је погодна за обраду. Истина, изворни код као једна структуирана ниска представља репрезентацију програма, али знатно је компликованија за рад.

Замислимо да желимо да пронађемо у програму све инструкције у којима додељујемо неку константу. Ако бисмо имали само изворни код на раполагању, било би неопходно да на неки начин претражимо текстуални фајл и из њега извучемо све инструкције доделе, и то само оне у којима додељујемо константе. То би захтевало да се суштински поново уради нека врста лексичке и синтаксичке анализе, и да тек онда тражимо одговарајуће инструкције.

Са друге стране, ако имамо AST на располагању, онда већ имамо сачуване све резултате лексичке и синтаксичке анализе. Дакле, знамо да нам је изворни код исправан и имамо релевантне информације о њему. Претрага доделе константе би се сада свела на претрагу графа (синтаксног стабла) и испитивања типа чворова.

Слична ситуација настаје и ако желимо да модификујемо програм. Рецимо да желимо да у инстукцијама доделе константе променимо вредност константе да буде увек 0. Помоћу синтаксног стабла то се своди на обилазак графа и промену одговарајућих вредности чворова. Овако можемо и да додајемо нове инструкције, додавањем нових чворова у стабло.

Укратно, синтаксна стабла омогућавају:

претрагу и модификацију програма (погодну за нпр. статичку анализу)
семантичку анализу (јер можемо да закључујемо о контексту тј. у ком смо делу програма)
интерпретацију и превођење програма (проласком кроз AST можемо да ивршавамо чворове стабла или да их преводимо)

У наставку ћемо детаљније обрадити последњу ставку одакле ће се видети јасније предности синтаксног стабла.

C++ имплементација

Овде се подразумева познавање основних елемената C++-a. У њих спадају: рад са динамички алоцираном меморијом, оператори и њихово предефинисање, као и класе и наслеђивање.

Већ смо поменули да сваки чвор синтаксног стабла има свој тип и одговарајуће податке које чува. Ово асоцира да сваки тип чвора може да се представи једном класом са одговарајућим пољима. Како је C++, између осталог, објектно-оријентисан језик, то ћемо искористити те погодности за представљање синтаксног стабла.

Зато ћемо да направимо класе Dodela, Sabiranje, Mnozenje, NizNaredbi, Log и сличне, чије ће инстанце бити чворови стабла.

С обзиром да желимо да направимо дрволику структуру у C++-у, чворови треба да чувају показиваче на своју децу. Овде, међутим, имамо различите типове чворова и немају сви исти број деце (неки их уопште и немају). Из тог разлога правимо једну апстрактну класу ASTCvor коју ће сви остали чворови стабла наслеђивати и сви показивачи на потомке ће показивати на тај тип (тј. биће типа ASTCvor *).

На пример, класе са два детета, пупут класе Sabiranje, ће изгледати овако

class Sabiranje : public ASTCvor {
public:
    // implementacije odgovarajucih metoda
private:
    ASTCvor *m_levi_izraz;
    ASTCvor *m_desni_izraz;
};

Док ће класе са једним дететом, као што је то класа Log, изгледати овако

class Log : public ASTCvor {
public:
    // implementacije odgovarajucih metoda
private:
    ASTCvor *m_izraz;
};

Битна предност оваквог приступа је што сада можемо да обезбедимо полиморфно понашање. Наиме, сваки од чворова треба да имплементира неке основне методе. На пример, нама ће бити важан метод interpretiraj којим ће се интерпретирати (извршити) чвор. Сваки од чворова треба да може да позове тај метод, али ће се његова имплементација разликовати у зависности од типа. Тако да је полиморфизам једно лепо решење за организацију позадинске логике. Поред њега, може бити битан и метод ispisi или метод prevedi ако желимо да генеришемо код (асемблер) за наш програм.

Имена класа и метода су нешто другачија у односу на званичне кодове са сајта. Некада је и имплементација другачија, али је основна идеја иста.

Пример синтаксног стабла

Хајде да конструишемо синтаксно стабло за један замишљен програмски језик и да на том примеру покријемо основе које ће у свим осталим примерима бити исте или сличне (наравно, биће неопходне одређене модификације зарад прилагођавања конкретном задатку).

Нека имамо програмски језик који:

ради са реалним бројевима
омогућава дефинисање променљивих са иницијализацијом (наредбе типа def x = 2.3)
омогућава доделу вредности променљивих (наредбе типа x = x * y + 2)
омогућава исписивање вредности израза (наредбе типа print(4.3 * ( - y + 2)))
омогућава поређење реалних израза на једнакост (наредбе типа x == 2 * y + 1.5 које на стандарни излаз исписују True, односно False)

Желимо да направимо синтаксно стабло за овај језик над којим ћемо моћи да извршимо две операције:

исписивање стабла, односно, одговарајући испис сваког његовог чвора (нека врста враћања у изворни код)
интерпретација стабла (односно, његово извршавање)

На пример, за изворни програм:

def x = 2.5;
x = x * x + 2;

print(- x);

16.5 == 2 * x;

Његово синтаксно стабло може да изгледа овако

kalkulator_ast_example

Овде чворови за дефинисање и доделу немају лево дете јер све наредбе тог типа у овом примеру прихватају само идентификаторе на левој страни. Зато уместо показивача на лево дете имамо једну ниску као податак у чвору.

Препорука: Ово је моменат где можете да покушате сами да имплементирате синтаксно стабло. Дакле, треба да се формира дрволика структура у C++ тако што се направе класе за све наведене типове уз одговарајућу класну хијерархију.

То значи да ће нам бити потребне класе:

NizNaredbi
Definicija
Dodela
Ispis
Poredjenje
Negacija
Sabiranje
Mnozenje
Promenljiva
Konstanta

Као што је већ речено, имаћемо и апстрактну класу ASTCvor коју ће све остале наслеђивати.

ast_ostale_klase

Такође, ради смањења дуплирања кода и лакше организације, можемо да направимо и помоћне класе као што је BinarniCvor која би груписала заједничке методе класа са два детета као што су Sabiranje, Mnozenje и Poredjenje.

Слично, можемо да додамо и класу UnarniCvor коју би наслеђивала класе са једним дететом. Ту спадају класе Negacija и Ispis (обе имају по једно дете тј. чуваће само једну променљиву типа ASTCvor *, а разликоваће се у интерпетацији).

ast_klase_operatori

Хијерархија попут ове ће бити присутна у свим нашим примерима, зато прођимо редом кроз све класе које се у њој појављују.

Да бисмо могли да једноставно користимо синтаксно стабло као једну структуру података касније, његову имлементацију одвојамо у посебне фајлове. Зато ће се све декларације налазити у sintaksno_stablo.hpp фајлу, а дефиниције у sintaksno_stablo.cpp фајлу. За сваки исечак кода ће бити наглашено ком фајлу припада.

Класа `ASTCvor`

Сви наредни кодови могу да се нађу на GitHub репозиторијуму ради лакшег праћења.

Ово је апстрактна класа коју све остале наслеђују. Треба да декларише методе које сви чворови имплементирају, и то ће зависити од задатка. У нашем случају, и то ће скоро увек бити тако, потребно је следеће:

виртуелни деструктор – јер ће подкласе да чувају показиваче на меморију која треба да се ослободи када се заврши са радом
метода interpretiraj – за ивршавање програма кроз синтаксно стабло
метода ispisi– за исписивање стабла
метода за клонирање чвора (она ће нам бити неопходна за нпр. конструктор копије)

То изгледа овако:

sintaksno_stablo.hpp

class ASTCvor {
public:
    virtual ~ASTCvor();
    virtual void ispisi(std::ostream &os) const = 0;
    virtual double interpretiraj(TabelaSimbola &tabela_simbola) const = 0;
    virtual ASTCvor *kloniraj() const = 0;
};

На GitHub репозиторијуму је, поред ових, декларисана и метода prevedi. Она ће бити игнорисана за сада, а детаљније о њој може се наћи у додатку.

Неколико коментара око саме декларације.

За почетак, метода ispisi као аргуманет узима референцу на објекат типа std::ostream. Ово радимо да бисмо могли да преоптеретимо оператор << и исписујемо чвор једноставније (помоћу std::cout << *cvor << std::endl;). Због тога у фајлу за заглавље додајемо још и наредну декларацију.

sintaksno_stablo.hpp

std::ostream &operator<<(std::ostream &os, const ASTCvor &ast_cvor);

Друго, у методи interpretiraj је интересантан и тип аргумента и тип повратне вредности.

Погледајмо прво аргумент. Запитајмо се како интерпретирати наредбу print(x)? Да бисмо то урадили неопходно је да, или знамо вредност променљиве x, или да знамо да та променљива уопште није ни дефинисана где бисмо избацили грешку. У сваком случају, неопходно је да имамо неке додатне информације о променљивама. Томе управо служи класа TabelaSimbola која само енкапсулира једну мапу која слика ниске у реалне бројеве, тј. чува вредности дефинисаних променљивих. Та класа ће се увек јављати због чега нам је важна, и њу ћемо прећи следећу. Приметимо још да не шаљемо референцу на константан објекат јер ће се табела симбола мењати током интерпретације.

Да бисмо разумели тип повратне вредности, запитајмо се како да интерпретирамо чвор Sabiranje тј. шта инструкција 1 + 2 треба да уради? Ово се може решити на више начина, али онај кога ћемо се ми држати ће бити да сваки чвор као резултат интерпретације враћа реалан број. То има смисла за инструкције које заиста то и раде (попут инструкција за сабирање и множење), али нема пуно смисла за нпр. инструкцију поређења на једнакост или за низ наредби. Свакако, ми ћемо у свим осталим примерима да бирамо да тип повратне вредности ове функције увек буде тип израза са којима радимо у програму. Овде ће то бити double, негде ће то бити int, али негде и типови које ћемо сами дефинисати, нпр. комплексан број.

Што се тиче фајла за дефинисања метода, ту имамо само наредно.

sintaksno_stablo.cpp

ASTCvor::~ASTCvor() {}

std::ostream &operator<<(std::ostream &os, const ASTCvor &ast_cvor) {
    ast_cvor.ispisi(os);
    return os;
}

Овде је важно да дефинишемо деструктор за наткласу (чак и ако је он празан тј. подразумеван), јер се приликом позива деструктора изведене класе и он позива. Без дефиниције, добијамо грешку приликом линковања.

Класа `TabelaSimbola`

Ова класа ће бити помоћна и служиће само за чување дефинисаних променљивих. У основи има једно поље, мапу која чува вредности променљивих. Такође је развајамо у посебне фајлове, tabela_simbola.hpp и tabela_simbola.cpp.

tabela_simbola.hpp

class TabelaSimbola {
public:
    void definisi_promenljivu(std::string &promenljiva, double vrednost);
    void dodeli_vrednost(std::string &promenljiva, double vrednost);
    double vrednost_promenljive(std::strint &promenljiva) const;

private:
    std::map<std::string, double> m_tabela;
};

Битно је приметити овде да мапа слика у double. У општем случају, то ће бити тип израза са којима радимо у програму (исти онај тип повратне вредности за interpretiraj). То може бити и неки наш дефинисан тип, као што је KompleksanBroj, али тада не бисмо чували директно објекте наше класе, већ показиваче на њих, нпр. KompleksanBroj *. Из тог разлога (јер чувамо показиваче на меморију алоцирану на хипу) је тада потребно да класи TabelaSimbola дефинишемо и одговарајући деструктор!

Имплементација се своди на позиве одговарајућих метода из мапе.

tabela_simbola.cpp

void TabelaSimbola::definisi_promenljivu(std::string &promenljiva, double vrednost) {
    // provera da li je promenljiva vec definisana i izbacivanje greske ukoliko jeste
    if (m_tabela.find(promenljiva) != m_tabela.end()) {
        std::cerr << "promenljiva " << promenljiva << " je vec definisana" << std::endl;
        exit(EXIT_FAILURE);
    }
    m_tabela[promenljiva] = vrednost;
}

void TabelaSimbola::dodeli_vrednost(std::string &promenljiva, double vrednost) {
    // provera da li je promenljiva vec definisana i izbacivanje greske ukoliko nije
    if (m_tabela.find(promenljiva) == m_tabela.end()) {
        std::cerr << "promenljiva " << promenljiva << " nije prethodno definisana" << std::endl;
        exit(EXIT_FAILURE);
    }
    m_tabela[promenljiva] = vrednost;
}

double TabelaSimbola::vrednost_promenljive(const std::string &promenljiva) const {
    auto it = m_tabela.find(promenljiva);
    if (it == m_tabela.end()) {
        std::cerr << "promenljiva " << promenljiva << " nije prethodno definisana" << std::endl;
        exit(EXIT_FAILURE);
    }
    return it->second;
}

Приметимо да у дефиницији методе vrednost_promenljive за враћање вредности нисмо користили

return m_tabela[promenljiva];

Разлог за то је што не можемо да користимо оператор [] над константним објектом m_tabela. Наиме, m_tabela је константан зато што смо декларисали методу vrednost_promenjlive као константну, а оператор [] може да додаје нови елементу у мапу када му се проследи кључ који се не налази у мапи, па у општем случају може да промени објекат над којим се позива.

У неким примерима неће бити неопходно да се раздвајају дефиниције и доделе променљивама, па тада није неопходно ни имати ове две засебне методе, већ само једну. Са друге стране, некада је пожељно да имплементирати и додатне методе (попут испитивања да ли је нека променљива дефинисана).

Класа `NizNaredbi`

Ово је класа која чува наредбе у редоследу у ком су и задате у изворном фајлу. По правилу, биће корени чвор синтаксног стабла јер ће сваки наш програм бити један низ наредби (али се може јавити и на другим местима, нпр. у телу петље).

Све наредбе су нам типа ASTCvor, желимо да очувамо њихов редослед, али нам њихов број није познат унапред. Зато ћемо у овој класи да направимо једно приватно поље које је динамички низ наредби, односно, које је типа std::vector<ASTCvor *>. Следи декларација класе.

sintaksno_stablo.hpp

class NizNaredbi : public ASTCvor {
public:
    NizNaredbi();
    NizNaredbi(const NizNaredbi &drugi);
    ~NizNaredbi();

    void dodaj_cvor(ASTCvor *cvor);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;

private:
    std::vector<ASTCvor *> m_naredbe;
};

Чим приметимо да чувамо показиваче, треба да размислимо о ослобађању меморије. Заиста, ми ћемо овде имати низ показивача на динамички алоциране објекте и зато је неопходно да сами имплементирамо деструктор. Отуда нам се у класи јавља декларација ~NizNaredbi() коју може да прати следећа имплементација.

sintaksno_stablo.cpp

NizNaredbi::~NizNaredbi() {
    for (ASTCvor *cvor : m_naredbe) {
        delete cvor;
    }
}

Како смо направили наш деструктор, сетимо се правила тројке², тј. ако нам је потребно да предефинишемо бар једно од подразумеваних

деструктора
конструктора копије
оператора доделе

потребно је да предефинишемо и сва три.

Зато се у класи налази декларација конструктора копије NizNaredbi(const NizNaredbi &drugi). Међутим, овде изостављамо предефинисање оператора доделе. Разлог за то је што га нећемо нигде користити, па га нећемо ни имплементирати. Наравно, то и даље значи да је он потребан ако бисмо желели да додељујемо вредности објектима овог типа, али то неће бити случај код нас. Имплементација конструктора копије је описана у наставку.

sintaksno_stablo.cpp

NizNaredbi::NizNaredbi(const NizNaredbi &drugi) {
    m_naredbe.resize(drugi.m_naredbe.size());
    for (size_t i = 0; i < drugi.m_naredbe.size(); i++) {
        m_naredbe[i] = drugi.m_naredbe[i]->kloniraj();
    }
}

Дакле, прво обезбедимо довољно простора у нашем вектору, а затим пролазимо кроз други вектор и копирамо елементе појединачно. Овде видимо зашто нам је важна метода kloniraj. Наиме, овде желимо да копирамо објекте чије типове не знамо у фази компилације (сви су они апстрактног типа ASTCvor, али не знамо њихов крајњи тип). Као решења овде правимо методу kloniraj и ослањамо се на њено полиморфно понашање.

Имамо још и методу за додавање нове инструкције.

sintaksno_stablo.cpp

void NizNaredbi::dodaj_cvor(ASTCvor *cvor) {
    m_naredbe.push_back(cvor);
}

И на крају имплементирамо све методе апстрактне класе ASTCvor. Све се своде на пролазак кроз низ инструкција и позива одговарајућих метода над појединачним инструкцијама.

sintaksno_stablo.cpp

void NizNaredbi::ispisi(std::ostream& os) const {
    for (ASTCvor *cvor : m_naredbe) {
        os << *cvor << ";\n";
    }
}

double NizNaredbi::interpretiraj(TabelaSimbola &tabela_simbola) const {
    for (ASTCvor *cvor : m_naredbe) {
        cvor->interpretiraj(tabela_simbola);
    }

    // vracamo neku vrednost samo da bismo
    // se uskladili sa definicijom metoda
    return 0;
}

ASTCvor *NizNaredbi::kloniraj() const {
    return new NizNaredbi(*this);
}

Приметимо да метода kloniraj враћа ASTCvor *, док у њеној имплементацији враћамо тип NizNaredbi. Ово је врло важно и у свим класама имплементација ће бити иста уз једину разлику у типу након кључне речи new.

Такође, приметимо да се овде ослањамо на конструктор копије и да је, између осталог, ово један од ралога зашто нам је он потребан.

Класе `Definicija` и `Dodela`

Ове две класе су јако сличне и имају идентичне декларације (до на разлику имена). Обе служе за рад са променљивама, и често их у примерима неће ни бити потребе да их разликујемо (то одговара програмским језицима без декларација променљивих). Овде су одвојене ради комплетности, јер им је семантика ипак мало другачија.

Дакле, обе треба да чувају један идентификатор (леву страну једнакости) и израз (десну страну једнакости). То ће бити једна ниска и позивач на ASTCvor јер не знамо шта може бити тај израз, па узимамо показивач на наткласу.

Чим имамо показиваче на динамички алоциране типове, биће нам потребно да предефинишемо деструктор, а самим тим и конструктор копије и оператор доделе. Поново нам оператор доделе неће бити важан, па имплементирамо само прва два.

Остале методе класе су оне наслеђене из класе ASTCvor које треба имплементирати.

Дакле, декларација класе Definicija:

sintaksno_stablo.hpp

class Definicija : public ASTCvor {
public:
    Definicija(const std::string &id, ASTCvor *izraz);
    Definicija(const Definicija &drugi);
    ~Definicija();

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;

private:
    std::string m_id;
    ASTCvor *m_izraz;
};

И њена имплементација:

sintaksno_stablo.cpp

Definicija::Definicija(const std::string &id, ASTCvor *izraz)
    : m_id(id), m_izraz(izraz) {}

Definicija::Definicija(const Definicija &drugi) {
    m_id = drugi.m_id;
    m_izraz = drugi.m_izraz->kloniraj();
}

Definicija::~Definicija() {
    delete m_izraz;
}

void Definicija::ispisi(std::ostream& os) const {
    os << "def " << m_id << " = " << *m_izraz;
}

double Definicija::interpretiraj(TabelaSimbola &tabela_simbola) const {
    double vrednost = m_izraz->interpretiraj(tabela_simbola);
    tabela_simbola.definisi_promenljivu(m_id, vrednost);

    // vracamo neku vrednost samo da bismo
    // se uskladili sa definicijom metoda
    return vrednost;
}

ASTCvor *Definicija::kloniraj() const {
    return new Definicija(*this);
}

Овде имамо прилику да видимо зашто нам је потребна класа TabelaSimbola. Њу користимо да бисмо сачували променљиве које се дефинишу током рада програма.

Такође, видимо и разлог зашто смо се одлучили да метод interpretiraj враћа double. Њеним позивом над чвором који представља израз једноставно добијамо вредност тог израза, што видимо у имплементацијци функције interpretiraj.

Аналогно њој, имамо и класу Dodela.

sintaksno_stablo.hpp

class Dodela : public ASTCvor {
public:
    Dodela(const std::string &id, ASTCvor *izraz);
    Dodela(const Dodela &drugi);
    ~Dodela();

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;

private:
    std::string m_id;
    ASTCvor *m_izraz;
};

sintaksno_stablo.cpp

Dodela::Dodela(const std::string &id, ASTCvor *izraz)
    : m_id(id), m_izraz(izraz) {}

Dodela::Dodela(const Dodela &drugi) {
    m_id = drugi.m_id;
    m_izraz = drugi.m_izraz->kloniraj();
}

Dodela::~Dodela() {
    delete m_izraz;
}

void Dodela::ispisi(std::ostream& os) const {
    os << m_id << " = " << *m_izraz;
}

double Dodela::interpretiraj(TabelaSimbola &tabela_simbola) const {
    double vrednost = m_izraz->interpretiraj(tabela_simbola);
    tabela_simbola.dodeli_vrednost(m_id, vrednost);
    
    // vracamo neku vrednost samo da bismo
    // se uskladili sa definicijom metoda
    return vrednost;
}

ASTCvor *Dodela::kloniraj() const {
    return new Dodela(*this);
}

Дакле, разлика је само у интерпретацији, и то у позиву методе над табелом симбола.

Класа `Promenljiva`

Ово је једноставна класа која чува једну ниску која представља идентификатор.

Декларација може бити оваква:

sintaksno_stablo.hpp

class Promenljiva : public ASTCvor {
public:
    Promenljiva(const std::string &id);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;

private:
    std::string m_id;
};

Имплементација оваква:

sintaksno_stablo.cpp

Promenljiva::Promenljiva(const std::string &id) : m_id(id) {}

void Promenljiva::ispisi(std::ostream& os) const {
    os << m_id;
}

double Promenljiva::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return tabela_simbola.vrednost_promenljive(m_id);
}

ASTCvor *Promenljiva::kloniraj() const {
    return new Promenljiva(*this);
}

Класа `Konstanta`

Ова класа треба да представља реалне константе, и зато треба да има само једну приватну променљиву типа double (у случају да радимо са неким другим типовима, она би чувала тај други тип).

Имплементација је праволинијска.

sintaksno_stablo.hpp

class Konstanta : public ASTCvor {
public:
    Konstanta(double vrednost);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;

private:
    double m_vrednost;
};

sintaksno_stablo.cpp

Konstanta::Konstanta(double vrednost) : m_vrednost(vrednost) {}

void Konstanta::ispisi(std::ostream& os) const {
    os << m_vrednost;
}

double Konstanta::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_vrednost;
}

ASTCvor *Konstanta::kloniraj() const {
    return new Konstanta(*this);
}

Класа `UnarniCvor`

Ово је наткласа свих класа које имају тачно једно дете. Зато треба да има једну променљиву типа ASTCvor * које ће бити protected видљивости (да бисмо могли да јој приступимо из њених поткласа).

Опет, чим памтимо показиваче на динамички алоцирану меморију, потребно је да предефинишемо деструктор. Као и у претходним случајевима, предефинисаћемо још и конструктор копије (који нам је важан због нпр. методе kloniraj), али нећемо оператор доделе јер нам неће бити потребан.

Декларација је у наставку.

sintaksno_stablo.hpp

class UnarniCvor : public ASTCvor {
public:
    UnarniCvor(ASTCvor *cvor);
    UnarniCvor(const UnarniCvor &drugi);
    ~UnarniCvor();

    // metode iz natklase
    virtual void ispisi(std::ostream& os) const = 0;
    virtual double interpretiraj(TabelaSimbola &tabela_simbola) const = 0;
    virtual ASTCvor *kloniraj() const = 0;

protected:
    ASTCvor *m_cvor;
};

Приметимо да је и ова класа апстрактна. Она је само посредник између класе ASTCvor и осталих конкретних класа са једним дететом. Зато су сви методи наткласе остављени без дефиниције (на крају њихових декларација стоји = 0). Заиста, ни нема смисла да имплементирамо ове методе, јер како да интерпретирамо чвор типа UnarniCvor? Морамо да знамо тачно о ком чвору се ради да бисмо то одрадили.

Није било неопходно наводити све методе апсрактне наткласе у нашој класи јер их не имплементирамо. Оне ће се подразумевано наследити и остаће без дефиниције ако их ми не дефинишемо. Овде је то урађено да би се нагласило да се ради о апстрактној класи. Такође, није неопходно да стоји кључна реч virtual испред декларације, али јесте неопходно да нагласимо = 0, иначе добијамо грешку од линкера јер очекује дефиницију методе.

Имплементација је слична претходним.

sintaksno_stablo.cpp

UnarniCvor::UnarniCvor(ASTCvor *cvor) : m_cvor(cvor) {}

UnarniCvor::UnarniCvor(const UnarniCvor &drugi) {
    m_cvor = drugi.m_cvor->kloniraj();
}

UnarniCvor::~UnarniCvor() {
    delete m_cvor;
}

Класа `Negacija`

Класа која наслеђује директно апстрактну класу UnarniCvor и остаје јој још само да имплементира њене методе.

sintaksno_stablo.hpp

class Negacija : public UnarniCvor {
public:
    Negacija(ASTCvor *cvor);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;
};

Како смо одговарајуће конструкторе и деструкторе имплементирали у наткласи, то овде остаје само да их позовемо и да имплементирамо недефинисане методе из ње. Тако у конструктору ове класе, само позивамо конструктор наткласе, док конструктор копије не морамо ни да декларишемо. При позиву конструктора прво се позива онај из наткласе, односно, све ће радити аутоматски.

sintaksno_stablo.cpp

Negacija::Negacija(ASTCvor *cvor) : UnarniCvor(cvor) {}

void Negacija::ispisi(std::ostream& os) const {
    os << "- (" << *m_cvor << ")";
}

double Negacija::interpretiraj(TabelaSimbola &tabela_simbola) const {
    // ovde nam je potrebno da pristupimo polju m_cvor
    // zato smo izabrali da on u natklasi ima protected vidljivost
    return - m_cvor->interpretiraj(tabela_simbola);
}

ASTCvor *Negacija::kloniraj() const {
    return new Negacija(*this);
}

То можемо да видимо код kloniraj метода. У њему директно позивамо конструктор копије класе Negacija. Тај конструктор прво позива конструктор копије наткласе, у овом случају класе UnarniCvor, који копира дубоко поље m_cvor, што је све што нам је потребно.

Класа `Ispis`

Ова класа ће бити готово идентична класи Negacija само ће се разликовати имплементације специфичних метода.

sintaksno_stablo.hpp

class Ispis : public UnarniCvor {
public:
    Ispis(ASTCvor *cvor);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;
};

sintaksno_stablo.cpp

Ispis::Ispis(ASTCvor *cvor) : UnarniCvor(cvor) {}

void Ispis::ispisi(std::ostream& os) const {
    os << "print(" << *m_cvor << ");";
}

double Ispis::interpretiraj(TabelaSimbola &tabela_simbola) const {
    double vrednost = m_cvor->interpretiraj(tabela_simbola);
    std::cout << vrednost << std::endl;

    // vracamo neku vrednost samo da bismo
    // se uskladili sa definicijom metoda
    return vrednost;
}

ASTCvor *Ispis::kloniraj() const {
    return new Ispis(*this);
}

Приметимо да нисмо имали посредну класу UnarniCvor обе ове класе би морале да префефинишу деструктор и конструктор копије. Имали бисмо дупликацију кода, и ако би било потребно да додајемо још неки тип чвора са само једним дететом, и за ту нову класу бисмо морали поново да их имплементирамо.

Класа `BinarniCvor`

Класа која апстрахује типове чворова са тачно два детета (попут класа Sabiranja, Mnozenje, Poredjenje). По имплементацији јако слична класи UnarniCvor, само се додаје још једно дете (сва објашњења су иста).

sintaksno_stablo.hpp

class BinarniCvor : public ASTCvor {
public:
    BinarniCvor(ASTCvor *levi, ASTCvor *desni);
    BinarniCvor(const BinarniCvor &drugi);
    ~BinarniCvor();

    // metode iz natklase
    virtual void ispisi(std::ostream& os) const = 0;
    virtual double interpretiraj(TabelaSimbola &tabela_simbola) const = 0;
    virtual ASTCvor *kloniraj() const = 0;

protected:
    ASTCvor *m_levi, *m_desni;
};

sintaksno_stablo.cpp

BinarniCvor::BinarniCvor(ASTCvor *levi, ASTCvor *desni)
    : m_levi(levi), m_desni(desni) {}

BinarniCvor::BinarniCvor(const BinarniCvor &drugi) {
    m_levi = drugi.m_levi->kloniraj();
    m_desni = drugi.m_desni->kloniraj();
}

BinarniCvor::~BinarniCvor() {
    delete m_levi;
    delete m_desni;
}

Даље следе имплементације класа које је наслеђују. Све је већ виђено раније, тако да следе само њихови кодови.

Класа `Sabiranje`

sintaksno_stablo.hpp

class Sabiranje : public BinarniCvor {
public:
    Sabiranje(ASTCvor *levi, ASTCvor *desni);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;
};

sintaksno_stablo.cpp

Sabiranje::Sabiranje(ASTCvor *levi, ASTCvor *desni)
    : BinarniCvor(levi, desni) {}

void Sabiranje::ispisi(std::ostream& os) const {
    os << "(" << *m_levi << ") + (" << *m_desni << ")";
}

double Sabiranje::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) + m_desni->interpretiraj(tabela_simbola);
}

ASTCvor *Sabiranje::kloniraj() const {
    return new Sabiranje(*this);
}

Класа `Mnozenje`

sintaksno_stablo.hpp

class Mnozenje : public BinarniCvor {
public:
    Mnozenje(ASTCvor *levi, ASTCvor *desni);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;
};

sintaksno_stablo.cpp

Mnozenje::Mnozenje(ASTCvor *levi, ASTCvor *desni)
    : BinarniCvor(levi, desni) {}

void Mnozenje::ispisi(std::ostream& os) const {
    os << "(" << *m_levi << ") * (" << *m_desni << ")";
}

double Mnozenje::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) * m_desni->interpretiraj(tabela_simbola);
}

ASTCvor *Mnozenje::kloniraj() const {
    return new Mnozenje(*this);
}

Класа `Poredjenje`

sintaksno_stablo.hpp

class Poredjenje : public BinarniCvor {
public:
    Poredjenje(ASTCvor *levi, ASTCvor *desni);

    // metode iz natklase
    void ispisi(std::ostream& os) const override;
    double interpretiraj(TabelaSimbola &tabela_simbola) const override;
    ASTCvor *kloniraj() const override;
};

sintaksno_stablo.cpp

Poredjenje::Poredjenje(ASTCvor *levi, ASTCvor *desni)
    : BinarniCvor(levi, desni) {}

void Poredjenje::ispisi(std::ostream& os) const {
    os << "(" << *m_levi << ") == (" << *m_desni << ")";
}

double Poredjenje::interpretiraj(TabelaSimbola &tabela_simbola) const {
    bool uslov = (m_levi->interpretiraj(tabela_simbola) == m_desni->interpretiraj(tabela_simbola));
    std::cout << (uslov ? "True" : "False") << std::endl;

    // vracamo neku vrednost samo da bismo
    // se uskladili sa definicijom metoda
    return uslov;
}

ASTCvor *Poredjenje::kloniraj() const {
    return new Poredjenje(*this);
}

Употреба

Када смо сада направили структуру података синтаксног стабла, хајде да га применимо на почетном примеру.

def x = 2.5;
x = x * x + 2;

print(- x);

16.5 == 2 * x;

Који желимо да преведемо у наредно стабло користећи све што смо до сада направили.

kalkulator_ast_example

Направимо нови C++ фајл primer_stabla.cpp и, за почетак, укључимо одговарајуће заглавље.

#include "sintaksno_stablo.hpp"

Синтаксно стабло сада можемо да формирамо тако што кренемо од објекта типа NizNaredbi и у њега редом додајемо одговарајуће наредбе. Односно…

…направимо објетак типа NizNaredbi (који ће бити корен стабла),

NizNaredbi *niz_naredbi = new NizNaredbi();

…и додајемо редом чворове у њега.

// def x = 2.5;
niz_naredbi->dodaj_cvor(
    new Definicija("x", new Konstanta(2.5))
);

// x = x * x + 2;
niz_naredbi->dodaj_cvor(
    new Dodela(
        "x",
        new Sabiranje(
            new Mnozenje(new Promenljiva("x"), new Promenljiva("x")),
            new Konstanta(2)
        )
    )
);

// print(- x);
niz_naredbi->dodaj_cvor(
    new Ispis(new Negacija(new Promenljiva("x")))
);

// 16.5 == 2 * x;
niz_naredbi->dodaj_cvor(
    new Poredjenje(
        new Konstanta(16.5),
        new Mnozenje(new Konstanta(2), new Promenljiva("x"))
    )
);

Можемо на крају да сачувамо niz_naredbi као објекат типа ASTCvor ради систематичности.

ASTCvor *ast = niz_naredbi;

Коначно, можемо да тестирамо имплементиране методе.

// ispis
std::cout << *ast << std::endl;

// interpretacija
// ne zaboravimo da nam je ovde potreban objekat tipa TabelaSimbola!
TabelaSimbola tabela_simbola;
ast->interpretiraj(tabela_simbola);

Преведимо програм (не заравимо изворне фајлове за синтаксно стабло и табелу симбола!)

$ g++ primer_stabla.cpp sintaksno_stablo.cpp tabela_simbola.cpp

Покретањем добијамо следећи испис:

$ ./a.out
def x = 2.5;
x = ((x) * (x)) + (2);
print(- (x));
(16.5) == ((2) * (x));

-8.25
True

Прве четири линије су испис стабла (видимо да се то своди практично на генерисање изворног кода назад из стабла), док су последње две резултат интерпретације. Дакле, наше стабло ради!

Остала је још једна важна ствар коју не треба да заборављамо, а то је цурење меморије. Овде смо алоцирали објекте на хипу и дужни смо их сами и ослободимо. Како смо за све претходне класе дефинисали одговарајуће деструкторе, то ће бити довољно само да додамо:

delete ast;

Коришћењем неког профајлера (попут Valgrind-а) можемо да се уверимо да су сви ресурси заиста ослобођени.

У синтаксичкој анализи

Наравно, не желимо да сами правимо синтаксно стабло као у претходном примеру, већ ћемо га формирати током синтаксичке анализе. Тако да ће за комплетирање овог примера бити потребно да комплетирамо прве две фазе компилације у потпуности, односно, да од улазног изворног фајла генеришемо синтаксно стабло.

Следеће: Формирање синтаксног стабла уз GNU Bison.

Прецизније би било поделити последње две фазе редом на генерисање међукода, машински независне оптимизације, генерисање кода и машински зависне оптимизације ↩
На постављеном линку могу се наћи још неке верзије овог „правила“ (попут rule of five), али ми овде не користимо move семантику, тако да нам неће бити од важности ↩

Увод и подсећање

Дефиниција и структура

Мотивација

C++ имплементација

Пример синтаксног стабла

Класа ASTCvor

Класа TabelaSimbola

Класа NizNaredbi

Класе Definicija и Dodela

Класа Promenljiva

Класа Konstanta

Класа UnarniCvor

Класа Negacija

Класа Ispis

Класа BinarniCvor

Класа Sabiranje

Класа Mnozenje

Класа Poredjenje

Употреба

У синтаксичкој анализи

Класа `ASTCvor`

Класа `TabelaSimbola`

Класа `NizNaredbi`

Класе `Definicija` и `Dodela`

Класа `Promenljiva`

Класа `Konstanta`

Класа `UnarniCvor`

Класа `Negacija`

Класа `Ispis`

Класа `BinarniCvor`

Класа `Sabiranje`

Класа `Mnozenje`

Класа `Poredjenje`