Parser à la mode

**ash.ice.loky** · 10/03/2006, 11h16

Salut,

Je dois réaliser un compilateur pour une machine cible factice.
Je possède bien entendu le jeu d’instructions assembleur de cette machine.
Pour avoir déjà réalisé l’exercice plusieurs fois je connais la procédure, seulement jusqu'à maintenant j’utilisais (imposé en fait ;-)) lex/yacc (flex/bison).

Pour ce projet ci, aucun outils n’est obligatoire, du coup j’aimerais toucher à autre, mais je ne sais pas trop vers quel lexer et parser m’orienté.

Windows de préférence (je préfère lorsque j’ai le choix).

Merci

**Laurent Gomila** · 10/03/2006, 12h05

boost::spirit vaut assurément le coup d'oeil, si tu possèdes un compilateur pas trop vieillot ; c'est un analyseur lexical / syntaxique à base de meta-programmation.

Sinon on parle souvent aussi de ANTLR, mais je ne connais pas plus que ça.

**ash.ice.loky** · 10/03/2006, 12h12

merci LouLou, je vais jeter un coup d'oeil du coté de Spirit.

**Process Linux** · 10/03/2006, 12h21

Personnellement , le choix le plus pertinant c'est lex/yacc (flex/bison).
d'abord il capitablise une experience assez interessante, et il est simple à implèmenter, il suffit de se concentrer sur les expressions régulières et la grammaire, ensuite , il suffit d'implémenter les méthodes d'executions une fois que la grammaire est bien construite.

**ash.ice.loky** · 10/03/2006, 12h26

Je n'ai rien contre lex/yacc mais j'ai envi de voir autre chose.
Si je ne trouve rien de convaincant je resterai su ce dinosaure ;-)

**Jean-Marc.Bourguet** · 10/03/2006, 14h16

Si tu utilises spirit, tu pourrais revenir en nous donnant une idee des perf a la compilation? La metaprogrammation, c'est bien mais quand il s'agit de generer un parseur j'ai quelques doutes.

Si tu veux essayer quelque chose et que tu ne l'as jamais fait, ecrire le parseur a la main avec des fonctions recursives peut etre interessant. Pour info, les parseurs de gcc pour le C et le C++ ont ete reecrit de cette maniere, le parseur Ada de gcc l'a toujours ete, sur les 3 parseurs VHDL sur lesquels j'ai travaille, 2 l'etait et celui qui ne l'etait pas etait le moins bon. Et soigner le comportement en cas d'erreur est beaucoup plus simple avec un tel parseur.

A+

--
Jean-Marc

**loufoque** · 10/03/2006, 16h36

avec boost spirit tu n'as pas besoin d'une phase séparé yacc->truc, la grammaire est directement spécifiée en C++.

**ash.ice.loky** · 10/03/2006, 18h58

Petit retour rapide sur spirit,

Lexer et parser réunis, assez pratique et plus rapide pour développer.
Librairie plus simple que lex et yacc à mettre en œuvre.

Je n’ai fait pour le moment que de petits tests et je les trouve concluants.
Pour les benchs il me faudrait une syntaxe plus poussé que mes tests, peut-être pour plus tard.

Par contre Jean-Marc, je ne comprends pas ce que tu veux dire par parser à fonctions récursives ?

**Jean-Marc.Bourguet** · 10/03/2006, 19h52

Envoyé par ash.ice.loky

Par contre Jean-Marc, je ne comprends pas ce que tu veux dire par parser à fonctions récursives ?

Quelque chose comme ça (note que c'est du C pas du C++, mais l'idée y est):

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
double eval_factor(char const* exp, char** end);
double eval_term(char const* exp, char** end);
double eval_exp(char const* exp, char** end);
 
char* skipws(char const* exp)
{
  while (isspace((int)(unsigned char)*exp)) {
    exp++;
  }
  return (char*) exp;
}
 
double eval_factor(char const* exp, char** end)
{
  double result;
  exp = skipws(exp);
  if (*exp == '(') {
    result = eval_exp(exp+1, end);
    if (**end != ')') {
      error("missing closing parenthesis", *end);
    } else {
      ++*end;
    }
  } else if (*exp == '+') {
    result = eval_factor(exp+1, end);
  } else if (*exp == '-') {
    result = -eval_factor(exp+1, end);
  } else {
    result = strtod(exp, end);
    if (*end == exp) {
      error("invalid number", *end);
    }
  }
  return result;
}
 
double eval_term(char const* exp, char** end)
{
  double result = eval_factor(exp, end);
  *end = skipws(*end);
  while (**end == '*' || **end == '/') {
    char const* op = *end;
    double factor = eval_factor(*end+1, end);
    if (*op == '*') {
      result *= factor;
    } else if (factor != 0.0) {
      result /= factor;
    } else {
      error("divide by 0.0", op);
    }
  }
  return result;
}
 
double eval_exp(char const* exp, char** end)
{
  double result = eval_term(exp, end);
  *end = skipws(*end);
  while (**end == '+' || **end == '-') {
    char const* op = *end;
    double term = eval_term(*end+1, end);
    if (*op == '+') {
      result += term;
    } else {
      result -= term;
    }
  }
  return result;
}
 
double eval(char const* exp)
{
  char* end;
  double result = eval_exp(exp, &end);
  if (*end != '\0') {
    error("trailing data after the expression", end);
  }
  return result;
}

**YéTeeh** · 10/03/2006, 20h46

Bonjour,

Ayant utilisé lex/yacc et boost::spirit, je viens donner mon avis.

Je n'ai utilisé lex et yacc que pour des projets universitaires et il est vrai que ça marche bien. Cependant je crois me souvenir que l'intégration du parser dans le projet n'était pas très confortable. De plus il est limité à un seul type de grammaire (je ne sais plus si c'est LL, LR ou LALR).

J'utilise boost::spirit pour parser des fichiers de description de niveau dans un jeu. Le jeu étant codé en C++, je préférais utiliser des outils eux aussi codés en C++. L'utilisation est assez simple, il permet même de parser avec des grammaires ambiguës. Je crois que la seule limitation est qu'il ne faut pas faire de règles récursives à gauche.

Les points faibles que je lui trouve :
- la compilation qui est un peu longue (quelques minutes sur un Duron à 1.3 GHz et 256 Mo de mémoire) ;
- la recherche d'erreurs : à cause des types templates énormes, on se retrouve assez rapidement avec plus de lignes que la console n'en contient et il est quelque fois assez difficle de remarquer la petite différence entre le type instancié et le type attendu ;
- Il faut compter quelques heures pour passer à travers la doc.

Du coté des points forts :
- je suis ravi du temps de parsing du fichier ;
- il est très facile de construire un arbre syntaxique ;
- il est facile de garder les positions et le contenu de l'entrée dans l'arbre syntaxique (pratique pour afficher les erreurs sémantiques) ;
- il est très facile d'afficher les erreurs de syntaxes pendant le parsing ;
- il est possible de sortir l'arbre syntaxique au format xml pour facilement retrouver où et pourquoi l'analyse sémantique ne passe pas ;
- il y a tout un tas de parsers prédéfinis pour lire des chaines, caractères, nombres ;
- toute la grammaire est dans le code, elle fait partie intégrante du programme (pas de préparatifs de précompilation comme pour lex/yacc) ;
- les concepts (grammaire, règles, arbre syntaxique, erreurs) sont implantés d'une manière très élégante ;
- il reste encore des choses que je n'ai pas utilisé.

boost::spirit : une fois qu'on l'a compris et que ça compile, c'est génial.

**Jean-Marc.Bourguet** · 10/03/2006, 21h17

Envoyé par YéTeeh

Les points faibles que je lui trouve :
- la compilation qui est un peu longue (quelques minutes sur un Duron à 1.3 GHz et 256 Mo de mémoire) ;

C'est quoi la complexité de ta grammaire?

**YéTeeh** · 10/03/2006, 21h34

Envoyé par Jean-Marc.Bourguet

C'est quoi la complexité de ta grammaire?

au temps pour moi : 25 règles, dont 4 récursives (petites).

comme je ne sais pas comment on mesure la complexité d'une grammaire, je vous met un petit 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
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
  m_u_integer_type =
    ( bs::no_node_d[ bs::str_p("u_integer") ]
      >> bs::no_node_d[ ( '(' | m_error_left_parenthesis ) ]
      >> ( m_u_integer_type   | m_error_u_integer )
      >> bs::no_node_d[ ( ')' | m_error_right_parenthesis ) ] )
    | bs::uint_p
    ;
 
  m_image_type =
    bs::no_node_d[ bs::str_p("image")
                   >> ( '('                    | m_error_left_parenthesis ) ]
    >> bs::infix_node_d[ ( m_identifier        | m_error_identifier )
                         >> ( ','              | m_error_comma )
                         >> ( m_u_integer_type | m_error_u_integer )
                         >> ( ','              | m_error_comma )
                         >> ( m_u_integer_type | m_error_u_integer )
                         >> ( ','              | m_error_comma )
                         >> ( m_u_integer_type | m_error_u_integer )
                         >> ( ','              | m_error_comma )
                         >> ( m_u_integer_type | m_error_u_integer )
                         >> ( ')'              | m_error_right_parenthesis ) ]
    >> !( bs::no_node_d[ bs::ch_p('{') ]
          >> *m_image_body_item
          >> bs::no_node_d[ ( '}'              | m_error_right_brace ) ] )
          ;
 
  m_item_creation =
    bs::no_node_d[ bs::str_p("create") ]
    >> !( bs::no_node_d[ bs::ch_p('[') ]
          >> ( bs::token_node_d[ bs::str_p("fixed") ] | m_error_fixed )
          >> bs::no_node_d[ bs::ch_p(']') | m_error_right_bracket ] )
    >> ( m_identifier | m_error_identifier )
    >> !( bs::no_node_d[ bs::ch_p('[') ]
          >> ( m_string_type | m_error_string )
          >> bs::no_node_d[ ( ']'           | m_error_right_bracket ) ] )
    >> ( ( bs::no_node_d[ bs::ch_p('{') ]
           >> *m_set_param
           >> bs::no_node_d[ ( '}' | m_error_right_brace ) ] )
         | bs::no_node_d[ bs::ch_p(';') ]
         | m_error_class_body_or_semicolon )
    ;
 
  m_set_param =
    ( bs::infix_node_d[ m_identifier
                        >> ( '('           | m_error_left_parenthesis )
                        >> ( m_string_type | m_error_string )
                        >> ( ','           | m_error_comma )
                        >> ( m_any_type    | m_error_type )
                        >> ( ')'           | m_error_right_parenthesis ) ]
      >> bs::no_node_d[ ( ';'              | m_error_semicolon ) ]
      )
    | ( ~bs::ch_p('}') >> m_error_identifier )
    ;

Je n'utilise pas tous les opérateurs proposés par boost::spirit, juste >>, |, *, !, ~

**Jean-Marc.Bourguet** · 10/03/2006, 22h00

Envoyé par YéTeeh

Envoyé par Jean-Marc.Bourguet

C'est quoi la complexité de ta grammaire?

au temps pour moi : 25 règles, dont 4 récursives (petites).

comme je ne sais pas comment on mesure la complexité d'une grammaire

Le nombre de règles me convenait bien.

Quelques points de comparaisons. Le parseur C de gcc 3.3.6 -- dernière version a avoir les parseurs C et C++ en yacc -- a 145 règles, le parseur C++ 217. bison compile en moins d'une seconde chacune de ces descriptions sur ma machine (athlon 1700). gcc met une poignée de secondes de plus à générer les fichiers objets.

**JolyLoic** · 11/03/2006, 13h17

Ce qu'il serait aussi intéressant de comparer, c'est le temps que met le programme résultant à parser un bout de code.

Si tu veux faire des comparaisons, tu peux peut-être utiliser boost::wave, une implémentation du préprocesseur en spirit, afin d'avoir une base commune.

**Jean-Marc.Bourguet** · 11/03/2006, 15h06

Il y a aussi d'autres choses à comparer. La qualité du traitement des erreurs (yacc est abissimal, à priori spirit étant LL devrait permettre mieux), les contraintes imposées sur les grammaires (spirit est LL donc a priori plus contraint que yacc qui est LALR et surtout bison qui peut aussi générer un parseur plus générique, capable de parser n'importe quelle grammaire non ambigue; mais si spirit permet d'avoir des contraintes sémantiques pour diriger le parsing -- un peu comme ANTLR qui est LL(k) -- ce peut être un avantage), les contraintes sur les actions sémantiques (spirit étant LL devrait en avoir moins), la possibilité de l'utiliser sur des compilateurs divers (rien que ce point élimine vraissemblablement spirit pour un temps de ma vie professionnelle).

Depuis que je sais que spirit existe j'ai envie de l'évaluer en profondeur (je ne sais même pas s'il est LL(1) ou LL(k). Mais ca demanderait beaucoup plus de temps que je n'en ai pour quelque chose que je ne peux pas faire sur mon temps de travail (si j'ai travaillé sur des parseurs pour des langages complets, ce n'est plus le cas maintenant). C'est un peu pourquoi je posais des questions et demandais des retours d'expérience.

**loufoque** · 11/03/2006, 19h23

http://www.boost.org/libs/spirit/doc/portability.html

Ça passe sur tous les compilateurs C++ relativement modernes.
Et y'a même des vieilles versions pour des trucs comme MSVC6. (il parait que y'a encore des gens qui compilent du C++ avec ça)

**Jean-Marc.Bourguet** · 11/03/2006, 19h41

Envoyé par loufoque

http://www.boost.org/libs/spirit/doc/portability.html

3 des 4 compilateurs que j'utilise au boulot ne sont pas dans la liste.

**black.out** · 12/03/2006, 09h10

hello, je m'incruste dans votre conversation afin de savoir si vous aviez un exemple de petit programme utilisant spirit car je n'ai pas encore reussi a en faire quelques chose ?

j'essai de faire un parser a la main mais je flanche et spirit pourrait etre sympa.

juste un petit exemple (calcullette, petit script, ...) MERCI

**JolyLoic** · 12/03/2006, 10h26

http://www.boost.org/libs/spirit/example/

Parser à la mode

Générateurs de compilateur

Discussions similaires

Partager

Partager