\documentclass[11pt]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphics}

\newcommand{\visiblespace}{\leavevmode\hbox{\tt\char`\ }}

\pagestyle{empty}

\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\textwidth}{1in}
\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Macros du contenu
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qpts}[1]{(\textit{#1~points.})}
\newcommand{\ddtodo}[1]{%
  \mbox{\textbf{!!!}}
  \mbox{\textbf{To}}
  \mbox{\textbf{do}}
  \mbox{\textbf{!!!}}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Corps du document
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\noindent
  \parbox[t]{3.25in}{
    Université Laval \newline
    Faculté des sciences et de génie \newline
    Département d'informatique et de génie logiciel \newline
    IFT-3101
  }
\hfill
  \parbox[t]{2in}{
    \hfill Danny Dubé \newline
    %\mbox{} \newline
    \mbox{} \hfill Hiver 2019 \newline
    \mbox{} \hfill{} {\scriptsize Version: 17 février}
  }

\vspace{0.25in}

\begin{center}
  {\LARGE
    \textbf{Travail pratique \#1}
  }
\\
  {\Large
    \textbf{Analyses lexicale et syntaxique}
  }
\end{center}

\section*{Questions}

\begin{enumerate}

\item \qpts{10} Énumérez, en ordre alphabétique, toutes les chaînes
  faisant partie des ensembles suivants.  \textbf{Note}: par
  définition, une chaîne ne peut apparaître plusieurs fois dans un
  ensemble; soit elle y apparaît, soit elle n'y apparaît pas.

  \begin{enumerate}

  \item L'ensemble des préfixes de \texttt{carte}.

  \item L'ensemble des suffixes propres de \texttt{joker}.

  \item L'ensemble des sous-chaînes propres de \texttt{main}.

  \item L'ensemble des sous-séquences de \texttt{aaaab}.

  \item L'ensemble
    \(
      \{ \mathtt{ab}, \mathtt{bc}, \mathtt{ca} \}^4 \cap
      \{ \mathtt{a}, \mathtt{b}, \mathtt{c} \} \cdot
      \{ \mathtt{ab}, \mathtt{bc}, \mathtt{ca} \}^3 \cdot
      \{ \mathtt{a}, \mathtt{b}, \mathtt{c} \}
    \).

  \end{enumerate}

\mbox{}

\item \qpts{10} Les langages suivants sont décrits informellement.
  Pour chacun, donnez une expression régulière ou une définition
  régulière qui le génère.  Donnez une explication dès que votre
  réponse est le moindrement complexe.

  \begin{enumerate}

  \item L'ensemble des chaînes sur l'alphabet~$\{ \mathtt{a},
    \mathtt{b}, \mathtt{c} \}$ dans lesquelles il apparaît au moins
    un~$\mathtt{b}$ et au moins deux~$\mathtt{c}$.  Par exemple, la
    chaîne $\mathtt{caacbaa}$ est dans le langage mais pas la chaîne
    $\mathtt{aaaccaca}$.
    
  \item L'ensemble des chaînes sur l'alphabet $\{ \mathtt{0},
    \mathtt{1}, \ldots, \mathtt{9} \}$ dont le total des chiffres
    atteint au moins~$5$.  Considérez que les naturels commencent par
    zéro.  Par exemple, la chaîne $\mathtt{26}$ est dans le langage
    mais pas la chaîne $\mathtt{3010}$.

  \item L'ensemble des chaînes sur l'alphabet $\{ \mathtt{a},
    \mathtt{b}, \mathtt{c}, \mathtt{d} \}$ qui ont à la
    fois~\texttt{abc} et~\texttt{bcd} comme sous-chaînes.  Par
    exemple, les chaînes $\mathtt{dbcdcabca}$ et $\mathtt{abcd}$ sont
    dans le langage mais pas la chaîne $\mathtt{ddabcaa}$.

  \item L'ensemble des chaînes sur l'alphabet $\{ \mathtt{a},
    \mathtt{b}, \mathtt{c} \}$ qui ont à la fois~$\mathtt{abc}$ comme
    sous-chaîne et~$\mathtt{cab}$ comme sous-séquence.  Par exemple,
    la chaîne $\mathtt{abcaabbcc}$ est dans le langage mais pas la
    chaîne $\mathtt{ccaabb}$.

  \item L'ensemble des chaînes sur l'alphabet $\{ \mathtt{a},
    \mathtt{b}, \mathtt{c}, \mathtt{d} \}$ qui n'ont pas la
    chaîne~$\mathtt{acdc}$ comme sous-séquence.  Par exemple, la
    chaîne $\mathtt{aabbccdd}$ est dans le langage mais pas la chaîne
    $\mathtt{dcbadcbadcba}$.

  \end{enumerate}

\mbox{}

\item \qpts{10} Supposons qu'on s'intéresse aux chaînes sur l'alphabet
  $\{ \mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d} \}$.  Supposons
  que, pour une raison quelconque, on souhaite distinguer les chaînes
  qui contiennent au moins une lettre qui se répète en deux positions
  successives.  Autrement dit, une chaîne avec répétition contient (au
  moins) l'une des sous-chaînes $\mathtt{aa}$, $\mathtt{bb}$,
  $\mathtt{cc}$ ou $\mathtt{dd}$.  Quand on identifie une chaîne qui
  contient une répétition quelque part, il faut produire le jeton
  \textbf{idRep}.  Sinon, quand on identifie une chaîne non-vide sans
  répétition, il faut produire le jeton \textbf{id}.  Donnez un ou des
  diagrammes de transition qui reconnaissent les motifs correspondant
  à ces jetons.

\mbox{}

\item \qpts{10} Dans les exercices reliés au chapitre~3 donnés sur le
  site web, on retrouve divers diagrammes de transition.  Transformez
  le dernier diagramme de la dernière page de ce document en fragment
  de code.  Par souci de simplicité, le diagramme est recopié ici.
  Pour produire le code, suivez la recette donnée vers la fin des
  notes de cours du chapitre~3.  Vous devez produire du code pour les
  sept états du diagramme.

  \begin{center}
    %% \fbox{%
      \scalebox{0.90}{%
        \includegraphics{page7.eps}%
      }%
    %% }
  \end{center}
  
\mbox{}

\item \qpts{10} Soit~$L_5$ le langage tiré de l'alphabet~$\{
  \mathtt{a}, \mathtt{b} \}$ qui contient les chaînes qui ont
  exactement deux fois plus de `$\mathtt{a}$' que de `$\mathtt{b}$'.
  Je propose la grammaire hors-contexte~$G_5$ ci-bas en prétendant
  qu'elle génère~$L_5$.  Faites une démonstration rigoureuse (par
  exemple, par induction) de~$L_5 \subseteq L(G_5)$; l'autre inclusion
  est triviale.
  \begin{eqnarray*}
      \makebox[0pt][r]{$G_5$:\qquad\qquad}
      S
    &
      \rightarrow
    &
      \epsilon
  \\
    &
      \mid
    &
      \mathtt{a} \, S \, \mathtt{a} \, S \, \mathtt{b}
  \\
    &
      \mid
    &
      \mathtt{a} \, S \, \mathtt{b} \, S \, \mathtt{a}
  \\
    &
      \mid
    &
      \mathtt{b} \, S \, \mathtt{a} \, S \, \mathtt{a}
  \\
    &
      \mid
    &
      S \, S
  \end{eqnarray*}
  \textbf{Indice:} Je vous suggère de considérer les bilans $f(v) =
  |v|_{\mathtt{a}} - 2|v|_{\mathtt{b}}$ pour les préfixes~$v$
  successifs d'un mot quelconque de~$L_5$.  La
  notation~$|v|_{\mathtt{a}}$ désigne le nombre de~`$\mathtt{a}$'
  dans~$v$; $|v|_{\mathtt{b}}$, le nombre de~`$\mathtt{b}$'.  Par
  exemple, la chaîne~$\mathtt{aaabab}$ est dans~$L_5$ et donne lieu à
  la suite de bilans~$0$, $1$, $2$, $3$, $1$, $2$ et~$0$.  Il faut
  noter que la suite de bilans doit commencer et finir par~$0$.
  Aussi, elle monte à coups de~$1$ et descend à coups de~$2$.

\mbox{}

\item \qpts{10} Considérons la grammaire du numéro précédent.  Donnez
  la dérivation à gauche d'abord, la dérivation à droite d'abord et
  l'arbre de dérivation pour la chaîne $\mathtt{abbaaa}$.

\mbox{}

\item \qpts{10} Considérons encore la même grammaire.  Dites si la
  grammaire est ambiguë.  Justifiez votre réponse à l'aide d'une
  démonstration ou d'un contre-exemple, selon que la grammaire est
  exempte d'ambiguïté ou pas.

\mbox{}

\item \qpts{10} Éliminez la récursion à gauche dans la grammaire
  suivante (inspirée de la syntaxe des expressions booléennes) en
  ordonnant les non-terminaux ainsi: $E$, $T$, $F$, $A$.  Décrivez en
  détail les étapes effectuées par l'algorithme (boucles sur~$i$
  et~$j$).

  \begin{eqnarray*}
    E & \rightarrow & E \, \textbf{ou} \, T \mid T
  \\
    T & \rightarrow & T \, \textbf{et} \, F \mid F
  \\
    F & \rightarrow & \textbf{non} \, F \mid A
  \\
      A
    &
      \rightarrow
    &
      ( \, E \, ) \mid \textbf{faux} \mid \textbf{vrai} \mid \textbf{id}
  \end{eqnarray*}

\mbox{}

\item \qpts{5} En imitant le pseudo-code présenté aux
  \mbox{pages~41--46} des notes de cours du chapitre~4, donnez
  l'implantation d'une fonction `\texttt{S()}' qui effectue l'analyse
  syntaxique descendante prédictive des chaînes générées par~$S$.
  Supposez que les fonctions `\textsf{\textit{peekToken}}' et
  `\textsf{\textit{readToken}}' sont fournies.
  \begin{eqnarray*}
      S
    &
      \rightarrow
    &
        \texttt{a} \, S \, \texttt{a}
      \mid
        \texttt{b} \, S \, \texttt{b}
      \mid
        \texttt{c}
  \end{eqnarray*}

\mbox{}

\item \qpts{5} À la façon de la page~48 des notes de cours du
  chapitre~4, donnez la trace des opérations effectuées par
  l'analyseur prédictif sans récursion sur la chaîne d'entrée
  $\mathtt{bbbaabdccddd}$.
  
  \begin{center}
  \begin{tabular}{@{}c|c|c|c|c|c@{}}
    \hline
    \hline
      \textsc{Non-}
    &
      \multicolumn{5}{c}{\textsc{Symbole d'entrée}}
  \\ \cline{2-6}
      \textsc{terminal}
    &
      $\mathtt{a}$
    &
      $\mathtt{b}$
    &
      $\mathtt{c}$
    &
      $\mathtt{d}$
    &
      $\$$
  \\ \hline
      $S$
    &
      $S \rightarrow \mathtt{a} \, S \, \mathtt{c}$
    &
      $S \rightarrow \mathtt{b} \, S \, \mathtt{d}$
    &
      $S \rightarrow \epsilon$
    &
      $S \rightarrow \epsilon$
    &
      $S \rightarrow \epsilon$
  \\ \hline
  \end{tabular}
  \end{center}

\mbox{}

\item \qpts{10} Considérons la grammaire de la question~5 à nouveau.
  Calculez les ensembles $\mathrm{FIRST}(S)$ et $\mathrm{FOLLOW}(S)$.

\mbox{}

\item \qpts{10} Considérons la grammaire suivante.  Les ensembles
  FIRST et FOLLOW sont précalculés.  Construisez la table d'analyse
  pour cette grammaire.

  \[
      \begin{array}{rcl}
        \strut & &
      \\
        A & \rightarrow & B \mid \mathtt{d} \, B
      \\
        B & \rightarrow & \mathtt{c} \, A \mid C \, \mathtt{b} \mid \mathtt{a}
      \\
        C & \rightarrow & \mathtt{a} \, B \mid \epsilon
      \end{array}
    \qquad\qquad
      \begin{array}{|c|c|c|}
      \hline
        \textbf{Non-term.} & \textrm{FIRST} & \textrm{FOLLOW}
      \\ \hline
          A
        &
          \{
            \mathtt{a},\,
            \mathtt{b},\,
            \mathtt{c},\,
            \mathtt{d}
          \}
        &
          \{
            \mathtt{b},\,
            \$
          \}
      \\
          B
        &
          \{
            \mathtt{a},\,
            \mathtt{b},\,
            \mathtt{c}
          \}
        &
          \{
            \mathtt{b},\,
            \$
          \}
      \\
          C
        &
          \{
            \mathtt{a},\,
            \epsilon
          \}
        &
          \{
            \mathtt{b}
          \}
      \\ \hline
      \end{array}
  \]

\end{enumerate}

\section*{Remise des travaux}

Vous devez remettre le travail dans la boîte de dépôt de
\textbf{monPortail} au plus tard le \textbf{25 février}.  Veuillez
ignorer la date de remise indiquée dans le plan de cours.  Les autres
modalités de remise demeurent telles que spécifiées dans le plan de
cours.

\end{document}
