analyse lexical en c++

Version imprimable

slt tous le monde j'ai un programme prolog et je veux écrir un programme en c++ pour l'analyse lexical de se programme (prolog);
et je c'est pas comment faire
merci d'avance

voila le programme en prolog
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 pere(farid,yacine). pere(yacine,djamel). pere(zaki,lotfi). pere(lotfi,halim). mere(imene,fatiha). mere(fatiha,nadjet). gpere(X,Z):-pere(X,Y),pere(Y,Z). gmere(X,Z):-mere(X,Y),mere(Y,Z).

22/11/2009, 19h13
jfouche

boost::spirit doit pouvoir répondre à la question, un tutorial est disponible...

Tiens, j'ai voulu tester boost.spirit (que je ne connaissais pas), et cela donne ça :

Code:

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
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
#include <boost/algorithm/string/trim.hpp>
 
#include <iostream>
#include <fstream>
#include <string>
 
struct Result
{
	enum Type { PERE, MERE };
 
	Type        type;
	std::string nom1;
	std::string nom2;
};
 
template <typename Iterator>
bool do_parse(Iterator first, Iterator last, Result& res)
{
	using boost::spirit::qi::eps;
	using boost::spirit::qi::char_;
	using boost::spirit::qi::_1;
	using boost::spirit::qi::phrase_parse;
	using boost::spirit::ascii::space;
	using boost::phoenix::ref;
	using boost::phoenix::push_back;
 
	Result::Type type;
	std::string  nom1;
	std::string  nom2;
 
	bool parsed = phrase_parse(first, last,
 
		//  Begin grammar
		(
			"pere(" >> +(char_ - ',')[push_back(ref(nom1), _1)] >> ',' 
			        >> +(char_ - ')')[push_back(ref(nom2), _1)] >> ")."
					>> eps[ref(type) = Result::PERE]
		|
			"mere(" >> +(char_ - ',')[push_back(ref(nom1), _1)] >> ',' 
			        >> +(char_ - ')')[push_back(ref(nom2), _1)] >> ")."
					>> eps[ref(type) = Result::MERE]
		),
		//  End grammar
 
		space);
 
	if (!parsed || first != last) // fail if we did not get a full match
		return false;
	res.type = type;
	res.nom1 = nom1;
	res.nom2 = nom2;
	return parsed;
}
 
/**
 *  Main program
 */
int main()
{
	std::ifstream ifile("test.txt");
	if (!ifile) {
		return EXIT_FAILURE;
	}
 
	bool ok = true;
	std::string line;
	while (ok && std::getline(ifile, line)) {
		boost::trim(line);
		if (line.empty()) {
			continue;
		}
		std::cout << "Parsing '" << line << "' : ";
        Result res;
        if (do_parse(line.begin(), line.end(), res)) {
            std::cout << "Succeeded" << std::endl;
            std::cout << " -> " << res.type << " : " << res.nom1 << ", " << res.nom2 << std::endl;
            std::cout << std::endl;
        }
        else {
            std::cout << "Failed !" << std::endl;
        }
	}
    return 0;
}

C'est probablement pas la meilleur solution, mais ça marche (pour pere et mere ). Je te laisse poursuivre.

PS : Des essais effectués par Eran Ifrah (l'auteur de l'IDE CodeLite) a montré que ce parseur est très lent par rapport à yacc/flex.

23/11/2009, 17h28
nikko34

ça marche sauf si c'est un cours et que l'exercise est d'écrire soit-même le parseur de zéro.
23/11/2009, 17h51
Goten

Citation:

PS : Des essais effectués par Eran Ifrah (l'auteur de l'IDE CodeLite) a montré que ce parseur est très lent par rapport à yacc/flex.

Ca dépend quelle version de spirit il a testé... si il est resté sur spirit.classic alors oui c'est un problème connu le parsage est lent sur certains compilos / machines.
23/11/2009, 18h34
jfouche

Citation:

Envoyé par nikko34

ça marche sauf si c'est un cours et que l'exercise est d'écrire soit-même le parseur de zéro.

Oui, mais bon, si est un exo, je ne suis pas sûr que c'est la réponse attendu par le prof. En plus, c'était plus pour tester, ce n'est pas fini, et je ne fais rien des résultats. Bref, si c'est un étudiant devant répondre à un exercice, il lui reste un gros travail d'apprentissage de cette bibliotheque si il veut arriver à ces fins...
23/11/2009, 18h36
jfouche

Citation:

Envoyé par Goten

Ca dépend quelle version de spirit il a testé... si il est resté sur spirit.classic alors oui c'est un problème connu le parsage est lent sur certains compilos / machines.

Il avait fait ces essais il y plus de 2 ans, donc sur une version 1.x. L'autre argument qu'il soumettait était la maintenance de parseur, plus simple (selon lui) avec yacc/flex. Vu que je n'ai pas le courage d'implementer un parseur c++ complet, je ne saurai dire si la version 2.1 de spirit à rattrapé suffisament sont retard pour pouvoir être intégrer dans le dev d'un IDE pour c++.
24/11/2009, 09h56
3DArchi

Citation:

Envoyé par jfouche

L'autre argument qu'il soumettait était la maintenance de parseur, plus simple (selon lui) avec yacc/flex.

J'ai fait à un moment donné un parser pour un projet avec Boost.Spirit. Le problème de perf n'était pas vraiment critique. Mais j'ai galéré à rendre compatible le code entre différents compilateurs. Et à chaque nouvelle version d'un compilateur ou de Boost, je repartais sur de nouveaux problèmes de compilation. Je n'ai pas essayé avec la dernière version car je dois avouer que ça m'a un peu refroidi.
24/11/2009, 16h45
JulienDuSud

Tiens, quelqu'un aurait un "vrai" tuto pour se lancer avec yacc/bison en C++ ?

Parce que la doc que j'ai trouvé concerne le C et rien qu'ça....
24/11/2009, 16h53
screetch

le parsing d'un fichier texte etant quelque chose de particulierement séquentiel, il n'est pas réellement necessaire d'ecrire en C++
ce qui peut etre interessant c'est avoir en sortie du parsing un arbre syntaxique, ce qui a cette fois ci plus de sens en objet.

Citation:

Envoyé par screetch

le parsing d'un fichier texte etant quelque chose de particulierement séquentiel, il n'est pas réellement necessaire d'ecrire en C++
ce qui peut etre interessant c'est avoir en sortie du parsing un arbre syntaxique, ce qui a cette fois ci plus de sens en objet.

Oui, c'est le but.

Exemple:
Code:

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 struct ScriptedApplication { vector<Variable> global_variables; vector<Procedure> global_functions; Procedure main; void run( main_params ); }; struct Procedure { vector< variant > params; Bloc instructions; ret_type run( params ); }; struct Bloc { vector< variant > bloc_instruction; // variant bloc ou instruction finale }; struct instruction { enum type { DECLARATION, ASSIGNATION, CONDITION_IF, LOOP_WHILE, ... }; ... };
etc...

Je sais que c'est très simple à faire avec Spirit, mais vu qu'apparemment tout le monde préfère YACC/LEX (apparemment pour sa simplicité ?) je me demandais ce que je ratais...

Et pas moyen de trouver une doc, du coup j'demande :p

24/11/2009, 18h04
white_tentacle

J'ai dans l'idée que les parseurs générés par lexx/yacc ne sont pas réentrants ? (utilisation de variables globales, de mémoire). C'est toujours vrai ou c'est ma mémoire qui me joue des tours ?
24/11/2009, 18h14
screetch

http://www.delorie.com/gnu/docs/bison/bison_66.html
http://flex.sourceforge.net/manual/Reentrant.html

Citation:

Envoyé par JulienDuSud

Oui, c'est le but.

Exemple:

Code:

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
 
struct ScriptedApplication {
    vector<Variable> global_variables;
    vector<Procedure> global_functions;
    Procedure main;
 
    void run( main_params );
};
 
struct Procedure {
   vector< variant > params;
   Bloc instructions;
 
   ret_type run( params );
};
 
struct Bloc {
   vector< variant > bloc_instruction; // variant bloc ou instruction finale
};
 
struct instruction {
   enum type {
      DECLARATION,
      ASSIGNATION,
      CONDITION_IF,
      LOOP_WHILE,
      ...
   };
   ...
};

etc...

Je sais que c'est très simple à faire avec Spirit, mais vu qu'apparemment tout le monde préfère YACC/LEX (apparemment pour sa simplicité ?) je me demandais ce que je ratais...

Et pas moyen de trouver une doc, du coup j'demande :p

Code:

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
%{
#include <cstdio>
#include <cstdlib>
 
class Operation
{
public:
    virtual ~Operation() { }
    virtual int eval() const = 0;
};
 
class Value : public Operation
{
    int m_value;
public:
    Value(int v) : m_value(v) { }
    virtual int eval() const { return m_value; }
};
 
class BinaryOperation : public Operation
{
protected:
    const Operation* m_left;
    const Operation* m_right;
 
    BinaryOperation(const Operation* left, const Operation* right) : m_left(left), m_right(right) { }
    ~BinaryOperation() { delete m_left; delete m_right; }
};
 
class Addition : public BinaryOperation
{
public:
    Addition(const Operation* left, const Operation* right)
        : BinaryOperation(left, right)
    {
    }
    virtual int eval() const { return m_left->eval()+m_right->eval(); }
};
 
class Soustraction : public BinaryOperation
{
public:
    Soustraction(const Operation* left, const Operation* right)
        : BinaryOperation(left, right)
    {
    }
    virtual int eval() const { return m_left->eval()-m_right->eval(); }
};
 
class Multiplication : public BinaryOperation
{
public:
    Multiplication(const Operation* left, const Operation* right)
        : BinaryOperation(left, right)
    {
    }
    virtual int eval() const { return m_left->eval()*m_right->eval(); }
};
 
class Division : public BinaryOperation
{
public:
    Division(const Operation* left, const Operation* right)
        : BinaryOperation(left, right)
    {
    }
    virtual int eval() const { return m_left->eval()/m_right->eval(); }
 
};
 
static int yylex()
{
    return fgetc(stdin);
}
 
static void yyerror(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
}
 
%}
 
%union
{
    const Operation* op;
}
%type <op> operation value
%start doPrint
 
 
%%
 
doPrint:
        operation '\n' { printf("result:%d\n", $1->eval()); delete $1; }
    ;
 
operation:
        value                   { $$ = $1; }
    |
        value '+' operation     { $$ = new Addition($1, $3); }
    |
        value '-' operation     { $$ = new Soustraction($1, $3); }
    |
        value '*' operation     { $$ = new Multiplication($1, $3); }
    |
        value '/' operation     { $$ = new Division($1, $3); }
    ;
 
value:
        '1' { $$ = new Value(1); }
    |
        '2' { $$ = new Value(2); }
    |
        '3' { $$ = new Value(3); }
    |
        '4' { $$ = new Value(4); }
    |
        '5' { $$ = new Value(5); }
    |
        '6' { $$ = new Value(6); }
    |
        '7' { $$ = new Value(7); }
    |
        '8' { $$ = new Value(8); }
    |
        '9' { $$ = new Value(9); }
    |
        '0' { $$ = new Value(0); }
%%
 
 
int main()
{
    yyparse();
}

24/11/2009, 18h43
screetch

Code:

bison calc.y -o calc.cc && g++ calc.cc -o calc

le calculateur comprend les chaines genre 1+2-3*4/5 (sans espace)
construit l'arbre des opérations, puis l'évalue (et le détruit)
exercice : ajoute les parenthèses
si ca prend plus de cinq lignes, tu as faux :)

je crois qu'il faut appuyer deux fois sur entrée et apres il dit syntax error, mais la flemme, c'est qu'un exemple