Discussion :

[emmesse]

bonjour,

suis-je bien au bon endroit pour parler d'un problème qui me met dans l’embarras, dans le livre "compilateurs principes techniques et outils"?

[dourouc05]

Peut-être, voire très probablement. Quel est ce problème ? De là, on pourra le dire plus précisément .

[emmesse]

c'est pour dire voilà:
dans le chapitre sur l'analyseur syntaxique descendant, dans la section de rattrapage d'erreur, l'entrée M[E,')'] est synchro et M[F,+] est aussi synchro. Pourtant, dans l'entrée erronée ")id*+id$", la parenthèse fermante est sautée tandis que quand on arrive à l'étoile, c'est le non-terminal F qui est dépilé.
quelqu'un pourrait-il m'éclairer su cette contradiction?

[dourouc05]

C'est donc bien le bon forum, mais la question est trop spécifique pour moi, je passe mon tour .

Pourrais-tu donner plus de contexte, histoire que des gens qui n'ont pas le livre sous la main puissent réfléchir un peu à ta question ?

[tbc92]

Pas sûr qu'on soit sur le bon forum, y a-t-il un forum voyance/boule de cristal ?

[emmesse]

il y a tout un chapitre sur le sujet, je ne sais pas si je serais capable de tout résumer:
grammaire non contextuelle :

E -> T E'
E' -> + T E' | epsilon (epsilon est la production vide)
T -> F T'
T' -> * F T' | epsilon
F -> ( E ) | id

table d'analyse :

figure 4.22:


Il y a une pile. Au départ, elle a le dollar au fond et l'axiome( = E ) au dessus et au somment. En avançant dans le flux d'entrée, de deux chose l'une. Le sommet de la pile est un terminal(un symbole d'entré id,+,*,(,),$) si le flux d'entrée donne un terminal qui est au somment de la pile, le terminal est dépilé et on avance dans le flux d'entrée. Sinon, il y a erreur. Si par contre le sommet de la pile est un non-terminal, on le dépile et on empile les symboles (terminaux et non-terminaux) de la production se trouvant dans la table d'analyse à la ligne du non-terminal et la colonne du terminal, avec le symbole le plus à gauche de la production, au sommet de la pile. cet algo se termine quand on a plus que le dollar dans la pile.

pour le rattrapage sur erreur, l'idée est que si on rencontre une erreur, les symboles sont sautés jusqu'à avoir dans l'entrée un terminal élément d'un ensemble de synchronisation. Alors on saute le terminal et on dépile lorsque le terminal de synchronisation est rencontré dans l'entrée (c'est ce que j'ai compris).

je cite le livre:
Cette table s'utilise de la façon suivante. Si l'annalyseur syntaxique cheche l'entré M[A,a] (M est le tableau, A un non-terminal et "a" un symbole) et constate qu'elle est vide, alors le symbole d'entrée a est sauté.Si l'entrée est "synchro", alors le non-terminal au sommet de la pile est dépilé afin d'essayer de contiinuer l'analyse syntaxique. Si une unité lexicale au sommet de la pile ne correspond pas au symbole d'entrée,alors on déplie l'unité lexicale, comme indiqué précédement.
Sur l'entrée erronnée )id*+id, l'analyseur et le mécanisme de ratrapâge d'erreur de la figure 4.22 se comporte comme indiqué à la figure 4.23

figure 4.23:



mon problème est que M[E,')'] est une entrée sychro E et n'est pas dépilé. Ils ont mis sychro à M[E,')'] car ')' est dans l'ensemble des symboles suivant E. Peut-être qu'il ne faudrais pas mettre '(' dans l'ensemble de synchronisation, malgré qu'il soit dans l'ensemble des suivants de E?
qu'en pensez-vous?

[emmesse]

je peux peut-être faire comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
X=sommet de la pile;
symbole=analex(); //analex est la fonction qui donne l'unité lexicale suivante
while(X!=dollar){  //dollar sert de marqueur de fin et se trouve au fond de la pile (ils disent "le terminal qui n'existe dans aucune grammaire")
   if(X==E && symbole==PF){   //PF=parenthèse fermante
      do{
         //chercher ici le non-terminal suiv tel que symbole est dans l'ensemble des premiers de suiv
         if(pas trouvé)
            symbole=analex();
      }while(pas trouvé de non-terminal dont symbole est dans l'ensemble PREMIER(suiv) && symbole!=dollar);
      if(symbole!=dollar){ //dollar sert aussi à indiquer la fin du fichier
         dépiler(); // on dépile E
         empiler(suiv);
         continue;
      }
      else
         //fin prématurée du fichier source
   }
   else if ... //autres cas
   symbole=analex();
   X=sommet de la pile;
}

qu'en pensez-vous?

[emmesse]

l'algo de mon précédent post est faux car il y a plusieurs solutions pour suiv.

je crois que j'ai compris ce qu'ils disent dans ce livre:

dans la figure 4.23, on lit "id est dans premier de E". Cela signifie que,après avoir dépilé E, car à la ligne E et la colonne parenthèse fermante on a "synchro", puisque le symbole qui suit est id, et que à la ligne E et à la colonne id la case n'est pas vide, ni synchro, alors E est à nouveau empilé.

ensuite, quand on arrive à " * + id $" avec " * F T' E' " dans la pile, l’étoile dans l'entrée correspond au sommet de la pile. Elle est donc dépilée et on passe à l'unité lexicale suivante. L'entrée contient alors "+ id $" et la pile "F T' E' ". comme dans la table, à la ligne F et colonne +, on trouve "synchro", F est dépilé. La pile contient alors " T' E' ". Comme à la ligne T' et la colonne '+' on a la production vide, on empile pas d'autre non-terminaux

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
X=sommet de la pile;
symbole=anaLex();
while(X!=DOLLAR){
   if(X==symbole){
      depiler();
      symbole=anaLex();
   }
   else if(X==E && symbole==PF){  //PF=parenthèse fermante
      depiler(); // on dépile E
      symbole=anaLex();
      if(symbole==ID||symbole==PO) //PO= parenthèse ouvrante
         empiler(E);
   }
   else if(X==E && (symbole==PLUS||symbole==ETOILE)){
      cerr<<"ligne "<<numLigne<<" identificateur ou parenthèse ouvrante attendu ici"<<endl;
      symbole=anaLex();
   }
   else if(X==E && symbole==ID){
      cout<<"E -> T E'"<<endl;
      depiler();
      empiler(Eprim);
      empiler(T);
   }
   else if(X==F && symbole==PLUS){
      depiler(); //on dépile F
      X=sommet de la pile;
   }
   else if(X==Tprim && (symbole==PLUS||symbole==PF||symbole==DOLLAR){  //PF=parenthèse fermante
      depiler();
      X=sommet de la pile;
   }
   else if(autres cas)
      ...
}