Remerciez-le!

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

Analyse syntaxique shift reduce

III 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 CIII 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 aABe aABe SS Ces réductions élaborent en sens inverse la dérivation droite suivante S ? aABe ? aAde ? aAbcde ? abbcde d d dd CIII 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 ?? ? ? ? CIII Analyse syntaxique par décalage réduction Exemple Considérons la grammaire suivante E E E E EE E E E id Une dérivation droite est E ? E E ? E EE ? E E id ? E id id ? id id id Id est un manche de la proto-phrase droite id id id car id est la partie droite de la production E id et le remplacement de id par E produit la proto-phrase droite précédente E id id CIII 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 EE E E E id Une dérivation droite est E ? E E E ? EE ? E E E ? E id ? E E id ? E E id ? E id id ? E id id ? id id id ? id id id Id est un manche de la proto-phrase droite id id id car id est la partie droite de la production E id et le remplacement de id par E produit la proto-phrase droite précédente E