\documentclass[a4paper]{article}
\setlength{\oddsidemargin}{-1cm} \setlength{\textwidth}{17cm}
\setlength{\textheight}{24cm} \setlength{\topmargin}{-2cm}
\pagestyle{empty}
\begin{document}
{\small

\begin{center}
{\bf Prevodioci i interpretatori - Decembar 2004.}\\
-teorijski deo-
\end{center}
\begin{enumerate}
    \item Za regularni izraz \verb"(ab|ba)+(ba?b)*", Tompsonovom konstrukcijom odrediti
    ekvivalentni kona\v cni automat, zatim odrediti njemu ekvivalentan automat bez
    $\varepsilon$ pokreta. Dobijeni automat determinizovati i minimizovati.
    \item
    \begin{enumerate}
        \item Kontekst slobodnom gramatikom opisati dekleraciju strukture
        u programskom jeziku C. Struktura mo\v ze da sad\v zi samo polja
        prethodno deklarisanih struktura i osnovnih tipova jezika C.
        \item Na osnovu date gramatike konstruisati odgovaraju\' cu LL(1)
            gramatiku i odrediti skupove izbora.
        \item Konstruisati odgovaraju\' ci potisni automat.
    \end{enumerate}
    \item Prevesti gramatiku
        \begin{eqnarray*}
        X&\rightarrow&XxY|Y\\
        Y&\rightarrow&YyZ|Z\\
        Z&\rightarrow&zXz|a
        \end{eqnarray*}
        u \v Comski i Gribah normalnu formu.
\end{enumerate}

\begin{center}
{\bf Prevodioci i interpretatori - Decembar 2004.}\\
-teorijski deo-
\end{center}
\begin{enumerate}
    \item Za regularni izraz \verb"(ab|ba)+(ba?b)*", Tompsonovom konstrukcijom odrediti
    ekvivalentni kona\v cni automat, zatim odrediti njemu ekvivalentan automat bez
    $\varepsilon$ pokreta. Dobijeni automat determinizovati i minimizovati.
    \item
    \begin{enumerate}
        \item Kontekst slobodnom gramatikom opisati dekleraciju strukture
        u programskom jeziku C. Struktura mo\v ze da sad\v zi samo polja
        prethodno deklarisanih struktura i osnovnih tipova jezika C.
        \item Na osnovu date gramatike konstruisati odgovaraju\' cu LL(1)
            gramatiku. Odrediti skup izbora za svako pravilo ove gramatike.
        \item Konstruisati odgovaraju\' ci potisni automat.
    \end{enumerate}

    \item Prevesti gramatiku
        \begin{eqnarray*}
        X&\rightarrow&XxY|Y\\
        Y&\rightarrow&YyZ|Z\\
        Z&\rightarrow&zXz|a
        \end{eqnarray*}
        u \v Comski i Gribah normalnu formu.
\end{enumerate}

{\small

\begin{center}
{\bf Prevodioci i interpretatori - Decembar 2004.}\\
-teorijski deo-
\end{center}
\begin{enumerate}
    \item Za regularni izraz \verb"(ab|ba)+(ba?b)*", Tompsonovom konstrukcijom odrediti
    ekvivalentni kona\v cni automat, zatim odrediti njemu ekvivalentan automat bez
    $\varepsilon$ pokreta. Dobijeni automat determinizovati i minimizovati.
    \item
    \begin{enumerate}
        \item Kontekst slobodnom gramatikom opisati dekleraciju strukture
        u programskom jeziku C. Struktura mo\v ze da sad\v zi samo polja
        prethodno deklarisanih struktura i osnovnih tipova jezika C.
        \item Na osnovu date gramatike konstruisati odgovaraju\' cu LL(1)
            gramatiku. Odrediti skup izbora za svako pravilo ove gramatike.
        \item Konstruisati odgovaraju\' ci potisni automat.
    \end{enumerate}
    \item Prevesti gramatiku
        \begin{eqnarray*}
        X&\rightarrow&XxY|Y\\
        Y&\rightarrow&YyZ|Z\\
        Z&\rightarrow&zXz|a
        \end{eqnarray*}
        u \v Comski i Gribah normalnu formu.
\end{enumerate}

\newpage
\begin{center}
{\bf Prevodioci i interpretatori - Decembar 2004.}\\
-prakti\v cni deo-
\end{center}
\begin{enumerate}
\item Direktorijum \verb"<dir>" sadr\v zi studentske web
prezentacije, pri \v cemu se svaka prezentacija nalazi u posebnom
poddirektorijumu sa indeksom studenta (npr. \verb"<dir>/mr05001").
Prezentacije se sastoje iz nekoliko {\sc html} datoteka koje mogu
biti sme\v stene i po poddirektorijumima studentovog osnovnog
direktorijuma. Napisati {\sc perl} skript koji za svakog studenta
koji ima prezentaciju ispisuje slede\' ce podatke
\begin{enumerate}
    \item Ukupan broj re\v ci u svim {\sc html} dokumentima pri \v
    cemu se prilikom brojanja re\v ci ne ra\v cunaju {\sc html}
    etikete.
    \item Broj slika koje prezentacija sadr\v zi
    \item Broj linkova koje prezentacija sadr\v zi
\end{enumerate}
Direktorijum \verb"<dir>" se navodi kao prvi argument komandne
linije skripta.

\item Neka je dat asemblerski jezik, za fiktivni nula-adresni ra\v
cunar. Asembler podr\v zava slede\'ce instrukcije

\begin{center}
\begin{tabular}{|p{1.6cm}|p{9cm}|}
\hline
\verb"push" $x$&postavlja $x$ na stek \\
\verb"pop" $x$&skida vrednost sa vrha steka i postavlja je u promenjivu $x$ ako je navedena \\
\verb"add" &skida dve vrednosti sa vrha steka i njihov zbir postavlja na stek\\
\verb"sub" &skida dve vrednosti sa vrha steka i njihovu razliku postavlja na stek\\
\verb"mul" &skida dve vrednosti sa vrha steka i njihov proizvod postavlja na stek\\
\verb"div" &skida dve vrednosti sa vrha steka i njihov koli\v cnik postavlja na stek\\
\verb"jmp" $labela$&bezuslovni skok na labelu $labela$ \\
\verb"jz" $labela$&skok na navedenu labelu ukoliko je na vrhu steka 0\\
\verb"jnz" $labela$&skok na navedenu labelu ukoliko na vrhu steka nije 0\\
\verb"cmp" & skida dve vrednosti sa vrha steka i postavlja 1 ako
su jednake i 0
ako nisu\\
\verb"cmpLT" & skida dve vrednosti sa vrha steka i postavlja 1 ako
je prva
manja od druge i 0 ako nije\\
\verb"cmpGT" & skida dve vrednosti sa vrha steka i postavlja 1 ako
je prva
ve\' ca od druge i 0 ako nije\\
\verb"print" & \v stampa vrednost sa vrha steka\\
\verb"stop" & prekida izvr\v savanje programa\\
\hline
\end{tabular}
\end{center}

Dopu\v stene labele su oblika \verb"Lxxx : " gde su \verb"x"
cifre.

Neka je, dalje, dat mali programski jezik koji podr\v zava samo
celobrojni tip podataka i na njemu definisane operatore \verb"+",
\verb"-", \verb"*", \verb"/", prefiksni operator inkrementiranja
(\verb"++") kao i relacijske operatore \verb"<", \verb">",
\verb"<=", \verb">=", \verb"==". Svi operatori imaju isto zna\v
cenje kao i u jeziku C. Od kontrolnih struktura jezik podr\v zava
uslovno grananje (if-then i if-then-else) tipa kao i while petlju
pri \v cemu je sintaksa ista kao u jeziku C. Definisana je jo\v s
i ugradjena funkcija \verb"print" sa jednim celobrojnim argumentom
koja slu\v zi sa \v stampanje.

Napraviti program koji vr\v si prevodjenje sa datog programskog
jezika na dati asembler. Npr.
\begin{verbatim}
                                   push 0
                                   pop x
                             L000:
                                   push x
                                   push 3
       x=0;                        compLT
       while (x<3)                 jz L001
       {   x=x+1;                  push x
           print(x);               push 1
       }                           add
                                   pop x
                                   push x
                                   print
                                   jmp L000
                             L001:
                                   stop
\end{verbatim}

\end{enumerate}


}
\end{document}
