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


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

    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Konstruisati minimalni deterministi\v cki kona\v cni automat
koji prihvata regularni jezik $\verb"(ab)*(ab?a|b)+"$


    \item {\sc ll(1)} gramatikom opisati strukturu centralnog dela
{\sc yacc} datoteke u kome je dat opis gramatike bez akcija.
Odrediti skupove izbora za datu gramatiku. Tablicom predstaviti
odgovaraju\' ci potisni automat.

    \item Napisati program u C-u koji tehnikom rekurzivnog spusta izra\v
    cunava vrednost iskazne formule koja se unosi sa standardnog
    ulaza. Formula se gradi 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). Npr.
     \verb"(T => F) \/ (F /\ T)".
\end{enumerate}



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

    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Konstruisati minimalni deterministi\v cki kona\v cni automat
koji prihvata regularni jezik $\verb"(ab)*(ab?a|b)+"$


    \item {\sc ll(1)} gramatikom opisati strukturu centralnog dela
{\sc yacc} datoteke u kome je dat opis gramatike bez akcija.
Odrediti skupove izbora za datu gramatiku. Tablicom predstaviti
odgovaraju\' ci potisni automat.

    \item Napisati program u C-u koji tehnikom rekurzivnog spusta izra\v
    cunava vrednost iskazne formule koja se unosi sa standardnog
    ulaza. Formula se gradi 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). Npr.
     \verb"(T => F) \/ (F /\ T)".
\end{enumerate}



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

    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Konstruisati minimalni deterministi\v cki kona\v cni automat
koji prihvata regularni jezik $\verb"(ab)*(ab?a|b)+"$


    \item {\sc ll(1)} gramatikom opisati strukturu centralnog dela
{\sc yacc} datoteke u kome je dat opis gramatike bez akcija.
Odrediti skupove izbora za datu gramatiku. Tablicom predstaviti
odgovaraju\' ci potisni automat.

    \item Napisati program u C-u koji tehnikom rekurzivnog spusta izra\v
    cunava vrednost iskazne formule koja se unosi sa standardnog
    ulaza. Formula se gradi 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). Npr.
     \verb"(T => F) \/ (F /\ T)".
\end{enumerate}



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

    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Konstruisati minimalni deterministi\v cki kona\v cni automat
koji prihvata regularni jezik $\verb"(ab)*(ab?a|b)+"$


    \item {\sc ll(1)} gramatikom opisati strukturu centralnog dela
{\sc yacc} datoteke u kome je dat opis gramatike bez akcija.
Odrediti skupove izbora za datu gramatiku. Tablicom predstaviti
odgovaraju\' ci potisni automat.

    \item Napisati program u C-u koji tehnikom rekurzivnog spusta izra\v
    cunava vrednost iskazne formule koja se unosi sa standardnog
    ulaza. Formula se gradi 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). Npr.
     \verb"(T => F) \/ (F /\ T)".
\end{enumerate}



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

    \item Ispitati da li je jezik opisan gramatikom $S\rightarrow
    xSy|\varepsilon$ regularan. Odgovor dokazati.

    \item Konstruisati minimalni deterministi\v cki kona\v cni automat
koji prihvata regularni jezik $\verb"(ab)*(ab?a|b)+"$


    \item {\sc ll(1)} gramatikom opisati strukturu centralnog dela
{\sc yacc} datoteke u kome je dat opis gramatike bez akcija.
Odrediti skupove izbora za datu gramatiku. Tablicom predstaviti
odgovaraju\' ci potisni automat.

    \item Napisati program u C-u koji tehnikom rekurzivnog spusta izra\v
    cunava vrednost iskazne formule koja se unosi sa standardnog
    ulaza. Formula se gradi 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). Npr.
     \verb"(T => F) \/ (F /\ T)".
\end{enumerate}


\newpage

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

\begin{enumerate}

    \item Direktorijum \texttt{studenti} sadr\v zi studentske
    dosijee imenovane uobi\v cajeno (npr. \texttt{mr01678}) koji sadr\v ze
    datoteke sa zadacima koje su studenti tokom leta
    radili. Studenti su mogli da biraju jedan od \v cetiri
    programska jezika i radili su 10 zadataka. Datoteke koje su
    predali su oblika \texttt{broj.ext}, \texttt{broj} predstavlja broj
    zadatka koji je re\v savan, a \texttt{ext}
    predstavlja oznaku programskog jezika u kome je zadatak ra\dj
    en (\texttt{c}, \texttt{cpp}, \texttt{java}, \texttt{pas}).
    Napisati \textsc{perl} skript koji na osnovu sadr\v zaja
    direktorijuma \verb"studenti" kreira \textsc{html} tabelu koja
    pregledno prikazuje rad studenata. Svaka vrsta se odnosi na
    po jednog studenta i po\v cinje njegovim brojem dosijea,
    a zatim, za svaki od 10 zadataka, sadr\v zi oznaku jezika u kome je
    zadatak ra\dj en, odnosno, oznaku \verb"-" ukoliko student nije radio
    taj zadatak.

    \begin{tt}
    \begin{tabular}{lcccccccccc}
        & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
        mr01567 & c & c & cpp & java & pas & - & - & cpp & java & pas\\
        mr01678 & c & cpp & java & java & - & c & - & cpp & pas & cpp\\

    \end{tabular}
    \end{tt}
    \hfill[15]

\item Napisati interpretator za mali jezik u kome je definisan tip
\verb"string" koji ozna\v cava niske karaktera. Nad niskama je
definisan operator \verb"+" i \verb"+=" koji ozna\v cavaju
konkantenaciju, zatim operator \verb"[m,n]" koji ozna\v cava
izdvajanje $n$ karaktera niske po\v cev\v si od pozicije $m$.
Definisan je operator * mno\v zenja niske brojem $n$ koja
nadovezuje $n$ kopija niske. Definisane su i funkcije
\verb"reverse" koja obr\' ce prosledjenu nisku kao i funkcija
\verb"print" koja ispisuje nisku na standardni izlaz. Jezik dopu\v
sta definisanje promenjivih, a konstante se navode unutar
navodnika. Jezik sadr\v zi i operator \verb"=~" koji proverava da li se
druga niska pojavljuje kao podniska prve i \v ciji je rezultat primene niska
\verb"found" odnosno \verb"not found". Npr.

\begin{verbatim}
string s = "abc";
string s1;
string t = s + "de"*2;
s += "gh";
s1 = s[2,2];
reverse(t);
print(s1);                  cg
print(t);                   ededcba
\end{verbatim}

\begin{enumerate}
\item Implementirati deklarisanje promenljivih i njihovo inicijalizovanje
konstantnim niskama kao i funkciju \verb"print".
\begin{verbatim}
string s = "abc";
print(s);
\end{verbatim}

\item Implementirati operatore konkatenacije \verb"+" i \verb"+=".
\begin{verbatim}
string s = "abc" + "def";
s += "ghi";
print(s);
\end{verbatim}

\item Implementirati mno\v zenje niske brojem.
\begin{verbatim}
string s = "a"*5;
print(s);
\end{verbatim}

\item Implementirati operator izdvajanja podniski.
\begin{verbatim}
string s = "abcdefg";
print(s[3,5]);
\end{verbatim}

\item Implementirati funkciju \verb"reverse".
\begin{verbatim}
string s = "abcdefg";
reverse(s);
print(s);
\end{verbatim}

\item Implementirati funkciju \verb"readln" koja u\v citava liniju
sa standardnog ulaza.
\begin{verbatim}
string s;
readln(s);
print(s);
\end{verbatim}

\item Implementirati operator \verb"=~".

\begin{verbatim}
string s, t;
readln(s);
readln(t);
print(s =~ t);
\end{verbatim}


\end{enumerate}
\end{enumerate}
\end{document}
