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

\begin{document}

\begin{small}

\begin{center}
\textbf{Prevodioci i interpretatori - maj 2007. - 2. kolokvijum}
\end{center}

% ****************************************************************
\paragraph{1. Konstrukcija gramatika}
% ****************************************************************
\begin{enumerate}

\item Definisati:
\begin{enumerate}
    \item Pojam (binarne) relacije na skupu $A$.
    \item Pojam tranzitivnog zatvorenja relacije.
    \item Kontekstno slobodne gramatike $G$.
    \item Relaciju neposrednog izvo\dj enja $\Rightarrow$ u gramatici $G$.
    \item Relaciju $\Rightarrow^*$.
    \item Jezik generisan gramatikom $G$.
    \item Izvo\dj enje nalevo i nadesno u gramatici $G$
\end{enumerate}

\item Definisati svojstvo jednozna\v{c}nosti KSG. \v{S}ta je
inherentno
vi\v{s}ezna\v{c}an jezik? \\
Ukoliko je mogu\' ce, kontekstno
slobodnom gramatikom opisati jezik:

\begin{enumerate}
\item svih niski nad $\Sigma=\{0, 1\}$ koji imaju isti broj nula i
jedinica.
\item $\{0^i1^j\ |\ i > j \geq 0\}$
\item $\{0^i1^j0^i\ |\ i > j > 0\}$
\item $\{0^i1^j0^i\ |\ i, j > 0\}$
\end{enumerate}

Odrediti koje su od konstruisanih gramatika vi\v sezna\v cne i, ukoliko je mogu\' ce,
osloboditi ih vi\v sezna\v cnosti.
\end{enumerate}

% ****************************************************************
\paragraph{2. Transformacije gramatika}
% ****************************************************************

\begin{enumerate}
\item Konstruisati ekvivalentnu \v cistu svojstvenu gramatiku za
gramatiku $S \rightarrow XY | ZW | A$, $X \rightarrow XX\ |\ A$,
$Y \rightarrow xY\ |\ Z$, $Z \rightarrow Y\ |\ W\ |\ AxZ$, $W
\rightarrow yW\ |\ \varepsilon$, $A \rightarrow W\ |\ y$.

\item Prevesti gramatiku $A \rightarrow AcB\ |\ BB\ |\ b$, $B
\rightarrow Ba\ |\ BAc\ |\ cA\ |\ b$ u Greibach i Chomsky normalnu
formu.
\end{enumerate}


% ****************************************************************
\paragraph{3. LL analiza}
% ****************************************************************

\begin{enumerate}
\item Definisati $LL$-gramatike i jezike. Koji uslov treba da bude
ispunjen da bi gramatika bila $LL(1)$?
\item \textsc{LL(1)} gramatikom opisati definiciju strukture u
programskom jeziku \textsc{C} i odrediti skupove izbora. Npr.
\begin{verbatim}
struct Cvor {
    char rec[100];
    int broj_pojavljivanja;
    struct Cvor *levi, *desni;
};
\end{verbatim}
Predstaviti tablicom automat za analizu nani\v ze. Simulirati rad automata
(prikazati konfiguracije kroz koje prolazi), prilikom prihvatanja niske:
\begin{verbatim}
struct Datum {
    int dan, mesec;
};
\end{verbatim}

\end{enumerate}

% ****************************************************************
\paragraph{4. LR analiza}
% ****************************************************************

\begin{enumerate}
\item Definisati klasu $LR$-gramatika. Kakav je odnos izme\dj u
$LR(1)$ i $LR(k)$-gramatika?
\item U jeziku \textsc{c}, dopu\v stena je vi\v sestruka dodela,
oblika \verb"a = b = c". Slede\' ca gramatika opisuje pomenuti
fragment jezika.
\begin{verbatim}
A ->  id = R
R ->  A | E
E ->  E + P | P
P ->  id | (A)
\end{verbatim}
Da li je data gramatika LR(0)? Konstruisati SLR(1) automat i
opisati ga ACTION i GOTO tablicama. Da li je gramatika SLR(1)?
Ukoliko nije, razre\v siti konflikte na proizvoljan na\v cin,
a zatim simulirati rad automata na prihvatanju niske \verb"a = b = c + d".
\end{enumerate}

% ****************************************************************
\paragraph{5. Atributi}
% ****************************************************************
\begin{enumerate}
\item Definisati pojam sintetizovanog atribute. \item Definisati
pojam $S$-atributske gramatike. \item Posmatrajmo jezik lista \v
ciji su elementi brojevi ili nove liste ovog oblika. Npr. $(5, (3,
2, ()), 1, ((4, 1), (2, (1, 1))))$ ili $((1, (0, 0)), 1, (2, 1))$.
Kontekstno slobodnom gramatikom opisati dati jezik, a zatim dodati
atribute i akcije kojima se izra\v cunava najve\' ca dubina
ugnje\v z\dj avanja lista. Za prvi primer je dubina 4, a za drugi
je dubina 3. Za prvi primer nacrtati stablo izvo\dj enja, i na
njemu uz svaki \v cvor ozna\v citi vrednosti odgovaraju\' cih
atributa (koji se dobijaju obilaskom drveta sa prvenstvom dubine
(depth first)).
\end{enumerate}

\end{small}
\end{document}
