doc/algo.tex


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

\chapter{Algorithmes mis en {\oe}uvre}
\paragraph{}
Le parser va tenter d'analyser une ligne et en sortir une pile polonaise inversée. Pour cela, il dispose
de quelques fonctions atomiques:
\begin{itemize}
\item push\_pile()
\item act\_pile()
\end{itemize}

qui sont des fonctions externes

\begin{itemize}
\item getword()
\item push\_op()
\item pop\_op()
\end{itemize}

qui sont des fonctions internes au parser. La fonction getword() est très intéressante car elle est
capable de sortir le premier mot de la chaîne passée en argument. Elle va faire la différence entre opérande et opérateur,
tout en ignorant les espaces et les tabulations. A partir de ce moment-là, la fonction parse\_pile n'a plus qu'un travail réduit.
Elle va lire la chaîne d'entrée mot par mot et en dégager au fur et à mesure deux piles, une d'opérandes (a l'aide de
push\_pile) et une d'opérateurs (à l'aide de push\_op). Au fur et a mesure de l'évaluation, elle va faire appel a act\_pile() afin
de vider sa pile d'opérateurs.
\paragraph{}
La manière dont le parser va empiler ou dépiler dépend simplement des opérateurs rencontrés. Il empile toutes les opérandes
rencontrées, sans distinction. Il va empiler tout opérateur sur sa pile d'opérateurs si le dernier opérateur a une priorité
inférieure. Sinon, il dépile le premier opérateur de la pile et l'envoie à act\_pile(). Il répète l'opération tant qu'il peut.
\paragraph{}
L'usage des parenthèses est très simple: la parenthèse gauche est considérée comme l'opérateur de plus haute priorité. Du coup,
chaque opérateur présent avant est dépilé. Par contre, une fois empilé, il est considéré comme étant l'opérateur de plus
petite priorité. Ainsi, chaque opérateur suivant est empilé directement. Lors d'une parenthèse droite, on dépile tout jusqu'à
ce que l'on rencontre une parenthèse gauche.
\paragraph{}
Lors d'une fin de ligne, tous les opérateurs restant sont vidés dans act\_pile().
\paragraph{}
Ainsi l'expression:
\begin{verbatim}
x + y * (z - t) + u
\end{verbatim}
est évaluée suivant la série d'appels:
\begin{verbatim}
push\_pile(x);
push\_pile(y);
push\_pile(z);
push\_pile(t);
act\_pile(-);
act\_pile(*);
act\_pile(+);
push\_pile(u);
act\_pile(+);
\end{verbatim}