\documentclass[a4paper]{article}
\textwidth 18cm \textheight 26cm \topmargin -3cm
\parindent 0.46in
\headsep 0.2in \oddsidemargin -2cm \evensidemargin 0cm
\hoffset0.8cm \voffset 1.8cm \pagestyle{empty}
\begin{document}

\begin{center}
\textbf{Prevodioci i interpretatori - Mart 2004.}\\
\end{center}
\begin{enumerate}
\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
cnim automatom opisati jezik $L\subset \{0,1\}^*$ koji se sastoji
od re\v ci u kojima se nula pojavljuje paran, a jedinica neparan
broj puta.

\item
\begin{enumerate}
\item LL(1) gramatikom opisati uslovne dodele u jeziku C, pri \v
cemu je re\v c o dodeli numeri\v ckoj promenljivoj. Npr.

\begin{verbatim}
             a = b > 1 ? 2+c*3 : 4-(c+a+3);
\end{verbatim}

\item Napisati program koji metodom rekurzivnog spusta prevodi
ispravnu uslovnu dodelu u odgovaraju\' ci if-iskaz. Gornji primer
treba prevesti u
\begin{verbatim}
                if (b>1)
                     a = 2+c*3;
                else
                     a = 4-(c+a+3);
\end{verbatim}


\end{enumerate}

\item Na jeziku C napisati program koji broji redove, re\v ci i
znakove unete sa standardnog ulaza, pri \v cemu se pod re\v cju
podrazumeva bilo koji niz znakova koji ne sadr\v zi razmak,
tabulator ili novi red.
\end{enumerate}

\vskip 1cm
\begin{center}
\textbf{Prevodioci i interpretatori - Mart 2004.}\\
\end{center}
\begin{enumerate}
\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
cnim automatom opisati jezik $L\subset \{0,1\}^*$ koji se sastoji
od re\v ci u kojima se nula pojavljuje paran, a jedinica neparan
broj puta.

\item
\begin{enumerate}
\item LL(1) gramatikom opisati uslovne dodele u jeziku C, pri \v
cemu je re\v c o dodeli numeri\v ckoj promenljivoj. Npr.

\begin{verbatim}
             a = b > 1 ? 2+c*3 : 4-(c+a+3);
\end{verbatim}

\item Napisati program koji metodom rekurzivnog spusta prevodi
ispravnu uslovnu dodelu u odgovaraju\' ci if-iskaz. Gornji primer
treba prevesti u
\begin{verbatim}
                if (b>1)
                     a = 2+c*3;
                else
                     a = 4-(c+a+3);
\end{verbatim}


\end{enumerate}

\item Na jeziku C napisati program koji broji redove, re\v ci i
znakove unete sa standardnog ulaza, pri \v cemu se pod re\v cju
podrazumeva bilo koji niz znakova koji ne sadr\v zi razmak,
tabulator ili novi red.
\end{enumerate}

\vskip 1cm
\begin{center}
\textbf{Prevodioci i interpretatori - Mart 2004.}\\
\end{center}
\begin{enumerate}
\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
cnim automatom opisati jezik $L\subset \{0,1\}^*$ koji se sastoji
od re\v ci u kojima se nula pojavljuje paran, a jedinica neparan
broj puta.

\item
\begin{enumerate}
\item LL(1) gramatikom opisati uslovne dodele u jeziku C, pri \v
cemu je re\v c o dodeli numeri\v ckoj promenljivoj. Npr.

\begin{verbatim}
             a = b > 1 ? 2+c*3 : 4-(c+a+3);
\end{verbatim}

\item Napisati program koji metodom rekurzivnog spusta prevodi
ispravnu uslovnu dodelu u odgovaraju\' ci if-iskaz. Gornji primer
treba prevesti u
\begin{verbatim}
                if (b>1)
                     a = 2+c*3;
                else
                     a = 4-(c+a+3);
\end{verbatim}


\end{enumerate}

\item Na jeziku C napisati program koji broji redove, re\v ci i
znakove unete sa standardnog ulaza, pri \v cemu se pod re\v cju
podrazumeva bilo koji niz znakova koji ne sadr\v zi razmak,
tabulator ili novi red.
\end{enumerate}


\newpage
\begin{enumerate}
\item[4.] Za neterminal $X$ gramatike $G=(N,\Sigma,P,S)$, ka\v
zemo da je \textit{beskoristan(useless)}, ako ne postoji
izvodjenje oblika
$$
S\Rightarrow^*wXy\Rightarrow^*wxy
$$
gde su $w,y,x\in \Sigma^*$.

Kontekstno slobodna gramatika $G$ je opisana u tekstualnoj
datoteci na slede\' ci na\v cin :
\begin{itemize}
\item $\Sigma=\{a,b,\ldots,z,A,B,\ldots,Z\}^+$, tj. terminali su
neprazne re\v ci engleske abecede. npr.

\verb"   Matematicki, fakultet, Beograd"

\item Neterminali su re\v ci iz $\Sigma$, zapisani izmedju znakova
$<$ i $>$. npr.

\verb"   <A>, <b>, <PREVODIOCI>, <Zdravo>".

\item Pravila su terminisana sa \verb";", a vi\v se desnih strana
pravila za jedan neterminal je razdvojeno sa \verb"|". Npr.

\begin{verbatim}
   <IZRAZ> ->   <IZRAZ> operator <TERM>
              | <TERM>;
\end{verbatim}

\end{itemize}
Napisati program koji oslobadja gramatiku $G$ beskorisnih
neterminala. Koristiti LEX i YACC. Opisati i postupak dobijanja
izvr\v snog koda programa.

\end{enumerate}


\vskip 0.7cm
\begin{enumerate}
\item[4.] Za neterminal $X$ gramatike $G=(N,\Sigma,P,S)$, ka\v
zemo da je \textit{beskoristan(useless)}, ako ne postoji
izvodjenje oblika
$$
S\Rightarrow^*wXy\Rightarrow^*wxy
$$
gde su $w,y,x\in \Sigma^*$.

Kontekstno slobodna gramatika $G$ je opisana u tekstualnoj
datoteci na slede\' ci na\v cin :
\begin{itemize}
\item $\Sigma=\{a,b,\ldots,z,A,B,\ldots,Z\}^+$, tj. terminali su
neprazne re\v ci engleske abecede. npr.

\verb"   Matematicki, fakultet, Beograd"

\item Neterminali su re\v ci iz $\Sigma$, zapisani izmedju znakova
$<$ i $>$. npr.

\verb"   <A>, <b>, <PREVODIOCI>, <Zdravo>".

\item Pravila su terminisana sa \verb";", a vi\v se desnih strana
pravila za jedan neterminal je razdvojeno sa \verb"|". Npr.

\begin{verbatim}
   <IZRAZ> ->   <IZRAZ> operator <TERM>
              | <TERM>;
\end{verbatim}

\end{itemize}
Napisati program koji oslobadja gramatiku $G$ beskorisnih
neterminala. Koristiti LEX i YACC. Opisati i postupak dobijanja
izvr\v snog koda programa.

\end{enumerate}


\vskip 0.7cm
\begin{enumerate}
\item[4.] Za neterminal $X$ gramatike $G=(N,\Sigma,P,S)$, ka\v
zemo da je \textit{beskoristan(useless)}, ako ne postoji
izvodjenje oblika
$$
S\Rightarrow^*wXy\Rightarrow^*wxy
$$
gde su $w,y,x\in \Sigma^*$.

Kontekstno slobodna gramatika $G$ je opisana u tekstualnoj
datoteci na slede\' ci na\v cin :
\begin{itemize}
\item $\Sigma=\{a,b,\ldots,z,A,B,\ldots,Z\}^+$, tj. terminali su
neprazne re\v ci engleske abecede. npr.

\verb"   Matematicki, fakultet, Beograd"

\item Neterminali su re\v ci iz $\Sigma$, zapisani izmedju znakova
$<$ i $>$. npr.

\verb"   <A>, <b>, <PREVODIOCI>, <Zdravo>".

\item Pravila su terminisana sa \verb";", a vi\v se desnih strana
pravila za jedan neterminal je razdvojeno sa \verb"|". Npr.

\begin{verbatim}
   <IZRAZ> ->   <IZRAZ> operator <TERM>
              | <TERM>;
\end{verbatim}

\end{itemize}
Napisati program koji oslobadja gramatiku $G$ beskorisnih
neterminala. Koristiti LEX i YACC. Opisati i postupak dobijanja
izvr\v snog koda programa.

\end{enumerate}


\end{document}
