==== SLR (suite) ==== === Construction de la Table d'Analyse === 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 | | | | * FOLLOW(E) = {+,),%%$%% } * FOLLOW(T) = {*, +, ), %%$%% } = FOLLOW(E) $\cup$ {*} * FOLLOW(F} = FOLLOW(T) ==== Analyse LR(1) ==== 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. === Opération de Fermeture === 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 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. === Opération GOTO === 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) == Exemple avec une plus petite grammaire == ---- ===== Navigation ===== [[compil_3| <= cours précédent ]] -/- [[compil_5| cours suivant =>]]