Discussion :

[emmesse]

Bonjour,

je suis dans l'algorithme de production (im)productives et je voulais savoir si il faut tenir compte des production vide.
epsilon est-il un terminal? la production vide est-elle productive?

Code C++ :

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
void syntaxique::improductifs(){
  std::vector<std::string>Prod,nouveaux;
  bool dansProd,pasajouter;
  for(auto p:grammaire){
    for(auto c:p.getlistecorps()){
      dansProd=true;
      for(auto s:c.getcontenu())
	if(s!="epsilon" && absent(terminaux,s)){
	  dansProd=false;
	  break;
	}
      if(dansProd && absent(Prod,p.gettete())){
	Prod.push_back(p.gettete());
	break;
      }
    }
  }
  do{
    nouveaux.clear();
    for(auto A:grammaire){
      if(absent(Prod,A.gettete()))
	for(auto c:A.getlistecorps()){
	  pasajouter=false;
	  for(auto s:c.getcontenu())
	    if(absent(terminaux,s) && absent(Prod,s)){
	      pasajouter=true;
	      break;
	    }
	}
      if( ! pasajouter)
	nouveaux.push_back(A.gettete());
    }
    for(auto x:nouveaux)
      if(absent(Prod,x))
	Prod.push_back(x);
  }while( ! nouveaux.empty());
  for(auto p:grammaire)
    if(absent(Prod,p.gettete())){
      std::cerr<<"Le non-terminal "<<p.gettete()<<" est improductif"
	       <<std::endl;
      ecriresortie=false;
    }
}

Code C++ :

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <string>
#include <vector>
#include <map>
#include "uniLex.hpp"
#include "lexical.hpp"
#include "symboles.hpp"
 
class production;
class corps;
 
class syntaxique{
public:
  syntaxique(char *nomfichier);
  void consommer(terminal const &t);
  void Grammaire();
  std::vector<production>Restegrammaire();
  std::vector<production>Suitegrammaire(std::vector<production>
					const &suitegrammaire_h);
  production Production();
  std::vector<corps> Listecorps();
  std::vector<corps> Restelistecorps(std::vector<corps>const
				     &restelistecorps_h);
  corps Corps();
  corps Restecorps(corps const &restecorps_h);
  std::string Tete();
  void sortie();
  std::vector<std::string>finprod(corps c,std::string s);
  void touslessuivants();
  void deuxannulables(production const &p);
  std::vector<std::string>suivants(std::string const &n);
  std::vector<std::string>suivantsn(std::string const &s,int const &n);
  void ajoutersuivants(std::vector<std::string> const &v,
		       std::string const &s);
  void recursivitees(production const &A);
  void ambigue(production const &p);
  //std::vector<production>commence(std::string const &recherche);
  std::string gettete();
  production quelleproduction(std::string const &t);
  std::vector<std::string> nonterminaux0(production const &A);
  bool annulable(std::string s);
  bool annulable(corps const &c);
  bool annulable(production const &p);
  bool annulable(std::vector<std::string>const & groupe);
  std::vector<std::string>premiers(std::string const &s);
  std::vector<std::string>premiers(std::vector<std::string>const & groupe);
  int comptersymboles(std::string const &s);
  void factorisable(production const &p);
  void improductifs();
private:
  bool ax;
  lexical L;
  uniLex a;
  std::vector<std::string>symboles;
  std::vector<std::string>nonterminaux;
  std::vector<std::string>terminaux;
  std::vector<std::string>pilerecurs;
  std::vector<std::string>pastester;
  std::vector<std::string>pilesuivants,dejacalcule,encours;
  std::vector<production>grammaire;
  bool ecriresortie,recurs;
  std::map<std::string,std::vector<std::string>>tabsuivants;
  std::map<std::string,int>traite;
};
 
class production{
public:
  void settete(std::string const &t);
  std::string gettete();
  void setlistecorps(std::vector<corps> const &liste);
  std::vector<corps>getlistecorps();
  bool deuxepsilon();
  void setaxiome(bool ax);
  bool getaxiome();
private:
  std::string tete;
  std::vector<corps> listecorps;
  bool axiome;
};
 
class corps{
public:
  void clear();
  void ajoutermot(std::string const &m);
  std::string getelem(int const &n);
  std::vector<std::string>getcontenu();
private:
  std::vector<std::string> contenu;
};

une idée?

[emmesse]

j'avais mal placé le if( ! pasajouter).
avec le code ci-dessous ça marche
(ça marche aussi si on ne teste pas si s!="epsilon")

Code C++ :

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
void syntaxique::improductifs(){
  std::vector<std::string>Prod,nouveaux;
  bool dansProd,pasajouter;
  for(auto p:grammaire){
    for(auto c:p.getlistecorps()){
      dansProd=true;
      for(auto s:c.getcontenu())
	if(s!="epsilon" && absent(terminaux,s)){
	  dansProd=false;
	  break;
	}
      if(dansProd && absent(Prod,p.gettete())){
	Prod.push_back(p.gettete());
	break;
      }
    }
  }
  do{
    nouveaux.clear();
    for(auto A:grammaire){
      if(absent(Prod,A.gettete()))
	for(auto c:A.getlistecorps()){
	  pasajouter=false;
	  for(auto s:c.getcontenu())
	    if(s!="epsilon" && absent(terminaux,s) && absent(Prod,s)){
	      pasajouter=true;
	      break;
	    }
	  if( ! pasajouter)
	    nouveaux.push_back(A.gettete());
	}
    }
    for(auto x:nouveaux)
      if(absent(Prod,x))
	Prod.push_back(x);
  }while( ! nouveaux.empty());
  for(auto p:grammaire)
    if(absent(Prod,p.gettete())){
      std::cerr<<"Le non-terminal "<<p.gettete()<<" est improductif"
	       <<std::endl;
      ecriresortie=false;
    }
}

[emmesse]

en fait, je ne sais toujours pas si epsilon est à considérer comme terminal dans le calcul des productions improductives
si on écrit la grammaire suivante:

Code :

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

1
2
3
A -> b B | a C
B -> b
C -> a C | epsilon

la production C est-elle improductive?

une idée?

[emmesse]

epsilon est un terminal et permet à C d'être productif
sans epsilon, C serait improductif car dérivation à l'infini