Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

III.6. Analyse syntaxique par décalage réduction (shift/Reduce) (Ascendante) II

III.6. Analyse syntaxique par décalage réduction (shift/Reduce) (Ascendante) III.6. Analyse syntaxique par décalage réduction (shift/Reduce) (Ascendante) • L’analyse par décalage-réduction a pour but de construire un arbre d’analyse pour une chaine source en commençant par les feuilles et en remontant vers la racine. • C’est un processus de « réduction » d’une chaine w vers l’axiome de la grammaire. • A chaque étape de réduction, une sous-chaine particulière correspondant à la partie droite d’une production est remplacée par le symbole de la partie gauche de cette production. • Si la sous-chaine est choisie correctement à chaque étape, alors une dérivation droite est ainsi élaborée en sens inverse. 1 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Considérons la grammaire avec les règles de production suivantes: S  aABe A  Abc | b B  d La phrase abbcde peut être réduite vers S par les étapes suivantes: abbcde abbcde aAbcde aAbcde aAde aAde aABeaABe S S Ces réductions élaborent en sens inverse la dérivation droite suivante: S  aABe  aAde  aAbcde  abbcde d d d d 2 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Manches Informellement, un « manche » d’une chaine est une sous-chaine qui correspond à la partie droite d’une production et dont la réduction vers le non terminal de la partie gauche de cette production représente une étape le long de la dérivation droite inverse. Formellement, un manche d’une proto-phrase droite  est une production A  et une position dans  où la chaine  peut être trouvée et remplacée par A pour produire la proto-phrase droite précédente dans une dérivation droite de . C-a-d si S *  A  *    d d Alors, A   dans la position qui suit  est un manche de    On dit aussi que «  est un manche pour    » 3 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Exemple Considérons la grammaire suivante: E  E + E E  E * E E  (E) E  id Une dérivation droite est : E  E+E  E + E * E  E + E * id3  E + id2 * id3  id1 + id2 * id3 Id1 est un manche de la proto-phrase droite id1+id2*id3 car id est la partie droite de la production E  id et le remplacement de id1 par E produit la proto-phrase droite précédente E + id2 * id3. 4 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction La grammaire est ambiguë car il y a une autre dérivation droite pour la même chaine: E  E + E E  E * E E  (E) E  id Une dérivation droite est : E  E+E E  E*E  E + E * E  E * id3  E + E * id3  E + E * id3  E + id2 * id3  E + id2 * id3  id1 + id2 * id3  id1 + id2 * id3 Id1 est un manche de la proto-phrase droite id1+id2*id3 car id est la partie droite de la production E  id et le remplacement de id1 par E produit la proto-phrase droite précédente E + id2 * id3. 5 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Proto-phrase droite Manche Production de réduction id1 + id2 * id3 Id1 Eid E + id2 * id3 id2 Eid E + E * id3 id3 Eid E + E * E E * E E  E * E E + E E + E E E+ E E 6 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Implantation à l’aide d’une pile de l’analyse par décalage-réduction Nous utilisons une pile pour conserver les symboles grammaticaux et un tampon d’entrée qui contient la chaine  à analyser. Le symbole $ est utilisé pour marquer le fond de la pile et l’extrémité droite du tampon d’entrée. 7 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction $ Id + id * id $ S $ Id + id * id $ Tampon Tampon Tête de L/E Tête de L/E Pile Pile Configuration initiale Configuration finale 8 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction PILE ENTREE SORTIE $ Id1 + id2 * id3 $ Décaler $id1 + id2 * id3 $ Réduire par Eid $E + id2 * id3 $ Décaler $E+ id2 * id3 $ Décaler $E+ id2 * id3 $ Réduire par E  id $E + E * Id3 $ Décaler $E + E * id3 $ Décaler $E + E * id3 $ Réduire par E  id $E + E * E $ Réduire par E  E*E $E + E $ Réduire par E  E+E $E $ Accepter 9 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Les opérations de base l’analyseur: (1) décaler, (2) réduire, (3) accepter et (4) erreur. 1. Dans une action décaler, le prochain symbole du tampon d’entrée est enlevé du tampon et placé en sommet de la pile. 2. Dans une action réduire, l’analyseur sait que l’extrémité de la partie droite du manche est dans la pile et décide par quel non-terminal remplacer le manche 3. Dans une action accepter, l’analyseur s’arrête et annonce la réussite finale de l’analyse. 4. Dans une action erreur, l’analyseur découvre qu’une erreur de syntaxe s‘est produite et appelle une routine de récupération sur erreur. 10 III.6. Analyse syntaxique par décalage réduction III.6. Analyse syntaxique par décalage réduction Algorithme par Décalage/Réduction (Shift/Reduce) (1) décaler, (2) réduire, (3) accepter et (4) erreur. - Initialement, la pile contient $ et l’entrée contient $ - A chaque étape, l’analyseur décale un ou plusieurs symboles (action décaler) jusqu’à ce qu’un manche apparaît au sommet de la pile. Une action réduire est alors réalisée en remplaçant le manche par la partie gauche de la règle de production associée. 11 uploads/S4/ analyse-syntaxique-shift-reduce.pdf