Liste chaînée (compilation)

**adrienmgs** · 25/12/2011, 17h49

Bonsoir,

Dans le cadre d'un projet de compilation, je bute sur la réalisation de l'arbre syntaxique abstrait (plus précisément sur les liste de déclaration de variables, arguments, fonctions) mais je pense que mon problème est indépendant du contexte.

Voici des extraits de mon code qui seront je l'espère suffisants :

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
35
36
37
38
39
40
41
42
43
 
n_l_dec *listedeclVariables(){
    n_dec *tete = NULL;
    n_l_dec *queue = NULL;
    if (syntout) out("<listedeclVariables>\n");
    tete = declVariable();
    //TEST
    printf("TEST 1 : %s\n", tete->nom);
    //TEST
    queue = listedeclVariablesBis();
    if (syntout) out("</listedeclvariables>\n");
    //TEST
    printf("TEST 2 : %s\n", tete->nom);
    //TEST
    return cree_n_l_dec(tete, queue);
}
 
n_l_dec *listedeclVariablesBis(){
    n_dec *tete = NULL;
    n_l_dec *queue = NULL;
    if (syntout) out("<listedeclVariablesBis>\n");
    if (cc == ','){
        cc = yylex();
        tete = declVariable();
        queue = listedeclVariablesBis();
    }
    if (syntout) out("</listedeclvariablesBis>\n");
    return cree_n_l_dec(tete, queue);
}
 
n_dec *declVariable(){
    n_dec *variable = NULL;
    if (syntout) out("<declVariable>\n");
    if (cc == ENTIER){
        cc = yylex();
        if (cc == ID_VAR){
            variable = cree_n_dec_var(yylval.string);
            cc = yylex();
        }
    }
    if (syntout) out("</declVariable>\n");
    return variable;
}

Et les structures utilisées dans ce extrait :

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
 
struct n_l_dec_{
  n_dec *tete;
  struct n_l_dec_ *queue;
};
 
n_l_dec *cree_n_l_dec(n_dec *tete, n_l_dec *queue);
 
struct n_dec_ {
  enum{foncDec, varDec, tabDec} type;
  char *nom;
  union {
    struct{n_l_dec *param; n_l_dec *variables; n_instr *corps;}foncDec_;
    struct{int type;}varDec_;
    struct{int taille;}tabDec_;
  } u;
//u n'est pas utilisé dans le cas d'une variable
};
 
n_dec *cree_n_dec_var(char *nom);

Voila, mon soucis est que au lieu de me retrouver avec une liste chainée dans laquelle je peux circuler avec une boucle while, j'ai seulement une instance (qui correspond à la dernière variable analysée).
par exemple dans la première fonction, le premier test affiche bien la première variable mais le deuxième affiche la dernière (j'espère que je suis assez clair...)

N'étant pas très au fait de la portée des variables en c, je pense que le problème vient de là, sans en être certain.

Je vous remercie d'avance de preter attention à mon problème, en espérant que vous pourrez me fournir des pistes pour le résoudre.

Bonnes fêtes,

Cordialement,

Adrien.

**mala92** · 26/12/2011, 09h59

Ca va être très compliqué de voir ton problème sans le code de remplissage de la liste.

Ton appel récursif de listedeclVariablesBis ne semble pas correcte : comment lies-tu les éléments de la liste entre-eux ?
J'ai l'impression que tu créés un élément sans le lier au précédent.

**adrienmgs** · 26/12/2011, 13h56

Tout d'abord, merci d'avoir pris le temps de me répondre,

Il y a clairement un problème de ce genre vu le retour de cette fonction !

La liste est justement censée être remplie par cette fontion listedeclVariablesBis().

En effet pour moi (et c'est surement là que je mérite des coups de baton) :
lors de l'appel récursif, vu que le retour de la fonction est un maillon de la liste stocké dans la variable queue de l'appel précédent, au fur à mesure que les appels imbriqués se terminent, la liste se construit.

Je devrais donc pouvoir régler le problème en passant le maillon précédent en paramètre de la fonction et en créant le maillon dont l'élément queue est initialisé à NULL avant l'appel récursif ?

Je vais tester cela, mais dans tous les cas, et pour éviter de futures erreurs, je suis curieux de savoir pourquoi ce code ne marche pas comme je l'attendais !

**mala92** · 26/12/2011, 14h39

Envoyé par adrienmgs

En effet pour moi (et c'est surement là que je mérite des coups de baton) :
lors de l'appel récursif, vu que le retour de la fonction est un maillon de la liste stocké dans la variable queue de l'appel précédent, au fur à mesure que les appels imbriqués se terminent, la liste se construit.

C'est ca ton souci, ce que tu fais n'est pas une liste chainée.

Envoyé par adrienmgs

Je devrais donc pouvoir régler le problème en passant le maillon précédent en paramètre de la fonction et en créant le maillon dont l'élément queue est initialisé à NULL avant l'appel récursif ?

Oui, c'est mieux.
Comment relies-tu les noeuds entre eux ?
Sans tenir compte de "tete", une liste chainée c'est :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct n_dec_ {
  enum{foncDec, varDec, tabDec} type;
  char *nom;
  union {
    struct{n_l_dec *param; n_l_dec *variables; n_instr *corps;}foncDec_;
    struct{int type;}varDec_;
    struct{int taille;}tabDec_;
  } u;
//u n'est pas utilisé dans le cas d'une variable
  struct n_dec_ *psuivant;
};

ta structure doit contenir un pointeur sur elle-même.
http://chgi.developpez.com/pile/

**adrienmgs** · 26/12/2011, 14h59

ok donc en fait dans la configuration actuelle toutes les instances sont perdues sauf la dernière ;p

Mais en fait la liste chainée est de type n_l_dec :

Code :

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

1
2
3
4
5
 
struct n_l_dec_{
  n_dec *tete;
  struct n_l_dec_ *queue;
};

Elle contient donc bien un pointeur sur l'élément suivant ?

n_dec est le type de donnée "porté" par le maillon de la liste.

donc en fait ma fonction listedecVariableBis() renvoie une liste chainée qui est censée venir ce greffer à la suite de celle créée lors des appels précédents de cette fonction, mais au lieu de cela, la liste renvoyée écrase la précédent à chaque appel, ce qui fait que cette liste ne contient toujours qu'un maillon.

Je vais essayer de reprendre tout ça après avoir lu ton lien, je pense que je me fais une mauvaise représentation du fonctionnement des liste chainées.

Merci de ton aide !

**mala92** · 26/12/2011, 15h43

Non, tu n'as pas fait une liste chainée !!
Tu as une structure qui pointe sur la tête de la liste et sur un élément de cette liste, donc rien n'est chainé.

**adrienmgs** · 26/12/2011, 23h00

Ce que je ne comprend pas c'est pourquoi je n'arrive pas à obtenir quelque chose du genre :

Code :

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

1
2
3
4
5
6
7
 
tete = 'donnée1'
queue-----|
          |------tete = 'donnée2'
                 queue-----|
                           |-----tete = 'donnée3'
                                 queue = NULL

alors que le code :

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
 
    n_l_dec *test1 = NULL;
    n_l_dec *test2 = NULL;
    n_l_dec *test3 = NULL;
    n_l_dec *temp = NULL;
    test1 = cree_n_l_dec(cree_n_dec_var("$a"), NULL);
    test2 = cree_n_l_dec(cree_n_dec_var("$b"), test1);
    test3 = cree_n_l_dec(cree_n_dec_var("$c"), test2);
    temp = test3;
    if (temp!=NULL){
        printf("TEST : %s\n", temp->tete->nom);
        while(temp->queue!=NULL){
            temp = temp->queue;
            printf("TEST : %s\n", temp->tete->nom);
        }
    }

affiche bien

Code :

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

1
2
3
4
 
$c
$b
$a

comme je l'attend...

Désolé, je suis un peu lourd, je passe surement à coté de quelque chose alors merci de ta patience !

**mala92** · 27/12/2011, 09h54

Dans ton premier message, ton algo semble foireux, mais sans savoir ce que font les fonctions cree_n_xxxx, ça être très compliqué de trouver le problème.

Dans ton dernier exemple, c'est encore tout faux !! Tu fais pointer temp sur test3 qui semble être le dernier élément de la chaîne.

Tu veux réellement faire une liste chaînée ? Ou un arbre ? Tu sembles lire un fichier XML, on peut voir sa tête ?

**adrienmgs** · 27/12/2011, 13h39

Pour le fichier, j'écris dedans, mais cette partie du code ne pose pas de problème, c'est pour avoir une trace de l'arbre syntaxique qui n'est pas réellement construit.

les fonctions de création sont :

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
 
n_l_dec *cree_n_l_dec(n_dec *tete, n_l_dec *queue)
{
  n_l_dec *n = malloc(sizeof(n_l_dec));
  n->tete = tete;
  n->queue = queue;
  return n;
}
 
n_dec *cree_n_dec_var(char *nom)
{
  n_dec *n = malloc(sizeof(n_dec));
  n->type = varDec;
  n->nom = nom;
  return n;
}

En fait je veux faire un arbre, mais lorsque que j'ai un nœud qui correspond à une liste de déclaration (n_l_dec = nœud liste déclaration), la première déclaration est stockée dans tete (premier fils), et la liste des suivantes dans queue (second fils).
(donc, dans mon exemple, temp3 est bien le premier maillon ! Même si j'avoue que nommer les variables dans le bon ordre et mettre les données qu'elles portent dans l'ordre alphabétique aurait été plus judicieux).

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
 
<listedecVariable>
      <declvariable>
            <var> $c </var>
      </declVariable>
      <listedecVariableBis>
            <declvariable>
                  <var> $b </var>
            </declVariable>
            <listedeclvariableBis>
                  <declVariable>
                        <var> $a </var>
                  </declvariable>
                  <listedeclvariableBis>
                  </listedeclvariableBis>
            </listedeclVariableBis>
      </listedecVariableBis>
</listedecVariable>

correspond au résultat du petit test que j'ai donné dans le message précédent.

Après c'est peut être toute mon approche qui est à revoir, mais quand bien même, j'aimerai comprendre ce qui ne va pas avec celle ci !

**mala92** · 27/12/2011, 14h45

A priori ca devrait marcher.

quelle est la différence entre n_dec et n_dec_ ?

**adrienmgs** · 27/12/2011, 15h07

Envoyé par mala92

A priori ca devrait marcher.

C'est bien ça qui m'attriste :p j'ai beau relire 50 fois mon programme, je ne vois pas ce qui cloche, il y a quelque chose qui doit interférer dans une autre fonction...

Envoyé par mala92

quelle est la différence entre n_dec et n_dec_ ?

Code :

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

1
2
 
typedef struct n_dec_ n_dec;

a priori ils sont équivalents.

Edit : j'ai réussi à localiser un peu plus le problème :

Par exemple si j'analyse la suite de declarations de variables "entier $a, entier $b, entier $c"

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
n_l_dec *listedeclVariables(){
    n_dec *tete = NULL;
    n_l_dec *queue = NULL;
    if (syntout) out("<listedeclVariables>\n");
    tete = declVariable();
    /*********************************************/
    printf("TEST VAR : %s\n", tete->nom);
    /*ici "$a" est affiché comme attendu*/
    /*********************************************/
    queue = listedeclVariablesBis();
    /*********************************************/
    printf("TEST VAR : %s\n", tete->nom);
    /*ici "$c" est affiché au lieu de "$a"*/
    /*********************************************/
    printf("TEST 2 : %s->%s->%s->\n", tete->nom, queue->tete->nom, queue->queue->tete->nom);
    /*cela affiche "$c->$c->$c", il y a donc bien le bon nombre de maillons*/
    /*********************************************/
    if (syntout) out("</listedeclvariables>\n");
    return cree_n_l_dec(tete, queue);
}
 
n_l_dec *listedeclVariablesBis(){
    n_dec *tete = NULL;
    n_l_dec *queue = NULL;
    if (syntout) out("<listedeclVariablesBis>\n");
    if (cc == ','){
        cc = yylex();
        tete = declVariable();
        queue = listedeclVariablesBis();
    }
    if (syntout) out("</listedeclvariablesBis>\n");
    return cree_n_l_dec(tete, queue);
}
 
n_dec *declVariable(){
    n_dec *variable = NULL;
    if (syntout) out("<declVariable>\n");
    if (cc == ENTIER){
        cc = yylex();
        if (cc == ID_VAR){
            variable = cree_n_dec_var(yylval.string);
            cc = yylex();
        }
    }
    if (syntout) out("</declVariable>\n");
    return variable;
}

Ainsi chaque maillon est identique au dernier, et j'ignore pourquoi.
Si il y a plus loin dans le programme une nouvelle liste de déclaration, chaque maillon de celle ci est identique à celui qui correspond à la dernière déclaration de cette autre liste.

**mala92** · 27/12/2011, 16h34

printf("TEST VAR : %s\n", tete->nom);
/*ici "$a" est affiché comme attendu*/ // ok
/*********************************************/
queue = listedeclVariablesBis();
/*********************************************/
printf("TEST VAR : %s\n", tete->nom);
/*ici "$c" est affiché au lieu de "$a"*/ // Non !! c'est exactement la meme variable et la meme ligne de code, donc c'est bien $c qui doit s'afficher

Code :

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

1
2
    printf("TEST 2 : %s->%s->%s->\n", tete->nom, queue->tete->nom, queue->queue->tete->nom);
    /*cela affiche "$c->$c->$c", il y a donc bien le bon nombre de maillons*/

Dans ce cas, c'est le parser (lex ?) qui déconne, non ?

**adrienmgs** · 27/12/2011, 16h44

printf("TEST VAR : %s\n", tete->nom);
/*ici "$a" est affiché comme attendu*/ // ok
/*********************************************/
queue = listedeclVariablesBis();
/*********************************************/
printf("TEST VAR : %s\n", tete->nom);
/*ici "$c" est affiché au lieu de "$a"*/ // Non !! c'est exactement la meme variable et la meme ligne de code, donc c'est bien $c qui doit s'afficher

Même variable, même ligne, donc cela devrait afficher deux fois la même chose non ?
"$a" et "$a" ou "$c" et "$c" or ce n'est pas le cas.

Je ne pense pas que ce soit le parser (que j'ai fait à la main) car le retour de l'analyse lexicale est correct :

Code :

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

1
2
3
4
5
6
7
8
9
(entier, 306)
($a, 316)
(,, 44)
(entier, 306)
($b, 316)
(,, 44)
(entier, 306)
($c, 316)
(;, 59)

et si je rajoute un printf dans declVariable(), j'ai bien $a, $b puis $c donc je pense que ce sont les bons token qui sont envoyés à mon analyseur syntaxique.

Le truc qui m'échappe c'est comment le premier maillon peut changer comme dans la première quote ...

Merci en tout cas de persister à essayer de m'aider !

**adrienmgs** · 27/12/2011, 17h01

Je pense que j'ai trouvé :

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
 
n_dec *declVariable(){
    n_dec *variable = NULL;
    char *temp;
    if (syntout) out("<declVariable>\n");
    if (cc == ENTIER){
        cc = yylex();
        if (cc == ID_VAR){
/*Ici je copie la valeur courante de yylvalstring dans une nouvelle variable*/
            temp = malloc(sizeof(yylval.string));
            strcpy(temp, yylval.string);
            variable = cree_n_dec_var(temp);
            cc = yylex();
        }
    }
    if (syntout) out("</declVariable>\n");
    return variable;
}

L'ancien code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n_dec *declVariable(){
    n_dec *variable = NULL;
    if (syntout) out("<declVariable>\n");
    if (cc == ENTIER){
        cc = yylex();
        if (cc == ID_VAR){
            variable = cree_n_dec_var(yylval.string);
/*Ici j'envoyais un pointeur sur la valeur actuelle de yylval.string, j'avais donc la valeur correspondant au dernier token*/
            cc = yylex();
        }
    }
    if (syntout) out("</declVariable>\n");
    return variable;
}

Je pense que c'est bon (je n'ai pas edit mon précédent message pour ne pas mélanger questions et solutions) je vais quand même attendre un peu avant de mettre résolu mais je pense que j'ai réglé le problème.

En tout cas merci beaucoup de ton aide et de ta patience mala92 !!