Discussion :

[Baldurien]

Bonjour,

Je suis en train actuellement de développer une grammaire simple gérant les mêmes expressions (à peu près) que le SQL et j'ai deux façons de le faire :

La première, c'est la plus naturelle : elle permet de regrouper les différents opérateurs par précédence et importance, de gérer l'associativité. C'est aussi la plus simple des deux :

Cela donne ça :

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
e_no_prec: e_xor XTF_T_LOGICAL_OR e_no_prec
         | e_xor
         ;
e_xor: e_and XTF_T_LOGICAL_XOR e_xor
     | e_and
     ;
e_and: e_equal_in XTF_T_LOGICAL_AND e_and
     | e_equal_in
     ;
 
e_equal_in: e_cmp XTF_T_IN e_cmp
          | e_cmp XTF_T_IS e_cmp
          | e_cmp XTF_T_CMP_EQ e_cmp
          | e_cmp XTF_T_CMP_NE e_cmp
          | e_cmp '=' e_cmp 
          | e_cmp
          ;
e_cmp: e_additive '<' e_additive
     | e_additive '>' e_additive
     | e_additive XTF_T_CMP_LE e_additive
     | e_additive XTF_T_CMP_GE e_additive
     | e_additive XTF_T_BETWEEN e_additive XTF_T_LOGICAL_AND e_additive
     | e_additive
     ;
 
e_additive: e_mult '+' e_additive
          | e_mult '-' e_additive
          | e_mult XTF_T_STRING_CONCAT e_additive
          | e_mult
          ;
 
e_mult: e_final '/' e_mult
      | e_final '*' e_mult
      | e_final '%' e_mult
      | e_final
      ;
 
e_final: '(' e_no_prec ')'
       | constant
       | variable
       ;

(constant & variable ne sont que les constantes et les variables)

A priori, il y a autant de productions (comprendre : X : A | B | ... | Z) que de niveau de précédence, et par production il y autant de règles qu'il n'y a d'opérateurs par précédence, plus une règle qui indique qu'il n'y pas d'opérateur.

Sauf que Bison/Yacc propose une autre façon de résoudre la chose - c'est celle retenue par PHP (cf. zend_language_parser.y) et mySQL (cf. sql_yacc.y) - :

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
%left XTF_T_LOGICAL_OR
%left XTF_T_LOGICAL_XOR
%left XTF_T_LOGICAL_AND
 
%nonassoc XTF_T_IN XTF_T_IS XTF_T_CMP_EQ XTF_T_CMP_NE '='
 
%nonassoc XTF_T_CMP_GE XTF_T_CMP_LE '<' '>' XTF_T_BETWEEN
 
%nonassoc XTF_T_STRING_FORMAT
 
%left '+' '-' XTF_T_STRING_CONCAT
 
%left '/' '*' '%'
 
expr: expr XTF_T_LOGICAL_OR expr
    | expr XTF_T_LOGICAL_XOR expr
    | expr XTF_T_LOGICAL_AND expr
    | expr_no_and
    ;
expr_no_and: expr_no_and XTF_T_IN expr_no_and
           | expr_no_and XTF_T_IS expr_no_and
           | expr_no_and XTF_T_CMP_EQ expr_no_and
           | expr_no_and '=' expr_no_and
           | expr_no_and XTF_T_CMP_NE expr_no_and
 
           | expr_no_and '<' expr_no_and
           | expr_no_and '>' expr_no_and
           | expr_no_and XTF_T_CMP_GE expr_no_and
           | expr_no_and XTF_T_CMP_LE expr_no_and
           | expr_no_and XTF_T_BETWEEN expr_no_and XTF_T_LOGICAL_AND expr_no_and
 
           | expr_no_and '+' expr_no_and
           | expr_no_and '-' expr_no_and
           | expr_no_and XTF_T_STRING_CONCAT expr_no_and
 
           | expr_no_and '/' expr_no_and
           | expr_no_and '%' expr_no_and
           | expr_no_and '*' expr_no_and
 
           | '(' expr ')'
 
           | constant
           | variable
           ;

Ce qui apparaît plus court.


Par rapport à l'automate, le premier exemple me donne 70 états contre 64 pour le second. Cependant, sur ce genre d'exemple ce n'est pas tellement la taille qui compte mais plutôt le nombre de transition par états: il y a largement plus de transitions pour le second que pour le premier.

N'ayant fait qu'un semestre de traduction, et ce semestre ne parlant pas tellement de performance des méthodes, je me demande quelle est la meilleure méthode à employer?

[Trap D]

A mon avis, c'est plutôt une question pour le forum "Algorithmes"

[Baldurien]

Dans ce cas, je laisse un modérateur déplacer tout cela (plutôt que de réécrire le même message).

Déplacé depuis le forum Autres langages & outils par Alcatîz

[sjrd]

Attention ! Il ne faut pas seulement prendre en compte l'automate d'analyse syntaxique, il faut aussi tenir compte de l'arbre syntaxique que tu obtiendras : lequel correspond le mieux à la structure vue par l'homme de la requête ?
En effet, outre l'analyse syntaxique, après il faut passer à l'analyse sémantique, souvent la plus délicate (à traiter à la main en général). Plus l'arbre syntaxique ressemble à l'idée que l'on se fait, humainement, de la syntaxe, plus l'analyse sémantique sera facile

Sinon entre 64 et 70 états c'est vrai qu'on ne fait pas trop la différence. Donc j'aurais tendance à voter la 1

[Baldurien]

Pour mon problème, il n'y a pas de réelles différences entre les deux grammaires (j'ai consulté aussi la list de Bison-Help).

Pour l'analyse sémantique, puisque c'est un langage à priori sans type, y a pas vraiment de gros besoins là dedans. Bien sûr, l'analyse sémantique ce n'est pas que ça (et en fait, je dois avouer que je n'ai jamais réellement fait d'analyse sémantique comme GCC le ferait).