У наставку ће бити представљен задатак какав се може наћи на испитним роковима. Циљ овог примера је да се покаже неколико кључних ствари које нису покривене у претходном разговору о синтаксним стаблима. То су:

  • рад са кориснички дефинисаним (непримитивним) типовима
  • истицање разлике између интерпретирања и формирања синтаксних стабала у акцијама у Bison-у (овде је она суптилнија него раније)
  • решавање нових shift/reduce конфликата у граматикама

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

Поставка проблема

Дат је програмски језик за рад са функцијама на следећи начин:

  • на располагању су константе функције, идентичка функција, sin, cos и све које се могу добити њиховом композицијом и основним аритметичким операцијама (изрази попут sin(x), cos(x), x, x + sin(x * x), cos(sin(x)) * cos(2 + x))
  • функције се могу чувати и доделити променљивама (наредбе попут f = sin(x), g = f(x * x))
  • могу да се рачунају вредности у тачки функција које су већ сачуване у променљивој (изрази попут f[0.5])
  • може да се рачуна извод функције (изрази попут f')
  • функције и променљиве се исписују на стандардни излаз (наредбе попут f, sin(g(x)), g'[-1])
  • наредбе се завршавају новим редовима

Дакле, дат је програмски језика за рад са функцијама које можемо да компонујемо, рачунамо њихов извод, као и вредност у тачки, док имамо само два типа наредби—испис и доделу. Пример програма:

f = sin(x)
f'

f[1]
g = 1 + f(x*x)
g
g[0.5]


g'
g'[0.5]

Задатак је да направимо:

  1. интерпретер за овај језик
  2. формирамо синтаксно стабло за њега које може да се исписује и интерпретира

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

Парсер

Као и свим задацима, почињемо од писања граматике језика и прављења парсера за језик који проверава само синтаксичку исправност улаза. Зато је потребно да направимо три фајла:

  • lexer.l (Flex фајл)
  • parser.ypp (Bison фајл)
  • Makefile

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

Крећемо од граматике и језика које иницијално попуњавамо празним акцијама. Сегмент акција може да изледа овако:

parser.ypp

program
    : niz_naredbi {}
    ;

niz_naredbi
    : niz_naredbi naredba {}
    | naredba {}
    ;

naredba
    : ID '=' izraz '\n' {}
    | izraz '\n' {}
    | '\n' {}
    ;

izraz
    : izraz '+' izraz {}
    | izraz '-' izraz {}
    | izraz '*' izraz {}
    | izraz '/' izraz {}
    | '-' izraz %prec UMINUS {}
    | '(' izraz ')' {}
    | izraz '\'' {}
    | izraz '[' BROJ ']' {}
    | izraz '(' izraz ')' {}
    | SIN '(' izraz ')' {}
    | COS '(' izraz ')' {}
    | BROJ {}
    | ID {}
    | PROMENLJIVA {}
    ;

Наредбе се не раздвајају ; већ новим редовима (симболом \n). То за последицу има да ћемо у правилима за нетерминал naredba да додамо правило које одговара празној наредби. Ово је потребно у случају да имамо више узастопних празних редова.

У правилима за izraz имамо правило izraz -> PROMENLJIVA које одговара симболу x у дефинисању функција (тј. идентичкој функцији). Потребно је да га разликујемо јер је x у нашем језику резервирана реч.

Осим њега, поменимо да правило izraz -> izraz '(' izraz ')' одговара композицији функција, док су остала правила виђена у грађењу израза.

Када само написали правила граматике, потребно је да декларишемо све терминале (који нису једнокарактерски). Односно, у сегмент дефиниција додајемо:

parser.ypp

%token SIN COS PROMENLJIVA
%token ID
%token BROJ

Међутим, нисмо готови – потребно је да разрешимо вишезначност наше граматике.

Shift/reduce конфликти

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

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

Shift/reduce конфликти најчешће значе да имамо проблема са приоритетом и решаваћемо их тако што дефинишемо асоцијативност и приоритет токена. Од ових 35 конфликата сигурно су неки узроковани приоритетом основних аритметичких операција. Зато додајмо у сегмент дефиниција:

parser.ypp

%left '+' '-'
%left '*' '/'
%right UMINUS

И у правила граматике за унарни минус:

parser.ypp

izraz
    ...
    | '-' izraz %prec UMINUS {}
    ...

Поновним превођењем фајла parser.ypp добијамо нови испис.

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

Ако бисмо превели са опцијом -Wcounterexamples добили бисмо излистано све конфликте. Њих читамо тако што тражимо линије које почињу са Example:. На пример, један од конфликата је следећи:

parser.ypp: warning: shift/reduce conflict on token '\'' [-Wcounterexamples]
  Example: izraz '+' izraz • '\''

Овде можемо да видимо генерисани пример (izraz '+' izraz '\''), као и на ком токену конфликт настаје (\'). Штавише, видимо и када се конфликт дешава. Наиме, симбол • означава место где је парсер стигао у читању улаза. Читање се одвија слева надесно и све лево од тачке је прочитано, а први симбол десно од тачке је на реду за читање. Заиста, тек када при читању парсер дође до симбола \', не зна да ли да настави даље са читањем или да замени оно што је прочитао, у овом случају да замени izraz '+' izraz са izraz.

Овде је пожељно подсетити се објашњења како Bison извршава парсирање

Читање даље са улаза (померање тачке удесно) се назива shift, a замена десне стране неког правила левом, reduce.

Као што је речено, у овом примеру, парсер не зна да ли да уради shift (чита даље) или reduce (мења прочитано), отуда и настаје shift/reduce конфликт.

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

parser.ypp

%left '+' '-'
%left '*' '/'
%right UMINUS
%right '\''

Поновним превођењем са генерисањем контрапримера, Bison налази још 10 конфликата. Један од њих је:

  Example: izraz '+' izraz • '[' BROJ ']'

Овде настаје конфликт јер Bison не зна како да парсира реч, да ли као

  • (izraz '+' izraz) '[' BROJ ']' или
  • izraz '+' ( izraz '[' BROJ ']').

Желели бисмо друго понашање, односно, треба да нагласимо парсеру да предност има оператор []. Међутим, заграде се састоје од два симбола и поставља се питање како да разрешимо овај конфликт?

Покушајмо да корак по корак анализирамо како се парсирање одвија за улаз izraz '+' izraz '[' BROJ ']'.

  1. На самом почетку, ништа није прочитано и имамо стање:

     • izraz '+' izraz '[' BROJ ']'

  2. shift: долази до читања првог нетерминала

     izraz • '+' izraz '[' BROJ ']'

    Тренутно је прочитано само реч izraz, што није десна страна ниједног правила. Наставља се даље.

  3. shift: чита се наредни терминал '+'

     izraz '+' • izraz '[' BROJ ']'

    На улазу је izraz '+' што и даље није десна страна правила. Наставља се даље.

  4. shift: чита се нетерминал izraz

     izraz '+' izraz • '[' BROJ ']'

    У овом тренутку прочитана је реч izraz '+' izraz. Сада постоје две могућности

    • радити shift: тада се чита наредни симбол тј. '['
    • радити reduce: тј. заменити прочитану реч правилом које одговара симболу '+' (тј. правило izraz -> izraz '+' izraz)

Можемо да закључимо да је овде потребно одредити приоритет терминала '[' и '+'. Дакле, приоритет заграда одређујемо задавањем приоритета леве заграде!

Слично, треба разрешити и конфликт композиције—изразе попут izraz '+' izraz '(' izraz ')'. Ово је исти проблем као претходни и потребно је да дефинишемо и приоритет токена '('.

Коначно, приоритети токена треба да изледају овако:

parser.ypp

%left '+' '-'
%left '*' '/'
%right UMINUS
%precedence '(' '['
%right '\''

Дозвољене декларације асоцијативности су:

  • %left - лева асоцијативност
  • %right - десна асоцијативност
  • %nonassoc- неасоцијативан оператор (грешка при извршавању ако се јави потреба за разрешавањем асоцијативности)
  • %precedence - без навођења асоцијативности

Лексер

Сада је могуће написати и лексер јер знамо који су нам токени потребни.

lexer.l

%option noyywrap

%{
    #include <iostream>
    #include <cstdlib>
    #include "parser.tab.hpp"
%}

PRIR_BROJ 0|[1-9][0-9]*
REAL_BROJ [+-]?{PRIR_BROJ}(\.{PRIR_BROJ}([eE][+-]{PRIR_BROJ})?)?
IDENTIFIKATOR [_a-zA-Z][_a-zA-Z0-9]*

%%

x {
    return PROMENLJIVA;
}

sin {
    return SIN;
}

cos {
    return COS;
}

{IDENTIFIKATOR} {
    return ID;
}

{REAL_BROJ} {
    return BROJ;
}

[+\-*/()\[\]='\n] {
    return *yytext;
}

[ \t] {

}

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

%%

Приметимо да сада симбол за нови ред \n не игноришемо јер нам је он сепаратор наредби.

Повезивање

Направимо још и Make фајл зарад лакшег превођења. Он може да изледа овако:

Makefile

CC = g++
CFLAGS = -Wall -Wextra

parser: lex.yy.o parser.tab.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
	$(CC) $(CFLAGS) -c $< -o $@

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

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

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

Интерпетација

У изради.

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

У изради.