Пример језика сличног Pascal-у

Задатак
Парсер
Синтаксно стабло
Акције у Bison-у и повезивање

Идеја наредног задатка је да илустује како се парсирају, интерпретирају и формирају синтаксна стабла програмских језика који садрже гранања и петље. Сви примери до сада су једино дозвољавали чување вредности у променљивама, док сада желимо да одемо корак даље и направимо сложенији програмски језик.

Главни изазов овде ће бити написати граматику која се уклапа са жељеном семантиком језика. Зато ћемо програмски језик поједноставити и фокусирати се оно што је ново—гранања и петље.

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

Задатак

Треба направити парсер за програмски језик налик Pascal-у. Парсер треба да формира синтаксно стабло које може да се исписује и извршава.

За језик важе следећа правила:

сви изрази су целобројног типа
програм почиње кључном речју begin, а завршава кључном речју end коју прати тачка (.)
променљивама се додељују вредности помоћу оператора :=(пример: x := 3)
изрази се исписују помоћу функције print (пример: print(x + 4))
изрази се могу сабирати, одузимати, поредити на једнакост и да ли су мањи, односно већи (оператори +, -, =, <, >); резултат израза поређења је 1 ако су тачни, односно 0, ако нису
може се користити наредба гранања у формату

if izraz then
    naredbe

или

if izraz then
    naredbe
else
    naredbe

где naredbe може бити једна наредба, или низ наредби при чему је у том случају неопходно окружити их кључним речима begin и end

Пример:

if x < 2 do
    print(x);
else
    begin
        x := x + 1;
        print(x);
    end

могу се формирати и петље на наредни начин:

while izraz do
    naredbe

где naredbe представља или једну наредбу, или низ наредби окружен са begin и end

белине и нови редови се игноришу, a појединачне наредбе (оне које нису у begin-end блоку) се завршавају симболом ;

Пример једног програма:

begin
    x := 0;
    while x < 5 do
        begin
            print(x);
            x := x + 1;
        end
    
    while x > 0 do 
        x := x - 1;

    if x < 5 then
        print(x);

    if x > 5 then
        print(x);
    else
        print(x - 10);

end.

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

Парсер

Поступак писања парсера језика увек почињемо писањем граматике језика, односно попуњавањем правила у Bison фајлу који по конвенцији именујемо parser.ypp. Након тога пишемо лексер у Flex-у, у фајлу lexer.l и, на крају, ради лакшег превођења, правимо Makefile.

Граматика језика

Почнимо од правила за изразе. Наш програм ради само са целобројним изразима и у њих убрајамо и изразе поређења (који ће бити третирани као у C-у тј. биће третирани као тачни ако и само ако су различити од 0).

parser.ypp

izraz
    : izraz '+' izraz {}
    | izraz '-' izraz {}
    | izraz '=' izraz {}
    | izraz '<' izraz {}
    | izraz '>' izraz {}
    | '(' izraz ')' {}
    | ID {}
    | BROJ {}
    ;

Што се наредби тиче, имамо стандардне наредбе за доделу и испис које описујемо као и у ранијим примерима.

parser.ypp

naredba
    : ID EQ izraz ';' {}
    | PRINT '(' izraz ')' ';' {}
    ...
    ;

Међутим, имамо и наредбе гранања и петљи. Њих можемо да опишемо на следећи начин.

parser.ypp

naredba
    ...
    | IF izraz THEN naredba {}
    | IF izraz THEN naredba ELSE naredba {}
    | WHILE izraz DO naredba {}
    ...
    ;

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

parser.ypp

naredba
    ...
    | BEGIN_TOKEN niz_naredbi END_TOKEN {}
    ;

Чиме омогућавамо надовезивање више наредби.

Напомена: Не можемо да користимо реч BEGIN за токен који одговара кључној речи begin зато што већ постоји макро са тим именом. Ако бисмо ипак пробали да га користимо, добили бисмо грешку попут наредне.
parser.tab.hpp:57:5: note: in expansion of macro ‘BEGIN’
57 |     BEGIN = 258,                   /* BEGIN  */
    |     ^~~~~
Из тог разлога именујемо токене BEGIN_TOKEN и END_TOKEN.

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

parser.ypp

program
    : BEGIN niz_naredbi END_TOKEN '.' {}
    ;

niz_naredbi
    : niz_naredbi naredba {}
    | naredba {}
    ;

Као и да декларишемо токене у сегменту дефиниција.

parser.ypp

%token BEGIN END_TOKEN EQ PRINT IF THEN ELSE WHILE DO
%token BROJ
%token ID

Чиме завршавамо нашу граматику.

Разрешавање конфликата

Ако покушамо да преведемо Bison фајл који смо написали до сада, добићемо наредно упозорење.

parser.ypp: warning: 26 shift/reduce conflicts [-Wconflicts-sr]
parser.ypp: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

Дакле, имамо shift/reduce конфликте у граматици. То је и очекивано, јер радимо са изразима и већ смо се сусретали са конфликтима који се јављају код њих. Зато додајемо у сегменту дефиниција приоритет токенима који се јављају у правилима за изразе.

parser.ypp

%left '='
%left '<' '>'
%left '+' '-'

Ако сада поново преведемо парсер, добијамо следећи излаз:

parser.ypp: warning: 1 shift/reduce conflict [-Wconflicts-sr]
parser.ypp: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

Ипак нисмо покрили један конфликт. Можемо да погледамо и тачно који ако преведемо фајл са опцијом Wcounterexamples. Односно, покретањем

$ bison --header -Wcounterexamples parser.ypp

добијамо

parser.ypp: warning: 1 shift/reduce conflict [-Wconflicts-sr]
parser.ypp: warning: shift/reduce conflict on token ELSE [-Wcounterexamples]
  Example: IF izraz THEN IF izraz THEN naredba • ELSE naredba
  Shift derivation
    naredba
    ↳ 6: IF izraz THEN naredba
                       ↳ 7: IF izraz THEN naredba • ELSE naredba
  Reduce derivation
    naredba
    ↳ 7: IF izraz THEN naredba                      ELSE naredba
                       ↳ 6: IF izraz THEN naredba •

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

IF izraz THEN IF izraz THEN naredba ELSE naredba

И заиста, тај израз можемо да тумачимо као

IF izraz THEN (
    IF izraz THEN
        naredba
    ELSE
        naredba
)

али и као

IF izraz THEN (
    IF izraz THEN
        naredba
)
ELSE
    naredba

Овде долазимо до суштине проблема који овај задатак треба да демонстрира—како решити shift/reduce кофликти код наредбе гранања. Shift/reduce конфликте смо решавали тако што смо додељивали приоритете одговарајућим токенима. Најједноставнији случајеви били су са операторима сабирања, одузимања, множења и сличним, где је интуитивно било јасно којим токенима треба доделити приоритет. Видели смо и сложеније примере, попут оператора [] који рачуна вредност функције у тачки. Већ ту није било интуитивно јасно ком токену треба доделити приоритет. Ипак, Bison нам је помагао тако што је исписивао да конфликт настаје на токену [ (приликом превођења парсера са Wcounterexamples), чиме смо знали да треба да доделимо приоритет левој загради.

Међутим, сада имамо још сложенију ситуацију. Bison нам говори да конфликт настаје на токену ELSE што нам није од толике користи с обзиром да не знамо који је то други токен коме треба да доделимо приоритет.

Да бисмо ово решили, неопходно је да знамо шта су тачно shift/reduce конфликти и како настају. То је објашњено у додатку претходне лекције. Иако обележен као додатак, овде ће то бити неопходан елемент за даље разумевање!

Дакле, парсер почиње са парсирањем речи

IF izraz THEN IF izraz THEN naredba ELSE naredba

и након 7 shift акција долази до следећег стања (врх стека је са десне стране).

корак	стање	стек	акција
7.	`IF izraz THEN IF izraz` `THEN naredba • ELSE naredba`	`IF izraz THEN IF izraz` `THEN naredba`	?

Парсер сада има две могућности: (1) да ради shift акцију тј. да чита токен ELSE или (2) да ради reduce тј. да редукује врх стека одговарајућим правилом.

Уколико се ради shift, одвијају се следећи кораци.

корак	стање	стек	акција
7.	`IF izraz THEN IF izraz` `THEN naredba • ELSE naredba`	`IF izraz THEN IF izraz` `THEN naredba`	shift
8.	`IF izraz THEN IF izraz` `THEN naredba ELSE • naredba`	`IF izraz THEN IF izraz` `THEN naredba ELSE`	shift
9.	`IF izraz THEN IF izraz` `THEN naredba ELSE naredba •`	`IF izraz THEN IF izraz THEN naredba ELSE naredba`	reduce
10.	`IF izraz THEN IF izraz` `THEN naredba ELSE naredba •`	`IF izraz THEN naredba`	reduce
11.	`IF izraz THEN IF izraz` `THEN naredba ELSE naredba •`	`naredba`	…

Стабло извођења у овом случају изледа овако:

dangling_else_shift_izvodjenje

Ако би се, ипак, у 7. кораку радио reduce, онда бисмо имали:

корак	стање	стек	акција
7.	`IF izraz THEN IF izraz` `THEN naredba • ELSE naredba`	`IF izraz THEN IF izraz THEN naredba`	reduce
8.	`IF izraz THEN IF izraz` `THEN naredba • ELSE naredba`	`IF izraz THEN naredba`	shift
9.	`IF izraz THEN IF izraz` `THEN naredba ELSE • naredba`	`IF izraz THEN naredba ELSE`	shift
10.	`IF izraz THEN IF izraz` `THEN naredba ELSE naredba •`	`IF izraz THEN naredba` `ELSE naredba`	reduce
11.	`IF izraz THEN IF izraz` `THEN naredba ELSE • naredba`	`naredba`	…

Док би стабло извођења изледало овако:

dangling_else_reduce_izvodjenje

Приметимо да првом случају (када се ради shift акција) одговара наредна семантика

IF izraz THEN (
    IF izraz THEN
        naredba
    ELSE
        naredba
)

а reduce акцији, одговара ова:

IF izraz THEN (
    IF izraz THEN
        naredba
)
ELSE
    naredba

Овај израз се у већини програмских језика тумачи на први начин, односно ELSE се везује за последњи IF. Зато желимо да парсер у овом случају уради shift тј. да дамо приоритет shift правилу.

Као што је наглашено у додатку претходне лекције, приоритет shift акције одређује приоритет токена који ће њом бити прочитан. У нашем случају, то ће бити приоритет токена ELSE.

Приоритет reduce акције одређује приоритет последњег токена који се јавља у правилу по коме ће се редуковање извршити. У нашем случају, редуковање се врши по правилу naredba -> IF izraz THEN naredba (то можемо да видимо из табеле која описује шта се дешава ако се изабере reduce акција). Дакле, приоритет reduce правила одређује приоритет токена THEN.

Зато да бисмо разрешили конфликт довољно је да додамо у сегмент дефиниција:

parser.ypp

%precedence THEN
%precedence ELSE

Чиме говоримо парсеру да shift акцијa има приоритет у односу на reduce и решавамо конфликт.

Напомена 1: Ово није једини начин на који смо могли да решимо овај конфликт. Наиме, то можемо да урадимо на бар још два начина.

У додатку претходне лекције поменуто је да се приоритет правила може доделити директивом %prec. Зато смо могли да експлицитно поставимо приоритет правила по коме се врши редуковање на приоритет помоћног токена IF_NAREBDA.
```
naredba
     ...
     | IF izraz THEN naredba %prec IF_NAREDBA {}
     ...
```
Док у сегменту дефиниција пишемо:
```
%precedence IF_NAREDBA
%precedence ELSE
```
Како Bison подразумева shift акцију у односу на reduce када долази до конфликта, то је други начин да заправо не урадимо ништа. Дакле, када закључимо да нам је shift жељена акција, можемо само да игноришемо упозорење са тим конфликтом. Ипак, пожељно је написати експицитно приоритете чак и када нам подразумевано понашање одговара.

Напомена 2: Проблем који смо описивали познат је као Dangling else. О њему се може пронаћи и званична Bison документација која га описује и разрешава.

Лексер

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

lexer.l

begin {
    return BEGIN_TOKEN;
}

end {
    return END_TOKEN;
}

if {
    return IF;
}

then {
    return THEN;
}

else {
    return ELSE;
}

while {
    return WHILE;
}

do {
    return DO;
}

print {
    return PRINT;
}

:= {
    return EQ;
}

[_a-zA-Z][_a-zA-Z0-9]* {
    yylval.niska = new std::string(yytext);
    return ID;
}

[1-9][0-9]*|0 {
    yylval.ceo_broj = atoi(yytext);
    return BROJ;
}

[+\-();<>.=] {
    return *yytext;
}

[ \t\n] {

}

. {
    std::cerr << "leksicna greska: " << yytext << std::endl;
    exit(EXIT_FAILURE);
}

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

Сада треба да проширимо парсер тако да формира синтаксно стабло произвољног програма на овом програмском језику. То радимо на стандардан начин: тако што посматрамо правила граматике и (углавном) за свако правило правимо класу која представља одговарајући чвор синтаксног стабла.

Увек правимо апстрактну класу ASTCvor коју ће све остале класе да наслеђују. Поред ње, често правимо и помоћне апстрактне (међукласе) UnarniCvor и BinarniCvor које ће наслеђивати класе са тачно једним, односно два детета. Овде ћемо направити и класу TernarniCvor за класе са тачно три детета (њу ће наслеђивати само класа за IF-ELSE чвор).

Хијерархија коју правимо ће изледати овако:

(1) класе које наслеђују директно апстрактну класу ASTCvor

pascal_sintaksno_stablo_ast_cvor

(2) класе које наслеђују класу UnarniCvor

pascal_sintaksno_stablo_unarnicvor

(3) класе које наслеђују класу BinarniCvor

pascal_sintaksno_stablo_binarnicvor

(3) класе које наслеђују класу TernarniCvor

pascal_sintaksno_stablo_ternarnicvor

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

Класа `TabelaSimbola`

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

tabela_simbola.hpp

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

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

tabela_simbola.cpp

void TabelaSimbola::dodeli_vrednost(const std::string &promenljiva, int vrednost) {
    m_tabela[promenljiva] = vrednost;
}

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

    // ne mozemo da uradimo
    // return m_tabela[promenljiva];
    // jer je metoda const, a operator[] potencijalno menja mapu
    return it->second;
}

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

Класа `ASTCvor` и њене поткласe

Као што смо се раније договорили, метода interpretiraj ће враћати објекат типа израза са којима радимо у програму. У овом случају то су цели бројеви, дакле, int.

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

ASTCvor::~ASTCvor() {}

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

Класа `NizNaredbiCvor`

sintaksno_stablo.hpp

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

    void dodaj_cvor(ASTCvor *cvor);

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

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

sintaksno_stablo.cpp

NizNaredbiCvor::NizNaredbiCvor() {}

NizNaredbiCvor::NizNaredbiCvor(const NizNaredbiCvor &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];
    }
}

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

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

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

int NizNaredbiCvor::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 *NizNaredbiCvor::kloniraj() const {
    return new NizNaredbiCvor(*this);
}

Класа `DodelaCvor`

sintaksno_stablo.hpp

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

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

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

sintaksno_stablo.cpp

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

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

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

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

int DodelaCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    tabela_simbola.dodeli_vrednost(m_id, m_izraz->interpretiraj(tabela_simbola));

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

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

Класа `PromenljivaCvor`

sintaksno_stablo.hpp

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

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

private:
    std::string m_id;
};

sintaksno_stablo.cpp

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

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

int PromenljivaCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return tabela_simbola.vrednost_promenljive(m_id);
}

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

Класа `KonstantaCvor`

sintaksno_stablo.hpp

class KonstantaCvor : public ASTCvor {
public:
    KonstantaCvor(int vrednost);

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

private:
    int m_vrednost;
};

sintaksno_stablo.cpp

KonstantaCvor::KonstantaCvor(int vrednost) : m_vrednost(vrednost) {}

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

int KonstantaCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_vrednost;
}

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

Класа `UnarniCvor` и њене поткласe

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 int interpretiraj(TabelaSimbola &tabela_simbola) const = 0;
    virtual ASTCvor *kloniraj() const = 0;

protected:
    ASTCvor *m_cvor;
};

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;
}

Класа `PotprogramCvor`

Ово је нова класа. Служи да представи блок наредби окружен кључним речима begin и end. Као таква, прослеђује сву логику свом једином детету—чвору који треба да представља низ наредби.

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

void PotprogramCvor::ispisi(std::ostream &os) const {
    os << "begin\n" << *m_cvor << "end";
}

int PotprogramCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_cvor->interpretiraj(tabela_simbola);
}

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

Класа `IspisCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

int IspisCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    std::cout << m_cvor->interpretiraj(tabela_simbola) << std::endl;

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

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

Класа `BinarniCvor` и њене поткласe

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 int 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;
}

Класа `IfCvor`

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

sintaksno_stablo.hpp

class IfCvor : public BinarniCvor {
public:
    IfCvor(ASTCvor *izraz, ASTCvor *telo);

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

sintaksno_stablo.cpp

IfCvor::IfCvor(ASTCvor *izraz, ASTCvor *telo)
    : BinarniCvor(izraz, telo) {}

void IfCvor::ispisi(std::ostream &os) const {
    os << "if " << *m_levi << " then\n" << *m_desni << "\n";
}

int IfCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    if (m_levi->interpretiraj(tabela_simbola)) {
        m_desni->interpretiraj(tabela_simbola);
    }

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

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

Класа `WhileCvor`

Слична ситуација као код IfCvor класе. Користимо while петљу језика у ком пишемо парсер за интерпретацију ових чворова и ослањамо се на то да табела симбола коју прослеђујемо као параметар методи interpretiraј мења стање програма.

sintaksno_stablo.hpp

class WhileCvor : public BinarniCvor {
public:
    WhileCvor(ASTCvor *izraz, ASTCvor *telo);

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

sintaksno_stablo.cpp

WhileCvor::WhileCvor(ASTCvor *izraz, ASTCvor *telo)
    : BinarniCvor(izraz, telo) {}

void WhileCvor::ispisi(std::ostream &os) const {
    os << "while " << *m_levi << " do\n" << *m_desni;
}

int WhileCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    while (m_levi->interpretiraj(tabela_simbola)) {
        m_desni->interpretiraj(tabela_simbola);
    }

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

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

Класа `SabiranjeCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

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

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

Класа `OduzimanjeCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

int OduzimanjeCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) - m_desni->interpretiraj(tabela_simbola);
}

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

Класа `JednakostCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

int JednakostCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) == m_desni->interpretiraj(tabela_simbola);
}

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

Класа `ManjeCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

int ManjeCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) < m_desni->interpretiraj(tabela_simbola);
}

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

Класа `VeceCvor`

sintaksno_stablo.hpp

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

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

sintaksno_stablo.cpp

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

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

int VeceCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    return m_levi->interpretiraj(tabela_simbola) > m_desni->interpretiraj(tabela_simbola);
}

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

Класа `TernarniCvor` и њене поткласe

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

sintaksno_stablo.hpp

class TernarniCvor : public ASTCvor {
public:
    TernarniCvor(ASTCvor *prvi, ASTCvor *drugi, ASTCvor *treci);
    TernarniCvor(const TernarniCvor &drugi);
    ~TernarniCvor();

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

protected:
    ASTCvor *m_prvi, *m_drugi, *m_treci;
};

sintaksno_stablo.cpp

TernarniCvor::TernarniCvor(ASTCvor *prvi, ASTCvor *drugi, ASTCvor *treci)
    : m_prvi(prvi), m_drugi(drugi), m_treci(treci) {}

TernarniCvor::TernarniCvor(const TernarniCvor &drugi) {
    m_prvi = drugi.m_prvi->kloniraj();
    m_drugi = drugi.m_drugi->kloniraj();
    m_treci = drugi.m_drugi->kloniraj();
}

TernarniCvor::~TernarniCvor() {
    delete m_prvi;
    delete m_drugi;
    delete m_treci;
}

Класа `IfElseCvor`

Нова класа која представља једноставну модификацију IfCvor класе додавањем још једног детета-чвора које представља тело else гране.

sintaksno_stablo.hpp

class IfElseCvor : public TernarniCvor {
public:
    IfElseCvor(ASTCvor *izraz, ASTCvor *then_telo, ASTCvor *else_telo);

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

sintaksno_stablo.cpp

IfElseCvor::IfElseCvor(ASTCvor *izraz, ASTCvor *then_telo, ASTCvor *else_cvor)
    : TernarniCvor(izraz, then_telo, else_cvor) {}

void IfElseCvor::ispisi(std::ostream &os) const {
    os << "if " << *m_prvi << " then\n";
    os << *m_drugi << "\nelse\n" << *m_treci;
}

int IfElseCvor::interpretiraj(TabelaSimbola &tabela_simbola) const {
    if (m_prvi->interpretiraj(tabela_simbola)) {
        m_drugi->interpretiraj(tabela_simbola);
    }
    else {
        m_treci->interpretiraj(tabela_simbola);
    }

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

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

Акције у Bison-у и повезивање

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

parser.ypp

program
    : BEGIN_TOKEN niz_naredbi END_TOKEN '.' {
        ast = new PotprogramCvor($2);
    }
    ;

niz_naredbi
    : niz_naredbi naredba {
        NizNaredbiCvor *niz_naredbi = dynamic_cast<NizNaredbiCvor *>($1);
        niz_naredbi->dodaj_cvor($2);
        $$ = niz_naredbi;
    }
    | naredba {
        NizNaredbiCvor *niz_naredbi = new NizNaredbiCvor();
        niz_naredbi->dodaj_cvor($1);
        $$ = niz_naredbi;
    }
    ;

naredba
    : ID EQ izraz ';' {
        $$ = new DodelaCvor(*$1, $3);
        delete $1;
    }
    | PRINT '(' izraz ')' ';' {
        $$ = new IspisCvor($3);
    }
    | IF izraz THEN naredba {
        $$ = new IfCvor($2, $4);
    }
    | IF izraz THEN naredba ELSE naredba {
        $$ = new IfElseCvor($2, $4, $6);
    }
    | WHILE izraz DO naredba {
        $$ = new WhileCvor($2, $4);
    }
    | BEGIN_TOKEN niz_naredbi END_TOKEN {
        $$ = new PotprogramCvor($2);
    }
    ;

izraz
    : izraz '+' izraz {
        $$ = new SabiranjeCvor($1, $3);
    }
    | izraz '-' izraz {
        $$ = new OduzimanjeCvor($1, $3);
    }
    | izraz '=' izraz {
        $$ = new JednakostCvor($1, $3);
    }
    | izraz '<' izraz {
        $$ = new ManjeCvor($1, $3);
    }
    | izraz '>' izraz {
        $$ = new VeceCvor($1, $3);
    }
    | '(' izraz ')' {
        $$ = $2;
    }
    | ID {
        $$ = new PromenljivaCvor(*$1);
        delete $1;
    }
    | BROJ {
        $$ = new KonstantaCvor($1);
    }
    ;

Потребно је да декларишемо тип токена и нетерминала у сегменту дефиниција.

parser.ypp

%union {
    int ceo_broj;
    std::string *niska;
    ASTCvor *ast_cvor;
}

%token BEGIN_TOKEN END_TOKEN EQ PRINT IF THEN ELSE WHILE DO
%token<ceo_broj> BROJ
%token<niska> ID

%type<ast_cvor> program niz_naredbi naredba izraz

На крају, направимо један Makefile којим ћемо превести цео парсер. То можемо да урадимо на следећи начин:

Makefile

CC = g++
CFLAGS = -Wall -Wextra

parser: lex.yy.o parser.tab.o tabela_simbola.o sintaksno_stablo.o
	$(CC) $(CFLAGS) $^ -o $@

lex.yy.o: lex.yy.c
	$(CC) $(CFLAGS) -c $< -o $@

lex.yy.c: lexer.l parser.tab.hpp
	flex --nounput $<

parser.tab.o: parser.tab.cpp parser.tab.hpp tabela_simbola.o sintaksno_stablo.o
	$(CC) $(CFLAGS) -c $< -o $@

parser.tab.cpp parser.tab.hpp: parser.ypp tabela_simbola.hpp sintaksno_stablo.hpp
	bison --header $<

tabela_simbola.o: tabela_simbola.cpp tabela_simbola.hpp
	$(CC) $(CFLAGS) -c $< -o $@

sintaksno_stablo.o: sintaksno_stablo.cpp sintaksno_stablo.hpp tabela_simbola.hpp
	$(CC) $(CFLAGS) -c $< -o $@

.PHONY: clean

clean:
	rm -f *.o parser lex.yy.* parser.tab.*

Коначно, превођењем и покретањем

$ make

$ ./parser < test

добијамо наредни излаз:

prihvaceno
begin
x:=0;
while (x) < (5) do
begin
print(x);
x:=(x) + (1);
end
while (x) > (0) do
x:=(x) - (1);
if (x) < (5) then
print(x);

if (x) > (5) then
print(x);
else
print((x) - (10));
end
0
1
2
3
4
0
-10

Програм се исписује, а затим и извршава на очекиван начин.

Задатак

Парсер

Граматика језика

Разрешавање конфликата

Лексер

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

Класа TabelaSimbola

Класа ASTCvor и њене поткласe

Класа NizNaredbiCvor

Класа DodelaCvor

Класа PromenljivaCvor

Класа KonstantaCvor

Класа UnarniCvor и њене поткласe

Класа PotprogramCvor

Класа IspisCvor

Класа BinarniCvor и њене поткласe

Класа IfCvor

Класа WhileCvor

Класа SabiranjeCvor

Класа OduzimanjeCvor

Класа JednakostCvor

Класа ManjeCvor

Класа VeceCvor

Класа TernarniCvor и њене поткласe

Класа IfElseCvor

Акције у Bison-у и повезивање

Класа `TabelaSimbola`

Класа `ASTCvor` и њене поткласe

Класа `NizNaredbiCvor`

Класа `DodelaCvor`

Класа `PromenljivaCvor`

Класа `KonstantaCvor`

Класа `UnarniCvor` и њене поткласe

Класа `PotprogramCvor`

Класа `IspisCvor`

Класа `BinarniCvor` и њене поткласe

Класа `IfCvor`

Класа `WhileCvor`

Класа `SabiranjeCvor`

Класа `OduzimanjeCvor`

Класа `JednakostCvor`

Класа `ManjeCvor`

Класа `VeceCvor`

Класа `TernarniCvor` и њене поткласe

Класа `IfElseCvor`