automate-8.tex

Contenu du fichier

\newpage
\section{Une grammaire $LR(1)$ non $LALR(1)$}
\begin{multicols}{2}
\subsection{Grammaire originale}
$$
\begin{array}[t]{l@{\ ::=\ }l}
S & aAd | aBe | bAe | bBd\\
A & c\\
B & c\\
\end{array}
$$
\subsection{Grammaire augment�
$$
\begin{array}[t]{l@{\ ::=\ }l}
S'& S\\
S & aAd | aBe | bAe | bBd\\
A & c\\
B & c\\
\end{array}
$$
\end{multicols}

\subsection{Automate $LR(0)$ avec symboles de pr�ision $LALR(1)$}
\begin{center}
\psset{unit=5mm,linewidth=\arrayrulewidth,arrowinset=0}
\setlength{\largeurProd}{10mm}\setlength{\largeurSP}{4mm}
%\framebox{
\begin{pspicture}(2,-15)(36,-1)
%\graphpaper[2](0,-20)(34,24)

\ETAT{0}{0}{-4}{
S'& .S    & \eof\\
\hline
S & .aAd & \eof\\
S & .aBe & \eof\\
S & .bAe & \eof\\
S & .bBd & \eof\\

}
\ETAT{1}{0}{-13}{
S'& S.    & \eof\\
}
\ETAT{2}{10}{-1}{
S & a.Ad & \eof\\
S & a.Be & \eof\\
\hline
A & .c & d\\
B & .c & e\\
}
\ETAT{3}{10}{-8}{
S & b.Ae & \eof\\
S & b.Bd & \eof\\
\hline
A & .c & e\\
B & .c & d\\
}
\ETAT{4}{20}{0}{
S & aA.d & \eof\\
}
\ETAT{5}{20}{-3}{
S & aB.e & \eof\\
}
\setlength{\largeurProd}{8mm}\setlength{\largeurSP}{6mm}
\ETAT{6-9}{20}{-6}{
A & c. & d,e\\
B & c. & e,d\\
}
\setlength{\largeurProd}{10mm}\setlength{\largeurSP}{4mm}
\ETAT{7}{20}{-10}{
S & bA.e & \eof\\
}
\ETAT{8}{20}{-13}{
S & bB.d & \eof\\
}

\ETAT{10}{30}{0}{
S & aAd. & \eof\\
}
\ETAT{11}{30}{-3}{
S & aBe. & \eof\\
}
\ETAT{12}{30}{-10}{
S & bAe. & \eof\\
}
\ETAT{13}{30}{-13}{
S & bBd. & \eof\\
}

\ncline{->}{0}{1}
\ncput*[npos=0.5]{S}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{0}{2}
\ncput*[npos=1.5]{a}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{0}{3}
\ncput*[npos=1.5]{b}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{2}{4}
\ncput*[npos=1.5]{A}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{2}{5}
\ncput*[npos=2.5]{B}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{2}{6-9}
\ncput*[npos=1.5]{c}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{3}{6-9}
\ncput*[npos=1.5]{c}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{3}{7}
\ncput*[npos=2.5]{A}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{3}{8}
\ncput*[npos=1.5]{B}
\ncline{->}{4}{10}
\ncput*[npos=0.5]{d}
\ncline{->}{5}{11}
\ncput*[npos=0.5]{e}
\ncline{->}{7}{12}
\ncput*[npos=0.5]{e}
\ncline{->}{8}{13}
\ncput*[npos=0.5]{d}
\end{pspicture}
%} %end of framebox
\end{center}


\subsection{Automate $LR(1)$}
\begin{center}
\psset{unit=5mm,linewidth=\arrayrulewidth,arrowinset=0}
\setlength{\largeurProd}{10mm}\setlength{\largeurSP}{4mm}
%\framebox{
\begin{pspicture}(2,-21)(36,0)
%\graphpaper[2](0,-24)(34,24)

\ETAT{0}{0}{-7}{
S'& .S    & \eof\\
\hline
S & .aAd & \eof\\
S & .aBe & \eof\\
S & .bAe & \eof\\
S & .bBd & \eof\\

}
\ETAT{1}{0}{-16}{
S'& S.    & \eof\\
}
\ETAT{2}{10}{-1}{
S & a.Ad & \eof\\
S & a.Be & \eof\\
\hline
A & .c & d\\
B & .c & e\\
}
\ETAT{3}{10}{-13}{
S & b.Ae & \eof\\
S & b.Bd & \eof\\
\hline
A & .c & e\\
B & .c & d\\
}
\ETAT{4}{20}{0}{
S & aA.d & \eof\\
}
\ETAT{5}{20}{-3}{
S & aB.e & \eof\\
}
\ETAT{6}{20}{-6}{
A & c. & d\\
B & c. & e\\
}
\ETAT{7}{20}{-15}{
S & bA.e & \eof\\
}
\ETAT{8}{20}{-18}{
S & bB.d & \eof\\
}
\ETAT{9}{20}{-11}{
A & c. & e\\
B & c. & d\\
}
\ETAT{10}{30}{0}{
S & aAd. & \eof\\
}
\ETAT{11}{30}{-3}{
S & aBe. & \eof\\
}
\ETAT{12}{30}{-15}{
S & bAe. & \eof\\
}
\ETAT{13}{30}{-18}{
S & bBd. & \eof\\
}

\ncline{->}{0}{1}
\ncput*[npos=0.5]{S}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{0}{2}
\ncput*[npos=1.5]{a}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{0}{3}
\ncput*[npos=1.5]{b}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{2}{4}
\ncput*[npos=1.5]{A}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{2}{5}
\ncput*[npos=2.5]{B}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{2}{6}
\ncput*[npos=1.5]{c}
\ncangles[angleA=0,offsetA=\psunit,armA=2\psunit,angleB=180,armB=0]{->}{3}{9}
\ncput*[npos=1.5]{c}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{3}{7}
\ncput*[npos=2.5]{A}
\ncangles[angleA=0,offsetA=-\psunit,armA=2\psunit,angleB=180,armB=0]{->}{3}{8}
\ncput*[npos=1.5]{B}
\ncline{->}{4}{10}
\ncput*[npos=0.5]{d}
\ncline{->}{5}{11}
\ncput*[npos=0.5]{e}
\ncline{->}{7}{12}
\ncput*[npos=0.5]{e}
\ncline{->}{8}{13}
\ncput*[npos=0.5]{d}
\end{pspicture}
%} %end of framebox
\end{center}