D'abord on calcule les états:
\begin{eqnarray}
goto\left(s_0 ,E \right) & = & \left\{E\prime\rightarrow E\cdot , E\prime\rightarrow E\cdot +T\right\} & = & s_1 \\
goto\left(s_0 , T\right) & = & \left\{E\rightarrow T\cdot,T\rightarrow T\cdot *F \right\} & = & s_2 \\
goto\left(s_0 , F ? \right) & = & \left\{T\rightarrow F\cdot \right\} & = & s_3 \\
goto\left(s_0 , ( ?\right) & = & \left\{F\rightarrow (\cdot E), E\rightarrow \cdot E+T,E\rightarrow \cdot T, T\rightarrow \cdot T*F, T\rightarrow \cdot F,F\rightarrow \cdot (E), F\rightarrow id\right\} & = & s_4 \\
goto\left(s_0 , id \right) & = & \left\{F\rightarrow id\cdot \right\} & = & s_5 \\
goto\left(s_1 , +\right) & = & \left\{E\rightarrow E+\cdot T, T\rightarrow \cdot T*F, T\rightarrow \cdot F, F\rightarrow \cdot (E), F\rightarrow id \right\} & = & s_6 \\
goto\left(s_2 , *\right) & = & \left\{T\rightarrow T*\cdot F, F\rightarrow \cdot (E),F\rightarrow\cdot id \right\} & = & s_7 \\
goto\left(s_4 , T\right) & = & \left\{ \right\} & = & s_2 \\
goto\left(s_4 , F\right) & = & \left\{ \right\} & = & s_3 \\
goto\left(s_4 , '(' \right) & = & \left\{ \right\} & = & s_4 \\
goto\left(s_4 , id\right) & = & \left\{ \right\} & = & s_5 \\
goto\left(s_4 , E \right) & = & \left\{F\rightarrow (E\cdot ), E\rightarrow E\cdot +T \right\} & = & s_8 \\
goto\left(s_6 , T\right) & = & \left\{ E\rightarrow E+T\cdot , T\rightarrow T\cdot *F\right\} & = & s_9 \\
goto\left(S_6 , F\right) & = & \left\{ \right\} & = & s_3 \\
goto\left(s_6 , '('\right) & = & \left\{ \right\} & = & s_4 \\
goto\left(s_6 , id\right) & = & \left\{ \right\} & = & s_5 \\
goto\left(s_7 , F\right) & = & \left\{T\rightarrow T*F\cdot \right\} & = & s_{10} \\
goto\left(s_7 ,'(' \right) & = & \left\{ \right\} & = & s_4 \\
goto\left(s_7 , id\right) & = & \left\{ \right\} & = & s_5 \\
goto\left(s_8 , ')'\right) & = & \left\{F\rightarrow (E)\cdot \right\} & = & s_{11} \\
goto\left(s_8 , + \right) & = & \left\{ \right\} & = & s_6 \\
goto\left(s_9 , * \right) & = & \left\{ \right\} & = & s_7 \\
\end{eqnarray}
On commence par placer acc
dans la colonne $ de la ligne correspondante à l'état qui contient S' → S.
On place les reduce
: pour chaque état s, on recherche une règle de la form A \rightarrow \alpha et on place reduce
de cette règle dans la case ACTION[s,a] pour tout a\in FOLLOW\left(A\right)
On place les shift
: à chaque fois qu'on a S'=GOTO[s,X] on place shift s'
dans la case GOTO[s,X].
| ACTION | GOTO |
| id | + | * | ( | ) | $ | E | T | F |
s0 | s5 | | | s4 | | | 1 | 2 | 3 |
s1 | | s6 | | | | acc | | | |
s2 | | R2 | s7 | | R2 | R2 | | | |
s3 | | R4 | R4 | | R4 | R4 | | | |
s4 | s5 | | | s4 | | | 8 | 2 | 3 |
s5 | | R6 | R6 | | R6 | R6 | | | |
s6 | s5 | | | s4 | | | | 9 | 3 |
s7 | s5 | | | s4 | | | | | 10 |
s8 | | s6 | | | s11 | | | | |
s9 | | R1 | s9 | | R1 | R1 | | | |
s10 | | R3 | R3 | | R3 | R3 | | | |
s11 | | R5 | R5 | | R5 | R5 | | | |
On redéfinit les états en s'appuyant sur la notion de règle pointée augmentée : un couple formé d'une règle pointée et d'un symbole terminal autre que $, le look ahead.
Exemple : \left[ A\rightarrow\alpha\cdot \beta , a\right]
Le look-ahead n'est utile que lorsque \beta = \epsilon, il permet à l'analyseur d'éviter de se tromper en signifiant que la règle A\rightarrow \alpha ne peut être utilisée que lorsque le prochain token est a
.
On déduit une nouvelle définition des opérations de fermeture et goto.
sur les règles pointées augmentées.
Intuitivement, comme pour l'analyse SLR, si la règle \left[A\rightarrow \alpha \cdot B\beta,a\right]\in S</jsm> et s'il existe une règle B\rightarrow \gamma, alors on doit ajouter à S la règle pointée B\rightarrow \cdot\gamma (avec un certain look-ahead). Le look-ahead sera 'a' si \beta = \epsilon ou bien \in FIRST\left(\beta a\right) sinon.
sur les règles pointées augmentées.
Par définition, GOTO(s,X) est la fermeture de l'ensemble des règles \left[ A\rightarrow \alpha X\cdot \beta , a\right] telles que \left[ A\rightarrow \alpha X\cdot \beta , a\right]\in S, et S_0 = fermeture\left(\left[S\prime\rightarrow S, dollar \right]\right)