emmesse

Dans un compilateur, l'analyseur syntaxique vérifie que le code source du programme est syntaxiquement cohérent. Pour cela, il se sert d’une grammaire hors contexte. Celle-ci est un ensemble de productions.
Une production se présente sous la forme d’un identificateur, servant de tête de production, puis une flèche de gauche à droite, se lisant "peut prendre la forme de", et, en partie droite, une suite d’identificateurs. Ces derniers sont des terminaux et des non terminaux. Un terminal est un identificateur, représentant un élément du langage, qui ne se présente jamais en partie gauche d’une production, tandis que un non terminal demande à être décrit, et apparaît au moins une fois en partie gauche d’une production.
Soit un exemple de grammaire, celle décrivant une somme, représentée par la suivante:

Code :

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

1
2
3
4
5
somme → somme plus terme
somme → terme
terme → identificateur
      → nombre
      → parenthèseouvrante somme parenthèsefermante

En effet, un terme unique est la somme de ce seul terme, d'où la production somme → terme. Si on ajoute à cette somme, ainsi qu’à n’importe quelle autre somme, un "plus" et un "terme", on obtient aussi une somme:
somme → somme plus terme.
On peut réitérer cette définition à l’infini. La production de départ, somme → somme plus terme, est appelé axiome de la grammaire hors contexte.

Dérivation gauche
Pour vérifier la cohérence syntaxique du code source, on peut utiliser la dérivation gauche. Ceci consiste à écrire sur la première ligne la tête de l’axiome, puis, on remplace, à la ligne suivante, le non terminal le plus à gauche par la partie droite de la production dont ce non terminal est la tête. Par exemple, soit la grammaire suivante:

Code :

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

1
2
3
4
affectation → identificateur resteaffectation
resteaffectation → égal suiteaffectation
suiteaffectation → identificateur égal suiteaffection
                 → expression

La dérivation gauche de la phrase "identificateur égal identificateur égal expression" est la suivante:

Code :

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

1
2
3
4
5
affectation
identificateur resteaffectation
identificateur égal suiteaffectation
identificateur égal identificateur égal suiteaffectation
identificateur égal identificateur égal expression

Chaque ligne d’une dérivation est appelé proto-phrase. Elle contient des terminaux et des non terminaux. Si la dernière ligne est une phrase, autrement dit ne comporte pas de non terminaux, alors la phrase est syntaxiquement cohérente par rapport à la grammaire correspondante.
arbre syntaxique abstrait
À partir d’une grammaire et d’une phrase, on peut élaborer un arbre, appelé arbre syntaxique abstrait. La racine de cet arbre est la partie gauche de l’axiome de la grammaire. Puis les identificateurs de la partie droite constituent chacun une branche de l’arbre issue de ce non terminal. Puis, les non terminaux engendrent aussi d’autres branche de l’arbre, jusqu’aux feuilles de l’arbre, qui sont les terminaux. Par exemple, avec la phrase "terme plus terme plus terme" et la grammaire des sommes ci-dessus, on élabore cet arbre syntaxique abstrait:


Production vide
La production vide, notée ε, est utilisée dans le cas où un non terminal est optionnel, par exemple:

Code :

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

1
2
3
conditionnelle → si condition alors séquence_instructions alternative finsi
alternative → sinon séquence_instructions
            → ε

Premiers d’un non terminal
L’ensemble "premiers(A)" d’une production A → α est l’ensemble des premiers terminaux qui peuvent commencer une chaîne dérivée de α. Un ensemble premiers(X) se calcule comme ceci:
appliquer ces règles jusqu’à ce que l’on ne puisse plus ajouter de symbole, y compris la production vide ε:
• si X est un terminal alors premiers(X)={X}
• si X → ε est une production, alors ajouter ε dans premiers(X)
• si X → Y1 Y2 … Yk est une production alors ajouter "a" s’il existe "i" tel que "a" est dans premiers(Yi) et ε dans tous les premiers de Y1 à Yi-1
• si ε est dans premiers(Yj) pour tout j compris entre 1 et k alors ajouter ε à premiers(X)
• si Y1 → ε on ajoute premiers(Y2) à premiers de X. si ε est dans premiers(Y1) et dans premiers(Y2) alors on ajoute premiers(Y3) à premiers(X), et ainsi de suite
Les premiers d’une chaîne X1 X2 … Xn se calcule ainsi:
appliquer ces règles jusqu’à ce que l’on ne puisse plus ajouter de symbole, y compris la production vide ε:
• on ajoute les symboles de premiers(X1).
• si X1 → ε alors on ajoute les symboles de premiers(X2).
• si X1 → ε et X2 → ε alors on ajoute premiers(X3).
• et ainsi de suite.
• si, pour tout i compris entre 1 et n, Xi → ε alors on ajoute ε.
Dans la grammaire suivante, les premiers de suiteSi son {sinonsi;sinon;ε}

Code :

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

1
2
3
4
conditionnelle → si condition alors séquence suiteSi finsi
suiteSi → sinonsi condition alors séquence suiteSi
        → sinon séquence
        → ε

Implémentation par la méthode de la descente récursive prédictive
La descente récursive prédictive consiste à faire de chaque non terminal une fonction. Dans celle-ci on appelle les fonctions correspondantes aux non terminaux de la partie droite de la production, et les terminaux sont consommés. Dans la fonction, les productions à dériver sont choisis en fonction du premier de chaque partie droite de la production. Par exemple, considérons la grammaire de la conditionnelle vue précédement:

Code :

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

1
2
3
4
conditionnelle → si condition alors séquence suiteSi finsi
suiteSi → sinonsi condition alors séquence suiteSi
        → sinon séquence
        → ε

un extrait de l’implémentation pourrait être 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
enum terminaux {si,alors,finsi,sinonsi,sinon}
void conditionnelle(){
	if(uniteelexicale==si){
		consommer(si);
		condition();
		consommer(alors);
		sequence();
		suitesi();
		consommer(finsi);
	}
	else
		std::cerr<<"erreur"<<std::endl;
}

void suitesi(){
	if(uniteelexicale==sinonsi){
		consommer(sinonsi);
		condition();
		consommer(alors);
		sequence();
		suitesi();
	}
	else if(uniteelexicale==sinon){
		consommer(sinon);
		sequence();
	}
	else
		; //production vide
}

consommer(terminal symbole){
	if(uniteelexicale==symbole)
		uniteelexicale=analex();//unitée lexicale suivante
	else
		std::cerr<<"erreur"<<std::endl;
}

Suppression des récursivités à gauche
un problème de boucle infinie peut arriver dans le cas où la partie droite d'une production débute par le même non terminal que la tête de cette production, comme, par exemple, la production somme:

Code :

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

somme → somme plus terme

En effet, la fonction somme() débute par un appel récursif sans que aucune unité lexicale n’aie été consommée, et produit donc une boucle infinie. Cela s’appelle une récursivité à gauche.
Prenons l'exemple cette grammaire récursive à gauche:

Code :

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

A → A α | β

voici l'arbre syntaxique abstrait pour l’entrée β α α:

Voici un arbre abstrait syntaxique issue de la même entrée, mais avec une grammaire hors contexte différente, sans récursivités à gauche:

le nœud A de cet arbre présente deux branches vers β et R. Il s’agit de la production suivante:

Code :

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

A → β R

les nœuds R ont soit deux branche vers α et R ou une branche vers ε. Il s'agit donc des productions

Code :

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

1
2
R → α R
R → ε

On a donc transformé une grammaire présentant une récursivité à gauche en une grammaire sans ce défaut. Voici la nouvelle grammaire:

Code :

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

1
2
3
A → β R
R → α R
R → ε

on peut généraliser ceci avec cette grammaire:

Code :

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

A → A α1 | A α2 | … | A αm | β1 | β2 | … |  βn

qui deviendra la suivante, sans récursivités à gauche:

Code :

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

1
2
A → β1 A' | β2 A' | … | βn A'
A' → α1 A' | α2 A' | … | αm A' | ε

application sur la grammaire des expressions
voici la grammaire des expressions:
E signifie "expression", T pour "terme", F pour "facteur", po pour parenthèse ouvrante et pf pour parenthèse fermante. L’étoile est l’opérateur de multiplication et slash celui de la division:

Code :

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

1
2
3
4
5
6
7
8
9
10
E → E plus T
  → E moins T
  → T
T → T étoile F
  → T slash F
  → F
F → identificateur
  → nombre
  → moins F
  → po E pf

cette grammaire tient compte de la priorité des opérateurs étoile et slash sur les opérateurs plus et moins.
cela donne, sans récursivités à gauche et avec les mêmes priorités des opérateurs:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
E → T E'
E' → plus T E'
   → moins T E'
   → ε
T → F T'
T' → étoile F T'
   → slash F T'
   → ε
F → identificateur
  → nombre
  → moins F
  → po E pf

Les suivants d’un non terminal
Pour un non-terminal A, suivants(A) est l’ensemble des terminaux qui peuvent apparaître immédiatement à droite de A dans une proto-phrase. Voici comment le calculer:
• si A est le symbole de départ (la partie gauche de l’axiome) alors on ajoute dollar, le marqueur de fin, dit le terminal qui n'existe dans aucune grammaire, à suivants(A)
• Si A → αBβ, on ajoute premiers(β), à l'exception de ε, à suivants(B);
• Si A → αB ou A → αBβ avec ε ∈ premiers(β), on ajoute les éléments de suivants(A) à suivants(B).

analyse descendante non récursive
L’analyse descendante non récursive consiste à utiliser une pile qui contiendra la proto-phrase en cours de dérivation. L’élément le plus à gauche de la proto-phrase se trouvera au sommet de la pile.
Si le sommet de la pile est un terminal, soit le terminal du texte d’entrée correspond au sommet de la pile, auquel cas ce sommet est dépilé, et le symbole suivant est lu, soit ils ne correspondent pas et une erreur de syntaxe a été trouvé. Si le sommet de pile est un non terminal, alors il est dépilé, puis on empile la partie droite de la production dont la tête est le non terminal considéré.
Au début du processus, la pile contient au fond le marqueur de fin, appelé dollar, qui est le terminal qui n’existe dans aucune grammaire. Puis au sommet on met la partie gauche de l’axiome.
La production qui doit être empilée à la place du non terminal est issue d’une table d’analyse, dont le nom est M. Celle-ci a une ligne par non terminal et une colonnes par terminal.
Pour construire cette table, les productions P → α β sont à la ligne du non terminal P et aux colonnes des éléments de premiers( α β ). Les productions P → ε sont à la ligne indiquée par P et aux colonnes indiquées par suivants(P). Les cases vides sont les cas d’erreur.
voici l'algorithme de l'analyse descendante non récursive:

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
positionner le pointeur d'entrée pe de sorte qu’il pointe vers a, le premier symbole du texte d'entrée;
mettre le sommet de pile dans X
tant que X≠dolar /* la pile n'est pas vide */
	si X vaut a
		dépiler et faire avancer pe (a est alors l'unité lexicale suivante)
	sinonsi X est un terminal alors
		erreur();
	sinonsi M[X,a] est une entrée d'erreur alors
		erreur();
	sinonsi M[X,a] = X → Y1 Y2…Yk
		émettre la production X → Y1 Y2…Yk
		dépiler
		empiler Yk, Yk-1,…,Y1, avec Y1 au sommet
	finsi
	mettre le sommet de pile dans X;
fintantque

Pour construire la table d’analyse de la grammaire des expressions vue ci-dessus nous allons déterminer les ensembles premiers et suivants de chaque non terminal de la grammaire. Souvenons-nous que po indique parenthèse ouvrante, et pf parenthèse fermante.

Code :

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

1
2
3
4
5
6
7
8
9
10
premiers(E)={identificateur;nombre;moins;po}
suivants(E)={pf;dollar}
premiers(E')={plus;moins;ε}
suivants(E')={pf;dollar}
premiers(T)={identificateur;nombre;moins;po}
suivants(T)={plus;moins;pf;dollar}
premiers(T')={étoile;slash;ε}
suivants(T')={plus;moins;pf;dollar}
premiers(F)={identificateur;nombre;moins;po}
suivants(F)={étoile;slash;plus;moins;pf;dollar}

voici la table d'analyse:


Ratrappage sur erreur en mode panique

le principe du mode panique est de, après une entrée erronée, sauter les unités lexicales jusqu'à lire une unité lexicale de synchronisation. L'efficacité de ce rattrapage est le choix des unité lexicales de synchronisation. Ici, nous allons choisir les suivants de chaque non terminal comme ensembles de synchronisation de ces non terminaux. Cela ne sera pas suffisant dans le cas d'autres compilateurs. Nous pourrions par exemple choisir aussi les fin de blocs et les suivants d'une expressions comme unité lexicales de synchronisation.
Si le sommet de pile contient un terminal et que celui-ci n'apparait pas dans le texte d'entrée alors on dépile ce sommet de pile.
voici la table d'analyse avec les cas de synchronisation. Ceux-ci se situent, pour chaque non terminal, à la ligne de ce non terminal et aux colonnes de ses terminaux de synchronisation.

cette table s'utilise ainsi:
Si le compilateur doit accéder à une case d'erreur, alors l'unité lexicale est sauté (on lit l'unité lexicale suivante). Si, par contre, cette case est une case synchro, alors le sommet de pile est dépilé.

Le programme
En ce qui concerne l’analyseur lexical, je vous propose de consulter mon billet de blog ici.
Nous aurons besoin d’un analyseur lexical qui isole les unités lexicales plus, moins, étoile, slash, identificateur, nombre, parenthèse ouvrante, parenthèse fermante et le marqueur de fin (dollar).

Code cpp :

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

1
2
3
4
5
6
7
8
9
10
11
12
//terminal.hpp
#ifndef TERMINAL_HPP 
#define TERMINAL_HPP
 
enum terminal {identificateur,nombre,plus,moins,etoile,slash,po,pf,dollar};
enum symbole{sE,sEprim,sT,sTprim,sF,snombre,sidentificateur,splus,smoins,
	     setoile,sslash,spo,spf,sdollar,sepsilon,ssynchro};
enum nonterminal{E,Eprim,T,Tprim,F};
constexpr size_t nbterminaux=9;
constexpr size_t nbnonterminaux=5;
constexpr size_t nbsymboles=16;
#endif

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
//main.cpp
#include <iostream>
#include <string>
#include <vector>
 
#include "syntaxique.hpp"
 
int main(int argc,char *argv[]){
  std::vector<std::string>args;
  for(unsigned i=0;i<static_cast<unsigned>(argc);++i)
    args.push_back(argv[i]);
  if(argc!=2)
    std::cerr<<"manque le fichier"<<std::endl;
  else{
    syntaxique S(args[1]);
    S.anasynt();
  }
}

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
//syntaxique.hpp
#ifndef SYNTAXIQUE_HPP
#define SYNTAXIQUE_HPP
#include <vector>
#include <string>

#include "lexical.hpp"
#include "terminal.hpp"

class syntaxique{
public:
  syntaxique(std::string fichierentree);
  void anasynt();
private:
  lexical L;
  terminal ulex;
  std::string lexeme;
  unsigned long int ligne;
  nonterminal symbole2nonterminal[nbnonterminaux];
  std::string symbole2string[nbsymboles];
  std::vector<symbole>pile;
  std::vector<symbole>M[nbnonterminaux][nbterminaux];
  bool vaut(symbole X, terminal a);
  void emettre(std::vector<symbole> const &production);
  bool estterminal(symbole X);
};
#endif

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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//syntaxique.cpp
#include <iostream>
#include <string>
#include <vector>

#include "terminal.hpp"
#include "syntaxique.hpp"

syntaxique::syntaxique(std::string fichierentree):L(fichierentree),ligne(1){
  symbole2nonterminal[sE]=E;
  symbole2nonterminal[sEprim]=Eprim;
  symbole2nonterminal[sT]=T;
  symbole2nonterminal[sTprim]=Tprim;
  symbole2nonterminal[sF]=F;
  symbole2string[snombre]="nombre";
  symbole2string[splus]="plus";
  symbole2string[smoins]="moins";
  symbole2string[setoile]="etoile";
  symbole2string[sslash]="slash";
  symbole2string[spo]="parenthèse ouvrante";
  symbole2string[spf]="parenthèse fermante";
  symbole2string[sdollar]="fin";
  symbole2string[sE]="expression";
  symbole2string[sEprim]="expressionprim";
  symbole2string[sT]="terme";
  symbole2string[sTprim]="termeprim";
  symbole2string[sF]="facteur";
  symbole2string[sidentificateur]="identificateur";
  symbole2string[sepsilon]="epsilon";

  M[E][plus]=M[E][etoile]=M[E][slash]={};
  M[E][pf]=M[E][dollar]={ssynchro};
  M[E][moins]=M[E][identificateur]=M[E][nombre]=M[E][po]={sT,sEprim};

  M[Eprim][plus]={splus,sT,sEprim};
  M[Eprim][moins]={smoins,sT,sEprim};
  M[Eprim][pf]=M[Eprim][dollar]={sepsilon};
  M[Eprim][etoile]=M[Eprim][slash]=M[Eprim][identificateur]=M[Eprim][nombre]=M[Eprim][po]={};

  M[T][moins]=M[T][identificateur]=M[T][nombre]=M[T][po]={sF,sTprim};
  M[T][plus]=M[T][pf]=M[T][dollar]={ssynchro};
    M[T][etoile]=M[T][slash]={};

  M[Tprim][plus]=M[Tprim][moins]=M[Tprim][pf]=M[Tprim][dollar]={sepsilon};
  M[Tprim][etoile]={setoile,sF,sTprim};
  M[Tprim][slash]={sslash,sF,sTprim};
  M[Tprim][identificateur]=M[Tprim][nombre]=M[Tprim][po]={};

  M[F][moins]={smoins,sF};
  M[F][identificateur]={sidentificateur};
  M[F][nombre]={snombre};
  M[F][po]={spo,sE,spf};
  M[F][plus]=M[F][etoile]=M[F][slash]=M[F][pf]=M[F][dollar]={ssynchro};
  pile.push_back(sdollar);
  pile.push_back(sE);
}

bool syntaxique::vaut(symbole X,terminal ulex){
  return X==sidentificateur && ulex==identificateur
    ||X==snombre && ulex==nombre
    ||X==splus && ulex==plus
    ||X==smoins && ulex==moins
    ||X==setoile && ulex==etoile
    ||X==sslash && ulex==slash
    ||X==spo && ulex==po
    ||X==spf && ulex==pf
    ||X==sdollar && ulex==dollar;
}

void syntaxique::anasynt(){
  L.analex(ulex,lexeme,ligne);
  symbole X=pile.back();//X est le sommet de la pile
  while(X!=sdollar){
    if(vaut(X,ulex)){
      pile.pop_back();
      L.analex(ulex,lexeme,ligne);
    }
    else if(estterminal(X)){
      std::cerr<<"ligne "<<ligne<<": "<<symbole2string[X]<<" attendu"
	       <<std::endl;
      pile.pop_back();
    }
    else if(M[X][ulex].size()==0){
      std::cerr<<"ligne "<<ligne<<": erreur"<<std::endl;
      if(ulex==dollar){
	std::cerr<<"fin de fichier prématuré"<<std::endl;
	break;
      }
      L.analex(ulex,lexeme,ligne);
    }
    else if(M[X][ulex][0]==ssynchro){
      std::cerr<<"ligne "<<ligne<<": erreur"<<std::endl;
      pile.pop_back();
    }
    else{
      std::cout<<symbole2string[X]<<" -> ";
      emettre(M[X][ulex]);
      pile.pop_back();
      for(int i=M[X][ulex].size();i>0;i--){
	symbole empiler=M[X][ulex][i-1];
	if(empiler!=sepsilon)
	  pile.push_back(empiler);
      }
    }
    X=pile.back();
  }
  if(ulex!=dollar)
    std::cerr<<"le fichier d'entrée n'a pas été entierement analysé"<<std::endl;

}

void syntaxique::emettre(std::vector<symbole> const &production){
  for(size_t i=0;i<production.size();i++){
    std::cout<<symbole2string[production[i]];
    if(i<production.size()-1)
      std::cout<<" ";
  }
  std::cout<<std::endl;
}

bool syntaxique::estterminal(symbole X){
  return X==sepsilon || X==splus || X==smoins || X==setoile || X==sslash
    || X==spo || X==spf || X==sidentificateur  || X==snombre || X==sdollar;
}

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
//lexical.hpp
 
#ifndef LEXICAL_HPP
#define LEXICAL_HPP
 
#include <string>
#include <fstream>
 
#include "terminal.hpp"
 
class lexical{
public:
  lexical(std::string fichierentree);
  void analex(terminal &ulex,std::string &lexeme,unsigned long int &ligne);
private:
  std::string texte;
  std::ifstream entree;
  size_t enavant,debutlex;
  int taille;
  std::string readFileIntoString(const std::string path);
  bool obtenirFDF(terminal &ulex);
  bool obtenirblanc(unsigned long int &ligne);
  bool obteniridentificateur(terminal &ulex,std::string &lexeme);
  bool obtenirnombre(terminal &ulex,std::string &lexeme);
  bool obtenirplus(terminal &ulex);
  bool obtenirmoins(terminal &ulex);
  bool obteniretoile(terminal &ulex);
  bool obtenirslash(terminal &ulex);
  bool obtenirpo(terminal &ulex);
  bool obtenirpf(terminal &ulex);
  std::string carsuiv();
};
#endif

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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
//lexical.cpp
#include <string>
#include <iostream>
 
#include "lexical.hpp"
#include "terminal.hpp"
 
lexical::lexical(std::string fichierentree):enavant(0),debutlex(0){
  entree.open(fichierentree.c_str());
  texte = readFileIntoString(fichierentree);
}
 
std::string lexical::readFileIntoString(const std::string path) {
  if (!entree.is_open()){
    std::cerr << "Could not open the file - '" << path << "'" << std::endl;
    exit(1);
  }
  else{
    return std::string(std::istreambuf_iterator<char>(entree),
		       std::istreambuf_iterator<char>());
  }
}
 
void lexical::analex(terminal &ulex,std::string &lexeme,
		     unsigned long int &ligne){
  if(obtenirblanc(ligne)){
    analex(ulex,lexeme,ligne); //ignorer le blanc. enavant pointe sur le premier caractère du lexeme suivant
  }
  else if(obtenirFDF(ulex))
    return;
  else if(obteniridentificateur(ulex,lexeme))
    return;
  else if(obtenirnombre(ulex,lexeme))
    return;
  else if(obtenirplus(ulex))
    return;
  else if(obtenirmoins(ulex))
    return;
  else if(obteniretoile(ulex))
    return;
  else if(obtenirslash(ulex))
    return;
  else if(obtenirpo(ulex)) //po=parenthèse ouvrante
    return;
  else if(obtenirpf(ulex)) //pf=parenthèse fermante
    return;
  else{
    std::cerr<<"caratère hors langage"<<std::endl;
    enavant+=taille;//ignorer le caractère hors  langage
    analex(ulex,lexeme,ligne);
  }
}
 
bool lexical::obtenirblanc(unsigned long int &ligne){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="\n"){
	ligne++;
	etat=1;
      }
      else if(caracterelu==" "||caracterelu=="\t"||caracterelu=="\r")
	etat=1;
      else{
	continuer=false;
	reussi=false;
	enavant=debutlex;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
    }
  return reussi;
}
 
bool lexical::obtenirFDF(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu[0]=='\0')
	etat=1;
      else{
	continuer=false;
	reussi=false;
	enavant=debutlex;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=dollar;
      break;
    }
  return reussi;
}
 
bool lexical::obteniridentificateur(terminal &ulex,std::string &lexeme){
  int etat=0;
  bool continuer=true;
  bool reussi;
  lexeme="";
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="_"){
	lexeme+=caracterelu;
	etat=0;
      }
      else if(caracterelu >="A" && caracterelu<="Z" || caracterelu >= "a" && caracterelu <= "z"){
	lexeme+=caracterelu;
	etat=1;
      }
      else{//echec
	enavant=debutlex;
	continuer=false;
	reussi=false;
      }
      break;
    case 1:
      caracterelu=carsuiv();
      if(caracterelu >="A" && caracterelu<="Z" || caracterelu >= "a" && caracterelu <= "z" || caracterelu >="0" && caracterelu <= "9" || caracterelu=="_"){
	lexeme+=caracterelu;
	etat=1;
      }
      else //autre caractère
	etat=2;
      break;
    case 2:
      continuer=false;
      reussi=true;
      enavant-=taille;//reculer pour le dépassement de caractère (autre caractère)
      ulex=identificateur;
    }
  return reussi;
}
 
bool lexical::obtenirnombre(terminal &ulex,std::string &lexeme){
  int etat=0;
  bool continuer=true;
  bool reussi;
  lexeme="";
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu==","){
	lexeme+=caracterelu;
	etat=2;
      }
      else if(caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=1;
      }
      else{
	continuer=false;
	reussi=false;
	enavant=debutlex;
      }
      break;
    case 1:
      caracterelu=carsuiv();
      if(caracterelu==","){
	lexeme+=caracterelu;
	etat=2;
      }
      else if(caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=1;
      }
      else if(caracterelu=="e"||caracterelu=="E"){
	lexeme+=caracterelu;
	etat=5;
      }
      else
	etat=4;//autre
      break;
    case 2:
      caracterelu=carsuiv();
      if(caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=3;
      }
      else{
	enavant=debutlex;
	continuer=false;
	reussi=false;
      }
      break;
    case 3:
      caracterelu=carsuiv();
      if(caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=3;
      }
      else if(caracterelu=="E" || caracterelu=="e"){
	lexeme+=caracterelu;
	etat=5;
      }
      else{
	etat=4;//autre caractère
      }
      break;
    case 4:
      continuer=false;
      reussi=true;
      ulex=nombre;
      enavant-=taille;//reculer pour le dépassement de caractère (autre caractère)
      break;
    case 5:
      caracterelu=carsuiv();
      if(caracterelu=="+" || caracterelu=="-"){
	lexeme+=caracterelu;
	etat=6;
      }
      else if (caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=7;
      }
      else{
	enavant=debutlex;
	continuer=false;
	reussi=false;
      }
      break;
    case 6:
      caracterelu=carsuiv();
      if (caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=7;
      }
      else{
	enavant=debutlex;
	continuer=false;
	reussi=false;
      }
      break;
    case 7:
      caracterelu=carsuiv();
      if (caracterelu>="0" && caracterelu<="9"){
	lexeme+=caracterelu;
	etat=7;
      }
      else
	etat=4;
      break;
    }
  return reussi;
}

bool lexical::obtenirplus(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="+")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=plus;
      break;
    }
  return reussi;
}

bool lexical::obtenirmoins(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="-")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=moins;
      break;
    }
  return reussi;
}

bool lexical::obteniretoile(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="*")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=etoile;
      break;
    }
  return reussi;
}

bool lexical::obtenirslash(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="/")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=slash;
      break;
    }
  return reussi;
}

bool lexical::obtenirpo(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu=="(")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=po;
      break;
    }
  return reussi;
}

bool lexical::obtenirpf(terminal &ulex){
  int etat=0;
  bool continuer=true;
  bool reussi;
  debutlex=enavant;
  std::string caracterelu;
  while(continuer)
    switch(etat){
    case 0:
      caracterelu=carsuiv();
      if(caracterelu==")")
	etat=1;
      else{
	enavant=debutlex;
	reussi=continuer=false;
      }
      break;
    case 1:
      continuer=false;
      reussi=true;
      ulex=pf;
      break;
    }
  return reussi;
}

std::string lexical::carsuiv(){
  if((unsigned char)texte[enavant] >= (unsigned char)0 && texte[enavant] <= (unsigned char)127)
    taille=1;
  else if((unsigned char)texte[enavant] >= (unsigned char)0xC2 && (unsigned char)texte[enavant] <= (unsigned char)0xdf)
    taille=2;
  else if((unsigned char)texte[enavant] >= (unsigned char)0xe0 && (unsigned char)texte[enavant] <= (unsigned char)0xef)
    taille=3;
  else if((unsigned char)texte[enavant] >= (unsigned char)0xf0 && (unsigned char)texte[enavant] <= (unsigned char)0xff)
    taille=4;
  else{
    std::cerr<<"caractère non UTF-8"<<std::endl;
    enavant++;
    return carsuiv();
  }
  std::string c=texte.substr(enavant,taille);
  enavant+=taille;
  return c;
}

l'expression à anlyser se trouve dans un fichier. le nom de ce fichier devra être mentionné dans la ligne de commande
mettons par exemple dans ce fichier l'expression r+84-5/(a+b)*25
ce programme répondra:

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
expression -> terme expressionprim
terme -> facteur termeprim
facteur -> identificateur
termeprim -> epsilon
expressionprim -> plus terme expressionprim
terme -> facteur termeprim
facteur -> nombre
termeprim -> epsilon
expressionprim -> moins terme expressionprim
terme -> facteur termeprim
facteur -> nombre
termeprim -> slash facteur termeprim
facteur -> parenthèse ouvrante expression parenthèse fermante
expression -> terme expressionprim
terme -> facteur termeprim
facteur -> identificateur
termeprim -> epsilon
expressionprim -> plus terme expressionprim
terme -> facteur termeprim
facteur -> identificateur
termeprim -> epsilon
expressionprim -> epsilon
termeprim -> etoile facteur termeprim
facteur -> nombre
termeprim -> epsilon
expressionprim -> epsilon

ou plus simplement avec a*5+b

Code :

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

1
2
3
4
5
6
7
8
9
10
11
expression -> terme expressionprim
terme -> facteur termeprim
facteur -> identificateur
termeprim -> etoile facteur termeprim
facteur -> nombre
termeprim -> epsilon
expressionprim -> plus terme expressionprim
terme -> facteur termeprim
facteur -> identificateur
termeprim -> epsilon
expressionprim -> epsilon