Accueil
analyse-syntaxique.tex
analyse-syntaxique.tex
—
TeX document,
14Kb
Contenu du fichier
\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\paperwidth}{595pt}
\setlength{\hoffset}{-1in}
\setlength{\oddsidemargin}{60pt}
\setlength{\textwidth}{475pt}
\setlength{\marginparsep}{0pt}
\setlength{\marginparwidth}{0pt}
\setlength{\paperheight}{845pt}
\setlength{\voffset}{-1in}
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{60pt}
\setlength{\textheight}{725pt}
\setlength{\footskip}{30pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{multicol}
\usepackage{enumerate}
\usepackage{graphpap}
%\usepackage{graphics}
\usepackage{pstricks}
\usepackage{pst-node}
\usepackage{pst-tree}
\usepackage{rotating}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newlength{\largeurProd}\newlength{\largeurSP}
\setlength{\largeurProd}{12mm}\setlength{\largeurSP}{8mm}
\newcommand{\ETAT}[4]{\rput[tl](#2,#3){%
{\renewcommand{\arraystretch}{1.2}\begin{tabular}{l}
\ E$_{#1}$\\
\rnode{#1}{\begin{tabular}{|p{5mm}@{$\rightarrow\ $}p{\largeurProd}@{\{}p{\largeurSP}@{\}\ }|}
\hline
#4
\hline
\end{tabular}}
\end{tabular}}}}
\newcommand{\ETATSSP}[4]{\rput[tl](#2,#3){%
{\renewcommand{\arraystretch}{1.2}\begin{tabular}{l}
\ E$_{#1}$\\
\rnode{#1}{\begin{tabular}{|p{5mm}@{$\rightarrow\ $}p{\largeurProd}|}
\hline
#4
\hline
\end{tabular}}
\end{tabular}}}}
\newcommand{\ETATSSPF}[4]{\rput[tl](#2,#3){%
{\renewcommand{\arraystretch}{1.2}\begin{tabular}{l}
\ E$_{#1}$\\
\rnode{#1}{\framebox{\begin{tabular}{|p{5mm}@{$\rightarrow\ $}p{\largeurProd}|}
\hline
#4
\hline
\end{tabular}}}
\end{tabular}}}}
\newcommand{\eof}{\#}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\contentsname}{Sections}
\setcounter{tocdepth}{1}
\renewcommand{\theenumi}{\alph{enumi}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Analyse $LL$ versus analyse $LR$}
\author{S�stien VERBOIS}
\date{}
%Facult�universitaires Notre-Dame de la Paix\\
%Institut d'Informatique\\
%Janvier 2003}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section{Une grammaire}
\begin{multicols}{2}
\subsection{Grammaire originale}
$$
\begin{array}[t]{cl@{\ ::=\ }l}
(1) & S & 0S2\\
(2) & S & A\\
(3) & A & 1K\\
(4) & K & A\\
(5) & K & \epsilon\\
\end{array}
$$
\subsection{Grammaire augment�
$$
\begin{array}[t]{l@{\ ::=\ }l}
S'& S\\
S & 0S2 | A\\
A & 1K\\
K & A | \epsilon\\
\end{array}
$$
\end{multicols}
\section{Automate �ile}
\subsection{Automate caract�stique}
\begin{center}
\psset{unit=5mm,linewidth=\arrayrulewidth,arrowinset=0}
\setlength{\largeurProd}{12mm}\setlength{\largeurSP}{8mm}
%\framebox{
\begin{pspicture}(-1,-23)(30,0)
%\graphpaper[2](0,-24)(34,24)
\ETATSSP{00}{0}{0}{
S'& .S\\
}
\ETATSSPF{01}{8}{0}{
S'& S.\\
}
\ETATSSP{10}{0}{-4}{
S & .0S2\\
}
\ETATSSP{11}{8}{-4}{
S & 0.S2\\
}
\ETATSSP{12}{16}{-4}{
S & 0S.2\\
}
\ETATSSPF{13}{24}{-4}{
S & 0S2.\\
}
\ETATSSP{20}{0}{-8}{
S & .A\\
}
\ETATSSPF{21}{8}{-8}{
S & A.\\
}
\ETATSSP{30}{0}{-12}{
A & .1K\\
}
\ETATSSP{31}{8}{-12}{
A & 1.K\\
}
\ETATSSPF{32}{16}{-12}{
A & 1K.\\
}
\ETATSSP{40}{0}{-16}{
K & .A\\
}
\ETATSSPF{41}{8}{-16}{
K & A.\\
}
\ETATSSPF{50}{0}{-20}{
K & .\\
}
\ncline{->}{00}{01}
\ncput*[npos=0.5]{S}
\ncbar[angle=180,offsetA=0.2\psunit,armA=0.5\psunit]{->}{00}{10}\ncput*[npos=1.5]{$\epsilon$}
\ncbar[angle=180,offsetA=-0.2\psunit,armA=1.5\psunit]{->}{00}{20}\ncput*[npos=1.5]{$\epsilon$}
\ncline{->}{10}{11}
\ncput*[npos=0.5]{0}
\ncline{->}{11}{12}
\ncput*[npos=0.5]{S}
\ncbar[angle=90,offsetA=0,armA=1.5\psunit]{->}{11}{10}\ncput*[npos=1.5]{$\epsilon$}
\ncangle[angleA=-90,offsetA=0,armB=1.5\psunit,angleB=90]{->}{11}{20}\ncput*[npos=1.5]{$\epsilon$}
\ncline{->}{12}{13}
\ncput*[npos=0.5]{2}
\ncline{->}{20}{21}
\ncput*[npos=0.5]{A}
\ncline{->}{20}{30}
\ncput*[npos=0.5]{$\epsilon$}
\ncline{->}{30}{31}
\ncput*[npos=0.5]{1}
\ncline{->}{31}{32}
\ncput*[npos=0.5]{K}
\ncangle[angleA=-90,offsetB=\psunit,armB=1.5\psunit,angleB=90]{->}{31}{40}\ncput*[npos=1.5]{$\epsilon$}
\ncangles[angleA=-90,offsetA=\psunit,armA=1.5\psunit,armB=9\psunit,angleB=0]{->}{31}{50}\ncput*[npos=1.5]{$\epsilon$}
\ncline{->}{40}{41}
\ncput*[npos=0.5]{A}
\ncline{->}{40}{30}
\ncput*[npos=0.5]{$\epsilon$}
\end{pspicture}
%} % end of framebox
\end{center}
\subsection{Trace de l'analyse du mot 0011122}
Voir page suivante.
\begin{center}
\begin{sidewaystable}\begin{tabular}{l|r|c}
\hline
Pile & Entr�& Action \\
\hline
\eof$[ S' \to .S] $ & 0011122\eof & expand\\
\eof$[ S' \to .S][ S \to .0S2] $ & 0011122\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2] $ & 011122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to .0S2] $ & 011122\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2] $ & 11122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A]$ & 11122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to .1K]$ & 11122\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K]$ & 1122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A]$ & 1122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to .1K]$ & 1122\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K]$ & 122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .A]$ & 122\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .A][ A \to .1K]$ & 122\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .A][ A \to 1.K]$ & 22\eof & expand\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to .A][ A \to 1K.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1.K][ K \to A.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to .A][ A \to 1K.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1.K][ K \to A.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to .A][ A \to 1K.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0.S2][ S \to A.]$ & 22\eof & reduce\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0S.2]$ & 22\eof & shift\\
\eof$[ S' \to .S][ S \to 0.S2][ S \to 0S2.]$ & 2\eof & reduce\\
\eof$[ S' \to .S][ S \to 0S.2]$ & 2\eof & shift\\
\eof$[ S' \to .S][ S \to 0S2.]$ & \eof & reduce\\
\eof$[ S' \to S.]$ & \eof & ACCEPTER\\
\hline
\end{tabular}\end{sidewaystable}
\end{center}
\subsection{Arbre syntaxique}
\begin{center}
\psset{levelsep=1cm,nodesep=1mm,treemode=R}
\pstree{\TR{S}}{
\TR{2}
\pstree{\TR{S}}{
\TR{2}
\pstree{\TR{S}}{\pstree{\TR{A}}{
\pstree{\TR{K}}{\pstree{\TR{A}}{
\pstree{\TR{K}}{\pstree{\TR{A}}{
\pstree{\TR{K}}{\TR{$\epsilon$}}
\TR{1}
}}
\TR{1}
}}
\TR{1}
}}
\TR{0}
}
\TR{0}
}
\end{center}
\section{Analyse $LL$}
\subsection{Fonctions $PREMIER$ et $SUIVANT$}
\begin{multicols}{2}
\subsubsection{$PREMIER$}
$
\begin{array}[t]{l}
PREM(S)=\{0\}\cup PREM(A)=\{0,1\}\\
PREM(A)=\{1\}\\
PREM(K)=PREM(A) \cup \{\epsilon\} =\{1, \epsilon\}\\
\end{array}
$
\subsubsection{$SUIVANT$}
$
\begin{array}[t]{l}
SUIV(S)=\{2,\eof\}\\
SUIV(A)=SUIV(S)\cup SUIV(K)=\{2,\eof\}\\
SUIV(K)=SUIV(A)=\{2,\eof\}\\
\end{array}
$
\end{multicols}
\subsection{Table d'analyse $LL(1)$}
\begin{center}
\begin{tabular}{c|cccc}
\hline
Non & \multicolumn{4}{c}{Symbole de pr�sion}\\
\cline{2-5}
terminal & 0 & 1 & 2 &\eof\\
\hline
S & $S\to0S2$ & $S\to A$ & ERROR & ERROR \\
A & ERROR & $A\to1K$ & ERROR & ERROR \\
K & ERROR & $K\to A$ & $K\to\epsilon$ & $K\to\epsilon$ \\
\hline
\end{tabular}
\end{center}
\subsection{Trace de l'analyse $LL(1)$ du mot $0011122$}
\begin{center}
\begin{tabular}{l|r|l}
\hline
Pile & Entr�& Action \\
\hline
\eof S & 0011122\eof & expand $S\to0S2$ \\
\eof 2S0 & 0011122\eof & shift $0$ \\
\eof 2S & 011122\eof & expand $S\to0S2$ \\
\eof 22S0 & 011122\eof & shift $0$ \\
\eof 22S & 11122\eof & expand $S\to A$\\
\eof 22A & 11122\eof & expand $A\to1K$\\
\eof 22K1 & 11122\eof & shift $1$\\
\eof 22K & 1122\eof & expand $K\to A$\\
\eof 22A & 1122\eof & expand $A\to1K$\\
\eof 22K1 & 1122\eof & shift $1$\\
\eof 22K & 122\eof & expand $K\to A$\\
\eof 22A & 122\eof & expand $A\to1K$\\
\eof 22K1 & 122\eof & shift $1$\\
\eof 22K & 22\eof & expand $K\to\epsilon$\\
\eof 22 & 22\eof & shift $2$\\
\eof 2 & 2\eof & shift $2$\\
\eof & \eof & ACCEPTER\\
\hline
\end{tabular}
\end{center}
\subsection{D�vation correspondante}
$$
\begin{array}{ll}
S & \stackrel{g}{\Rightarrow} 0S2\stackrel{g}{\Rightarrow}00S22\stackrel{g}{\Rightarrow}
00A22\stackrel{g}{\Rightarrow}001K22\stackrel{g}{\Rightarrow}001A22
\\
& \stackrel{g}{\Rightarrow} 0011K22 \stackrel{g}{\Rightarrow}
0011A22\stackrel{g}{\Rightarrow}00111K22\stackrel{g}{\Rightarrow}0011122
\\
\end{array}
$$
\section{Analyse $LR$}
\subsection{D�rminisation de l'automate caract�stique}
$$
\begin{array}{lll}
E_0:= \varepsilon \text{Ferm}([S'\to.S]) %= \{[S'\to.S],[S\to.0S2],[S\to.A],[A\to.1K]\}
&\hspace{1.5cm}&
\\
\delta(E_0,S)=\varepsilon\text{Ferm}(\text{Trans}(E_0,S)) =: E_1
&&
\delta(E_2,A)=\varepsilon\text{Ferm}(\text{Trans}(E_2,A)) = E_3
\\
\delta(E_0,0)=\varepsilon\text{Ferm}(\text{Trans}(E_0,0)) =: E_2
&&
\delta(E_2,1)=\varepsilon\text{Ferm}(\text{Trans}(E_2,1)) = E_4
\\
\delta(E_0,A)=\varepsilon\text{Ferm}(\text{Trans}(E_0,A)) =: E_3
&&
\delta(E_4,K)=\varepsilon\text{Ferm}(\text{Trans}(E_4,K)) =: E_6
\\
\delta(E_0,1)=\varepsilon\text{Ferm}(\text{Trans}(E_0,1)) =: E_4
&&
\delta(E_4,A)=\varepsilon\text{Ferm}(\text{Trans}(E_4,A)) =: E_7
\\
\delta(E_2,S)=\varepsilon\text{Ferm}(\text{Trans}(E_2,S)) =: E_5
&&
\delta(E_4,1)=\varepsilon\text{Ferm}(\text{Trans}(E_4,1)) = E_4
\\
\delta(E_2,0)=\varepsilon\text{Ferm}(\text{Trans}(E_2,0)) = E_2
&&
\delta(E_5,2)=\varepsilon\text{Ferm}(\text{Trans}(E_5,2)) =: E_8
\\
\end{array}
$$
\subsection{Automate $LR(0)$}
\begin{center}
\psset{unit=5mm,linewidth=\arrayrulewidth,arrowinset=0}
\setlength{\largeurProd}{12mm}\setlength{\largeurSP}{8mm}
%\framebox{
\begin{pspicture}(-1,-18)(28,0)
%\graphpaper[2](0,-24)(34,24)
\ETATSSP{0}{0}{0}{
S'& .S\\
\hline
S & .0S2\\
S & .A\\
A & .1K\\
}
\ETATSSPF{1}{11}{0}{
S'& S.\\
}
\ETATSSP{2}{11}{-7}{
S & 0.S2\\
\hline
S & .0S2\\
S & .A\\
A & .1K\\
}
\ETATSSPF{3}{11}{-3}{
S & A.\\
}
\ETATSSPF{4}{0}{-7}{
A & 1.K\\
\hline
K & .A\\
K & .\\
A & .1K\\
}
\ETATSSP{5}{22}{-10}{
S & 0S.2\\
}
\ETATSSPF{6}{0}{-14}{
A & 1K.\\
}
\ETATSSPF{7}{11}{-14}{
K & A.\\
}
\ETATSSPF{8}{22}{-14}{
S & 0S2.\\
}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{0}{1}
\ncput*[npos=2.5]{S}
\ncangles[angleA=-90,offsetA=1\psunit,angleB=180,offsetB=\psunit,armB=2\psunit]{->}{0}{2}
\ncput*[npos=1.5]{0}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{0}{3}
\ncput*[npos=2.5]{A}
\ncline{->}{0}{4}
\ncput*[npos=0.5]{1}
\ncangle[angleA=-90,offsetA=-\psunit,angleB=-90,offsetB=-\psunit,armB=\psunit]{->}{2}{2}
\ncput*[npos=1.5]{0}
\ncline{->}{2}{3}
\ncput*[npos=0.5]{A}
\ncline{->}{2}{4}
\ncput*[npos=0.5]{1}
\ncangles[angleA=0,armA=0,angleB=180,armB=0]{->}{2}{5}
\ncput*[npos=2.5]{S}
\ncangle[angleA=180,offsetA=-\psunit,angleB=180,offsetB=-\psunit,armB=\psunit]{->}{4}{4}
\ncput*[npos=1.5]{1}
\ncline{->}{4}{6}
\ncput*[npos=0.5]{K}
\ncangles[angleA=0,armA=2\psunit,offsetA=-\psunit,angleB=180,offsetB=0]{->}{4}{7}
\ncput*[npos=1.5]{A}
\ncline{->}{5}{8}
\ncput*[npos=0.5]{2}
\end{pspicture}
%} % end of framebox
\end{center}
\subsection{Calcul de $SUIVANT$}
\begin{multicols}{3}
\begin{itemize}
\item $SUIV(S)=\{\eof, 2\}$
\item $SUIV(A)=\{\eof, 2\}$
\item $SUIV(K)=\{\eof, 2\}$
\end{itemize}
\end{multicols}
\subsection{Table d'analyse $SLR(1)$}
\begin{center}
\begin{tabular}{c|cccc|ccc}
\hline
Etat & \multicolumn{4}{c|}{Action} & \multicolumn{3}{c}{Successeur}\\
\cline{2-8}
n\textsuperscript{o} & 0 & 1 & 2 &\eof& A & K & S \\
\hline
0 & s2 & s4 & & & 3 & & 1 \\
1 & & & & A & & & \\
2 & s2 & s4 & & & 3 & & 5 \\
3 & & & r2 & r2 & & & \\
4 & & s4 & r5 & r5 & 7 & 6 & \\
5 & & & s8 & & & \\
6 & & & r3 & r3 & & \\
7 & & & r4 & r4 & & \\
8 & & & r1 & r1 & & \\
\hline
\end{tabular}
\end{center}
\subsection{Trace de l'analyseur $SLR(1)$ sur $0011122$}
\begin{center}
\begin{tabular}{l|r|r}
\hline
Pile & Entr�& Action \\
\hline
\eof$E_0$ & 0011122\eof & shift $E_2$ \\
\eof$E_0$ 0 $E_2$ & 011122\eof & shift $E_2$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ & 11122\eof & shift $E_4$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ & 1122\eof & shift $E_4$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ 1 $E_4$ & 122\eof & shift $E_4$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ 1 $E_4$ 1 $E_4$ & 22\eof & reduce $K\to\epsilon$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ 1 $E_4$ 1 $E_4$ K $E_6$ & 22\eof & reduce $A\to1K$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ 1 $E_4$ A $E_7$ & 22\eof & reduce $K\to A$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ 1 $E_4$ K $E_6$ & 22\eof & reduce $A\to1K$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ A $E_7$ & 22\eof & reduce $K\to A$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ 1 $E_4$ K $E_6$ & 22\eof & reduce $A\to 1K$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ A $E_3$ & 22\eof & reduce $S\to A$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ S $E_5$ & 22\eof & shift $E_8$ \\
\eof$E_0$ 0 $E_2$ 0 $E_2$ S $E_5$ 2 $E_8$ & 2\eof & reduce $S\to 0S2$\\
\eof$E_0$ 0 $E_2$ S $E_5$ 2 & \eof & shift $E_8$ \\
\eof$E_0$ 0 $E_2$ S $E_5$ 2 $E_8$ & \eof & reduce $S\to 0S2$\\
\eof$E_0$ S $E_1$ & \eof & ACCEPTER\\
\hline
\end{tabular}
\end{center}
\subsection{R�ction correspondante}
$$
\begin{array}{ll}
0011122 & \stackrel{d}{\Leftarrow} 00111K22 \stackrel{d}{\Leftarrow}0011A22
\stackrel{d}{\Leftarrow} 0011K22 \stackrel{d}{\Leftarrow}001A22
\\
&\stackrel{d}{\Leftarrow} 001K22 \stackrel{d}{\Leftarrow} 00A22
\stackrel{d}{\Leftarrow} 00S22 \stackrel{d}{\Leftarrow} 0S2
\stackrel{d}{\Leftarrow} S
\\
\end{array}
$$
\end{document}
