Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

m1ilc:compil_3 [2009/10/09 18:52]
suitable créée
m1ilc:compil_3 [2010/01/05 06:39] (Version actuelle)
suitable
Ligne 2: Ligne 2:
 ===== Analyse Syntaxique (2) ===== ===== Analyse Syntaxique (2) =====
  
 +==== Analyse Ascendante ====
  
-==== Analyse Descendante (fin) ====+Ceci conduit à des analyseurs plus puissants au sens où elle réussit avec un sur-ensemble stricte de grammaires.
  
-=== Utilisation de FIRST & FOLLOW  ====+=== Exemple ===
  
-Pour construire la table d'analyse avec FIRST et FOLLOW, l'idée est que pour toute règle de grammaire <jsm>A \rightarrow \alpha</jsm>, si <jsm>\alpha\in FIRST(A)</jsm> alors on va utiliser cette règle pour développer A par <jsm>\alpha</jsm> quand le token courant dans la chaine est <jsm>\alpha</jsm>.  Une complication arrive lorsque <jsm>\alpha = \epsilon</jsm> ou bien <jsm>\alpha \Rightarrow^* \epsilon</jsm>; dans ce cas, on doit également développer A par <jsm>\alpha</jsm> si le token courant dans la chaine est un élément de FOLLOW(A).+La grammaire G0 mais sans la multiplication
  
-== Calcul des ensembles FIRST &ampFOLLOW ==+  - E -&gtE + T 
 +  - E -> T 
 +  - T -> (E) 
 +  - T -> id
  
-  * Pour calculer FIRST(X): +Analyse de la chaine ''id + (id + id )'' 
-    * si X est un terminal, FIRST(X) = {X} +On s'aide d'un pile pour mémoriser les parties de l'arbre en cours de construction.
-    * si X est un non-terminal, pour toutes les règles de la forme <jsm>X\rightarrow X_1 X_2 \ldots X_n</jsm> ajouter <jsm>FIRST\left(X_1 X_2 \ldots X_n\right)</jsm> +
-  * Pour calculer/construire <jsm>FIRST\left(X_1 X_2 \ldots X_n\right)</jsm>,  +
-    * ajouter <jsm>FIRST\left(X_1\right)</jsm> +
-    * si <jsm>\epsilon \in FIRST\left(X_1\right)</jsm> ajouter <jsm>FIRST\left(X_2\right)</jsm> +
-    * si <jsm>\epsilon \in FIRST\left(X_1\right)\cap FIRST\left(X_2\right)</jsm> ajouter <jsm>FIRST\left(X_3\right)</jsm> +
-    * ... +
-    * si <jsm>\epsilon\in \cap_{i=1}^{n-1} FIRST\left(X_i\right)</jsm> ajouter <jsm>FIRST\left(X_n\right)</jsm>+
  
-== Démonstration ==+FIXME page de l'exemple à saisir (28/9 # 4)
  
-| FIRST(F) | ={ | (, id | } | +=== Algorithme naïf ===
-| FIRST(T') | ={ | *, e | } | +
-| FIRST(T)=FIRST(F) | ={ | (, id | } | +
-| FIRST(E') | ={ | +, e | } | +
-| FIRST(E)=FIRST(T) | ={ | (, id | } |+
  
-Pour calculer FOLLOW +... par décalages et réductions. 
-  * mettre ''$'' dans FOLLOW(S) + 
-  * s'il existe une règle de la forme <jsm>A\rightarrow \alpha B \beta</jsm> mettre +A chaque étape on examine les premeiers éléments au sommet de la pile ; ce doit être le préfixe  de la partie droite d'une ou plusieurs règles (notion de préfixe viable). 
 + 
 +  * Si aucun préfixe n'est la partie droite d'une règle de grammaire, alors "shift" : on avance dans la chaine et on empile le token courant. 
 +  * Sinon, on choisit entre shift et reduce. Si on choisit reduce, on choisit un préfixe qui est la partie droite d'une règle, on dépile la partie droite de cette règle et on empile la partie gauce. 
 +  * on repète ceci avec des retours arrières jusqu'à ce que la pile ne contienne que et qu'il n'y ait plus de token à lire. 
 + 
 +=== Problèmes Rencontrés === 
 + 
 +  * Comment choisir entre ''shift'' et ''reduce''? 
 +  * Comment choisir entre ''redue'' et ''reduce''? 
 + 
 +La décision entre shift et reduce doit prendre en compte non seulement le token courant--le sommet de la pile--mais aussi le contenu de toute la pile! __Solution__ : on introduit des états qui représentent l'information de toute la pile. 
 + 
 +=== Principe de l'analyse LR === 
 + 
 +L'algorithme (famille d'algorithmes) utilise  
 +  * un pointeur sur la chaine (suffixée par $) 
 +  * une pile avec des états : un état est une description du contenu de la pile pour que la question du choix ''shift/reduce'' ne se pose plus. Le contenu de la pile (à l'horizontale) est :<jsmath> 
 +s_0 x_1 s_1 x_2\ldots x_m sm 
 +</jsmath> où les <jsm>s_i</jsm> sont des états, et les <jsm>x_i</jsm> sont des éléments de <jsm>V \cup \Sigma \cup\left\{ $ \right\}</jsm> 
 +  * une table d'analyse qui comporte 2 parties 
 +    * une table ACTION indexée par les états (en ligne) et les terminaux (y compris $) en colonne.  ACTION[s<sub>i</sub>, a] peut contenir '''shift s<sub>j</sub>'' où s<sub>j</sub> est un état, ou ''reduce  r<sub>k</sub>'' où r<sub>k</sub> est une règle de grammaire, ou "erreur". 
 +    * une table GOTO indexée par les états (lignes) et non-terminaux (colonnes). GOTO[ s<sub>i</sub>, A] est intuitivement le nouvel état à empiler. 
 +     
 +Initialement le pointeur pointe sur le 1° élément de la chaine et la pile contient s<sub>0</sub>. 
 + 
 +A chaque itération, on examine l'élément ACTION[s<sub>m</sub>, a] où s<sub>m</sub> est l'état au sommet de la pile, ''a'' est l'élément courant de la chaine.  On réalise le traitement suivant : 
 +  * si cet élément est ''shift s'' alors on empile ''a'' pis ''s'' et on avance le pointeur dans la chaine. 
 +  * si cet élément est "reduce k"" alors on trouve la longueur l de la partie droite de la règle #k et on dépile 2*l éléments de la pile puis empile ''A'' puis ''GOTO[s<sub>m-l</sub>, A]''. 
 +  * sinon : terminer : cet élément est soit "accepté" soir "erreur". 
 + 
 +Tous les analyseurs LR fonctionnent selon ce principe.  Ils ne diffèrent entre eux que par la facons de définir et calculer les états (et tables). Nous verrons par la suite: 
 +  * l'analyse SLR (simple LR) ainsi nommé parce qu'elle est simple à implémenter et elle est la moins puissante. Les autres utilisent de l'information de prévision. 
 +  * l'analyse LR(1), la plus puissante mais aussi la plus couteuse. 
 +  * l'analyse LALR(1) offre un bon compromis puissance/cout.  Yacc et bison créent des analyseurs LaLR(1).
  
-==== Analyse Ascendante ==== 
  
-FIXME incomplet, à terminer 
  
----- +==== Navigation ====
-==== Amont Avale ====+
  
-[[compil_2|<= cours précedent]] -\- [[compil_4| cours suivant =>]]+[[compil_ii_2|<= Analyse LL(1)]] -\- [[compil_4| Analyse SLR(1) cours suivant =>]]
 
m1ilc/compil_3.txt · Dernière modification: 2010/01/05 06:39 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki