Théorie des langages : Cours analyse syntaxique
Télécharger PDFCH.3 L'ANALYSE SYNTAXIQUE • 2.1 Le rôle de l’analyseur syntaxique • 2.2 Les grammaires • 2.3 L’analyse descendante • 2.4 L’analyse ascendante 1 RI 2013/2014 A. MERAZI Rôle central de la partie frontale : active l’analyseur lexical; vérifie la conformité syntaxique; construit l’arbre d’analyse ; prépare ou anticipe la traduction ; gère les erreurs communes de syntaxe. programme source analyseur lexical analyseur syntaxique table des symboles unité lexicale (sur requête) arbre d’analyse Le rôle de l’analyseur syntaxique 2 RI 2013/2014 A. MERAZI Rôle de l’analyseur syntaxique Détection des erreurs de syntaxe : En plus de découvrir la structure arborescente du texte source, l’analyseur syntaxique doit aussi détecter les portions de textes invalides en signalant des erreurs de syntaxe. Exemples d’erreurs syntaxiques dans C : Oubli d’un point virgule. Oubli du parenthèse ouvrante après le for. Manque d’une expression après l’opérateur *. 3 RI 2013/2014 A. MERAZI Rôle de l’analyseur syntaxiqueRôle de l’analyseur syntaxique Détection des erreurs de syntaxe : Illustrons quelques exemples d’erreurs syntaxiques en C : a = 5 + 6 // " ; " point virgule manquant for i = 5; i < 12; i++) // " ( " manquante a = b + c - 5 *; // expression manquante = 12 + 5; // identificateur manquant a = = 3; // expression invalide 4 RI 2013/2014 A. MERAZI Rôle de l’analyseur syntaxiqueRôle de l’analyseur syntaxique Outils pour l’analyse syntaxique : L’analyseur lexical se base sur les expressions régulières et les automates finis déterministes pour rechercher les jetons à partir du fichier source. L’analyseur syntaxique utilise la grammaire du langage pour combiner les jetons en unités syntaxiques. 5 RI 2013/2014 A. MERAZI L'analyseurL'analyseur syntaxiquesyntaxique Étant donné un mot terminal, déterminer s’il est ou non engendré par la grammaire ; si oui, en donner un arbre d’analyse. •Deux catégories d'analyseurs syntaxiques: –Descendant – produit l'arbre syntaxique en commençant par la racine –Ascendant – commence par les feuilles Dans les deux cas on utilise une grammaire hors-
contexte comme description du langage. 1-6 RI 2013/2014 A. MERAZI L'analyseurL'analyseur syntaxiquesyntaxique (suite)(suite) •Parseurs descendants –On commence avec le symbole de départ et on détermine la séquence de règles nécessaires pour dériver l'entrée (suite de token)
<départ> entrée •Algorithme LL: –Left-to-right scan (lecture de l'entrée de gauche à droite) –Leftmost derivation (dérivation par la gauche) 1-7 RI 2013/2014 A. MERAZI L'analyseurL'analyseur syntaxiquesyntaxique (suite)(suite) •Parseurs ascendants –On commence avec l'entrée et on applique à rebours les règles de la grammaire afin d'obtenir la symbole de départ.
entrée <départ> •Algorithme LR: •Left-to-right scan •Rightmost derivation 1-8 RI 2013/2014 A. MERAZI Les grammaires Syntaxe spécifiée par des règles de grammaire. • Symboles terminaux (= unités lexicales) alphabet T ; • Symboles non terminaux(= catégories grammaticales) alphabet V ; V T = . • P={Règles de grammaire x w , où x V et où w (TV)* w est un mot quelconque, même vide.} • Exemples : instr si expr alors instr sinon instr phrase gsujet gverbe gcomplément • Axiome S (= programme), (S V). Langage engendré = mots terminaux dérivant de l’axiome. 9 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Définitions : Une GHC est dite "immédiatement récursive à gauche", si elle contient une production de la forme « A A ». Une GHC est dite "indirectement récursive à gauche", si elle contient un symbole non terminal « A » tel qu’il existe une dérivation d’au moins une étape de la forme « A
+ A » où « » une forme quelconque de la grammaire. 10 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Exemples : Soit G la GHC suivante : S ScA | B A Aa | B Bb | d | e G est immédiatement récursive à gauche, à cause des productions : S ScA, A Aa et B Bb 11 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Exemples : Soit G la GHC suivante : S Aa | b A Bc B Sb | G est indirectement récursive à gauche, à cause de la dérivation suivante : S Aa Bca Sbca (donc S
+ Sbca). 12 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Algorithme d’élimination de la récursivité à gauche immédiate : Remplacer toute règle de production de la forme « A A | » par les deux règles suivantes : A A’ A’ A’ | La grammaire ainsi obtenue reconnaît le même langage que la grammaire initiale RG. 13 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Exemple Exemple :: Prenons la GHC immédiatement récursive à Prenons la GHC immédiatement récursive à gauche : gauche :
S ScA | B A Aa | B Bb | d | e Éliminons les récursivités à gauche immédiates de Éliminons les récursivités à gauche immédiates de cette grammaire : cette grammaire :
14 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Exemple Exemple :: On obtient la grammaire :On obtient la grammaire : S BS’ S’ cAS’ | A A’ A’ aA’ | B dB’ | eB’ B’ bB’ | 15 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Algorithme d’élimination de la récursivité à gauche indirecte : Ordonner les « non terminaux » de la grammaire considérée : A1 , A2 , ..., An . Pour i := 1 à n Faire : Pour j := 1 à (i -1) Faire : oRemplacer chaque production de la forme
« A
i Aj » où « A
j
1 | ... |
k », par la production « A
i 1 | ... | k ». FinPour {j} 16 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Algorithme d’élimination de la récursivité à gauche indirecte : Éliminer les récursivités immédiates à gauche des Ai -productions (productions issues de Ai ). FinPour {i} La grammaire ainsi obtenue reconnaît le même langage que la grammaire initiale RG. 17 RI 2013/2014 A. MERAZI Grammaires récursives à gauche Exemple : Considérons la GHC récursive à gauche : S Aa | b A Ac | Sd | Éliminons les récursivités à gauche contenues dans cette grammaire : On ordonne les non terminaux : S, A. i = 1 : pas de récursivité immédiate dans les productions S Aa | b. 18 RI 2013/2014 A. MERAZI Grammaires récursives à Grammaires récursives à gauchegauche Exemple Exemple :: i = 2 et j = 1. On obtient : A Ac | Aad | bd | oOn élimine la récursivité immédiate : A bdA’ | A’ A’ cA’ | adA’ | Donc, on a obtenu la grammaire suivante :Donc, on a obtenu la grammaire suivante : S Aa | b A bdA’ | A’ A’ cA’ | adA’ | 19 RI 2013/2014 A. MERAZI Grammaires Grammaires factorisablesfactorisables à à gauchegauche Exemple : Considérons la GHC suivante : S abcdeaTca | abcdfXy Au départ, pour savoir s'il faut choisir la production « S abcdeaTca » ou la production
« S abcdfXy », il faut avoir lu la 4
ième lettre du mot (qui est soit un « e », ou soit un « f »). On ne peut donc pas dès le départ savoir quelle production prendre. 20 RI 2013/2014 A. MERAZI Grammaires Grammaires factorisablesfactorisables à à gauchegauche Algorithme de factorisation à gauche Algorithme de factorisation à gauche :: PourPour chaque non terminal « A », chaque non terminal « A », FaireFaire :: Trouver le plus long préfixe « » commun à deux de ses alternatives ou plus. Si , Remplacer « A 1 |...|n |1 |...|
p » (où les
i ne commencent pas par ), par les deux productions : oA A’ |
1 | ... | p oA’
1 | ... |
n RecommencerRecommencer jusqu'à ne plus en trouver. jusqu'à ne plus en trouver.
21 RI 2013/2014 A. MERAZI Grammaires Grammaires factorisablesfactorisables à gaucheà gauche Exemple : Soit G la GHC suivante : S iEtS | iEtSeS | a E b On factorise G à gauche : S iEtSS’ | a S’ eS | E b 22 RI 2013/2014 A. MERAZI Exemple : Expressions arithmétiques Arbre d’analyse de 3*6+2 E E E * E E + nombre nombre nombre Les valeurs explicites sont des attributs des unités lexicales. L’association aux unités lexicales est réalisée par l’analyseur lexical. 3 6 2 E nombre E ( E ) E E + E E E – E E E * E E E / E Grammaire non ambiguë pour les expressions arithmétiques : Choix : associativité à gauche priorité de * et / sur + et – E E +T | E –T | T T T *F | T /F | F F ( E ) | nombre Grammaire précédente ambiguë L’analyse descendante Une procédure par terme. Problème : récursivité directe à gauche ; nécessité d’une transformation pour l’éliminer. Grammaire de départ Grammaire modifiée E TG G +TG | T FU U *FU | F (E ) | nombre A E$ (production augmentée) E TG G +TG | T FU U *FU | F (E ) | nombre Fonctions PREMIER et SUIVANT x PREMIER(x) SUIVANT(x) PREMIER(x) = ensemble des terminaux pouvant apparaître au début d’une dérivation de x. SUIVANT(x) = ensemble des terminaux pouvant suivre x dans une dérivation Calcul de PREMIER Calcul de PREMIER
PREMIER() = {désigne l'ensemble des terminaux qui commencent les chaînes qui se dérivent de } •un terminal a PREMIER(), si et seulement s’il existe une dérivation de la forme a. •PREMIER (a) = {a}
if a T PREMIER () = {} PREMIER (A) =
A PREMIER() for A P PREMIER (X1 X2 ...Xk ) = Si pour tout j = 1, ..., i-1 : PREMIER(Xj ) alors
ajouter PREMIER (Xi ) to PREMIER (X1 X2 ...Xk ) Si pour tout j = 1, ..., k : PREMIER (Xj ) alors ajouter to PREMIER(X1 X2 ...Xk ) 27 RI 2013/2014 A. MERAZI Calcul de PREMIER : PREMIER(x) = { a terminal | il existe une dérivation x a} ; si x est annulable, il faut y ajouter . Exemple de la grammaire précédente : Annulables : G et U Graphe : A E T F ( nombre G + U * PREMIER(A) = PREMIER(E) = PREMIER(T) = PREMIER(F) = { (, nombre } PREMIER(G) = {+, } PREMIER(U) = { *, } Calcul de SUIVANT :Calcul de SUIVANT : SUIVANT(A) = {définit l'ensemble des terminaux a qui peuvent apparaître immédiatement à droite de A} SUIVANT(A) =
Si pour tout (B A ) P faire
ajouter PREMIER ()\{} à SUIVANT(A)
Si pour tout (B A ) P & PREMIER() faire
ajouter SUIVANT(B) à SUIVANT(A)
Si pour tout (B A) P faire
ajouter SUIVANT(B) à SUIVANT(A)
Si A est l'axiome alors Mettre $ dans Suivant(A) 29 RI 2013/2014 A. MERAZI Calcul de SUIVANT : SUIVANT(x) = { a terminal | définit l'ensemble des terminaux a qui peuvent apparaître immédiatement à droite de x dans une proto-phrase, c'est à dire l'ensemble des terminaux a tels qu'il existe une dérivation de la forme S * xa , où et sont des chaînes de symboles grammaticaux. }. Exemple de la grammaire précédente : Graphe : E T F ) G + U * $ SUIVANT n’a pas de sens pour l’axiome A de la production augmentée. SUIVANT(G) = SUIVANT(E) = { $, ) } SUIVANT(U) = SUIVANT(T) = { +, $, ) } SUIVANT(F) = { *, +, $, ) } Grammaires LL(1)Grammaires LL(1) Une grammaire GHC est LL(1) si pour toute régle de production de la forme:
A
1 |
2 | ... | n 1.A n’est pas récursif à gauche 2.PREMIER+ (i ) PREMIER
+ (j ) = , avec i j 3.Si
i
* alors 3.a.
j
* pout tout i j 3.b. PREMIER+ (j ) SUIVANT+ (A) =
pour tout i j 31 RI 2013/2014 A. MERAZI NonNon--LL(1) LL(1) ExemplesExemples 32 Grammaire Non LL(1) car: S S a | a Récursive à gauche S a S | a PREMIER+ (aS) PREMIER+ (a) S a R | R S | Pour R: S
* S a R a R S | Pour R: PREMIER+ (S) SUIVANT+ (R) RI 2013/2014 A. MERAZI Grammaires LL(1)Grammaires LL(1) Théorème Théorème :: Si une grammaire hors contexte est LL(1), alors :Si une grammaire hors contexte est LL(1), alors : Elle est non ambiguë. Elle est non récursive à gauche. Elle est factorisée à gauche. Autrement dis, si une grammaire est ambiguëAutrement dis, si une grammaire est ambiguë, , récursive récursive à gauche ou non factorisée à gauche, à gauche ou non factorisée à gauche, alors cette grammaire n’est pas LL(1). alors cette grammaire n’est pas LL(1).
33 RI 2013/2014 A. MERAZI Construction de la table Construction de la table d’analyse prédictived’analyse prédictive Construction d’une table d’analyse Construction d’une table d’analyse :: Une table d'analyse syntaxique prédictive non Une table d'analyse syntaxique prédictive non récursive est un tableau M à deux dimensions qui récursive est un tableau M à deux dimensions qui indique pour chaque symbole non terminal X et indique pour chaque symbole non terminal X et chaque symbole terminal a ou le symbole $, la chaque symbole terminal a ou le symbole $, la règle de production à appliquer.règle de production à appliquer. L’algorithme de construction d’une telle table est L’algorithme de construction d’une telle table est le suivant :le suivant : 34 RI 2013/2014 A. MERAZI Construction de la table Construction de la table d’analyse prédictived’analyse prédictive Construction d’une table d’analyse : Pour chaque production A Faire : Pour tout a PREMIER() (et a ), rajouter la production A dans la case M[A, a]. Si PREMIER(), alors pour chaque symbole b SUIVANT(A), ajouter A dans la case M[A, b]. Chaque case M[A, a] vide est une erreur de syntaxe. Une grammaire est dite LL(1), si sa table d’analyse M ne contient que des entrées simples. 35 RI 2013/2014 A. MERAZI Table d’analyse LL(1) : + * ( ) n $ E G T U F 1 1 2 3 3 4 4 6 5 6 6 7 8 Les case vides de la table correspondent à des erreurs syntaxiques. La table commande les branchements dans les procédures de l’analyse par descente récursive. On peut l’utiliser comme donnée d’un programme universel d’analyse descendante non récursive. 0 A E$ 1 E TG 2 G +TG 3 G 4 T FU 5 U *FU 6 U 7 F ( E ) 8 F nombre ExempleExemple Table Table d’analyse d’analyse LL(1) :LL(1) : 37 E T G G + T G | T F U U * F U | F ( E ) | nombre nombre + * ( ) $ E E T G
E T G
G G + T G
G G T T FU
T F U
U U U * F U
U U F F nombre F ( E ) A PREMIER() SUIVANT(A) E T G
(nombre $ ) G + T G
+ $ ) G $ ) T F U
(nombre + $ ) U * F U
* + $ ) U + $ ) F ( E ) ( * + $ ) F nombre nombre * + $ ) RI 2013/2014 A. MERAZI Analyseur prédictifAnalyseur prédictif Dans la plupart des cas, en écrivant Dans la plupart des cas, en écrivant soigneusement une grammaire, après avoir soigneusement une grammaire, après avoir élimine les récursivités gauche et l'avoir élimine les récursivités gauche et l'avoir factorisée a gauche, nous pouvons obtenir une factorisée a gauche, nous pouvons obtenir une grammaire qui peut être analysée par descente grammaire qui peut être analysée par descente récursive ou non récursive sans rebroussement, récursive ou non récursive sans rebroussement, c'est a dire obtenir un analyseur prédictif.c'est a dire obtenir un analyseur prédictif. RI 2013/2014 A. MERAZI 38 Analyseur prédictifAnalyseur prédictif L'analyseur non récursif de la figure ciL'analyseur non récursif de la figure ci--dessous dessous recherche la production a appliquer dans une recherche la production a appliquer dans une table d'analyse. Dans ce qui suit, nous verrons table d'analyse. Dans ce qui suit, nous verrons comment cette table peut, pour certaines comment cette table peut, pour certaines grammaires, être construite directement.grammaires, être construite directement. RI 2013/2014 A. MERAZI 39 Analyseur prédictifAnalyseur prédictif RI 2013/2014 A. MERAZI 40 RI 2013/2014 A. MERAZI 41 Analyseur prédictifAnalyseur prédictif RI 2013/2014 A. MERAZI 42 Analyseur prédictifAnalyseur prédictif RI 2013/2014 A. MERAZI 43 Analyseur Analyseur prédictifprédictif RI 2013/2014 A. MERAZI 44 Sur la chaîne source id + id* id l'analyseur prédictif effectue la séquence d'actions de la table ci-
dessous Pile $E $GT $GUF $GUid $GU $G
$GT+ $GT $GUF $GUid $GU
$GUF* $GUF $GUid $GU
$G $ Entrée id+id*id$ id+id*id$ id+id*id$ id+id*id$ +id*id$ +id*id$ +id*id$ id*id$ id*id$ id*id$ *id$ *id$ id$ id$ $ $ $ Sortie E T G T F U
F id U G + T G
T F U F id U * F U
F id U
G
ExempleExemple Table d’analyse Table d’analyse LL(1) :LL(1) : 45 S i E t S B | a B e S | E b a b e i t $ S S a
S i E t S B
B B B e S B E E b A PREMIER() SUIVANT(A) S i E t S B
i e $ S a
a e $ B e S e e $ B e $ E b
b t Conflit: 2 entrées RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Implémentation d’un analyseur syntaxique Implémentation d’un analyseur syntaxique prédictive prédictive :: L’analyse prédictive est caractérisée par la L’analyse prédictive est caractérisée par la simplicité de son implémentation.simplicité de son implémentation. Un analyseur syntaxique prédictif se programme Un analyseur syntaxique prédictif se programme comme un ensemble de procédures récursives qui comme un ensemble de procédures récursives qui coopèrent pour traiter l’entrée.coopèrent pour traiter l’entrée. L’idée est très simple : à chaque non terminal, on L’idée est très simple : à chaque non terminal, on définit une procédure récursive. définit une procédure récursive.
46 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Implémentation d’un analyseur syntaxique Implémentation d’un analyseur syntaxique prédictive prédictive :: On définit une procédure « Accepter(Lexème) » On définit une procédure « Accepter(Lexème) » pour simplifier le code des autres procédures.pour simplifier le code des autres procédures. Cette procédure consiste à avancer jusqu’à la Cette procédure consiste à avancer jusqu’à la prochaine unité lexicale de l’entrée si son prochaine unité lexicale de l’entrée si son argument concorde avec le symbole de prévision.argument concorde avec le symbole de prévision. L’analyse syntaxique débute par un appel à la L’analyse syntaxique débute par un appel à la procédure correspondant à l’axiome.procédure correspondant à l’axiome. 47 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Écriture d’une procédure pour une Écriture d’une procédure pour une production production :: À chaque production, on fait correspondre une À chaque production, on fait correspondre une procédure.procédure. Pour simplifier l’implémentation, le nom de la Pour simplifier l’implémentation, le nom de la procédure est celui du non terminal dans la partie procédure est celui du non terminal dans la partie gauche de la production.gauche de la production. Chaque terminal en partie droite est comparé au Chaque terminal en partie droite est comparé au symbole de prévision et chaque non terminal en symbole de prévision et chaque non terminal en partie droite conduit à un appel de sa procédure.partie droite conduit à un appel de sa procédure. 48 RI 2013/2014 A. MERAZI Forme conceptuelle de l’analyseur:Forme conceptuelle de l’analyseur: A A
1 1 ||
2 2 || ... | ... |
n n
/ /
I I = x= x11 xx
22 ... ... xx
kk voidvoid A() {A() {
switchswitch((symbole_previsionsymbole_prevision) {) {
casecase premierpremier++ ((11 )) ::
Accepter(Accepter(xxii ); ); sisi xx
i i T; T; OU OU xxii (); (); sisi xx
i i VV
breakbreak;;
casecase premierpremier++ ((22 )) :: ...... ...... breakbreak;; defaultdefault :: Erreur(); } /* fin Erreur(); } /* fin switchswitch */*/ } /* fin procédure A() */} /* fin procédure A() */ 49 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Exemple Exemple :: Considérons la grammaire :Considérons la grammaire : S aSbT
(1) S cT (2) S d (3) T c (4) T bS (5) Cette grammaire peut très bien être analysée par Cette grammaire peut très bien être analysée par un analyseur syntaxique prédictive. un analyseur syntaxique prédictive.
50 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Programme C de l’analyseur prédictif Programme C de l’analyseur prédictif :: voidvoid S() {S() {
switchswitch((symbole_previsionsymbole_prevision) {) {
casecase ''aa'' :: Accepter(Accepter(''aa');');
S();S();
Accepter('Accepter('bb');');
T();T();
breakbreak;;
51 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Programme C de l’analyseur prédictif Programme C de l’analyseur prédictif ::
casecase ''cc'' :: Accepter(Accepter(''cc');');
T();T();
breakbreak;;
casecase ''dd'' :: Accepter(Accepter(''dd');');
breakbreak;;
defaultdefault : : ErreurErreur(); } /* fin switch */(); } /* fin switch */ } /* fin } /* fin procédureprocédure S() */S() */ 52 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Programme C de l’analyseur prédictif Programme C de l’analyseur prédictif :: voidvoid T() {T() {
switchswitch((symbole_previsionsymbole_prevision) {) {
casecase ''bb'' :: Accepter(Accepter(''bb');');
S();S();
breakbreak;;
casecase ''cc'' :: Accepter(Accepter(''cc');');
breakbreak;;
53 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Programme C de l’analyseur prédictif Programme C de l’analyseur prédictif ::
defaultdefault :: Erreur(); } /* fin Erreur(); } /* fin switchswitch */*/ } /* fin procédure T() */} /* fin procédure T() */ voidvoid Erreur()Erreur() {{
printfprintf("Erreur syntaxique : %c ("Erreur syntaxique : %c attenduattendu\\nn", ", symbole_previsionsymbole_prevision);); }} 54 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique prédictiveprédictive Programme C de l’analyseur prédictif Programme C de l’analyseur prédictif :: voidvoid Accepter(Accepter(charchar lexemelexeme) ){{ ifif((symbole_previsionsymbole_prevision == == lexemelexeme))
symbole_previsionsymbole_prevision = = entreeentree[++[++indiceindice];];
elseelse Erreur();Erreur(); }} 55 RI 2013/2014 A. MERAZI 56 RI 2013/2014 A. MERAZI ANALYSE SYNTAXIQUEANALYSE SYNTAXIQUE ASCENDANTEASCENDANTE 57 RI 2013/2014 A. MERAZI Analyse syntaxique Analyse syntaxique ascendante ascendante
Principe Principe :: L’analyse syntaxique ascendante essai de construire un L’analyse syntaxique ascendante essai de construire un arbre syntaxique du bas (les unités lexicales) vers le arbre syntaxique du bas (les unités lexicales) vers le haut (l'axiome de la grammaire).haut (l'axiome de la grammaire). L’analyse syntaxique ascendante utilise en général un L’analyse syntaxique ascendante utilise en général un modèle appelé modèle par "modèle appelé modèle par "décalage & réductiondécalage & réduction".". Ce modèle n'autorise que deux opérations :Ce modèle n'autorise que deux opérations : Décalage (shift) : consiste à décaler d'une lett