\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}
\usepackage{comment}

\begin{document}
\begin{small}

\begin{center}
\textbf{Prevodioci i interpretatori - februar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Konstruisati kona\v cni transduktor koji odre\dj uje
    celobrojni koli\v cnik pri deljenju broja zapisanog u osnovi 6 brojem 5.
    Npr. za ulaz \verb"150342" transduktor na izlazu daje broj \verb"21154"\hfill[13]

    \item LL(1) gramatikom opisati deklaracije (i mogu\' cu inicijalizacije) jednodimenzionalnih odnosno
    vi\v sedimenzionalnih nizova u jeziku \textsc{C}. Npr.
\begin{verbatim}
    int a[10], b[] = {1, 5, 8};
    char s[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|int a[10], b[] = {1, 5, 8};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.\hfill[14]

\item LR gramatikom opisati osnovne regularne izraze sa operacijama
konkatenacije, \verb"*" i \verb"|" nad azbukom $\Sigma=\{a, b\}$.  Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"(a|b)*c". Da li je konstruisana gramatika SLR?\hfill[13]
\end{enumerate}
\begin{enumerate}
\item[4.] Data je KS gramatika $G=(\{S\}, \{a, b\}, P, S)$, gde je $P$ skup $
S\rightarrow aSb\ |\ aaSb\ |\ \varepsilon
$
\begin{enumerate}
    \item Dokazati da je data gramatika vi\v sezna\v cna.
    \item Konstruisati nevi\v sezna\v cnu gramatiku $G'$ ekvivalentnu datoj.
    \item Dokazati da $G'$ nije vi\v sezna\v cna i da je $L(G)=L(G')$\hfill[10]
\end{enumerate}
\end{enumerate}



\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Konstruisati kona\v cni transduktor koji odre\dj uje
    celobrojni koli\v cnik pri deljenju broja zapisanog u osnovi 6 brojem 5.
    Npr. za ulaz \verb"150342" transduktor na izlazu daje broj \verb"21154"\hfill[13]

    \item LL(1) gramatikom opisati deklaracije (i mogu\' cu inicijalizacije) jednodimenzionalnih odnosno
    vi\v sedimenzionalnih nizova u jeziku \textsc{C}. Npr.
\begin{verbatim}
    int a[10], b[] = {1, 5, 8};
    char s[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|int a[10], b[] = {1, 5, 8};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.\hfill[14]

\item LR gramatikom opisati osnovne regularne izraze sa operacijama
konkatenacije, \verb"*" i \verb"|" nad azbukom $\Sigma=\{a, b\}$.  Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"(a|b)*c". Da li je konstruisana gramatika SLR?\hfill[13]
\end{enumerate}
\begin{enumerate}
\item[4.] Data je KS gramatika $G=(\{S\}, \{a, b\}, P, S)$, gde je $P$ skup $
S\rightarrow aSb\ |\ aaSb\ |\ \varepsilon
$
\begin{enumerate}
    \item Dokazati da je data gramatika vi\v sezna\v cna.
    \item Konstruisati nevi\v sezna\v cnu gramatiku $G'$ ekvivalentnu datoj.
    \item Dokazati da $G'$ nije vi\v sezna\v cna i da je $L(G)=L(G')$\hfill[10]
\end{enumerate}
\end{enumerate}


\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Konstruisati kona\v cni transduktor koji odre\dj uje
    celobrojni koli\v cnik pri deljenju broja zapisanog u osnovi 6 brojem 5.
    Npr. za ulaz \verb"150342" transduktor na izlazu daje broj \verb"21154"\hfill[13]

    \item LL(1) gramatikom opisati deklaracije (i mogu\' cu inicijalizacije) jednodimenzionalnih odnosno
    vi\v sedimenzionalnih nizova u jeziku \textsc{C}. Npr.
\begin{verbatim}
    int a[10], b[] = {1, 5, 8};
    char s[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|int a[10], b[] = {1, 5, 8};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.\hfill[14]

\item LR gramatikom opisati osnovne regularne izraze sa operacijama
konkatenacije, \verb"*" i \verb"|" nad azbukom $\Sigma=\{a, b\}$.  Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"(a|b)*c". Da li je konstruisana gramatika SLR?\hfill[13]
\end{enumerate}
\begin{enumerate}
\item[4.] Data je KS gramatika $G=(\{S\}, \{a, b\}, P, S)$, gde je $P$ skup $
S\rightarrow aSb\ |\ aaSb\ |\ \varepsilon
$
\begin{enumerate}
    \item Dokazati da je data gramatika vi\v sezna\v cna.
    \item Konstruisati nevi\v sezna\v cnu gramatiku $G'$ ekvivalentnu datoj.
    \item Dokazati da $G'$ nije vi\v sezna\v cna i da je $L(G)=L(G')$\hfill[10]
\end{enumerate}
\end{enumerate}

\newpage
\begin{center}
\textbf{Prevodioci i interpretatori - februar 2006. - prakti\v cni deo
ispita}
\end{center}

\begin{enumerate}
  \item Sa standardnog ulaza se unosi niz linija od kojih svaka sadr\v zi
  ispravan aritmeti\v cki izraz sa operacijama sabiranja i mno\v zenja
  celih brojeva. Napisati {\sc perl} skript koji tehnikom rekurzivnog spusta
  izra\v cunava i ispisuje vrednost svakog unetog izraza.
  Npr.\hfill[15]
  \begin{verbatim}
        > (3+6)*2
        (3+6)*2 = 18
        > 2*(3+1+2)*32
        2*(3+1+2)*32 = 384
  \end{verbatim}

  \item Napraviti interpreter za mali jezik iskaznog ra\v cuna. Jezik
  dozvoljava definisanje iskaznih formula i iskaznih promenljivih.
  Iskazne formule se grade od 26 iskaznih slova (\verb|[a-z]|), konstanti
  \verb"T" i \verb"F" i prethodno definisanih iskaznih promenljivih koje
  se navode u obliku \verb"{prom}".  Dozvoljene operacije, u opadaju\' cem
  prioritetu, su negacija (\verb"~"), konjunkcija (\verb"/\"),
  disjunkcija (\verb"\/") i  implikacija (\verb"=>"). Funkcija \verb"print(f)" ispisuje formulu \verb"f"
  na standardni izlaz, \verb"substitute(f, p, g)" zamenjuje sva pojavljivanja
  iskaznog slova \verb"p" u formuli \verb"f" formulom \verb"g", a funkcija
  \verb"value(f, valuation)" ispisuje vrednost formule pri datoj valuaciji
  promenljivih. Valuacije se navode u obliku \texttt{[p1->v1, ..., pn->vn]}.
  Prijaviti gre\v sku ukoliko navedena valuacija nije dovoljna za
  odre\dj ivanje vrednosti formule (Npr. \verb"value(p/\q, [p->T])").


  \begin{verbatim}
  f1 := (p => (q \/ ~p)) => q;
  f2 := {f1} /\ ~q;
  f3 := substitute(f2, p, T);
  print(f3);                                ((T => (q \/ (~T))) => q) /\ (~q)
  value(f1, [p->T, q->F]);                  T
  \end{verbatim}

  \begin{enumerate}
    \item Gramatikom opisati dati jezik i konstruisati leksi\v cki
    analizator. \hfill[4]
    \item Definisati hijerarhiju klasa (struktura) za predstavljanje
    iskaznih formula u obliku stabla.   \hfill[12]
    \item Implementirati funkciju \verb"print". \hfill[3]
    \item Implementirati funkciju \verb"substitute". \hfill[6]
    \item Implementirati funkciju \verb"value".\hfill[10]
  \end{enumerate}

\end{enumerate}

\begin{center}
\textbf{Prevodioci i interpretatori - februar 2006. - prakti\v cni deo
ispita}
\end{center}

\begin{enumerate}
  \item Sa standardnog ulaza se unosi niz linija od kojih svaka sadr\v zi
  ispravan aritmeti\v cki izraz sa operacijama sabiranja i mno\v zenja
  celih brojeva. Napisati {\sc perl} skript koji tehnikom rekurzivnog spusta
  izra\v cunava i ispisuje vrednost svakog unetog izraza.
  Npr.\hfill[15]
  \begin{verbatim}
        > (3+6)*2
        (3+6)*2 = 18
        > 2*(3+1+2)*32
        2*(3+1+2)*32 = 384
  \end{verbatim}

  \item Napraviti interpreter za mali jezik iskaznog ra\v cuna. Jezik
  dozvoljava definisanje iskaznih formula i iskaznih promenljivih.
  Iskazne formule se grade od 26 iskaznih slova (\verb|[a-z]|), konstanti
  \verb"T" i \verb"F" i prethodno definisanih iskaznih promenljivih koje
  se navode u obliku \verb"{prom}".  Dozvoljene operacije, u opadaju\' cem
  prioritetu, su negacija (\verb"~"), konjunkcija (\verb"/\"),
  disjunkcija (\verb"\/") i  implikacija (\verb"=>"). Funkcija \verb"print(f)" ispisuje formulu \verb"f"
  na standardni izlaz, \verb"substitute(f, p, g)" zamenjuje sva pojavljivanja
  iskaznog slova \verb"p" u formuli \verb"f" formulom \verb"g", a funkcija
  \verb"value(f, valuation)" ispisuje vrednost formule pri datoj valuaciji
  promenljivih. Valuacije se navode u obliku \texttt{[p1->v1, ..., pn->vn]}.
  Prijaviti gre\v sku ukoliko navedena valuacija nije dovoljna za
  odre\dj ivanje vrednosti formule (Npr. \verb"value(p/\q, [p->T])").


  \begin{verbatim}
  f1 := (p => (q \/ ~p)) => q;
  f2 := {f1} /\ ~q;
  f3 := substitute(f2, p, T);
  print(f3);                                ((T => (q \/ (~T))) => q) /\ (~q)
  value(f1, [p->T, q->F]);                  T
  \end{verbatim}

  \begin{enumerate}
    \item Gramatikom opisati dati jezik i konstruisati leksi\v cki
    analizator. \hfill[4]
    \item Definisati hijerarhiju klasa (struktura) za predstavljanje
    iskaznih formula u obliku stabla.   \hfill[12]
    \item Implementirati funkciju \verb"print". \hfill[3]
    \item Implementirati funkciju \verb"substitute". \hfill[6]
    \item Implementirati funkciju \verb"value".\hfill[10]
  \end{enumerate}

\end{enumerate}

\end{small}
\end{document}
