\documentclass[a4paper]{article}
\setlength{\oddsidemargin}{-1cm} \setlength{\topmargin}{-3cm}
\setlength{\textwidth}{18cm} \setlength{\textheight}{26cm}
\pagestyle{empty}

\def\DJ{\leavevmode\setbox0=\hbox{D}\kern0pt
 \rlap{\kern.04em\raise.188\ht0\hbox{-}}D}
\def\dj{\leavevmode\setbox0=\hbox{d}\kern0pt
 \rlap{\kern.215em\raise.46\ht0\hbox{-}}d}

\usepackage{amssymb}

\begin{document}
\begin{center}
\textbf{Prevodioci i interpretatori - decembar 2005. - teorijski
deo}
\end{center}
\begin{enumerate}
    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati potisni automat
koji tehnikom analize navi\v se prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i prikazati rad automata prilikom njenog prihvatanja.

    \item Konstruisati potisni automat koji analizom navi\v se prihvata jezik iskaznih formula.
    Formule se grade kori\v s\' cenjem veznika \verb"/\" koji predstavlja
    konjunkciju, \verb"\/" disjunkciju, \verb"=>" implikaciju, i konstanti \verb"T" i \verb"F"
    (veznici su navedeni u opadaju\' cem redosledu prioriteta). Prikazati rad automata na prihvatanju
    niske \verb"(T => F) \/ (F /\ T)".
\end{enumerate}

\vskip 1cm

\begin{center}
\textbf{Prevodioci i interpretatori - decembar 2005. - teorijski
deo}
\end{center}
\begin{enumerate}
    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati potisni automat
koji tehnikom analize navi\v se prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i prikazati rad automata prilikom njenog prihvatanja.

    \item Konstruisati potisni automat koji analizom navi\v se prihvata jezik iskaznih formula.
    Formule se grade kori\v s\' cenjem veznika \verb"/\" koji predstavlja
    konjunkciju, \verb"\/" disjunkciju, \verb"=>" implikaciju, i konstanti \verb"T" i \verb"F"
    (veznici su navedeni u opadaju\' cem redosledu prioriteta). Prikazati rad automata na prihvatanju
    niske \verb"(T => F) \/ (F /\ T)".
\end{enumerate}

\vskip 1cm

\begin{center}
\textbf{Prevodioci i interpretatori - decembar 2005. - teorijski
deo}
\end{center}
\begin{enumerate}
    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati potisni automat
koji tehnikom analize navi\v se prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i prikazati rad automata prilikom njenog prihvatanja.

    \item Konstruisati potisni automat koji analizom navi\v se prihvata jezik iskaznih formula.
    Formule se grade kori\v s\' cenjem veznika \verb"/\" koji predstavlja
    konjunkciju, \verb"\/" disjunkciju, \verb"=>" implikaciju, i konstanti \verb"T" i \verb"F"
    (veznici su navedeni u opadaju\' cem redosledu prioriteta). Prikazati rad automata na prihvatanju
    niske \verb"(T => F) \/ (F /\ T)".
\end{enumerate}





\newpage

\begin{center}
\textbf{Prevodioci i interpretatori - decembar 2005. - prakti\v
cni deo}
\end{center}

\begin{enumerate}
\item {\sc html} datoteka \v cije se ime navodi kao prvi argument komandne linije {\sc perl} skripta sadr\v zi tabelu
u kojoj se nalaze rezultati odr\v zanog ispita. Tabela ima tri kolone i u prvoj se nalazi
ime i prezime studenta u drugoj broj poena na teorijskom delu ispita i u tre\' coj broj poena
na prakti\v cnom delu ispita.
Napisati skript koji u datoteku \verb"sortirano.html" ispisuje studente ure\dj ene opadaju\' ce po
ukupnom broju poena.


\item Napisati interpretator za jezik koji dopu\v sta definisanje matemati\v ckih funkcija jedne promenljive $x$,
izra\v cunavanje njihovih vrednosti i pronala\v zenje njihovih izvoda. Funkcije se defini\v su aritmeti\v ckim
operacijama sabiranja i mno\v zenja i kompozicijom elementarnih funkcija $x$, $\sin(x)$, $\cos(x)$ i $\exp(x)$. Npr.
$$
\sin(\exp(x)+x)*\cos(x)
$$
Komande jezika se navode u posebnim linijama. Jezik dopu\v sta definisanje funkcijskih
promenljivih. Izvod se izra\v cunava ukoliko
se nakon imena promenljive navede apostrof \verb|'|, dok se vrednost izra\v cunava ukoliko se iza imena navede vrednost
broja u okviru uglastih zagrada.
Npr.
\begin{verbatim}
f = sin(x)
f'                     1*cos(x)
f[1]                   0.841741
g = 1+f(x*x)
g                      1+sin(x*x)
g[0.5]                 1.49493
g'                     0+1*x+x*1*cos(x*x)
\end{verbatim}


\begin{enumerate}
\item Napisati leksi\v cki analizator za opisani jezik.
\item Napisati apstraktnu klasu \verb"Funkcija" sa metodima
\begin{verbatim}
        float vrednost(float x);
        Funkcija* izvod();
        void print(ostream& ostr);
\end{verbatim}
i sa svim ostalim potrebnim metodama.

\item Kreirati tablicu simbola u kojoj se \v cuvaju vrednosti promenljivih

\item Napisati klasu \verb"KonstantnaFunkcija" koja predstavlja vrstu funkcije i kojom se predstavljaju
funkcije oblika $f(x)=c,\ c\in \mathbb{R}$
\item {\sc yacc} gramatikom opisati naredbe jezika pri \v cemu su dopu\v stene isklju\v cvo definicije
konstantnih funkcija
\begin{verbatim}
f = 7
f'             0
f[0.3]         7
\end{verbatim}


\item Napisati klasu \verb"IdentickaFunkcija" koja predstavlja vrstu funkcije i kojom se predstvlja funkcija
$f(x)=x$. Pro\v siriti interpretator tako da prihvata i identi\v cku funkciju.
\begin{verbatim}
f = x
f'             1
f[0.3]         0.3
\end{verbatim}

\item Napisati klasu \verb"BinarniOperator" koja predstavlja vrstu funkcije i na osnovu nje izgraditi
operacije \verb"Plus" i \verb"Puta". Pro\v siriti interpretator tako da prihvata definisanje aritmeti\v ckih
kombinacija funkcija.
\begin{verbatim}
f = x*(1+x)
f'             (1*(1+x))+(x*(0+1))
f[0.3]         0.39
\end{verbatim}


\item Napisati klasu \verb"ElementarnaFunkcija" koja predstavlja vrstu funkcije i na osnovu nje izgraditi
operacije \verb"Sin", \verb"Cos" i \verb"Exp". Pro\v siriti interpretator tako da dopu\v sta definisanje
elementarnih funkcija.
\begin{verbatim}
f = sin(x)
f'             cos(x)
f[0.3]         0.29552
\end{verbatim}

\item Dodati mogu\' cnost pravljenja kompozicija funkcija definisanjem metode
\begin{verbatim}
        Funkcija* kompozicija(Funkcija* f);
\end{verbatim}

\end{enumerate}

\end{enumerate}
\end{document}
