\documentclass[a4paper, serbian]{article}
\usepackage{babel}

\setlength{\oddsidemargin}{-2cm} \setlength{\evensidemargin}{-2cm}
\setlength{\textwidth}{19cm}

\setlength{\topmargin}{-3cm} \setlength{\textheight}{26cm}

\pagestyle{empty}


\begin{document}
{\small
\begin{center}
\textbf{Prevodioci i interpretatori - mart 2005. \\teorijski
deo}
\end{center}

\begin{enumerate}
\item Minimalnim determnisti\v ckim kona\v cnim automatom i regularnim izrazom opisati
jezik svih binarnih brojeva koji imaju svojstvo da su deljivi sa tri, a da ne sadr\v ze
podre\v c 101.
\item Opisati LL(1) gramatikom iterativne iskaze jezika C. Telo iterativnih iskaza ograni\v citi tako da mogu
da sadr\v ze samo druge iterativne iskaze ili iskaze dodele aritmeti\v ckih izraza promenljivim. Uslove ograni\v citi samo
na osnove relacije (\verb"<", \verb">", \verb"==", \verb"!=", \ldots) nad aritmeti\v ckim izrazima. Npr.
\begin{verbatim}
for (i = 0; i < n-1; i = i+1)
{   j = i+1;
    while(j < n)
        j = j+1;
}
\end{verbatim}
\item Kontekstno slobodnom gramatikom opisati ispravne opise {\sc html} tabela.
Na osnovu gramatike, konstruisati postisni automat koji metodom sintaksne analize navi\v se prihvata pomenuti jezik.
Pretpostaviti da se izme\dj u etiketa nalazi tekst prepoznat u fazi leksi\v cke analize kao token \verb"cdata".
Simulirati rad potisnog automata i napisati najde\v snje izvodjenje za tabelu:
\begin{verbatim}
<table>
    <tr><td>cdata</td><td>cdata</td></tr>
    <tr><td>cdata</td></tr>
</table>
\end{verbatim}
Da li je pomenuti jezik regularan? Ukoliko jeste, opisati ga regularnim izrazom, a ukoliko nije, dokazati da nije.

\end{enumerate}

\begin{center}
\textbf{Prevodioci i interpretatori - mart 2005. \\teorijski
deo}
\end{center}

\begin{enumerate}
\item Minimalnim determnisti\v ckim kona\v cnim automatom i regularnim izrazom opisati
jezik svih binarnih brojeva koji imaju svojstvo da su deljivi sa tri, a da ne sadr\v ze
podre\v c 101.
\item Opisati LL(1) gramatikom iterativne iskaze jezika C. Telo iterativnih iskaza ograni\v citi tako da mogu
da sadr\v ze samo druge iterativne iskaze ili iskaze dodele aritmeti\v ckih izraza promenljivim. Uslove ograni\v citi samo
na osnove relacije (\verb"<", \verb">", \verb"==", \verb"!=", \ldots) nad aritmeti\v ckim izrazima. Npr.
\begin{verbatim}
for (i = 0; i < n-1; i = i+1)
{   j = i+1;
    while(j < n)
        j = j+1;
}
\end{verbatim}
\item Kontekstno slobodnom gramatikom opisati ispravne opise {\sc html} tabela.
Na osnovu gramatike, konstruisati postisni automat koji metodom sintaksne analize navi\v se prihvata pomenuti jezik.
Pretpostaviti da se izme\dj u etiketa nalazi tekst prepoznat u fazi leksi\v cke analize kao token \verb"cdata".
Simulirati rad potisnog automata i napisati najde\v snje izvodjenje za tabelu:
\begin{verbatim}
<table>
    <tr><td>cdata</td><td>cdata</td></tr>
    <tr><td>cdata</td></tr>
</table>
\end{verbatim}
Da li je pomenuti jezik regularan? Ukoliko jeste, opisati ga regularnim izrazom, a ukoliko nije, dokazati da nije.

\end{enumerate}

\begin{center}
\textbf{Prevodioci i interpretatori - mart 2005. \\teorijski
deo}
\end{center}

\begin{enumerate}
\item Minimalnim determnisti\v ckim kona\v cnim automatom i regularnim izrazom opisati
jezik svih binarnih brojeva koji imaju svojstvo da su deljivi sa tri, a da ne sadr\v ze
podre\v c 101.
\item Opisati LL(1) gramatikom iterativne iskaze jezika C. Telo iterativnih iskaza ograni\v citi tako da mogu
da sadr\v ze samo druge iterativne iskaze ili iskaze dodele aritmeti\v ckih izraza promenljivim. Uslove ograni\v citi samo
na osnove relacije (\verb"<", \verb">", \verb"==", \verb"!=", \ldots) nad aritmeti\v ckim izrazima. Npr.
\begin{verbatim}
for (i = 0; i < n-1; i = i+1)
{   j = i+1;
    while(j < n)
        j = j+1;
}
\end{verbatim}
\item Kontekstno slobodnom gramatikom opisati ispravne opise {\sc html} tabela.
Na osnovu gramatike, konstruisati postisni automat koji metodom sintaksne analize navi\v se prihvata pomenuti jezik.
Pretpostaviti da se izme\dj u etiketa nalazi tekst prepoznat u fazi leksi\v cke analize kao token \verb"cdata".
Simulirati rad potisnog automata i napisati najde\v snje izvodjenje za tabelu:
\begin{verbatim}
<table>
    <tr><td>cdata</td><td>cdata</td></tr>
    <tr><td>cdata</td></tr>
</table>
\end{verbatim}
Da li je pomenuti jezik regularan? Ukoliko jeste, opisati ga regularnim izrazom, a ukoliko nije, dokazati da nije.

\end{enumerate}

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

\begin{enumerate}
\item Napisati perl skript koji za sve {\sc html} datoteke koje se nalaze u
direktorijumu \v cije se ime navodi kao argument komandne linije generi\v se odgovaraju\' ce
``obojene'' {\sc html} datoteke tj. {\sc html} datoteke koje slu\v ze za pregledno prikazivanje
{\sc html} koda na webu. Potrebno je da sve etikete budu podebljane i obojene jednom bojom,
imena njihovih atributa drugom, a vrednosti atributa tre\' com bojom. Pri tom, svi brojevi
koji se javljaju u okviru etiketa bi trebalo da budu isko\v seni.


\item Napraviti interpreter za minijaturni skript jezik koji pomalo li\v ci na jezik {\sc perl}.
Jezik odlikuje skalarni tip podataka koji obuhvata cele brojeve i niske karaktera, i
nizovni tip koji predstavlja liste skalara. Promenljive u programu se ne deklari\v su,
ali va\v zi ograni\v cenje da
imena skalarnih promenljivih po\v cinju znakom \verb"$" (npr. \verb"$scalar"), dok sve
liste po\v cinju simbolom \verb"@" (npr. \verb"@list"). Jedina naredba je naredba dodele.

Nad brojevnim skalarima su definisane
uobi\v cajene aritmeti\v cke operacije, dok su nad niskama definisane operacije konkatenacije
\verb".", mno\v zenja brojem \verb"x" koje ozna\v cava konkatenaciju odredjeni broj puta,
kao i operator izdvajanja podniske (\verb"[m,n]") koji izdvaja $n$ karaktera po\v cev\v si
od pozicije $m$. Brojevni skalari se implicitno konvertuju u niske karaktera koje sadr\v ze
njihovu tekstualnu reprezentaciju, dok se niske konvertuju u cele brojeve koje opisuju
(odnosno $0$ ukoliko ne sadr\v ze opis broja).

Nad listama su definisane funkcije \verb"push" koja ubacuje dati skalar na kraj date liste
i \verb"pop" koja vra\' ca poslednji element liste. Nad listama je definisan i operator
indeksnog pristupa \verb"[n]" koji vra\' ca $n$-ti element liste.

Jezik poseduje funkciju \verb"print" koja slu\v zi za ispis.

Npr.
\begin{verbatim}
$broj = 2;                                  # $broj postaje 2
$string = "abc";                            # $string postaje "abc"
@list = ($broj, "def");                     # @list postaje (2, "def")
$string = ($string x ($broj+1))."ab"[0,1];  # $string postaje "abcabcabca"
push(@list, $string);                       # @list postaje (2, "def", "abcabcabca")
print(@list);                               # ispisuje se (2, "def", "abcabcabca")
\end{verbatim}
\end{enumerate}


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

\begin{enumerate}
\item Napisati perl skript koji za sve {\sc html} datoteke koje se nalaze u
direktorijumu \v cije se ime navodi kao argument komandne linije generi\v se odgovaraju\' ce
``obojene'' {\sc html} datoteke tj. {\sc html} datoteke koje slu\v ze za pregledno prikazivanje
{\sc html} koda na webu. Potrebno je da sve etikete budu podebljane i obojene jednom bojom,
imena njihovih atributa drugom, a vrednosti atributa tre\' com bojom. Pri tom, svi brojevi
koji se javljaju u okviru etiketa bi trebalo da budu isko\v seni.


\item Napraviti interpreter za minijaturni skript jezik koji pomalo li\v ci na jezik {\sc perl}.
Jezik odlikuje skalarni tip podataka koji obuhvata cele brojeve i niske karaktera, i
nizovni tip koji predstavlja liste skalara. Promenljive u programu se ne deklari\v su,
ali va\v zi ograni\v cenje da
imena skalarnih promenljivih po\v cinju znakom \verb"$" (npr. \verb"$scalar"), dok sve
liste po\v cinju simbolom \verb"@" (npr. \verb"@list"). Jedina naredba je naredba dodele.

Nad brojevnim skalarima su definisane
uobi\v cajene aritmeti\v cke operacije, dok su nad niskama definisane operacije konkatenacije
\verb".", mno\v zenja brojem \verb"x" koje ozna\v cava konkatenaciju odredjeni broj puta,
kao i operator izdvajanja podniske (\verb"[m,n]") koji izdvaja $n$ karaktera po\v cev\v si
od pozicije $m$. Brojevni skalari se implicitno konvertuju u niske karaktera koje sadr\v ze
njihovu tekstualnu reprezentaciju, dok se niske konvertuju u cele brojeve koje opisuju
(odnosno $0$ ukoliko ne sadr\v ze opis broja).

Nad listama su definisane funkcije \verb"push" koja ubacuje dati skalar na kraj date liste
i \verb"pop" koja vra\' ca poslednji element liste. Nad listama je definisan i operator
indeksnog pristupa \verb"[n]" koji vra\' ca $n$-ti element liste.

Jezik poseduje funkciju \verb"print" koja slu\v zi za ispis.

Npr.
\begin{verbatim}
$broj = 2;                                  # $broj postaje 2
$string = "abc";                            # $string postaje "abc"
@list = ($broj, "def");                     # @list postaje (2, "def")
$string = ($string x ($broj+1))."ab"[0,1];  # $string postaje "abcabcabca"
push(@list, $string);                       # @list postaje (2, "def", "abcabcabca")
print(@list);                               # ispisuje se (2, "def", "abcabcabca")
\end{verbatim}
\end{enumerate}

}
\end{document}
